Chun Du, Manfred Rosendahl

Universitaet Koblenz-Landau,

Institut fuer Informatik, Rheinau 3-4,

56075 Koblenz, F. R. Germany


In 4th Eurographics Workshop on Object Oriented Graphics, Sintra, Portugal, 9.-11.5.94.


Many conventional CAD systems are only Computer Aided Drafting system. The designer uses CAD system to draw the design results. The designing activities were happened in the mind of the designer and have almost finished when the designer begins to work with CAD system. The CAD system serves the user to document the design results but do very littel as aid in the process of design. This is because the conventional CAD systems only register the geometric data on Cartesian level but not semantic information from the application, for example the construction of objects and functional relationships among them. The management and manipulation of design information, and the communication with the user therefore take place on the geometric data level. The user has to convert high-level functional specifications into low-level data which can be accepted by the system. A great deal of semantics information are lost during this information translation. Some parametric design systems offer high-level integrated graphic commands which also transmit the semantic information (for example parallelism, tangency, perpendicularity) by creating geometric objects. But these information get lost as soon as the graphic commands finish. Figure 1.1 shows the problem.

In figure 1.1(a) are two circles which locate on the same horizont. A line is tangent to the two circles. Figure 1.1(b) shows a moving of one circle and its result which happens in many conventional CAD systems. The intended relationship among the objects are lost. There is obviously a gap between the knowledge of the system and the user's intention.

Functional relationships can be represented as geometric and dimensional relationships in geometric model which sometimes are called constraints. There have been many approaches which attempt to bring these constraints into geometric model. The purely algebraic approach [7,8,13] maintains the relationships among geometric objects through algebraic equations. Points (called characteristic points) and dimensions are taken as the basic elements to form constraint equations which will be solved simultaneously in order to guarantee the consistency of the geometric model after the model has been modified. Another approach is to use geometric reasoning mechanism in which the dimensions and geometric relationships are defined as either facts or rules[1,2,3,14]. These facts or rules are used to do the inferences on the symbolic level to maintain the consistency of the model. Some approaches of parametric design[9,12] define construction sequences for sample models. The dimensional and topological information of sample models are recorded in these sequences. A geometric model is created by running a group of construction sequences. Variants of the model can be achieved by running the sequences again with different dimensional parameters where the topological structure stays invariable.

In this paper we introduce an approach to integrate the geometric relationship, including dimensional relationship, into the geometric model using object-oriented methodology. We call it constructive geometric modelling. The strategie is to set up funtional dependences among geometric objects according to the geometric relationships among them. In other words, we define a geometric object on the basis of its relationships to other geometric objects. The geometric relationships among them stay invariable as long as this object exists. In section 2 the strategie of our approach is introduced; section 3 discusses how to define classes of geometric objects; section 4 introduces the object-oriented implementation and in section 5 the maintenance of the consistence of geometric model is discussed.


There are various kinds of geometric relationships among geometric objects. Following geometric relationships are dealt with in our approach:

1)Structural relationship

This is 'composed-of' relationship between geometric objects according to the normal concept of geometry, i.e. an object is a component of another object. For example, the centre point and radius are components of the circle.

2)Dimensional relationship

This is numerical relationship among the dimensions. For example, the radius of a circle is the length of a line.

3)Topological relationship

This is spatial relationship among the objects in 2-dimensional space. For example, tangency, parallelism, perpendicularity, relative location and intersection.

The strategie is to create a geometric object according to its geometric relationships to other geometric objects and let the geometric relationships embeded in the construction of this geometric object.

We define a geometric object through an evaluation process based on its geometric relationships to other geometric objects, i.e. its geometric data (dimension or coordinate) are calculated on the basis of

Thus such a geometric object is functionally dependent on the objects to which it has geometric relationships.

For the geometric objects in a structural relationship this method is direct. We define an object as the composition of all other objects in this relationship, for example, a circle is defined by a point and a radius. For the objects in dimensional and topological relationships where symmetrical dependences offen occur the method is not directly applicable. What we have done is to force one of the object involved in one of these two kinds relationships to be calculated based on its relationships to other objects in the same relationships. For example, a line can be defined such that its two ends are two circles which are tangent to the line.

The geometric relationships thus exist in the evaluation process of each geometric object. Through the calculation of geometric data of objects the geometric relationships among objects are guaranteed and the consistence of the geometric model is maintain when the model has been modified.


Geometric modelling primitives are basic geometric object types. There are two kinds of GMPs: absolute GMP and conditioned GMP.

Absolute GMPs are those GMPs who have no evaluation processes. They are independent. There are five absolute GMPs: value, point, line, cirle and arc. Each of them has geometric data as attribute as following.

GMP Attribute

Value x : real

Point x,y : real

Line x1,y1,x2,y2 : real

Circle x,y,r : real

Arc x,y,r,angle1,angle2:real

Conditioned GMPs are those GMPs who are functionally defined on the basis of relationships to other GMPs. A conditioned GMP is derived from an absolute GMP, i.e. it inherits the attribute from an absolute GMPs and therefore has the same geometric character with this absolute GMP. Each conditioned GMP has references to the related GMPs and also an evalution process which calculate its attribute by using the attribute of its related GMPs and geometric relationships among them. Obviously, for the conditioned GMPs with the same attribute there can be different evaluation processes according to the different relationships they are involved. We differentiate them according to the different evaluation process. Thus each conditioned GMP has its own way to calculate its attribute. Figure 2.1 is an example of conditioned GMP and its evaluation process.


Geometric modelling primitives are implemented as classes. Geometric objects are instances of their classes. The instances of absolute GMPs are called absolute objects. The instances of conditioned GMPs are called conditioned objects. Absolute GMPs are superclasses and conditioned GMPs are subclasses. Figure 3.1 is the hierarchy of the classes. Because of the size of page we haven't shown all the subclasses. Class VALUE actually has 7 subclasses and class POINT has 10 subclasses.

The class point, line, circle and arc are absolute classes. They don't have any instances. Other classes are concrete classes whose instances are geometric objects of geometric model. The definition of root class ANY and classes for absolute GMPs are shown in following which are written in Borland Pascal 7.0:

  • any=object(node)
  • computed:byte;
  • alter:integer;
  • constructor init;
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;
  • value=object(any)
  • x:real;
  • constructor init(xx:real);
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;
  • point=object(any)
  • x,y:real;
  • procedure compute(kind:tvalkind);virtual;
  • constructor init(xx,yy:real);
  • constructor load(var id:stream);
  • procedure store(var id:stream);
  • end;
  • item=object(any)
  • constructor init;
  • constructor load(var id:stream);
  • procedure store(var id:stream);
  • end;
  • line = object(item)

  • x1,y1,x2,y2:real;
  • constructor init(xx1,yy1,xx2,yy2:real);
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;

    circle = object(item)

  • x,y,r:real;
  • constructor init(xx,yy,rr:real);
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;

    arc = object(circle)

  • angle1,angle2:real;
  • constructor init(xx,yy,rr,iangle1,iangle2:real);
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;

    The method init creates an instance of the corresponding class. Method compute calculates the geometric data (attribute) of the instance created by method init. It is the evaluation process for each object. Method store writes the instance in an external file, and method load read in the instance from the external file. The attribute computed signifies whether this instance has been computed. The attribute alter indicates one solution if there are many solutions for the evaluation process. There are also some implementation-oriented methods which are not presented here. The method compute is overridden in each class. Each class has its own evaluation process to calculate its geometric data according to which kinds of relationships it has to which kinds of classes.

    In following is a subclass of class line where attributes ii1 and ii2 are the addresses of the eventually related objects and methods i1 and i2 are functions to get related objects.

    line_2o = object(line)

  • ii1,ii2:word;
  • constructor init(a1,a2:anyptr;lalter:integer);
  • function i1 :anyptr;
  • function i2 :anyptr;
  • procedure compute(kind:tvalkind);virtual;
  • procedure store(var id:stream);
  • constructor load(var id:stream);
  • end;

  • procedure line_2o.compute(kind:tvalkind);
  • var
  • t1,21 : pointer;
  • class1,class2 : char;
  • combination : string[2];
  • begin
  • if ((not computed) and byte(kind))=0 then exit;
  • { if this object is computed then go out }
  • i1^.compute(kind);
  • i2^.compute(kind);
  • { send stimuli 'compute' to objects i1 and i2 }
  • computed:=computed or byte(kind);
  • { marking the attribute 'computed' }
  • t1:=typeof(i1^); t2:=typeof(i2^);
  • if is_subclass(t1,typeof(value)) then class1:='v' else
  • if is_subclass(t1,typeof(point)) then class1:='p' else
  • if is_subclass(t1,typeof(line)) then class1:='l' else
  • if is_subclass(t1,typeof(circle)) then class1:='c';
  • if is_subclass(t2,typeof(value)) then class2:='v' else
  • if is_subclass(t2,typeof(point)) then class2:='p' else
  • if is_subclass(t2,typeof(line)) then class2:='l' else
  • if is_subclass(t2,typeof(circle)) then class2:='c';
  • combination:=check_valid_combination(class1,class2);

    { check if the combining of the two objects make sense }

  • if combination='dl' then
  • line_dl(i1,i2,alter,x1,y1,x2,y2)
  • { parallel line to a line on certain distance }

  • else
  • if combination='pp' then
  • line_pp(i1,i2,x1,y1,x2,y2)
  • { line between two points }
  • else
  • if combination='pl' then
  • line_pl(i1,i2,alter,x1,y1,x2,y2)
  • { perpendicular line between a line and a point }

  • else
  • if combination='pc' then
  • line_pc(i1,i2,alter,x1,y1,x2,y2)
  • { tangent line between a circle and a point }

  • else
  • if combination='lc' then
  • line_lc(i1,i2,alter,x1,y1,x2,y2)
  • { perpendicular/tangent line between a line and a circle }

  • else
  • if combination='cc' then
  • line_cc(i1,i2,alter,x1,y1,x2,y2);
  • { tangent or perpendicular line between two circles }

  • if combination='ll' then
  • line_ll(i1,i2,alter,x1,y1,x2,y2);
  • { line between two lines }


    The attributes x1, y1, x2 and y2 of the line are obtained in method compute. The object i1 and i2 are polymorphic objects. Their methods compute are dynamically bound to them at the time when an instance of class line_2o is computed. Obviously the two related geometric objects must have been created before the instance of class line_2o is created. We call this kind of building of model constructive geometric modelling.


    A geometric model constructed on the basis of our GMPs contains an inner structure which is the dependences among the geometric objects according to the geometric relationships among them. Through the dependences among the objects the geometric relationships are guaranteed. The dimensional and positional changes of some objects will not destroy the consistence of the geometric model as long as the geometric model gets evaluated after each change.

    Evaluating a geometric model means to evaluate all its geometric objects. Evaluating a geometric object again means to send him a stimulus 'compute' which stimulates its method compute to take action. Because of the dependence of a conditioned object on its related objects the evaluation of its related objects should be done earlier. Thus the stimulus first is further sent to its related objects. The evaluation of this conditioned object will not take place until all its related objects are evaluated. This process runs recursively until all the geometric objects are newly evaluated. The dimensional and positional changes therefore are propagated from absolute objects to conditioned objects in a direction opposite to the propagation of stimulus 'compute'. The geometric relationships among the geometric objects thereby are maintained. Figure 4.1(a) shows a sample model and figure 4.1(b) shows the dependences among the objects and the directions of the two propagations. Each object in a geometric model will only be calculated once. This is guaranteed by the attribute computed of each object.

    The dependences among geometric objects are required acyclic. But there is not always an acyclic construction of geometric model for the functional requirements in CAD application. Figure 4.2 is an example. The line L of class line_2o is tangent to two circles C1 and C2 and is dependent on them, as well as its length. If we fixed the length of the line there would be conflict. In that case we have to give up one degree-of-freedom, for example the cordinate X1 of C1. Through purposively iterated change of X1 the length of the line will keep invariable. Such additional dimensional demand on a conditioned object, such as the length of the line, is called late constraint because they usually are added into the geometric model after the model has been constructed. Each late constraint needs a free variable to keep it invariable. So it actually is an constraint equation in which the unknown variable is the free variable. All the constraint equations in a geometric model will be managed together and solved using Newton-Raphson iteration method. A procedure is developed which decomposes the system of constraint equations using matrix calculation so that not all the equations have to be solved simultaneously.

    With constructive geometric modelling and the concept of late constraint we have reached a quite good compromise of geometric modelling which is not only feasible to relatively simple modelling task, but also big complicated one.


    The constructive geometric modelling method allows a geometric model to contain geometric relationships among the objects. A part of semantic inforomation, for example functional relationships, are stored in the geometric model. A CAD system thereby becomes more intelligent. The object-oriented methodology is the only elegent tool to implement it because each geometric object is functionally defined through operation. The features, such like inheritance and polymorphism, make the implementation of our strategie possible.


    [1] Aldefeld B, 'Variation of geometries based on a geometric- reasoning method', CAD vol 20 no 3, 1988, pp 117-126.

    [2] Arbab F, 'Examples of Geometric Reasoning in OAR',in Akman V, Hagen P.J.W.ten and Veerkamp P.J(Eds.) Intelligent CAD System II, Springer-Verlag, 1988, pp 32-57.

    [3] Arbab F and Wang B ' A Geometric Constraint Management System in OAR' in Hagen P.J.W.ten and Veerkamp P.J(Eds.) Intelligent CAD System III, Springer-Verlag,1991, pp 205-231.

    [4] Berling R, Du C and Rosendahl M, 'A relational CAD system with an object oriented design', research report 10/91, University of Koblenz-Landau, 1991.

    [5] Du C, Rosendahl M and Berling R, 'Variation of Geometry and Parametric Design', Proc. 3rd. international conference on CAD and computer graphics, Beijing, Aug. 23-26, 1993, pp 400-405,international academic publishers.

    [6] Kondo K, 'Algebraic method for manipulation of dimensional relationships in geometric models', CAD, vol 24, no 3, March, 1992.

    [7] Light R and Gossard D, 'Modification of geometric models through variational geometry', CAD vol 14, no 4, 1982, pp 209-214.

    [8] Lin V C, Gossard D C,and Light R A, 'Variational Geometry in Computer-Aided Design', Computer Graphics, vol 15, no 3, 1981, pp 171-177.

    [9] Roller D,'An approach to computer-aided parametric design' CAD, vol 23, no 5,June, 1991, pp 385-391.

    [10] Roller D, Schonek F and Verroust A, 'Dimension-driven geometry in CAD: a survey' in Strasser W and Seidel H-P (Eds.) Theory and Practice of Geometric Modeling, Springer Verlag, 1989, pp 509-523.

    [11] Rosendahl M, Berling R, and Du C, 'Objektorientierte Implementierung eines relationalen CAD-Systems', Research report 4/92, University of Koblenz-Landau, 1992.

    [12] Rossignac J, Borrel P and Nackman L R, 'Interactive Design with Sequences of Parameterized Transformations', in Akman V, Hagen P.J.W.ten and Veerkamp P.J(Eds.) Itelligent CAD System II, Springer-Verlag, 1988, pp 93-125.

    [13] Serrano D and Gossard D, 'Constraint Management in Conceptual Design' in Sriram D and Adey R A (Eds.) Knowledge Based Expert Systems in Engineering:Planning and Design, Computational Mechanics Publications, 1987.

    [14] Sunde G, 'Specification of Shape by Dimension and other Geometric Constraints',IFIP WG. 5.2 on Geometric Modeling,Rensselaerville, NY, May, 1986.