Manfred Rosendahl, Roland Berling, Chun Du
Introduction
The main issue of constraint-based geometric modeling is to use constraints to guarantee the consistenc of the geometric model. In purely algebraic modeling there are equations between the elements of the geometric model defined, which are solved to find the characteristic points of the model[LiGo82,LGL81,SeGo87]. Commercial CAD-systems using this approach are for instance I-DEAS Master Series from SDRC[ChSch90], I/EMS from Intergraph, Sigraph-Design developed by Siemens or Design-View from ComputerVision. To avoid iterations to solve the nonlinear equation systems in some cases algebraic methods can be used[BuPe93].
Another way is to use geometric reasoning mechanism in which the dimensions and geometric relationships are defined as either facts or rules [VSR92]. This can also be done in the form of Prolog clauses [Ald88, Arb88, ArWa91].
In some commercial system e.g. Pro/ENGINEER from Parametric Technology Corporation the method feature design is used.
In the RelCAD system a constructive approach to variational geometry is used,. to reduce the number of equations, which have to be solved. Another feature, which was introduced to the constraint based geometric modeling is the Segment-concept. In normal CAD-Systems collections of elements, called group, block or segment are either programmed or the parameters can only be insertion point, angle, size. In the RelCAD-System a segment is a collection of objects that not only logically belong together, but also have geometric/numerical relationships among each other. They can even have relationships to objects outside the segment and are thereby be dependent on them. Any object of a segment definition can be treated as a parameter, not only dimensions or points but also other items and even segments.
When creating a segment instance, actual parameters for the corresponding formal parameters of the segment definition are assigned and by inserting the actual parameters the segment instance can be computed. A segment instance is treated in RelCAD as a normal geometric object and can therefore also be an element of an other segment definition, since nested segments can easily be defined. In a CAD-model also access from outside to the local elements of a segment instance is needed. To realize this despite the fact, that in RelCAD the definition of a segment is only stored once, a replacement element is introduced, which holds the information to access a local element of a segment instance.
The RelCAD system was developed at the University of Koblenz as an application extension to the general 2D CAD-system VarioCAD, also developed there.
Each element of the geometric model is either an absolute one or defined by its relations to other geometric objects. So any changes in an object cause changes in all objects, which directly or indirectly depend on them. This is achieved because the dependencies built a directed acyclic graph (DAG). the method how to change an object, which is not a leaf in the graph, will be explained later.
The following objects are defined as absolute geometric and nongeometric objects:
The relationships between the objects are typed according to these absolute object types. Only Arc is a subclass of Circle and can be used if a circle is required.
From these absolute classes, which have no relations the Constructive classes with relations are derived. The relations are defined in all directions e.g. a point can be derived from geometric elements and also geometric elements can be derived from points.
Some of the classes which are defined, with their corresponding absolute class:
Figure 1
Figure 1 shows the definition of a derived element LINE_2O. This element has 2 support elements C1 and C2.
Figure 2
Up until now we have only discussed definitions with acyclic dependencies. There is also a class, which deals with cyclic dependencies. It is used to set extra dimensional restrictions on derived objects. For example, it could be used to fix the length of the line L in figure 2 This kind of constraint is called late constraint, because it is mostly assigned to the objects after they have been created. We call the derived object to which the late-constraint is assigned a late-constrained-object. A late constraint causes cyclic dependency among the geometric objects, because as an extra independent dimensional constraint it influences the original dimension of a late-constrained-object and thereby the support objects of it, which again determine the original dimension.
For example, if the length of the line L in figure 2(a) is fixed, the positions and radii of both circles C1 and C2 are also restricted. Changing of them leads to a irregular value for the length of the line L which does not agree with the fixed length.
Figure 2.(b) illustrates the situation of cyclic dependency. In order to maintain the consistency of the late constraint a free dimension which directly or indirectly supports the late-constrained-object should be selected as a maintaining variable. A maintaining variable of a late constraint has the following tasks:
1) When the value of the late constraint has changed the maintaining variable should also be changed so that one of the support objects of the late-constrained-object gets the new data which leads to a consistent late constraint.
2) When the support objects of the late-constrained-object have changed the maintaining variable should be changed so that the late constraint remains satisfied.
A dimension is no longer free if it is selected as the maintaining variable of a late constraint. Figure 2(b) shows an example where the coordinate X1 is selected to be the maintaining variable if the length of the line L is fixed to be the value V.
The evaluation of a late-constrained-object is more complicated then the evaluation of other geometric objects because of the cyclic dependency among the late-constrained object, its late-constraint, and the maintaining variable of the late-constraint. An iterative procedure is used to find an appropriate value for the maintaining variable to satisfy the late-constraint. More then one late constraint can exist in a model at the same time and some of them may be related to each other when the maintaining variable of one late constraint is the support object of another late-constrained-object. The related late constraints should be satisfied simultaneously, which means we have 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 (independent and related) by using Newton-Raphson iterative method. When evaluating a geometric model this process will not be run until all other objects of the model have been evaluated.
Because the late constraints are necessary only when the geometric model can not be constructed in sequential order any more and because they are assigned to the model after the main part of the model has been sequentially constructed, the number of the constraint equations which have to be solved simultaneously can be reduced by the user.
Late constraints are also used to change the data of conditioned objects, that means objects, which are not a leaf in the relation graph. If the user wants to change such an object, he has to choose, which independent objects(leaves) should be given free. Then a temporarily late constraint is solved to find a solution with the new values of the dependent objects.
A family of design parts with various dimensions are often needed during the design. The concept segment serves this purpose.
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 the procedure concept concept.
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 realisation of a segment schema. It is derived from the segment scheme and the actual parameters and is an appearance of the segment. Segment schemes correspond to procedure declarations and segment instances correspond to procedure calls.
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 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 sequences 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. The actual parameters define the relations of the segment to the rest of the model.
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.
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 as separate classes and set up a connection between them.
Two new classes are defined. They are also called segment scheme and segment instance. A segment scheme contains
The component objects are mostly related to each other and some of them have relationship with formal parameters.
A segment instance contains
Segment scheme and segment instance are also treated as classes (or types) like the other classes. An instance of the segment scheme class is a concrete segment scheme with a definite number of geometric objects as components and a 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 3 shows the segment scheme class, segment instance class and their instances.
Figure 3
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.
The formal parameters can be either
Formal parameters are support objects of some component objects in a segment scheme. Therefore they determine 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 object in the same absolute object-class. Therefore an actual parameter can be a derived object. Actual parameters do not belong to the segment instance. They are local geometric objects in the geometric model. If the formal parameter is a segment instance the actual parameter must be an instance of the same segment schema.
Figure 4
This is also the way compatible elements are defined.
Definition: 2 elements are compatible if they are either
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 4 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.
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 5
Figure 5(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 5(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.
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 to recognize which group of objects compose a segment.
Figure 6
To make the accessing possible, five new classes are defined, which are called substitute classes. They belong to the five absolute-classes respectively. Each instance of these substitute classes contains a path to get the geometric values of the inside object of the segment instance. The first element in the path is the reference to segment instance in which the wanted component object appears. Then the position of this component object in segment scheme is stored. If the substituted object is a local element of a local segment the path goes further until the last element of the path. 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 6 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.
Besides the parameters another concept used in programming languages is the concept of conditional statements. A conditional element can be introduced in the segment concept with the following class:
Depending on cond the condelement results either in truepart^ or falsepart^. So far true- and falsepart could only contain one element. If they should contain more than one element a segment-instance had to be used. To simplify this, it is practical to define a grouping of elements too. This can be achieved by the following class:
When defining a condelement it has to be insured, that there is no relation between the elements of the true part and the elements of the false part. Also it has to be defined, how a relation to the condelement from outside are invoked. It has to be insured that the invoked relation to the truepart and to the falsepart are compatible. If true- and falsepart have only one element these elements must be compatible. But in any other case, if one part has more than one element, the access has to be defined like the access to local elements of a segment was defined. This substitute element includes a path to truepart and a path to the falsepart. If there is no true- or no falsepart no relations from outside to the elements of a condelement may be defined. Otherwise under one condition this relation could not be evaluated.
The last concept of programming languages which was included in the RelCAD system was the concept of repetition. The definition of the class is
The elements of then loop are numbered 0..n-1. Then a difference diff between first and second is computed. Depending on the value of kind the following elements of the loop are defined:
Type of I th element
loop(kind)
isforloop first+i*diff
isuntilloop first+i/((n-1)*di
ff)
iswhileloop first+i/(n*diff)
A forloop is given by the first and second element. The difference is taken further to the other elements. A untilloop is defined by the first and the last elements. The elements between are defined though, such that the difference between the elements are equal. The whileloop is nearly the same, only second does not give the last element, but of that which would be the next one.
Figure 7
E.g. in a 4-star the angles of the 4 lines would be: 0,90,180,270.
The last problem is to define the difference between 2 elements. From an element characteristic scalar values are derived and the difference between these scalar values define the difference of the 2 elements. The characteristic values according to the absolute type on an element are:
Type Characteristic values
Value Value
Point Px, Py
Line Length, Angle, P1x, P1y, P2x, P2y
Circle Radius, Centerx, Centery
Arc Radius, Centerx, Centery, Startangle,
Endangle
For some derived types of elements additional characteristic values are needed. E.g. the angle of a polar point in the example above. So the difference between P1 and P2 in the example would be the angle-difference of 360. Because the n-star is defined as a whileloop the difference is divided by n
Conclusions
A system for constraint geometric design was explained. The characteristics different to other approaches are mainly the contained segments and the introduction of segments with alternatives and with repetitions.
References