Applying Design Patterns to Two-dimensional Graphics Applications

 

Summary

This article discusses how the object-oriented paradigm can be applied to the construction of class libraries and reusable designs. In particular, we show how design patterns are applied to creating software for two-dimensional applications in Computer Aided Design (CAD). The emphasis is on flexibility and reusability.

 

Statement of the Problem

The system that we discuss in this article is one which is built from C++ classes representing two-dimensional graphics entities. These entities can be simple (such as point, line and circle) or they may be composites (such as lists, arrays and general collections of simple objects). We are specifically interested in Computer Aided Design (CAD) applications and to this end we need to create a number of class hierarchies which are related to these geometric objects. This is necessary because in CAD software we do not only work with simple geometry but also with concepts and entities which add value to the geometry. Examples of such extended entities are:

 

These are some of the issues which concern us when we write software for CAD. Our specific interest lies in creating context-independent class libraries and building blocks which can be used to create customised applications. By context-insensitive we mean that the software is independent of the particular environment in which it is to operate. This means that it must be independent of the particular GUI, database and other software which is being used at a given moment in time. The advantages of this approach are:

 

The class library which we discuss is based on the commercial product "CADObject" (see [CADObject96]). This is a suite of classes consisting of approximately ten hierarchies and which is suitable for all kinds of graphical applications ranging from holography, mechanical engineering, games and virtual reality. We are also in the process of integrating CADObject with classes for numerical simulation (e.g. finite element analysis) so that a much tighter and integrated coupling can be realised between current CAD and engineering applications.
CADObject has been created on the basis that it must be extendible, robust, reusable and flexible. This has been achieved by applying sound engineering principles such as Information Hiding, layering and by using the design patterns ideas developed in [Gamma95].

 

An Introduction to the ANSI/SPARC Model and its Relation to Design Patterns

Before we start with the details of design patterns we wish to give an introduction to the ANSI/SPARC model. This has its origins in database design theory but it is so universal that it can be applied to many application areas and furthermore, it can serve as the foundation for a number of well-known techniques from other branches of software, for example the Model View Controller (MVC) paradigm for GUI applications. Finally, the ANSI/SPARC model can be used to explain many of the underlying ideas which are part of the design patterns catalogues in [Gamma95].

Based on this model we can partition all systems, programs and processes into three separate and more or less independent domains. These domains are based on functionality and are sometimes given the synonyms expertise area, logical subsystem or subject area.
In order to be able to use and apply the ANSI/SPARC model in CAD and graphics applications we need to know how the model is partitioned and what its components are. In general, the model consists of three layers, each one having its own set of responsibilities. More precisely, the model is partitioned into the internal, conceptual and external layers (see [Tsichritzis78]). First of all, the external layer is concerned with that part of the application which is directly visible to clients (for example, GUI software); for this reason it is sometimes called the presentation layer. The internal layer is concerned with the 'raw' or unprocessed data which will be transformed in one or more ways in order to be delivered to the external layer. Finally, the conceptual layer is the intermediary between the internal and external layers and it represents the business rules and core activities of an application. In a more general business setting, we see the ANSI/SPARC model being used in the literature (see for example, [Bogan94], page 52). In business environments for example, we are concerned with converting raw materials into sellable products by using the knowledge and intelligence of the people in an organisation. In such cases we can think of a workflow scheme consisting of three domains for input (internal layer), processing (conceptual layer) and output (external layer). Specifically, each layer is concerned with the following issues:

 

The different layers may communicate with each other in different, depending ways. For example, a system may be implemented as a batch program in which the output from the internal layer functions as input to the conceptual layer while the output from the conceptual layer is used as input to the external layer. In such cases there is a one-way flow of information but it is also possible for pairs of layers to communicate in a peer-to-peer fashion. For example, it is possible for the internal and conceptual layer to be active and have the ability to send information to each other. In this case we speak of collaborating layers.

The above results can easily be mapped to reusable designs which can be applied to produce flexible and reusable software for CAD applications. In particular, we show the situation in Figure 1 in which each layer in a given problem or model is equivalent to a number of classes, each one having its own specific interface. In this case we see that there are different types of input and output while there are different types of processes which produce an output from a given input. To give a specific example, consider the problem of producing metal forms of varying shape (for example squares and circles) from larger chunks of metal which have circular and rectangular forms. There are different strategies or layouts for making these objects.

Figure 1: Communicating Hierarchies Paradigm
Figure 1: Communicating Hierarchies Paradigm

 

For example, we might wish to create the metal object based on minimum wastage as far as the raw material is concerned or that the objects should be produced in some other way (for example, that they are aligned in such a way that the laser cutting machine is used optimally). In this case, we have the input layer being represented by the rectangular and circular shapes, while the output layers represent finished products in the form of small squares and circles. How these are created is determined by the processing layer which holds company design rules and business knowledge about how the metal parts should be produced. In this way we can achieve high degrees of flexibility because it is possible to vary each of the layers independently of each other during production runs.
Having discussed the three-layer model in general we now continue our treatment of developing object-oriented software for CAD. To this end, we show how the above theoretical analysis can be mapped to some well-known design patterns.

 

Basic Object Functionality and Domain Objects

CADObject was originally developed for CAD applications but the classes have been designed in such a way that they can be extended to other applications. In this sense we can view them as classes which are more or less application-independent and which can be extended to new customer needs.
In this particular case the class interfaces consist of operations for creating instances and providing support for geometric queries such as intersections, calculating distances between objects and determining other object properties such as area and length. There is no provision in the basic class library for input-output, geometric transformations or adding new application-dependent data to objects. However, by using appropriate design patterns we can ensure that the library can be extended and adapted to new situations without distorting the original class structure. A subset of the basic functionality is shown in Figure 2.

Figure 2: Basic Shape Hierarchy
Figure 2: Basic Shape Hierarchy

 

Extending Object Functionality

Since the class library has only basic geometric functionality we need to produce mechanisms which allow us to extend essential responsibilities. Examples of possible extensions are:

Different applications and user groups will have different needs as far as extra functionality is concerned. In particular, a requirement is that customers do not pay for what they do not need and this forces us to create an infrastructure which is flexible in the sense that functionality can be easily added to and removed from the basic class library. To this end, we apply the Visitor pattern (see [Gamma95]). This is one of the most important and useful patterns and we often use it to create new functionality which can be 'appended' to existing class libraries.
In order to show how the Visitor works in this context, we consider the problem of creating functionality for geometric transformations. To this end, we create a class hierarchy as shown in Figure 3. In this case the abstract base class Transform contains pure virtual member functions. There is one entry for each class in the Shape hierarchy of Figure 2. The class interface for Transform is:

class Transform
{ // Abstract base class with functionality for transforming 2d shapes (lite version)

private:
public:

// ...

// Operator overloading
virtual Circle visit(const Circle& cir) const = 0;
virtual Line visit(const Line& lin) const = 0;
virtual Point visit(const Point& pnt) const = 0;

// etc}

};

Figure 3: Transformation Class Hierarchy
Figure 3: Transformation Class Hierarchy

 

In this case we have chosen the interface in such a way that a given shape can be transformed into another one. In many cases however, it is more practical to define a modifier operation which acts on the shape and modifies its internal structure (in this case, its position is modified, for example).

Thus, the interface would be:

class Transform
{ // Abstract base class with functionality for transforming 2d shapes (lite version)

private:
public:

// ...
virtual ~Transform();

// Operator overloading
virtual void visit(Circle& cir) const = 0;
virtual void visit(Line& lin) const = 0;
virtual void visit(Point& pnt) const = 0;

// etc

};

 

However, we keep to the original class interface for Transform. We show the two different alternatives to emphasise the fact that more than one solution is possible.
Derived classes of Transform must implement these functions. For example, the class Scale has member functions for scaling shapes. Its interface is:

class Scale : public Transform
{ // Transformation class from scaling 2d geometric objects

private :

Point scalefactor; // The scale factor

public :

// Constructors & destructors
Scale(const Point& scale_factor); // Non-uniform scaling
Scale(double scale_factor); // Uniform scaling
virtual ~Scale();

// Destructor

// Operator overloading
Circle visit (const Circle& cir) const;
Line visit(const Line& lin) const;
Point visit(const Point& pnt) const;

};

 

In order to implement the class Scale, each member function must be coded. We show how this is achieved for the Circle class. In this case we use the public interface of Circle.

Circle Scale::visit(const Circle& cir) const
{
// To scale the circle we first get the centre point of the circle
// calculate a point on the circle and scale this point. Then
// construct a new circle with the centre point and the distance
// to the scaled point for the radius.

Trans3d trans; // Create transformation matrix
trans.scale(scalefactor); // Assign scale factor to matrix

// Calculate a point on the circle by taking its centrepoint
// and use the radius as distance to the point on the circle.
Point endpoint(cir.centre(),cir.radius(),Degree(0.0));
Point centrepoint = cir.centre();
endpoint = trans.transform(endpoint);
centrepoint = trans.transform(centrepoint);
return Circle(cir.centre(),centrepoint.dist(endpoint));

}

To show how transformations work, we consider the problem of scaling shapes. The following code realises this:

Scale sc(0.5); // Uniform scaling
Line lin(Point(0.0, 0.0), Point(1.0, 1.0));
Line lin2 = sc.visit(lin);

 

The flexibility of this approach lies in the fact that the Shape and Transform hierarchies have weak coupling with each other. Transform is a client of all the derived classes of Shape. However, neither Shape nor its derived classes know about the existence of Transform (at the moment!). In this case we can speak of single dispatch (see [Gamma95]) in the sense that two criteria determine which will fulfil a request, namely the name of the request (scale, viewport, rotate, ...) and the type of receiver (circle line ...). Thus, it is possible to execute the following code:

Transform* tr[3];
tr[0] = new Scale (0.5); // Scale by half
tr[1] = new Rotate(Degree(45.0)); // Rotate by 45 degrees
tr[2] = new Mirror(Point(0.0, 0.0)); // Mirror in the origin

Circle cir(Point(1.0, 1.0), 2.0);
Circle result;

// 'Animate' the circle
for (int j = 0; j < 3; j++)
{

result = tr[j] -> visit(cir);

}

 

What happens if we wish to transform a complete CAD drawing? Then we have a problem because a CAD drawing is implemented as a Shape container and the polymorphic effect which we wish to achieve is not realised by the single despatch mechanism. The solution to this problem is to apply the so-called double dispatch mechanism. In this case the operation that is invoked depends on the name of the request and on types of two receivers. In this case we need to extend Shape so that it becomes a client of Transform (but not of Transforms derived classes). In order to implement the double dispatch mechanism by defining an operation accept() which allows dynamic binding to both shapes and transformations. What is needed is to define it as a pure virtual member function in Shape and redefining it in derived classes:

class Shape
{
public:

void accept(const Transform& tr) const = 0;

};

class Circle : public Shape
{
public:

void accept (const Transform& tr) const { tr.visit(*this);}

};

class Line : public Shape
{
public:

void accept (const Transform& tr) const { tr.visit(*this);}

};

 

With this new functionality it is possible to realise dynamic binding in both directions. The following example shows how the mechanism works when we wish to scale a list of shapes:

// Create CAD 'drawing' object
Shape* sarr[4];
sarr[0] = new Point (0.0, 0.0);
sarr[1] = new Point(1.0, 3.0);
sarr[2] = new Line (Point(), Point(100.0, 100.0));
sarr[3] = new Circle (Point(1.0, 1.0), 1.412);

// Create scaling 'driver' object
Scale sc(0.5);

// Now scale the CAD drawing object
for (int j = 0; j < 4; j++)
{

sarr[j] -> accept(sc);

}

 

Finally, it is possible to 'animate' a container object with this functionality and this has applications in kinematics, robotics and visualisation. In short, the Visitor pattern is a powerful mechanism for extending the applicability of C++ classes. It is used for displaying graphical objects on different display media and in combination with different applications, for example AutoCAD, Microstation, GDI (Microsoft), OpenGL and X Windows. See Figure 4 for the class hierarchy. The client-server relationship between Shape and Driver is shown in Figure 5: the class Shape (and each derived class) knows about the top-level Driver class only while Driver (and each of its derived classes) knows about each class in the Shape hierarchy.

Figure 4: Output Drivers for Shapes
Figure 4: Output Drivers for Shapes

 

Figure 5: Double Dispatch Mechanism (Multiple Polymorphism)
Figure 5: Double Dispatch Mechanism (Multiple Polymorphism)

 

Creating Recursive Aggregates

In many CAD applications it is necessary to create and manipulate objects which are built from simpler objects. In these cases we speak of aggregate objects. Examples of aggregates in CAD are lines, polylines, blocks and regions. In particular, it is important to be able to create recursive aggregates. These are objects which consist of instances of the same class. Furthermore, when developing software we may wish to ignore the difference between these composite objects and other simple objects. In order to achieve this end the Composite pattern is used. An example is shown in Figure 2; the class ShapeComposite is derived from Shape but consists of other Shape instances. In this way it is possible to create composites which consist of other composites, for example. In practice we need to differentiate between the different ways to create composites and for this reason new derived classes of ShapeComposite have been created to accommodate different applications, for example:

 

Thus, the ShapeComposite has no private member data but may have a number of default member functions. Specialised derived classes can be constructed which satisfy particular needs. For example, ShapeTree represents a multi-levelled tree structure in which it is possible to quickly access objects in a two-dimensional space. This is needed for interference and collision testing applications.

 

Creating new Subsystems: A Dimension Hierarchy

In CAD applications it is often necessary to dimension geometric objects. For example, an architectural drawing for a house is annotated by giving the extent of the house and its separate rooms. Most CAD packages offer functionality for this. It is possible however, to create a class hierarchy representing different types of dimensions. This is shown in Figure 6. There are a number of basic types (such as linear and radius) dimensions while composite dimensions are also used. For example, baseline and continuous dimensions represent list of linear and horizontal dimensions, respectively.

Figure 6: Dimension Class Hierarchy


Figure 6: Dimension Class Hierarchy

 

The dimension hierarchy is related to the Shape hierarchy in the sense that its implementation depends on the geometric functionality in the geometric classes while each geometric object has one or more associated dimension instances. The ANSI/SPARC model is applicable here: shapes are to be found in the internal layer, dimensions in the conceptual layer while display options (for example, the so-called dimension picture) are to be found in the external layer.
In the next article in this series we shall discuss the Decorator, Mediator and Observer patterns for three-dimensional graphics applications.

 

Conclusions

This article has introduced a number of design techniques which help software developers become more productive. Design patterns encapsulate knowledge that experienced C++ developers have been using for a number of years. Many seemingly new software problems can be mapped as one or more patterns for which there is a standard plan of execution, as described in [Gamma95]. For example, the Composite pattern is used to motivate and design recursive aggregations. Once you have learned to create composites for shapes, for example, it is then easy to reapply this knowledge to new problems, such as dimensions and dialog boxes in GUI design.
In the next article in this series we shall discuss how design patterns can help in creating software for three-dimensional computer graphics.

 

About the Author

Daniel J. Duffy is director and founder of Datasim BV, Amsterdam, a training and software development organisation which has been involved with OOT since 1988. He is chief designer of CADObject, a class library consisting of 600 C++ classes which is used to build applications for CAD, computer graphics, engineering and simulated worlds. He has been involved in many types of OO projects in finance, CAD, logistics and engineering . He is convinced that software development should be based on a building block or factory foundation and that new applications and prototypes should be built using ideas, architectures and designs which have been applied from previous projects. Duffy has a Ph.d. in numerical mathematics from Trinity College, Dublin.

Daniel Duffy can be reached on the e-mail address dduffy@datasim.nl

 

References

  1. [Bogan94] C. E. Bogan, M. J. English "Benchmarking for Best Practices, Winning Through Innovative Adaption", McGraw-Hill New York 1994.
  2. [CADObject96] CADObject Reference Manual, Datasim BV Amsterdam, Nederland 1996.
  3. [Duffy95] Daniel J. Duffy "From Chaos to Classes - Software Development in C++", McGraw-Hill London UK 1995.
  4. [Foley87] J. D. Foley et al "Computer Graphics, Principles and Practice", Addison-Wesley Reading MA 1987.
  5. [Gamma95] E. Gamma et al "Design Patterns - Elements of Reusable Object-Oriented Software", Addison-Wesley Reading MA 1995.
  6. [Tsichritzis78] D. Tsichritzis, A. Klug eds. (1978) "The ANSI/X3/SPARC DBMS framework: report of the study group on database management systems", Information Systems, Volume 3, (173-191), published by Pergamon Press Ltd, Oxford UK.

 

[ Homepage | Articles]