Graphics Reference
In-Depth Information
real world
objects
and queries
mathematical
objects
and maps
finite
representations
actual
implementations
→
→
→
Figure 5.1.
The real world to implementation pipeline.
Some texts and papers use the term “solid modeling” in the context of represent-
ing 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 mod-
eling 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 cov-
erage 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 mod-
eling. Most of this chapter 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 dis-
cusses 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 his-
torical order, with emphasis on the more popular ones. The two most well-known rep-
resentation 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, representa-
tions 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 repre-
sentations 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 repre-
sent 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 ever-
present 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 geo-
metric modeling. We describe what is meant by algorithmic modeling and discuss
