Graphics Reference
In-Depth Information
-
C
B
=
A
B
C
A
Figure 12.27
A hemispherical bowl modeled as a CSG object in terms of the intersection
between the AABB
A
and the difference between the spheres
B
and
C
.
predicate is, of course, just a normal intersection test, as discussed in detail in
Chapter 5.
PartiallyOutside()
is a new type of collision predicate not discussed
earlier. However, its implementation is generally straightforward. For example, for
the particular test needed here a sufficient condition for a line segment, triangle,
polygon, or polyhedron to test as partially outside a sphere is if one or more vertices
of the tested object lie outside the sphere.
12.6
Consistency Testing Using Euler's Formula
Badly formed geometry can also be detected through tests of the topology of the
geometry. First, to set the stage two solid bodies are deemed topologically equivalent,
or
homeomorphic
, to each other if their surface boundaries can be deformed into each
other without cutting or gluing in trying to match them up. Polyhedra homeomorphic
to a sphere are called
simple polyhedra
. A tetrahedron and a cube are both examples
of simple polyhedra, as are all convex polyhedra.
The mathematical relationship between the number of vertices (
V
), faces (
F
), and
edges (
E
) of a simple polyhedron is succinctly stated in
Euler's formula
:
V
+
F
−
E
=
2.
For example, the polyhedron in Figure 12.28a satisfies the formula because
V
=
9,
F
2.
When a polyhedron has one or more holes in it, it is no longer simple but belongs
to the class of
nonsimple polyhedra
. The number of holes is referred to as the
genus
of
the polyhedron. Any polyhedron of zero genus (no holes) is topologically equivalent
to a sphere, of genus one to a torus, of genus two to a solid figure eight, and so on.
Another way of looking at it is that all polyhedra are topologically equivalent to a
=
9, and
E
=
16 give
V
+
F
−
E
=
9
+
9
−
16
=
