Graphics Reference
In-Depth Information
(a)
(b)
Figure 12.29
The number of edges in a closed manifold mesh consisting of triangles and
quads only is
E
= (3
T
+ 4
Q
)/2. For the cube on the left, consisting of two triangles and six
quads, this gives 15 edges. The cube on the right consists of three triangles and five quads,
for which the formula gives 14.5 edges. Because this is not an integral number, the cube on
the right cannot be correctly formed (and indeed, there is a t-junction on the top face).
The number of triangles in a closed manifold mesh consisting of triangles and quads
must also be even, in that
T
=
2
V
−
2
Q
−
4 is always an even number as well.
12.7
Summary
It is important for collision detection systems to be given well-formed geometry as
their input. If they are not, the presence of duplicated vertices, nonplanar polygons,
t-junctions, and similar sources of robustness problems can easily cause severe failures
such as objects falling through seemingly solid geometry.
This chapter presented solutions enabling taking an unstructured collection of
polygons — a polygon soup — as input, and turning it into a well-formed mesh.
The tools required for this cleanup process are generic and applicable to many other
situations.
Discussed was how to weld duplicate vertices. The chapter also described how
to compute adjacency information for vertices, edges, and faces, allowing the repair
of cracks and t-junctions between neighboring faces. It discussed how to merge co-
planar faces into a single face, and how to test for planarity and co-planarity in the
first place. Because most collision systems work best with convex inputs methods
for decomposing concave objects and faces into convex (or triangular) pieces were
discussed. Suggestions were also given for how to deal with “nondecomposable”
concave objects, such as the inside of a bowl, which is concave everywhere. Last,
Euler's formula was presented as an inexpensive way to test the validity of closed
meshes.
