**ABSTRACT:**

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.

**KEYWORDS:**

Geometric model, geometric relationship, geometric constraint, dimension, segment, parameter, variation.

**1. INTRODUCTION**

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 [14]. 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 [14]. 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 [14].

Roller's advanced method for interactive generation of parametric
models in CAD systems [8] belongs to this category. Rossignac
*et.al.* [11] 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 [1] 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 [1].

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

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

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,

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

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 (**Rel**ational **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)

alter:integer;

constructor init(ia1,ia2:anyptr;ialt:integer);

function a1 : anyptr;

function a2 : anyptr;

procedure compute(kind:tvalkind);virtual;

.

.

end;

The procedure * compute* uses the two support objects
which are obtained by functions

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.

**6. CONCLUSION**

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.

**REFERENCES:**

[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] **Kondo K**, 'Algebraic method for manipulation of
dimensional
relationships in geometric models', CAD, vol 24, no 3, March,
1992.

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

[7] **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.

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

[9] **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.

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

[11] **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.

[12] **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.

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

[14] 'CAD-Ausbildung fuer die Konstruktionspraxis', Carl Hanser Verlag, 1986.