[CS Home Page] [Top Level - All Titles] [Top Level - This Title] [Expand This View] [Collapse This View] [Previous Hit] [Next Hit] [Clear Search] [Show Frames]

Expand Search




IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 1077-2626/96$05.00 © 1996 IEEE
Vol. 2, No. 1: MARCH 1996, pp. 3-10

A Road Map To Solid Modeling

*

Christoph M. Hoffmann

Jaroslaw R. Rossignac

Abstract[mdash]The objective of solid modeling is to represent, manipulate, and reason about, the three-dimensional shape of solid physical objects, by computer. Such representations should be unambiguous.

Solid modeling is an application-oriented field that began in earnest in the early 1970s. [46]. Major application areas include design, manufacturing, computer vision, graphics, and virtual reality. Technically, the field draws on diverse sources including numerical analysis, symbolic algebraic computation, approximation theory, applied mathematics, point set topology, algebraic geometry, computational geometry, and data bases. Monographs and major surveys of solid modeling include [13], [19], [27], [37], [44], [45], [46].

In this road map article, we begin with some mathematical foundations of the field. We review next the major representation schemata of solids. Then, major layers of abstraction in a typical solid modeling system are characterized: The lowest level of abstraction comprises a substratum of basic service algorithms. At an intermediate level of abstraction there are algorithms for larger, more conceptual operations. Finally, a yet higher level of abstraction presents to the user a functional view that is typically targeted towards solid design. Here, we will look at some applications and at user interaction concepts.

The classical design paradigms of Solid Modeling concentrated on obtaining one specific final shape. Those paradigms are becoming supplanted by feature-based, constraint-based design paradigms that are oriented more toward the design process and define classes of shape instances. These new paradigms venture into territory that has yet to be explored systematically. Concurrent with this paradigm shift, there is also a shift in the system architecture towards modularized confederations of plug-compatible functional components. We explore these trends lightly in the last section.

Index Terms[mdash]Solid modeling, solid representations, conversion between solid representations, feature-based design, constraint-based design.

1. MATHEMATICAL FOUNDATIONS

An algebraic halfspace is defined as the point set H = {(x, y, z) | p(x, y, z) [le] 0 }, where p(x, y, z) is a polynomial in x, y, and z with real coefficients. A semialgebraic set is any point set obtained as the result of a finite number of set operations (union, intersection, difference) applied to algebraic halfspaces. Bounded, homogeneously three-dimensional, semialgebraic sets were proposed in the 1970s as mathematical models for solids [43] by Requicha, who called such sets r-sets. Requiring homogeneous three-dimensional sets conforms with the intuition of modeling physical solids. The requirement to build r-sets from finitely many set operations applied to algebraic halfspaces is intuitively a variational restriction on the solid boundary. It conforms to the intuition that any line should not intersect the solid boundary infinitely often.

In recent years, more general mathematical models of solids have been proposed that do not require homogeneously three-dimensional sets. The relaxation responds to applying the tools of solid modeling to more general problem domains. For example, in some approaches to robot motion planning, configuration spaces are modeled and analyzed, and those spaces usually are dimensionally inhomogeneous. In fact, they may require higher dimensional spaces with noneuclidean metrics.

Other applications require modeling an inhomogeneous solid interior, for instance in the investigation of composite structures, such as certain industrial parts or electronic components. When geological structures are modeled for the oil industry, dimensionally inhomogeneous structures arise as well. Such models require sets of semialgebraic sets to express internal boundaries and irregularities.

Tools from algebraic geometry have been applied systematically to problems in geometric and solid modeling. Such tools include elimination techniques that algorithmically reduce the number of variables in a system of nonlinear equations, or else transform such systems to equivalent ones that are in a form that is especially well-suited to solving the system. For an introduction and a sampling of some of the results in this subject see, e.g., [4], [7], [8], [14], [19], [53]. Such symbolic computation algorithms tend to require highly sophisticated adaptations to geometric problems, because applying them straightforwardly usually leads to unacceptable running times or to mathematical representations that are computationally fragile.

A difficult subject in need of foundational work is tolerancing and the general problem of drawing logical conclusions from computations that are inexact. Further discussed in Section 3.1, these subjects pose extremely demanding problems that remain wide open to future advances.

2. SOLID REPRESENTATIONS

The three dominant solid representations in use are constructive solid geometry (CSG), boundary representation (Brep), and spatial subdivision. There are other representation schemata as well, less widely used. Conversion between different representations is in some cases an open problem.

Any solid representation should admit the unambiguous, algorithmic determination of point membership: Given any point p = (x, y, z), we have to be able to determine algorithmically whether the point is inside, outside, or on the surface of a solid. Moreover, restrictions on the topology of the solid and its embedding are desirable that exclude, for example, fractal solids.

These restrictions are intuitive. However, as indicated before, increasingly solid modeling departs from this strict notion of solid and permits representing a mixture of solids, surfaces, curves and points. Such generalizations require the development of new or extensively modified classical data structures to represent solids.

2.1 Constructive Solid Geometry

Classical Constructive Solid Geometry, CSG, represents a solid as a set-theoretic Boolean expression of primitive solid objects, of a simpler structure. Both the surface and the interior of the final solid are thereby implicitly defined. The CSG representation is valid if the primitives are valid. A solid's surface is closed and orientable and encloses a volume. The traditional CSG primitives are block, sphere, cylinder, cone, and torus.

A solid is represented as an algebraic expression that uses rigid motions and regularized set operations. The traditional operations are regularized union, intersection and difference. A regularized set operation requires taking the closure of the interior of the set-theoretic result. Regularization eliminates lower-dimensional components from the solid representation such as interior, or dangling exterior, faces, edges, and vertices.

Each solid has a default coordinate system. Using a rigid body transformation, the solid is positioned relative to a global coordinate system. A Boolean operation then combines the solids with respect to the common coordinate system. The result solid can be repositioned by another rigid-body transformation.

As example, consider Fig. 1. Using the coordinate system conventions for the primitives as shown, the CSG representation of the T-bracket is the expression 

  block(8, 3, 1) <* move(block(1, 3, 3), (0, 4, 1))
      - *  move(cylinder(0.5, 1), (1.8, 1.8, -0.5))     (1)

where the * indicates a regularized operation.

Fig. 1. Left and middle: CSG primitives block(w, d, h) and cylinder(r, h) with default coordinate systems. Right: T-bracket as union of two blocks minus a cylinder.

Basic operations one performs on CSG representations are classifying points, curves, and surfaces with respect to a solid; detecting redundancies in the representation; and approximating CSG objects systematically.

More general primitives are obtained by considering the volume covered by sweeping a solid along a space curve, or sweeping a planar contour bounding an area. Defining a sweep is delicate, requiring many parameters to be exactly defined, but simple cases are widely used. They are extrusion, i.e., sweep along a straight line; and revolution, i.e., a sweep about an axis. The evaluation of general sweeps can be done by a number of methods; e.g., [1], [27], [40]. Spatial deformations of solids are another way to obtain new solids, whether they be used as primitives or as final solids. A general set of primitives is the set of algebraic halfspaces; [4].

2.2 Boundary Representation

In boundary representation, Brep, the solid surface is represented as a quilt of faces, edges, and vertices. A distinction is drawn between the topological entities, vertex, edge, and face, related to each other by incidence and adjacency, and the geometric location and shape of these entities; Fig. 2. For example, when representing polyhedra, the faces are polygons described geometrically by a face equation plus a description of the polygon boundary. Geometrically, the entities in a Brep must not intersect anywhere except in edges and vertices that are explicitly represented in the topology data structure. In addition to the classification operations mentioned for CSG, Boolean union, intersection and difference operations are usually implemented for Brep systems. Both regularized and nonregularizing Boolean operations may occur.

Fig. 2. Topological entities of a box. Adjacency and incidence are recorded in boundary representation (Brep). Dotted arrows indicate face orientation.

Different Brep schemata appear in the literature, divided into two major families. One family restricts the solid surfaces to oriented manifolds. Here, every edge is incident to two faces, and every vertex is the apex of a single cone of incident edges and faces. The second family of Brep schemata allows oriented nonmanifolds in which edges are adjacent to an even number of faces. When these faces are ordered radially around the common edge, consecutive face pairs alternatingly bound solid interior and exterior [62]. See Fig. 3 for examples.

More general nonmanifold Breps are used in systems that combine surface modeling with solids modeling. In such representation schemata, a solid may have interior (two-sided) faces, dangling edges, and so on [62]. Such systems are used, for example, by the oil industry for modeling geological structures, or to model civil engineering projects.

Fig. 3. A nonmanifold solid without dangling or interior faces, edges and vertices; the nonmanifold edges and vertices are drawn with a thicker pen.

The topology may be restricted in more technical ways. For instance, the interior of a face may be required to be homeomorphic to a disk, and edges to have two distinct vertices. In that case, the Brep of a cylinder would have four faces, two planar and two curved. Such restrictions often reflect algorithmic requirements of the implementation and are sometimes transparent to users of the system.

2.3 Spatial Subdivision Representations

Spatial subdivision decomposes a solid into cells, each with a simple topological structure and often also with a simple geometric structure. We categorize subdivision representations into boundary conforming and boundary approximating.

Boundary conforming subdivision schemata include