Graphics Reference
In-Depth Information
Figure 5.14.
Cutting and pasting.
and pasting example. Specifically, we show how to cut the torus to get a rectangle and
how, looking at it backward, we can get the torus from the rectangle by pasting appro-
priate edges together.
Elementary collapses or expansions do not change the Euler characteristic of a
space. On the other hand, cutting and pasting operations usually do change the Euler
characteristic. It turns out that these four operations do an excellent job to completely
describe and define surfaces. (In higher dimensions things get more complicated.)
Every surface, and hence solid in 3-space, can be obtained from a point by a sequence
of elementary expansions, cuts, and pastes. Modelers based on Euler operations use
a boundary representation for solids and simply define procedures that mimic the col-
lapses, expansions, cutting, and pasting operations just described by modifying the
cell structure of this boundary representation in a well-defined way.
Definition.
The
Euler operation representation
of polyhedra is defined by the collec-
tion of pairs (
X
,(s
1
,s
2
,..., s
k
)), where
X
is a polyhedra and s
1
,s
2
,..., s
k
is a sequence
of Euler operations that produces ∂
X
starting with the empty set.
Euler operations were first introduced by Baumgart in his thesis and then used
in his computer vision program GEOMED ([Baum75]). Braid, Hillyard, and Stroud
([BrHS80]) showed that only five operators are needed to describe the boundary sur-
faces of three-dimensional solids. Such a surface satisfies the Euler equation
(
)
VEF
-+=
2
SH
-
,
where
V = the number of vertices,
E = the number of edges,
F = the number of faces,
S = the number of solid components, and
H = the number of holes in the solid.
They used a set of these Euler operations in their BUILD modeling system. Although
one can make other choices for the five primitive operators, it seems that the bound-
ary representation part of modelers built on Euler operations tend to use either
