13.472J/1.128J/2.158J/16.940J
COMPUTATIONAL GEOMETRY
Lecture 1
Nicholas M. Patrikalakis
Massachusetts Institute of Technology
Cambridge, MA 02139-4307, USA
cCopyright ?2003 Massachusetts Institute of Technology
Contents
1 Introduction and classi?cation of geometric modeling forms 2
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Geometric modeling forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Wireframe modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Surface modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3 Solid modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 Non-two-manifold modeling . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Basic classi?cation of solid modeling methods . . . . . . . . . . . . . . . . . . . 7
1.3.1 Decomposition models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Constructive solid geometry (CSG) . . . . . . . . . . . . . . . . . . . . . 14
1.3.3 Boundary representation (B-Rep) . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Alternate classi?cation of geometric modeling forms . . . . . . . . . . . . . . . 18
1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.4.2 Unevaluated representation systems . . . . . . . . . . . . . . . . . . . . 18
1.4.3 Evaluated representation systems . . . . . . . . . . . . . . . . . . . . . . 20
Bibliography 21
1
Lecture 1
Introduction and classi?cation of
geometric modeling forms
1.1 Motivation
Geometric modeling deals with the mathematical representation of curves, surfaces, and solids
necessary in the de?nition of complex physical or engineering objects. The associated ?eld of
computational geometry is concerned with the development, analysis, and computer implemen-
tation of algorithms encountered in geometric modeling. The objects we are concerned with in
engineering range from the simple mechanical parts (machine elements) to complex sculptured
objects such as ships, automobiles, airplanes, turbine and propeller blades, etc. Similarly, for
the description of the physical environment we need to represent objects such as the ocean
bottom as well as three-dimensional scalar or vector physical properties, such as salinity, tem-
perature, velocities, chemical concentrations (possibly as a function of time as well).
Sculptured objects play a key role in engineering because the shape of such objects (e.g.
for aircraft, ships and underwater vehicles) is designed in order to reduce drag or increase the
thrust (eg. for propeller blades). At the same time these objects need to satisfy other design
constraints to permit them to ful?ll certain design requirements (e.g. carry a certain payload,
be stable in perturbations, etc). Similarly, there are objects which have signi?cant aesthetic
requirements, eg. cars, yachts, consumer products.
Typically, engineers deal with the de?nition of complex shapes such as engines, automobiles,
aircraft, ships, submarines, underwater robots, o?shore platforms, etc. The shape of these
objects is usually not fully known in advance (except when a baseline design is available).
Consequently, the usual design procedure is iterative, involving:
? Shape creation based on certain design requirements;
? Analysis to evaluate the performance of the object; and,
? Shape modi?cation to improve the shape, followed by analysis (and so on in an iterative
loop) until a satisfactory (and in simple cases, an optimal) design is reached, which
satis?es all the design requirements and minimizes a certain cost function.
Geometric modeling attempts to provide a complete, ?exible, and unambiguous represen-
tation of the object, so that the shape of the object can be:
2
? Easily visualized (rendered)
? Easily modi?ed (manipulated)
? Increased in complexity
? Converted to a model that can be analyzed computationally
? Manufactured and tested
Computer graphics is an important tool in this process as visualization and visual inspection
of the object are fundamental parts of the design iteration. Computer graphics and geometric
modeling have evolved into closely linked ?elds within the last 30 years, especially after the in-
troduction of high-resolution graphics workstations, which are now pervasive in the engineering
environment.
The remainder of this lecture introduces many of the di?erent approaches to geometric
modeling representations that have evolved over the last four decades.
1.2 Geometric modeling forms
Several di?erent geometric modeling forms have evolved over the last forty years. For the
de?nition of model, we can say that an abstract entity M is a model of an object O if M can
be used to answer speci?c questions about O.
Di?erent forms of geometric modeling can be distinguished based on exactly what is being
represented, the amount and type of information directly available without derivation, and
what other information can and cannot be derived.
1.2.1 Wireframe modeling
Figure 1.1: Wire frame model of a cube.
Wireframe modeling, developed in the early 1960’s, is one of the earliest geometric modeling
techniques. It represents objects by edge curves and vertices on the surface of the object,
including the geometric equations of these entities (and also possibly but not always adjacency
information), as shown in Figure 1.1. The traditional drawings of a ship’s lines (Figure 1.2 [4])
is a form of a wireframe model of a ship hull. It is created by intersecting the hull surface with
three sets of orthogonal planes. Usually the hull surface is taken as the molded hull surface
which is the inner side of the hull plating. Intersections of the hull surface with vertical planes
(from bow to stern) are called buttock lines. Intersections of the hull surface with horizontal
3
planes (parallel to keel) are the waterlines, while intersections with transverse vertical planes
are called sections. Wireframes are rather incomplete and possibly ambiguous representations
that were superseded by surface models.
1.2.2 Surface modeling
Surface modeling techniques, developed in the late 1960’s, go one step further than wireframe
representations by also providing mathematical descriptions of the shape of the surfaces of
objects, as shown in Figure 1.3.
Surface modeling techniques allow graphic display and numerical control machining of care-
fully constructed models, but usually o?er few integrity checking features (e.g. closed volumes).
The surfaces are not necessarily properly connected and there is no explicit connectivity infor-
mation stored. These techniques are still used in areas where only the visual display is required,
e.g. ?ight simulators.
1.2.3 Solid modeling
Solid modeling, ?rst introduced in the early 1970’s, explicitly or implicitly contains information
about the closure and connectivity of the volumes of solid shapes. Solid modeling o?ers a
number of advantages over previous wireframe and surface modeling techniques. In principle,
it guarantees closed and bounded objects and provides a fairly complete description of an object
modelled as a rigid solid in 3D space [7, 6, 8].
Figure 1.4 illustrates that for a boundary based solid model of a single homogeneous object,
every surface boundary is always directly adjacent to one other surface boundary, guaranteeing
a closed volume. Solid models, unlike surface models, enable a modeling system to distinguish
the outside of a volume from the inside. This capability, in turn, allows integral property
analysis for the determination of volume, center of volume or gravity, moments of inertia, etc.
An example is Baumgart’s winged edge data structure [1, 2], where every edge has a start
and end point, a face on either side, and at least two edges from each vertex bounding the
faces. This information can be put in tabular form (perhaps using a relational database) or in
a graph like data structure and used to ensure adjacency.
Typical solid modeling systems also o?er tools for the creation and manipulation of complete
solid shapes, while maintaining the integrity of the representations.
Solid modeling techniques exclude the two previous modeling forms (wireframe and surface
modeling). The reason is that the solid modeling forms are traditionally constrained to work
only with two-manifold solids.
In a two-manifold solid representation, every point on the surface has a neighborhood on
the surface which is topologically equivalent to a two-dimensional disk. In other words, even
though the surface exists in three dimensional space, it is topologically ?at when the surface is
examined closely in a small enough area around any given point, as illustrated by the cube in
Figure 1.5.
1.2.4 Non-two-manifold modeling
Non-two-manifold modeling [1, 9, 5, 10] is a new modeling form which removes constraints
associated with two-manifold solid modeling forms by embodying all of the capabilities of
Figure 1.2: Wire frame model of a ship hull.
Figure 1.3: Surface model of a cube.
Figure 1.4: Solid model of a cube.
the previous three modeling forms in a uni?ed representation. The following diagrams (in
Figure 1.6) demonstrate non-two-manifold situations.
In an environment which allows non-two manifold situations, the surface area around a
given point on a surface might not be ?at in the sense that the neighborhood of the point
need not be equivalent to a simple two-dimensional disk. This allows topological conditions
such as a cone touching another surface at a single point, more than two faces meeting along
a common edge, and wire edges emanating from a point on a surface. A non-two-manifold
representation therefore allows a general wire frame mesh with surfaces and enclosed volumes
embedded in space. Overall, non-two-manifold representations have superior ?exibility, can
represent a larger variety of objects, and can support a wider variety of applications than
two-manifold representations, but at a cost of a larger size and more complex data structure.
Applications of the non-two-manifold representation include:
? Distinguish between two di?erent solids, such as a beam welded to a plate (Figure 1.7).
? Represent a solid volume with a cutout and the volume that was cut out (Figure 1.8).
? Distinguish between the components of a composite plate (Figure 1.9).
? Represent a ?nite element mesh embedded in a solid object (Figure 1.10).
? Represent di?erent dimensions simultaneously, such as a volume with a cut plane and an
axis of revolution (Figure 1.11).
?
P2
P1
Figure 1.5: The cube is a two manifold object.
1.3 Basic classi?cation of solid modeling methods
Current computer-aided design and manufacturing (CAD/CAM) systems used for solid object
representation are generally based on three di?erent types of modeling methods:
1. Decomposition models that represent solids in terms of a subdivision of space. - p.7
2. Constructive models that represent solids by Boolean (set) operations on primitive solids
such as rectangular boxes, cylinders, spheres, cones, torii (appropriately sized, positioned
and oriented). - p.14
3. Boundary models that represent solids in terms of their bounding faces, which are them-
selves bounded by edges and the edges by vertices. - p.16
A more detailed description of these models follows.
1.3.1 Decomposition models
Exhaustive enumeration
Exhaustive enumeration is a representation by means of cubes of uniform size, orientation, and
which are nonoverlapping, see Figure 1.12. An object is represented by a three dimensional
Boolean array. Each cell represents a cubic volume of space. If a cell intersects with the
region of interest it has a true value. Otherwise, the value is false. This can be pictured as
a box divided into 3D cubical pixels, with 0 assigned if empty and 1 assigned if full. This
representation involves:
? Regular subdivision of space.
? It stores just one corner of each cube.
? For ?xed space of interest we need just a 3-D array, C
ijk
of binary data, and overall
box/space coordinates:
1 if the cube i, j, k intersects the solid
C
ijk
=
0 if the cube i, j, k is empty
(1.1)
common edge
face
Figure 1.6: Examples of non-two manifold models.
beam
plate
Figure 1.7: Beam welded to a plate.
cutout
block
Figure 1.8: Block with cutout.
Applications of exhaustive enumeration methods include:
? Underwater environment representation.
? Finite elements meshing (?rst step in an algorithm to build such a mesh).
? Medical 3D data representation.
? Preprocessing representation for speeding up operations on other representations (eg.
approximating integral properties such as volume, center of gravity, moments of inertia,
distance transforms).
Properties of exhaustive enumeration methods include:
A
composite plate
B
C
Figure 1.9: Composite plate.
Figure 1.10: Finite element mesh.
center line
center line
cutting plane
solid volume
Figure 1.11: Representation of dimensions.
Figure 1.12: Exhaustive enumeration.
1 2
3
4
1
2 3
4
full
empty
partially full
Figure 1.13: Quadtree representation.
? Expressive power: approximation scheme.
? Unambiguous and unique for ?xed space and resolution. There do not exist di?erent
representations for the same object.
? Memory intensive: eg. 256
3
→ 16M bits and this is a bare minimum.
? Closure
1
of operations (eg. Booleans).
? Computational ease for algorithms: VLSI implementation for volume rendering. However,
for high resolution the algorithm slows down.
Boundary cell enumeration
This is a boundary based version of the above technique. Only the cells that intersect region
boundaries have true values.
Space subdivision
Some of the motivations behind space subdivision methods include:
? Smaller memory requirements if adaptive subdivision is used;
? Octree/quadtree representations lead to a recursive subdivision into 8 octants (or 4 quad-
rants) that can be represented as an 8-ary tree (or 4-ary tree).
In an octree representation a solid region is represented by hierarchically decomposing a
usually cubic volume of space into successively smaller cubes (8 of them). Hierarchical division
and cube orientation usually follows the spatial coordinate system. An example of quadtree,
the two dimensional analogue, is shown Figure 1.13.
1
Closure means that an operation such as Boolean results in an object of the same topological type that can
be represented by the same type of data structure.
This is a trivial example. The method can continue to many more levels for a much more
complex model. Some tolerance for minimum size blocks is required. In addition, this very
concise representation would become very large if the coordinate system was changed; for
example, rotated 45 degrees.
This method leads to a quick way to compute the area and other integral properties of a
region. It is often used in data analysis in ?elds such as medical applications and sonar imaging.
To create an octree, we apply a classi?cation procedure to a given solid (represented in
Boundary Representation, Constructive Solid Geometry, Exhaustive Enumeration, etc.) and
decide if a given node of the octree is:
? Exterior to solid (white);
? Interior to solid (black);
? Partially interior to solid (grey).
The classi?cation procedure is used recursively. It could be based on Boolean solid opera-
tions, especially intersection. Figure 1.14 provides an example of octree representation.
Figure 1.14: An octree model.
Some of the properties of octrees include:
? Expressive power: they are an approximation scheme;
? Validity: if no special connectivity is required, all octrees are valid;
? Unambiguous and unique: for a ?xed resolution there is only one compacted
2
octree;
? Memory: not as large as Exhaustive Enumerations, yet much larger than Boundary
Representation and Constructive Solid Geometry models;
? Closure of operations: for example Boolean operations and transformations;
? Computational ease: somewhat more complex than exhaustive enumeration.
Cell decompositions
The motivation for cell decomposition methods is:
? Use of elements other than cubes, see Figure 1.15 for an example.
? Application: ?nite element method, scienti?c visualization.
? Cells are parametrized instances of a generic cell type, eg. a cell bounded by quadratic
curves and surfaces.
? Cells are homeomorphic to spheres.
? Cells meet at a vertex, edge, face otherwise the representation is invalid.
? Cells are disjoint and non-overlapping.
? Cells may belong to di?erent cell types, eg. box-like, tetrahedra-like, etc.
Figure 1.15: A cell decomposition (?nite element mesh).
A cell decomposition can be represented using the cell-tuple data structure [3]. See Figure
1.16 for a 2D example.
The properties of cell decomposition methods are:
? Expressive power: very general and accurate;
2
Algorithms such as set operations can create octrees with unnecessary nodes (eg. an internal nodes whose
children are all black). Such nodes can be removed with a relatively simple tree traversal algorithm.
Figure 1.16: Cell data structure.
? Validity: requires an intersection test for veri?cation;
? Unambiguous representation;
? Nonunique: Similar to the Constructive Solid Geometry method we will see below, the
same object can be represented at di?erent resolutions or with di?erent types of mesh
(eg. hexahedral, tetrahedral, etc.);
? Generation: by conversion from other representations;
? Concise: memory utilization is less than octrees, yet more than Boundary Representation;
? Applicability: ?nite element meshing, multimaterial non-homogeneous objects, visualiza-
tion of ?elds, etc.
1.3.2 Constructive solid geometry (CSG)
Constructive Solid Geometry (CSG) is the Boolean combination of primitive volumes that
include the surface and the interior. For example, primitives including rectangular box, sphere,
cylinder, cone and torus can be combined using intersection, union and di?erence operators to
form complex solids. Positioning operators (position, orientation) and size operators are applied
to the primitives before the Boolean operators are invoked, see Figure 1.17 for an example.
Terminal nodes on the binary tree are primitive volumes; other nodes are Boolean operators.
This representation has a direct manufacturing analogue, where di?erence indicates drilling or
machining and union indicates for example welding.
Another example of a related representation is sweeps, where more general primitives are
obtained by sweeping a solid along a space curve or sweeping a planar curve through a revolution
(U)
(-)
P(sphere)
P(box)
P(cylinder)
Figure 1.17: Boolean operations and primitives.
about an axis in its plane. Sweeps are useful in the representation of blends, volumes swept by
machine tools, and in robotics.
In a survey of machine elements, 90 to 95% of parts could be represented accurately using
the CSG method with the above simple primitive solids.
1.3.3 Boundary representation (B-Rep)
Objects are represented in terms of their boundary elements (e.g. vertices, edges, faces) which
are related through adjacency.
?
This is the most generally used representation today due to its
?exibility. In these notes, we develop the theory of curves and surfaces which form the edges
and faces of B-Rep models.
Figures 1.18 and 1.19 show an example of a tetrahedron and its B-Rep model.
V1
f2
V4
V3
e1
e2
e3
e5
e6
e4
f4
f3
f2
V2
V4
V1
V2
e1
e3
e2
f3
f4
e4
e5e6
V3
Top View
f1
Figure 1.18: A tetrahedron
?
Two boundary elements, which are bounded by next lower dimension boundary elements, are called adjacent,
if they share one common next lower dimension boundary element. For instance, two surfaces having a common
edge are adjacent, or two edges having a common vertex are adjacent.
Object definition (region)
Boundary definition
Faces:
f1
f2
f3
f4
Loops:
Edges:
Vertices:
Topological Information
L1
L2
L3
L4
e1
e2
e3
e4
e5
e6
V1
V2
V3
V4
Vertex assignment
(x1,y1,z1) (x2,y2,z2)
(x3,y3,z3)
(x4,y4,z4)
(Geometry)
Figure 1.19: Boundary representation model for a tetrahedron
1.4 Alternate classi?cation of geometric modeling forms
1.4.1 Introduction
The wide variety of representation techniques developed (many of which were identi?ed above)
can be di?erentiated on the basis of at least three independent criteria concerning the repre-
sentation:
? boundary based or volume based
? object based or spatially based
? evaluated or unevaluated in form
A representation is boundary based if the solid volume is speci?ed by its surface boundary.
If the solid is speci?ed directly by its volume it is volume based.
A representation is object based if it is fundamentally organized according to the charac-
teristics of the actual geometric shape itself. It is spatially based when the representation is
organized around the characteristics of the spatial coordinate system it uses.
Evaluated or unevaluated characterization is roughly a measure of the amount of work
necessary to obtain information about the objects being represented with respect to a speci?c
goal.
What is best depends on the application! A good system should support multiple repre-
sentational techniques to ensure their e?ciency over a broad range of applications.
We have three di?erent criteria with two choices, so eight categories result. The following
Table 1.1 gives examples in each category:
Unevaluated Class
boundary based volume based
spatial based Half Space Octree
object based Euler Operators CSG
Evaluated Class
boundary based volume based
spatial based Boundary Cell Enumeration Cell Enumeration
object based Boundary Representation Non-parametric Primitives
Table 1.1: Classi?cation of geometric modeling forms
1.4.2 Unevaluated representation systems
Unevaluated representation systems require some form of procedural interpretation to be used
with respect to the speci?ed application.
Spatial, boundary based: half space technique A solid is represented by successively
dividing space in half with usually in?nite surface descriptions and selecting the half space on
a speci?ed side of the surface, eventually enclosing the solid region. The intersection of the half
spaces represents the solid. Only convex regions can thus be described unless unions are also
employed. Figure 1.20 demonstrates the half space technique in a two dimensional format.
Figure 1.20: Half space technique of model representation.
This technique is classi?ed as spatial based because the surface descriptions are positioned
in spatial coordinate space rather than being relative to the object.
Spatial, volume based: octree representation A solid region is represented by hierarchi-
cally decomposing a usually cubic volume of space into successively smaller cubes (8 of them).
Hierarchical division and cube orientation usually follows the spatial coordinate system.
Object, boundary based: Euler operators The object is procedurally described as a
sequence of “Euler Operators,” as in Figure 1.21. An (amorphous) topological sphere is topo-
logically modi?ed using the Euler Operators such as:
? msv = make shell, vertex
? mev = make edge, vertex
? mef = make edge, face
v1
v2
v3
v4
f1
e1
e2
e3
e4
f2
Figure 1.21: Boundary based representation Using Euler operations.
These operators ensure that Euler’s Formula is always satis?ed:
V ? E + F ? L
i
= 2(S ? G)
where:
? V = number of vertices
? E = number of edges
? F = number of faces
? L
i
= number of internal loops
? S = number of surfaces (shells)
? G = genus (number of handles or through holes)
Object, volume based: constructive solid geometry (CSG) Constructive Solid Geom-
etry (CSG) is the Boolean combination of primitive volumes that include the surface and the
interior. For example, a box, sphere, cylinder, torus and cone can be combined using intersec-
tion, union and di?erence operators to form many surfaces. In addition, positioning operators
such as position, orientation and size are applied to the primitives before the Boolean operators
are applied.
Another example of an object, volume based representation is sweeps, where more general
primitives are obtained by sweeping a solid along a space curve or sweeping a planar curve
through a revolution.
1.4.3 Evaluated representation systems
Evaluated representation systems usually require substantially less computation to be useful in
speci?c applications.
Spatial, volume based: cell enumeration An object is represented by a three dimensional
Boolean array. Each cell represents a cubic volume of space. If a cell intersects with the region
of interest it has a true value. Otherwise, the value is false. This can be pictured as a box
divided into pixels, with 0 assigned if empty and 1 assigned if full.
Spatial, boundary based: boundary cell enumeration This is a boundary based version
of the above technique. Only the cells which intersect region boundaries have true values.
Object, Boundary Based: Boundary Representation (b-rep) Objects are represented
in terms of their boundary elements (e.g. vertices, edges, faces) which are related through
incidence and adjacency. This is the most generally used representation today, and will be
discussed in detail in further lectures.
Object, volume based: non-parametric primitives Simple ?xed position objects. This
is not a particularly ?exible representation.
Bibliography
[1] L. Bardis and N. M. Patrikalakis. Topological structures for generalized boundary repre-
sentations. MITSG 94-22, MIT Sea Grant College Program, Cambridge, Massachusetts,
September 1994.
[2] B. G. Baumgart. Winged edge polyhedron representation. Technical Report STAN-CS-
320, Computer Science Department, Stanford University, 1972.
[3] E. Brisson. Representing geometric structures in d dimensions: Topology and order.
Discrete and Computational Geometry, 9:387–426, 1993.
[4] J. P. Comstock, editor. Principles of Naval Architecture. The Society of Naval Architects
and Marine Engineers, New York, 1967.
[5] E. L. G¨ oz and F. B. Prinz. Node-based representation of non-manifold surface bound-urs¨
aries in geometric modeling. In M. Wozny, J. Turner, and K. Preiss, editors, Geometric
Modeling for Product Engineering. North-Holland, 1989.
[6] C. M. Ho?mann. Geometric and Solid Modeling: An Introduction. Morgan Kaufmann
Publishers, Inc., San Mateo, California, 1989.
antyl¨[7] M. M¨ a. An Introduction to Solid Modeling. Computer Science Press, Rockville,
Maryland, 1988.
[8] M. E. Mortenson. Geometric Modeling. John Wiley and Sons, New York, 1985.
[9] J. Rossignac and M. O’Connor. SGC: A dimension-independent model for pointsets with
internal structures and incomplete boundaries. In M. Wosny, J. Turner, and K. Preiss,
editors, Geometric Modeling for Product Engineering, pages 145–180. North-Holland, 1989.
[10] K. Weiler. Edge-based data structures for solid modeling in curved surface environments.
IEEE Computer Graphics and Applications, 5(1):21–40, January 1985.