The last four topics covered the basic mathematics and computer graphics algorithms needed to display two- or three-dimensional points and segments. As limited as this may sound, this is actually enough to develop a quite decent modeling system that would handle complex linear three-dimensional objects as long as we represent them only in terms of their edges (“wireframe" mode). Such a system might be adequate in many situations. On the other hand, one would certainly not get any eyecatching displays in this way. To generate such displays, we need to represent objects more completely. Their surfaces, not just their edges, must be represented. After that, there is the problem of determining which parts of a surface are visible and finally the problem of how to shade those visible parts.
Recall the general geometric modeling pipeline shown in Figure 5.1. Of interest are the last three boxes and maps between them. This topic presents a survey of the various approaches that have been used to deal with that part of the pipeline. First, one has to understand the "pure" mathematical objects and maps. The next task is to represent these in a finite way so that a computer can handle them. Finally, the finite (discrete) representations have to be implemented with specific data structures. By in large, users of current CAD systems did not require the systems to have much understanding of the "geometry" of the objects. That is not to say that no fancy mathematics is involved. The popular spline curves and surfaces involve very intricate mathematics, but the emphasis is on "local" properties. So far, there has not been any real need for understanding global and intrinsic properties, the kind studied in topology for example.
Figure 5.1. The real world to implementation pipeline.
Some texts and papers use the term "solid modeling" in the context of representing objects in 3-space. Since this term connotes the study of homogeneous spaces (n-manifolds), we prefer to use the term "geometric modeling" and use it to refer to modeling any geometric object. Three-dimensional objects may be the ones of most interest usually, but we do not always want to restrict ourselves to those.
The first steps to develop a theoretical foundation for the field of geometric modeling were taken in the Production Automation Project at the University of Rochester in the early 1970s. The notion of an r-set and that of a representation scheme were introduced there. These concepts, along with the creation of the constructive solid geometry (CSG) modeler PADL-1 and the emphasis on the validity of representations, had a great influence on the subsequent developments in geometric modeling. R-sets were thought of as the natural mathematical equivalent of what one would refer to as a "solid" in everyday conversation. Using r-sets one could define the domain of coverage of a representation more carefully than before. The relevance of topology to geometric modeling was demonstrated. The terms "r-set" and "representation scheme" are now part of the standard terminology used in discussions about geometric modeling. Most of this topic is spent on describing various approaches to and issues in geometric modeling within the context of that framework.
Section 5.2 defines r-sets and related set operations. Section 5.3 defines and discusses what is called a representation scheme. The definitions in these two sections are at the core of the theoretical foundation developed at the University of Rochester. After some observations about early representation schemes in Section 5.3.1, Sections 5.3.2-5.3.9 describe the major representation schemes for solids in more or less historical order, with emphasis on the more popular ones. The two most well-known representation schemes, the boundary and CSG representations, are discussed first. After that we describe the Euler operations representation, generative modeling and the sweep representations, representations of solids via parameterizations, representations based on decomposition into primitives, volume modeling, and the medial axis representation. Next, in Section 5.4, we touch briefly on the large subject of representations for natural phenomena. Section 5.5 is on the increasingly active subject of physically based modeling, which deals with incorporating forces acting on objects into a modeling system. Feature-based modeling, an attempt to make modeling easier for designers, is described in Section 5.6. Having surveyed the various ways to represent objects, we discuss, in Section 5.7, how functions and algorithms fit into the theory. Section 5.8 looks at the problem of choosing appropriate data structures for the objects in geometric modeling programs. Section 5.9 looks at the important problem of converting from one scheme to another. Section 5.10 looks at the everpresent danger of round-off errors and their effect on the robustness of programs. Section 5.11 takes a stab at trying to unify some of the different approaches to geometric modeling. We describe what is meant by algorithmic modeling and discuss what computability might mean in the continuous rather than discrete setting. Finally, Section 5.12 finishes the topic with some comments on the status and inadequacies in the current state of geometric modeling.
R-Sets and Regularized Set Operators
One of the terms that is used a lot in geometric modeling is the term "solid." What does it mean? It should be very general and include all the obvious objects. In particular, one would want it to include at the very least all linear polyhedral "solids." One also wants the set of solids to be closed under the natural set operations such as union, intersection, and difference.
Intuitively, a solid is something that is truly three-dimensional and also homogeneous in the sense that, if we take a solid like the unit cube and stick a (onedimensional) segment onto it forming a set such as
which is shown in Figure 5.2, then we do not want to call X a solid. A definition of a solid needs to exclude the existence of such lower-dimensional parts.
Note that the definitions depend on the dimension n of the Euclidean space under consideration because the interior of a set does. For example, the unit square is an r-set in R2 but not in R3 (Exercise 5.2.1). Note also that the set X in equation (5.1) is not an r-set because
One can also show that
Figure 5.2. A nonsolid.
In other words, rX is an r-set for any subset X of Rn. R-sets seem to capture the notion of being a solid. Anything called a solid should be an r-set, but we shall refrain from giving a formal definition of the word "solid." In many situations, one would probably want that to mean a compact (closed and bounded) n-manifold. R-sets are more general than manifolds, however. The union of two tetrahedra which meet in a vertex is an r-set but not a 3-manifold because the vertex where they meet does not have a Euclidean neighborhood.
Because halfplanes are r-sets we get all our linear polyhedral "solids" from those via the Boolean set operators such as union, intersection, and difference. We can think of halfspaces as primitive building blocks for r-sets if we allow "curved halfspaces" by extending the notion as follows:
Definition. A halfspace in Rn is any set of the form
whereIf H is a halfspace, then we shall call rH a generic halfspace. A finite combination of generic halfspaces using the standard operations of union, intersections, difference, and complement is called a semialgebraic or semianalytic set if the functions f are all polynomials or analytic functions, respectively.
For example, the infinite (solid) cylinder of radius R about the z-axis, that is,is a generic halfspace, in fact, a semialgebraic set. See Figure 5.3. Semialgebraic sets are an adequate set of building blocks for most geometric modeling and are also "computable" (see Section 5.11).
Next, we need to address a problem with the standard Boolean set operators, namely, they are not closed when restricted to r-sets. For example, the intersection of the two r-setsis not an r-set. See Figure 5.4.
From the point of view of solids, we would like to consider X and Y as being disjoint. One sometimes calls X and Y quasi-disjoint, which means that their intersection is a lower-dimensional set. If we want closure under set operations, we need to revise their definitions.
Figure 5.3. A generic halfspace.
Figure 5.4. Quasi-disjoint sets.
where c and Δ are the complement and symmetric difference operators, respectively.
(1) The regularized set operators take r-sets into r-sets. Furthermore, there are algorithms that perform these operations.
(2) The class of regular semialgebraic or semianalytic sets is closed under regularized set operations.
Proof. For (1) see [Tilo80] or [Mort85]. For (2) see [Hiro74].
Even though r-sets are quite general, they have their limitations.
(1) Although they have attractive features from a mathematical point of view, they are complicated to deal with computationally.
(2) One may want to deal with nonsolids like in Figure 5.2. This is not possible with r-sets.
Nevertheless, at least one has something mathematically precise on which to base proofs.
Geometric modeling systems have taken many different approaches to representing geometric objects. The following definitions ([ReqV82]) can be thought of as a start towards being able to evaluate and judge these approaches in a rigorous way.
Figure 5.5. Representation scheme.
Figure 5.6. Example of ambiguous representation scheme.
Definition. A representation scheme, or simply representation, of a set of “objects” O using a set L is a relation r between O and L. If (x,y) e r, then we shall say that y represents x. A representation scheme r is unambiguous (or complete) if r is one-to-one. A representation scheme r is unique if r is a function (that is, single-valued). The elements of L are called representations or syntactically correct representations and those in the range of r are called the semantically correct or valid representations.
See Figure 5.5. The term “syntactically/semantically correct” is used, because if r is a representation scheme, we can think of r(x) as a set of encodings for x in a “language” L. The semantically correct elements of L are those “sentences” which have a “meaning” in that there is an object that corresponds to them. The terms unambiguous and unique separate out those relations that are not many-to-one or one-to-many, respectively. To be unambiguous means that if one has the encoding, then one knows the object to which it corresponds. To be unique means that there is only one way to encode an object.
Example. Let O be the set of polygons in the plane that have positive area but no holes. Let L be the set of finite sequences of points. For example, the sequence (2,1), (-1,3), (4,5) belongs to L. Define a representation scheme for O using L by associating to each object in O the set of its vertices listed in some order. This representation scheme is neither unambiguous nor unique. It is ambiguous because the objects in Figures 5.6(a) and (b) both have the same vertices. It is not unique because the vertices of an object can be listed in many ways. Furthermore, not all sequences of points are semantically correct. A sequence of collinear points does not correspond to a polygon in O.
We could modify Example 5.3.1. For example, we could require the polygons to be convex or we could require that the vertices be listed in counter-clockwise order. In both instances we would then have an unambiguous representation scheme.
There are reasons for why unambiguousness and uniqueness are important properties of a representation scheme. It is difficult to compute properties from ambiguous schemes. For example, it would be impossible to compute the area of a polygon with the ambiguous scheme in Example 5.3.1. An example of why uniqueness is important is when one wants to determine if two objects are the same. The ability to test for equality is important because one needs it for
(1) detecting duplication in data base of objects
(2) detecting loops in algorithms, and
(3) verifying results such as in case of numerically controlled (NC) machines where it is important that the desired object is created
With uniqueness one merely needs to compare items syntactically. Note that the problem of determining whether two sets are the same can be reduced to a problem of whether a certain other set is empty, because two sets X and Y are the same if and only if the regularized symmetric difference XD*Y is empty.
Although unambiguousness and uniqueness are highly desirable, such representations are hardly ever found. Two common types of nonuniqueness are
(1) permutational (as in the example where sequences of points represent a polygon) and
(2) positional (where different representations exist due to primitives that differ only by a rigid motion).
Eliminating these types of nonuniqueness would involve a high computational expense.
The domain of a representation scheme specifies the objects that the scheme is capable of representing. One clearly wants this to be as large as possible. In particular, one would want it to include at the very least all linear polyhedral "solids." One also wants the domain to be closed under some natural set operations such as union, intersection, and difference. This raises some technical issues.
One issue that has become very important in the context of representation schemes is validity.
The Basic Validity Problem for a Representation Scheme: When does a representation correspond to a "real" object, that is, when is a syntactically correct representation semantically correct or valid?
Ideally, every syntactically correct representation should be semantically correct because syntactical correctness is usually much easier to check than semantic correctness. Certainly, a geometric database should not contain representations of nonsense objects. The object in Figure 5.7 could easily be described in terms of surface patches and so its definition would seem correct from a local point of view, but taken in its entirety it clearly does not correspond to a real object.
Figure 5.7. A nonsense object.
In early geometric modeling systems, validity of a representation was the responsibility of the user, but this has changed. It is no longer acceptable to assume human intervention to correct errors. For one thing, a modeling system might have to feed its geometric data directly to another system such as a robot and bad data might crash that system.
Here are some other informal properties of representation schemes:
(1) Robustness and numeric precision (see Section 5.10 for a discussion of this topic)
(2) Compactness (for storing): “Verbose” representations may contain redundancies that would make verifying validity harder. On the other hand, in the usual trade-off, this may improve performance.
(3) Computational ease and applicability: No representation is best for everything. To support a variety of applications, we could have multiple representations for each object, but then one must maintain consistency.
(4) Ability to convert between different representation schemes: One may want to pass data between different modelers, but even a single modeler may contain more than one representation scheme.
Along with a formalization of the objects that constitute the domain of a modeler, one should also specify and formalize the allowable operations and functions. This formalization has only been carried out in a minimal way so far. We postpone this largely ad hoc discussion to Section 5.7. Insofar as the usual definition of the term “representation scheme” does not address operations and functions, it is an incomplete concept. The term “object representation scheme” would have been more appropriate because it is more accurate.
Representation schemes coupled with the user interface of a modeler have a great influence on the way that a user will think about objects or shapes. One needs to distinguish between a machine representation and a user representation. The discussion above has concentrated on the former, which may or may not be visible to the user, but the latter is also very important and deals with the user interface. A driving force behind generative modeling, which will be described in Section 5.3.5, had to do with giving a modeler a desirable user representation. The issues involved with user representations are similar to but not the same as those for machine representations. Some important informal questions that a user representation must address are
(1) To what class of shapes is a user restricted?
(2) How does a user describe and edit the possible shapes and how easy is this?
(a) How shapes are described can easily limit the user’s ability to use good designs and even to think up a good design in the first place.
(b) How much input is required for each shape?
(c) Can a user easily predict the output from the input?
(d) How accurate are the representations with respect to what the user wants?
(e) Are the operations that a user can perform on shapes closed in the sense that the output to an operation can be the input to another?
(3) How fast and how realistically can the shapes be generated on a display?
(4) What operations can a user perform on shapes and how fast can they be carried out?
Of course, the type of user representation that one wants depends on the user. Here we have in mind a more technical type of user. Later in Section 5.6 we consider a user in the context of a manufacturing environment.