1.3.1 Basic Concepts

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 1.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 1.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.

1.3.2 Set Topology (Unary Operators)

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.

1.3.3 Binary Operators

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.

1.3.4 Set Theoretic Operators

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 1.2 Axioms of r-sets. 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 1.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 1.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 1.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 1.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 1.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.