8. Product Modelling

8.1 Introduction

The role of this chapter is to provide a description of how products will be modelled for use in subsequent sections of the thesis. The representation is similar to other approaches, but has some subtle differences to support the subsequent planning process. This is not to say that the method is a replacement of previous methods, in fact it may be used to imitate many of the other methods available.

The description begins with a review of solid modelling as it applies to product modelling. This is followed by some discussion of how to incorporate not only solid modelling, but other aspects of product design, into an algebraic form. Software implementations were used for verification of the method. These include capabilities for storage of arbitrary sets, and storage and manipulation of Boolean equations.

If the reader requires more background in solid modeling, they are directed to Requicha and Rossignac [1992] and Stewart [1990].

8.2 The Basic Types of Solid Models

Requicha [1992] asserts that there are three fundamental methods for representing solid objects: Decomposition, Boundaries, and Construction. Decomposition uses representations which attempt to divide space in some discrete manner. These approaches include thin 2 dimensional slices, voxels, ray casting, oct-trees, and binary space partition trees. Boundary methods use the faces, edges, and vertices of the object. Various data structures differentiate much of the work in this field. Requicha [1992] also states that additional information is required with the boundaries to establish solid properties. Finally, Constructive approaches build up the data representation from other geometries. The most popular constructive techniques are the CSG (Constructive Solids Geometry) and Sweeping methods.

There are clear differentiations between each of the three main solid modelling approaches. The Constructive methods are well defined volumes, whereas the other methods are subject to spatial resolution, volume location and data abstraction problems. For example the CSG method is described by Requicha as “rooted, directed, acyclic, binary graphs, where the internal nodes correspond to Boolean operations or rigid-body transformations and where leaves are primitive bounded solids or half spaces. CSG representations are concise, always valid in the r-set modeling domain, and easily parameterized and edited.”

Higher level methods for representing solids have also been examined in recent research. One particular method often cited is feature modelling. In this approach the part is described with features. The features are treated as solids, and operated upon as solids [ElMaraghy, 1991]. In addition to problems mentioned in the last chapter, a problem it causes for Solid Modeling is that when features overlap there is no method for determining priority [Requicha, 1992]. For example, if a fillet overlaps a hole, does the fillet cover the hole, or is it removed?

The CSG representation has been chosen for this thesis because it is both abstract and unambiguous. This makes it well suited to serve as the basis for this reasoning system. More specifically the representation will be done with the CSG expressions in Boolean form.

8.3 Boolean Based Solid Geometry

An analytic expression of geometry can provide an exact representation of a part. As the geometry of the part is analyzed, it may be decomposed into boundaries, then surfaces, and finally lines. At each interpretation some information is lost. Boolean operations on sets are the most abstract representation of solids, with the least detail. By its nature the CSG representation is informationally complete, concise, and the method of representation ensures syntactic correctness.

Constructive Solid Geometry (CSG) is an explicit mathematical representation. The geometry may be expressed as a Boolean equation with sets as the variables. This means there are a number of basic properties that are of relevance to any work using these equations. This section of the chapter will address the basic properties and relationships of interest.

CSG models are based upon Boolean operations performed on primitive solids. Many names have been given to this method, for example Constructive Solids Geometry (CSG) and the Set Theoretic method. There are also many basic representations that may be used. One is the CSG tree, which is a combination of operations and primitives as seen in Figure 8.1 CSG Representation in Tree and Expression Form. The nodes of the tree are operations, and the leaves of the tree are primitives. There are only two children for each node. The top of the tree is referred to as the root. Another method for representation is in expression form. The expression form uses operators applied to the variables, which represent the primitives (see Lee and Jea [1988] for more examples). Other deviations on the expressions have been developed by various researchers, such as Woo [1977]. He uses a similar expression structure, but each term has the same operator applied to all of the variables within the set of brackets.

 

Figure 8.1 CSG Representation in Tree and Expression Form

Some of the distinctive features of CSG models are globalness, non-uniqueness, and redundancy. The term ‘global’ refers to the possible distribution of solids over a tree, or an expression, whatever the case. There have been attempts to overcome this by using normal [Goldfeather et. al., 1986] and canonical [Kakaza and Okino, 1984] forms. Although these methods may still leave distributed terms, they do reduce the distribution. The non-uniqueness property refers to the infinite number of ways in which specific solid geometries may be composed. This is still an ongoing research problem. Some authors [Woodwark, 1988] view this as a major problem for CSG when finding a single set of manufacturing features for a part. But, as the reader will see, I have exploited this to find many alternative manufacturing features for production. The redundancy problem builds upon the non-uniqueness. In this case there are two primitives that cancel each other. Tilove [1984] gives as an example a CSG tree where the designer has used a cylinder to fill a previously cut hole. To solve this problem Tilove [1984] developed algorithms for Null Object Detection (NOD), to determine when there are redundant primitives.

A set topology is considered to be a set of points in space. By definition, these points do not include a boundary. The standard topological operators are complement, interior, closure and boundary. These unary operators differ from the binary operators in that they only operate on one set.

When dealing with two interacting topologies, binary operators are required to describe the interaction. The commonly used operators are union (OR), intersection (AND) and difference (AND with NOT). If these operators are applied with ignorance to the point sets there are possible overlap and singular contact point problems. When these binary operators are used in combination with the unary operators the result is a theoretically correct and complete set of operators. These are described in the next section.

The basic operators were described before, and there are other enhanced operators such as Assemble [Arbab, 1990] [Hartquist and Marisa, 1985]. These operators work on basic sets of topological primitives. The primitives can be represented in a few different forms. The traditional approach uses r-sets [Requicha, 1980] and a newer approach uses s-sets [Arbab, 1990].

An r-set [Tilove and Requicha, 1980] is used to represent a homogenous solid in three dimensional Euclidean space. The face of the solids is assumed to be rational, therefore there are no unassociated vertices, edges, faces. This also implies no infinitely thin holes or cracks. The volumes must be enclosed by a set of boundaries. The set is closed, which means that it includes its own boundary. The set is also regular which means it is equal to the closure of its interior. And, the set is semianalytic, which means it can be expressed as a finite boolean combination of analytic sets. When operations are done they may not result in a set which is closed and regular. Therefore, a special set of operators have been developed which force a closed regular object. These are the Regularized operators. When applied these operators will eliminate dangling planes, vertices, edges, infinitely small holes and cracks. The definitions of these operators is given in Figure 8.2 Axioms of r-sets (These ensure that all sets are closed, and regular). The r-set approach is not always desirable. When dealing with assemblies, non-manifold contact r-sets would call for physically connected parts. But, it may be desired to have parts that are physically separate, such as press fits. [Aside: manifold solids have edges bounding exactly two faces, and vertices acting as a point of a cone. Nonmanifold parts touch with one or both parts along points, or edges only, therefore not sharing any volume at the point of contact. In more practical terms, nonmanifold objects can erroneously suggest that part of an object exists without any volume].

 

Figure 8.2 Axioms of r-sets (These ensure that all sets are closed, and regular)

One simple method of allowing touching parts is to use an assembly operator, this allows aggregates of r-sets (each part in the assembly is stored separately). PADL2 [Hartquist and Marisa, 1985] uses these sets to represent assemblies. Extended CSG trees are used to represent Assembly operators, along with Regularized Boolean operators. The axioms in Figure 8.3 Axioms for Assembly Operators are for assembly operators, and will permit us to manipulate the individual assemblies, without forcing them to join. Arbab [1990] discusses the use of the Assembly operator, and likens it to a placeholder in the CSG trees. This method cannot derive a single r-set, thus a re-evaluation is required whenever a new operator is applied. Also, because the sets are stored separately, mathematical errors may accumulated differently and result in slight variations in object positions after transformations.

 

Figure 8.3 Axioms for Assembly Operators

When dealing with assemblies, an alternative to r-sets and Assembly operators are open regular sets. These sets have all of the properties of the r-sets, except that points on the boundary are not considered part of the volume. This allows surfaces to make contact, without having to become a single solid [Arbab, 1991]. This method does not allow internal nonmanifold boundaries. To allow internal boundaries, hypersets may be used [Requicha, 1992]. A volume set is decomposed into volume subsets (hypersets) which are the result of previous set operations that have resulted in the nonhomogenous solid.

Arbab [1990] proposes s-sets as an alternative to r-sets, Assembly operators, and open regular sets. The essential feature of this method is that separate internal boundaries are allowed within the solids. An assembly operator is an inherent part of s-sets. The basic s-set operators are shown in Figure 8.4 Open Regular Axioms for s-sets. Note that the assembly operator only acts when the components do not intersect in the first intersection axiom. A preferred approach to the assembly axiom is also provided that will split the assembled volume into three components. The internal boundaries are not preserved by all operations, only the assembly operation may create new internal boundaries. Arbab also poses a set of axioms specifically for a B-Rep of s-sets.

 

Figure 8.4 Open Regular Axioms for s-sets

The methods previously described are concerned with exact representations of solids. In actuality, solids never conform exactly to a geometrical form. Variational classes have been introduced as a method for dealing with sets of acceptable tolerances for solids [Requicha, 1992].

In the authors opinion the most flexible approach which has been developed is Selective Geometry Complexes (SGC). This method uses aggregates of mutually disjoint cells that are connected in a continuous geometry. The sets can be open or closed, and the geometry expressed in equation form. For example, a union of two shapes could result in one solid, containing three separate volume regions. Where the two solids touched, an unknown volume would now exist, hence the three regions are required. Rossignac and Requicha [1991] developed a new representation scheme called Constructive Non-Regularized Geometry (CNRG) which takes advantage of previous set operations, including SGC. In total, their representation scheme allows all of the previous regularized operations, as well as nonhomogenous solids (materials with varying properties), and assemblies. This method is very exciting, and would be excellent for representing the solids commonly found in design. Unfortunately, at the time of writing, this work was still under development, and not in a suitable state for use.

The previous discussion indicates that there are many methods for modelling solids in a set theoretic approach. It also indicates that there are no ‘perfect’ methods yet. As a result it was decided that the design representation should be as abstract as possible, to ensure conformity to whatever method is developed. In practical terms this means that the Assembly operator will be maintained as an independent operator keeping all of the geometries separate. This is most similar to the r-set approach. Eventually, new operators for assembly can be added when the tools to support them are available.

8.4 Manipulating Solid Models of Designs

It was decided to use the non-uniqueness and global nature of the CSG representation to drive the logic of the BCAPP planning system. But, in addition to this the CSG expression will be represented with Boolean expressions to allow use of Boolean algebra. This section will describe my particular representation. The following sections will discuss implementation of this representation in a Boolean Algebra program, and representing product designs with Boolean equations of sets.

8.5 A Computer Based Boolean Design Representation

First, while the scope of operators is clearly defined in Boolean algebra, they can be somewhat confusing to comprehend. The problem of changing operator scope will require that any computer program understand the rules for their application. This would require some form of complex algorithm to determine operator scope before the simplest operation could be performed. To simplify this problem a Nested Boolean form is adopted which is very scope specific, similar to that used in Woo[1977]. This form puts each operator in a set of brackets. As in normal algebra, nested terms in brackets must be performed first. This method does not in any way restrict the use of any of the Boolean operators, but removes any question of ambiguity in interpretation. A detailed discussion will follow, but an example of this is,

A * B + A * ~C (3.1)

becomes,

( + ( * A B ) ( * A ( ~ C ) ) ) (3.2)

While the first equation above would require some interpretation as to order, the second form specifies that the NOT operation, and the AND operations must be performed before the OR operation. The only addition is the generous use of brackets, and the collection of an operator over a list of terms. In a more logical form the equality of both representations may be shown by first considering the premise that precedence of operations in an expression is directly based upon either conventions of priority for operations, or precedence that is clearly indicated by bracketed terms. Therefore, when considering the conventional precedence of operators, a high priority operator would be forced to occur first, as if it were in brackets. When brackets are used anyway, they duplicate the brackets in the Nested Boolean representation.

Secondly, because of the nature of design, we would attempt to economize on effort by reusing terms, and sets. As is seen in the expression above (3.2), A is reused in the same equation. Say for example that A is a common screw. In the equation above it would be used twice. The problem arises in that the set that defines the geometry of the screw, also defines attributes such as position. In the representation above, both of the screws would overlap in space. This assertion is obviously nonsense, so to overcome it, enhancements were added to the equations. These come in the form of attribute sets that may be appended to any symbol, or term in an equation. An example is seen below,

( + ( * A;move_to_B B ) ( * A;Fixture ( ~ C );Move_to_A );Move_to_spot )

In this case some terms and symbols have been augmented with additional property sets that effectively become part of the original set. Therefore in this case we have defined only one A, but after adding ‘move_to_B’ to one, and ‘Move_to_A’ to the other, they now become separate, and individual sets. This starts to explore the subtle differences of equations of sets to be discussed later.

Thirdly, the exclusive use of Boolean operators is not realistic here because of the use of sets, and the irrationality of product representation. Therefore the Boolean operators have been supplemented with some other operators and constraints. As discussed before, assemblies are difficult to model within one solid model. As a result we use the assembly operator used in many solid modelers. This allows parts which may overlap in a geometrical model (e.g., a press fit) to coexist separately. This also allows the designer to specify when an assembly is actually desired.

While the mathematical descriptions in the previous section outlined the theoretical model of the product, it was necessary to describe the part in some file format for verification of the method, and for other stages of testing.

The file format chosen was a text format, which would allow easy editing and verification. A sample of the file format is shown in Figure 8.5 A Sample File Defining a Part. Within the file the sets are defined by giving the set name, and then a list of properties, delimited by the ‘{‘ and ‘}’ brackets. All of the properties are arbitrary, except for the ‘EQUATION’ property. The purpose of the ‘EQUATION’ property is to indicate how other sets combine into this one.

This format has been left particularly loose, so as to not restrict future development. The problems with fixed fields are emphasized by the number of special cases required for small differences, as can be seen in vonRimscha [1989]. One potential problem that could result from the free form representation is the inadvertent creation of a recursive reference for a child to a parent, which is physically impossible. Within my thesis I will use a few properties that can be considered standard, such as ‘translate_y’. Most of the attributes will be easy to identify from their name only. The selection of properties should be done on an application specific basis. A readily available example of this is, that by choosing ‘translate_y’ we assume all coordinates are Cartesian, whereas we may have a robotics based design which considers cylindrical coordinates the norm, such as ‘translate_r’. A number of properties have been identified in other work that must be stored in addition to the basic solid model for completeness. Some of these other properties are tolerances and material [Braid, 1986].

The file below is one of the test files used to verify the software written. It depicts a nut and bolt assembly (as indicated by the ‘main’ classifier). Notably, this set only contains an equation. In a practical use this would probably contain some information from the designer. The expression contains a Boolean equation that refers to ‘nut’, and to ‘bolt’. And, the set ‘bolt’ is modified by adding ‘move_to_hole’. The ‘move_to_hole’ set is now appended onto the ‘bolt’ set for the assembly operation.

main nut_and_bolt {

EQUATION: ( : nut bolt )

}

nut {

EQUATION: ( & A ( ~ B ) )

}

bolt {

EQUATION: ( + C ( & D;test1 ( ~ E ) )

}

test1 {

color =SILVER

}

A {

form = BLOCK

width = 10.0

depth = 10.0

height = 4.0

name = Nut_Blank

}

B {

form = CYLINDER

radius = 2.0

height = 5.0

name = tapped_radius_hole

finish = threaded

diameter_tolerance = 0.1

}

C {

form = CYLINDER

radius = 2.0

height = 5.0

name = bolt_shaft

finish = threaded

translate_x = 0.0

translate_y = 0.0

translate_z = 0.0

rotate_x = 0.0

rotate_y = 0.0

rotate_z = 0.0

}

D {

form = CYLINDER

radius = 3.0

height = 1.0

name = bolt_head

finish = polish

diameter_tolerance = .1

translate_x = 0.0

translate_y = 0.0

translate_z = 3.0

rotate_x = 0.0

rotate_y = 0.0

rotate_z = 0.0

}

E {

form = BLOCK

width = 9.0

depth = .5

height = .5

translate_x = 0.0

translate_y = 0.0

translate_z = 3.25

rotate_x = 0.0

rotate_y = 0.0

rotate_z = 0.0

}

move_to_hole {

translate_x = 3.0

}

Figure 8.5 A Sample File Defining a Part

This particular structure can be of use because the process planner in not just receiving geometry, but also some insight to the designers methodology. For example, the assembly of the nut and bolt in a traditional solid model would just be two separate non-overlapping geometries. In this model we can clearly (and easily) identify the two separate parts that are assembled. The file format not only represents the final geometry, but the designer’s perceptions of the design.

When the file format is loaded it can be easily interpreted into a Boolean equation. The example below uses substitution to expand the equation in the main set to a final geometric description.

( : nut bolt;move_to_hole ) (3.3)

( : ( & A ( ~ B ) ) bolt;move_to_hole ) (3.4)

( : ( & A ( ~ B ) ) ( + C ( & D;test1 ( ~ E ) ) );move_to_hole ) (3.5)

The final equation is of the type that can be used to drive a solid modeler. The figure below was automatically generated from the ‘nut_and_bolt’ file above, and coincidently also helped verify the correctness of the low level boolean algebra routines.

Figure 8.6 The ‘nut_and_bolt’ Example Interpreted into Geometry (modelled rendered using ACIS [Spatial Technology, 1991])

The representation here was developed to facilitate testing of the system. In review it is safe to say that this system could eventually benefit by the incorporation of a more formal language structure, such as that of PDL [H. A. ElMaraghy, 1991], or ALPS [Mantyla, 1993].

8.6 A Data Structure for Storing Boolean Algebra

The Boolean algebra methods described in this thesis are supported by a set of Boolean algebra data structures. These structures were written in C++, thus there is some use of inheritance, and functions are associated with the Boolean data structure [Strousap, 1986].

As shown before, each term is represented in a LISP like fashion with an operator being first in the list, followed by a list of operands. An example of this equation form is shown in Figure 8.7 Nested Boolean Algebra Data Structure (Only a partial example is given for clarity), along with a data structure diagram that is used to store the equation (only part of the equation is shown for the purpose of clarity). The Operation List may be thought of as storing the start of each nested term, it coincides with the open bracket ‘(‘ and the operator. Therefore, each operator is assigned a row. The row points to a list of terms. The other field in the row is for a symbol pointer. The Symbol Pointer allows a text string (and other symbol information) to be associated with each operation. The append list field allows lists of appended properties, such as ‘test’, to be appended to symbols and terms.

The Term Lists array is simply for storing lists of arguments for the operations. The reader will note that the pointer refers to both the Operation List, and the Symbol List. This allows both sets, like ‘A’ and sub-terms ‘(+ D G)’ to exist in common. The ‘type’ field specifies which type of pointer is in the ‘pointer’ field. The ‘point to next’ field provides a linked list of the arguments, and terminates with a ‘last’ marker.

Finally, the Symbol list is used to store textual information for recall by the user. These also contain two fields for use by the calling routines. A ‘pointer’ field is provided so that the user may store a reference to an outside object (like a geometric primitive), whereas a ‘type’ field provides information about the pointer type. There are additional types of data associated with each list for the purposes of maintenance, as is described on the next paragraph.

 

Figure 8.7 Nested Boolean Algebra Data Structure (Only a partial example is given for clarity)

The reader should note that the data structures in Figure 8.7 Nested Boolean Algebra Data Structure (Only a partial example is given for clarity) do not show the method for dynamic memory allocation. The lists shown in the data structure have many rows which will be added and deleted in a semi-random fashion. As a result, a reuse mechanism structure has developed for each of the lists. One example of this structure is shown in Figure 8.8 Dynamic Memory Structures Added to Lists, and may be viewed as a generic approach for all of the lists above. In Figure 8.7 Nested Boolean Algebra Data Structure (Only a partial example is given for clarity) both ‘used’ and ‘point to next’ are added data fields. This structure makes allocation of a new row, simply a matter of deleting from the head of empty linked list, and pushing onto the head of the used list. Deletion of an existing term is a case of modifying next pointers to point over the defunct term, then pushing the now empty term onto the empty list. The used and unused flags are updated to make validity checking easier, without having to retrace lists. The end of list pointer makes range checking easy, when the array has been dynamically allocated (as was done using C++).

 

Figure 8.8 Dynamic Memory Structures Added to Lists

Public functions have been created to manipulate each object. These are structured so that the functionalities are nested. Some of the functions are listed below.

Symbol List: