Graphics Reference
In-Depth Information
and algorithms. Their data structure allows for nonmanifold objects and specifies the
following information about vertices, edges, and faces:
vertex:
the adjacent edges and faces
edge:
the bounding vertices and adjacent faces with the faces listed in a con-
tiguous cyclical order with respect to their intersection with a plane
orthogonal to the edge
face:
the bounding edges and vertices as circular lists with the face to the right
Normal planes to edges and planes associated to planes are assumed to be oriented
appropriately. To achieve irredundancy of information, planes are defined via equa-
tions that are oriented so that the associated normals point out of the associated solid.
Vertices are defined as the intersection of the planes to which their adjacent faces
belong. Edges are oriented and defined by their bounding vertices. The entire geom-
etry is defined by a unique set of plane equations.
Since all Boolean set operations can be defined by the intersection and comple-
ment operation, the interesting operation is intersection. We consider the simplest,
but most important, case of finding the intersection of two solids
X
and
Y
with con-
nected boundaries. The initial overall strategy is
(1) If no pair of faces from
X
and
Y
intersect, check if one solid is contained in
the other and quit.
(2) Intersect the boundaries of
X
and
Y
. For each face
f
of
X
that intersects
Y
find the cross-section of
Y
with respect to the plane of
f
. Determine the part
of
X
«*
Y
contained in that cross-section. These regions will be defined by
points and line segments lying in the boundary of
X
.
(3) The cells obtained in Step (2) will also lie in faces of
Y
. We use these cells to
determine the subdivision of those faces of
Y
. Then using face adjacency infor-
mation for
Y
, we find and add all the faces of
Y
lying in the interior of
X
.
(4) Assemble all the intersection faces into the solid
X
«
* Y
.
The problem with Step (2) is that intersections are computed in isolation that can
lead to the inconsistencies mentioned above, therefore, Step (2) and (3) are replaced
by
(2¢) For each intersecting pair of faces
f
and
g
from
X
and
Y
, respectively, deter-
mine the points and segments in which they intersect. Using three-
dimensional neighborhood information for each intersection, the relevant
parts are then transferred to all adjacent faces of
X
and
Y
.
(3¢) Finally, those faces of either solid that are contained in the other are found
using face adjacency information for the solids.
Bounding boxes are used for faces to speed up the algorithm and avoid unneces-
sary checks for face/face intersections along with efficient algorithms for determining
whether intervals intersect. The most work takes place in Step (2). It is here that one
makes sure that each element of the intersection is computed in a consistent way with
respect to all adjacent cells. For intersecting faces one has to
