Automated variation of design models is an important function of CAD system. There are two aspects to variant generation: one is to generate a family of design parts whose members have different dimensions; the other is to maintain the consistency of the model when some of the dimensions have changed. An approach is introduced in this paper which is capable of satisfying the requirements in both aspects. The feature of this approach is to represent geometric objects based on its relationship to other objects. Moreover, the concept of parameterized segment makes it possible to define any kind of design part and achive any variantion on it.
Geometric model, geometric relationship, geometric constraint, dimension, segment, parameter, variation.
One of the important issues in CAD is the automated variation of design models. Many approaches have been presented to solve this problem by using dimensions which are treated as geometric constraints or parameters in different systems [1,3,5,6,7,8,11,12,13]. In these approaches the adjustment or the variation of geometric model can usually be achieved by changing some of its dimensions or providing new parameters. This capability allows:
(a) the correction and adjustment of geometric model;
(b) the generation of a family of parts whose members differ only in dimension.
The author takes the view that from the existing approaches two categories can be recognized. They are program-based variation and algebra-based variation.
Program-based variation is a standard methodology of CAD used to generate variantions of a design part . Using this method a design part is created by running a program which takes some of the dimensions as parameters. According to different values of parameters, variantions on the master part are created. The program can be generated in batch or interactive mode . In batch mode, the program is written by designer either in a high-level programming language, e.g. Fortran, or macro programming language with special graphics commands; in interactive mode, the commands and dimensions that the designer has selected to construct the model are automatically recorded by the system to generate a program .
Roller's advanced method for interactive generation of parametric models in CAD systems  belongs to this category. Rossignac et.al.  has generalized this method so that it can also be used in non-geometric models. They presented an approach for capturing the functional and relational aspects of a design as a sequence of parameterized unevaluated operations.
Algebra-based variation uses mathematical methods to create variantion. The most well-known approach is to translate each constraint into an equation and then to solve the system of (non-linear) equations [6,7,12]. Other approaches using geometric reasoning [1,2,3,13] also seem to belong to this category because for each kind of geometric relationship, usually represented in the form of Prolog-clauses and used for
symbolic reasoning, there is at least one corresponding algebraic equation existing in the background and is used to do numerical computation to get the geometric data.
The author is of the opinion that most of the approaches in the second category are suitable for or only interested in the maintenance of the consistency of the geometric model. How to impose constraints on a model, how to detect and avoid over-/under-constraining and how to satisfy the constraints are therefore of main interest.
Aldefeld's approach  can do the work of both categories. His system has two parts. In the 'reasoning' part, knowledge, implied by the given constraints, is made explicit using a set of symbolic geometric rules and inferencing. Under-, over-, and redundant constraining is detected and a construction plan is derived from the history of inferences. In 'numerical' part, instances of a given generic model are generated by executing the geometry program as listed in the construction plan .
Our approach possesses also the capability to either define and generate a family of parts with various dimensions or maintain the consistancy of an existing model when some of its constraints have changed. In section 2, how to model geometric object and constraint is discussed; section 3 refers to the issues of geometric modelling and constraint maintenance; in section 4 parameterized segment is introduced; section 5 is about the implementation of a CAD system.
2. MODELLING GEOMETRIC OBJECT AND GEOMETRIC CONSTRAINT
Not only dimensions, but also geometric relationships among geometric objects are basic elements for the construction and the variation of the geometric models. We call them geometric constraint. Many conventional approaches in variational geometry represent geometric objects and geometric constraints separately. Geometric constraints appear as equations or predicates which control the variation of geometric models. Our approach represents geometric objects and relationships in an integrated way. Dimensions, including dimensional expressions, are treated as geometric objects. A geometric relationship is represented as an operation to evaluate a geometric object using other geometric objects which are geometrically related to it. A geometric object is therefore represented by a geometric relationship and other related geometric objects. For example, through calculating the two ends of a line L1 so that this line is parallel to another line L2 on a certain distance D1, a geometric relationship 'parallelism' is represented. Meanwhile, the line L1 can be represented based on this relationship, the line L2 and the dimension D1. A geometric object represented with this method is dependent on its related objects which are called support objects. The significant feature of this modeling method is that the geometric relationships are embedded in the geometric model. In the following we discuss the definition of geometric objects on the level of types (or classes). The types of geometric objects are called Geometric Modelling Primitives(GMP).
There are five absolute GMPs. They are value, point, line, circle, and arc. Value is a single numerical data; point consists of two numerical data; line is defined by four numerical data; circle is composed of three numerical data; and arc consists of five numerical data. These structural definitions are called geometric character of the GMPs.
There are also a group of conditioned GMPs. Each conditioned GMP has not only the same geometric character with respect to one of the absolute GMPs, but also information about how it is evaluated. This information includes:
(a) a process which computes the geometric character of this GMP,
(b) a number of related GMPs named support GMPs.
The computing process of (a) uses the information of (b) to compute the data of this GMP. It knows how to do the computation so that the geometric relationship between this GMP and its support GMPs keeps valid.
Figure 2.1(a) shows the definition of a conditioned GMP Line_2o. This GMP has two support GMPs C1 and C2 instead of two end points. Figure 2.1(b) shows the definition of conditioned GMPs pointRelRef and pointPolar.
There are many GMPs who have the same geometric character but different computing process and support GMPs. We say that these GMPs belong to a GMP-class. There are five GMP-classes based on five absolute GMPs. Each conditioned GMP of a GMP-class is derived from the absolute GMP of this GMP-class. For example, the two points P1 in figure 2.1(b) belongs to the same GMP-class point. They have the same geometric character but are represented differently.
In addition to absolute and conditioned GMPs there is also a special GMP of class value which confines the dimension of conditioned GMPs. This kind of GMP is called late constraint. A late constraints is independent of the construct of the GMP it is assigned to. For example, the length of the line L in figure 2.1(a) can be fixed by a late constraint.
3. GEOMETRIC MODELLING WITH GMPS AND CONSTRAINT MAINTENANCE
Each geometric object in a geometric model is an instance of one of the GMPs. An absolute object is an instance of an absolute GMP; a conditioned object is an instance of a conditioned GMP. A geometric model is composed of conditioned objects, absolute points, absolute values and late constraints.
Conditioned geometric objects are dependent on other geometric objects. This dependency is restricted to be acyclic and leads to certain sequences in constructing a geometric model. A conditioned object can only be created when all its support objects have existed in the model. Through the dependency among the objects geometric constraints are maintained. Constraint maintenance is enabled through the constraint propagation which is again enabled through the propagation of computation of geometric objects. The propagation of computation is a recursive process of running the computing process of the support objects in each conditioned geometric object until those objects are reached which either have no computing process, e.g. absolute objects, or have been computed. Through the directed propagation of computation any changes of data of an absolute object can be propagated to those conditioned objects which are directly or indirectly supported by it. This is the propagation of computed value. These two propagation processes work in opposite directions.
Figure 4.1(a) shows a sample model and figure 4.1(b) is the relationship tree and the directions of the two propagation processes.
When cyclic dependency happens during the construction of a geometric model late constraints have to be used. They are called late constraints because they are mostly assigned to the objects after these objects have been created. A late constraint causes cyclic dependency because it is an independent dimensional constraint to a conditioned object and influences the geometric data of some support objects of this object which are used to evalute the original dimension of this object. This conditioned object is called late-constrained-object. A late constraint can be satisfied through varying a free dimension in the support objects of the late-constrained-object so that the original dimension of it equals the late constraint. This free dimension is called maintaining variable. This variable is no longer free if it is selected to maintain the invariableness of the late constraint. More then one late constraint can exist in a model and some of them may be related to each other when a maintaining variable of a late constraint is a support object of another late-constrained-object. The related late constraints should be satisfied simultaneously which means to solve a set of (non-linear) constraint equations where the unknowns are the maintaining variables. For each geometric model there is one process to satisfy all late constraints by using Newton-Raphson iterative method. When evaluating a geometric model this process will not be run until the computing processes of all other objects of the model have done. Figure 3.2 is an example of late constraint and cyclic dependency.
The concept of late constraint can also be used to intentionally change the data of conditioned object, e.g. to move circle C2 of figure 2.3(a) to an intended new position by changing two absolute values X1 and Y1 of figure 2.3(b). In this case, the new position or dimension of the conditioned object can be seen as a temporary late constraint. The free variables X1 and Y1 are then maintaining variables of it.
It is necessary to use late constraint only when the model can not be constructed in sequential order because of circular dependencies in the model. Therefore a model without circular dependencies is first constructed and the remaining properties are put into the model by means of late constraints. The number of constraint equations which have to be solved simultaneously can be thereby reduced to a minimum.
In comparison with the conventional approaches of constraint manipulation, this approach has many advantages:
(a) Because the constraints are assigned during the construction of a model their correctnesses are quitely guaranteed, while the conventional assignment of constraints in a postprocess is error-prone;
(b) Over- or under-dimensioning does not happen in most cases (except for late constraints) , whereas in the conventional method a process has to be developed to detect such situations;
(c) the geometric relationships are inherent part of a geometric model, while the conventional assignment of such implicit geometric constraint in a postprocess is quite complicated;
(d) it is faster to propagate the changing of local constraints.
4. PARAMETRIC DESIGN USING SEGMENT
A family of design parts with various dimensions are often needed during the design. The concept segment serves this purpose.
4.1 About segment
The concept of the segment is similar to the concept of the procedure in high-level programming languages, e.g. Pascal. Therefore we introduce our segment by comparing it with procedure.
The Segment has two related aspects: segment scheme and segment instance. Segment scheme describes the inner structure of the segment. It determines what components the segment has, e.g. the number of the components, the type of each component and the relationships among the components. A segment instance is a graphical representation of the segment. It derives from the segment scheme and the actual parameters and is an appearance of the segment. The concept of actual parameter will be introduced later. Segment schemes correspond to the definitions of the procedures and segment instances correspond to the callings of procedures in the program.
In the following discussion we still use the word 'segment' when it is not necessary to differentiate the segment scheme from the segment instance. We still say 'the components of the segment' when it is not necessary to know exactly how the components are defined within the segment scheme and the segment instance.
Another significant feature of the segment is that segment can also have parameters. Similar to the parameters of the procedure there are two different forms of parameters for the segment: formal parameters and actual parameters. The formal parameters exist in the segment scheme and determine the types and the seguences of the actual parameters. The actual parameters do not belong to the segment instance but are used by the segment instances to determine the size, the variational shape and the position of the segment instance.
Each procedure can be called many times in a program. Similarly, a segment scheme can also be associated with many segment instances which means that some segments may have different graphical representations. This can happen when the data of the actual parameters are different for each segment instance with the same inner structure.
4.2 The segment as GMP
The graphical representations of the segments are called 'segment instances' because they could be treated as the instances of the class 'segment scheme' from the point of view of the object-oriented methodology. In our approach we define these two concepts separately and set up a connection between them.
Two new GMPs are defined. They are also called segment scheme and segment instance. A segment scheme contains
(a) a list of formal parameters, and
(b) a list of components.
The component objects are mostly related to each other and some of them have relationship with formal parameters.
A segment instance contains
(a) a list of actual parameters,
(b) a corresponding segment scheme, and
(c) a process to compute the graphical data of the segment instance using actual parameters and the segment scheme.
Segment scheme and segment instance are also treated as classes (or types) like the other GMPs. An instance of the segment scheme class is a concrete segment scheme with a definite number of geometric objects as components and a definite number of formal parameters of certain types. A concrete segment scheme does not appear in the geometric model. An instance of the segment instance class is the representation of a certain concrete segment scheme in the geometric model. Figure 4.1 shows the segment scheme class, segment instance class and their instances.
In the following discussion we call the instance of the segment scheme class segment scheme and the instance of the segment instance class segment instance when there is no misunderstanding.
4.3 The parameters of the segment
The formal parameters can be of any basic types, e.g. value, point, line, circle or arc. They are absolute objects. But they can also be segment instances. Formal parameters are support objects of some component objects in a segment scheme. Therefore they determines the graphical data of these component objects.
An actual parameter must be of the same type with the corresponding formal parameter or a type derived from it, i.e. a GMP in the same GMP-class. Therefore an actual parameter can be a conditioned object. Actual parameters do not belong to the segment instance. They are local geometric objects in the geometric model.
The data of the actual parameters determine the size, the variational shape and the position of a segment instance through formal parameters. The computing process of a segment instance does the following operations:
(a) It copies the graphical data of the actual parameters into the formal parameters of the associated segment scheme;
(b) It runs all the computing processes of the component objects in the associated segment scheme to generate the graphical data for each component;
(c) It returns all the graphical data obtained in (b) to the segment instance.
Figure 3.2 shows the actual and formal parameters and the segment scheme. The arrows within the segment scheme illustrate the supporting relation of component objects.
With different actual parameters variations on the segment scheme can be generated. When a segment instance uses local objects of a model as actual parameters it is fully embedded in the geometric model.
4.4 The external object of the segment
Although the component objects of the segment are geometrically related to each other it is still possible for them to access the objects outside the segment, which means that a component object of a segment has objects outside the segment as its support objects. Such 'outside' object is called external object.
Figure 3.3(a) shows an example, where P0 is an external object of the segment instances S1, S2 and S3. From the segment scheme shown in figure 3.3(b) we can see that P0 is not the component object but is used to support a component object. S1, S2 and S3 are segment instances with the same segment scheme but different actual parameters P1, P2 and P3.
The concept of the external object is similar to the concept of the global variables in a high-level programming language. The difference between external objects and actual parameters of the segment instance is that the external objects remain the same for each segment instance based on the same segment scheme, while actual parameters can be different objects of the same type.
4.5 Accessing component objects of a segment from outside
A segment instance exists as a single geometric object in the geometric model. This means that a component object of a segment can not appear as a real geometric object in the geometric model. Nevertheless it should be possible to access a component object of a segment from outside. For example, the user should be able to pick an object in the geometric model and use it as support object to create another object although the object he is picking might be a component object of a segment. This function is important because the user of the CAD system can see the graphical form of the single objects but has difficulty recognizing which group of objects compose a segment.
To make the accessing possible, five new GMPs are defined, which are called substitute GMPs. They belong to five GMP-classes respectively. Each of these substitute GMPs contains
(a) a process to get its geometric character,
(b) a path to records where the wanted component is in the segment scheme.
A substitute object is an instances of a substitute GMP. The first element in the path of a substitute object is the segment instance in which the wanted component object appears. The position of this component object in segment scheme is stored as the last element in this path. The path may also contain the positon of a component segment instance if the wanted component object appears in this segment instance. The process of getting geometric character finds the wanted component object by going along this path, gets its data and delivers the data to the substitute object.
An access to a component object of a segment is realized as an access to a substitute object of this component object. Figure 4.4 shows an example of substitute object where C1 and C2 are substitute objects of the circles in the segment instances Instance-1 and Instance-2 respectively.
5. OBJECT-ORIENTED IMPLEMENTATION OF A CAD SYSTEM
A 2D CAD sytem -- RelCAD (Relational CAD) is implemented based on the concepts discussed in this paper, using object-oriented programming techniques. All the GMPs implemented as classes. There is a system wide superclass defining the common properties and operations for all other classes. The classes of conditioned objects are defined as subclasses of the classes of absolute objects. Figure 6.1 shows the class hierarchy. Due to the diagram size, only some of the classes of conditioned objects are presented.
An example of class, written in Pascal 5.5, is shown below:
line_2o = object(line)
function a1 : anyptr;
function a2 : anyptr;
The procedure compute uses the two support objects which are obtained by functions a1 and a2 to compute the coordinates of both end points of line_2o. The geometric characters of class line_2o (two end points) are inherited from its superclass line. Information pertaining to relationships among objects are directly used in the procedure compute.
An interactive user interface has been developed, which
(a) allows the user to construct geometric model (including geometric objects and relationships) interactively;
(b) provides tools to edit geometric relationships and vary the geometric model interactively;
(c) provides an environment in which the user can define segment scheme interactively;
(d) provides help for the user to create segment instances.
A segment management subsystem has also been developed. This system stores those segment schemes which may be used in many models or different applications in a public segment library. The system also supports the access to a local segment scheme of an existing model from another model. Transportation of segment scheme between two models or between model and library is also supported.
The feature of this approach is to define a geometric object on the basis of its relation to other geometric objects. Geometric relationships are embeded in the geometric model. This makes the derivation of variant models easier and reduces the number of equations which have to be solved simultaneously. The parameterized segments makes it possible to define any kind of master part and to generate any kind of variant of it.
 Aldefeld B, 'Variation of geometries based on a geometric- reasoning method', CAD vol 20 no 3, 1988, pp 117-126.
 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.
 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.
 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.
 Kondo K, 'Algebraic method for manipulation of dimensional relationships in geometric models', CAD, vol 24, no 3, March, 1992.
 Light R and Gossard D, 'Modification of geometric models through variational geometry', CAD vol 14, no 4, 1982, pp 209-214.
 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.
 Roller D,'An approach to computer-aided parametric design' CAD, vol 23, no 5,June, 1991, pp 385-391.
 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.
 Rosendahl M, Berling R, and Du C, 'Objektorientierte Implementierung eines relationalen CAD-Systems', Research report 4/92, University of Koblenz-Landau, 1992.
 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.
 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.
 Sunde G, 'Specification of Shape by Dimension and other Geometric Constraints',IFIP WG. 5.2 on Geometric Modeling,Rensselaerville, NY, May, 1986.
 'CAD-Ausbildung fuer die Konstruktionspraxis', Carl Hanser Verlag, 1986.