Graphics Reference
In-Depth Information
holes must be filled in. For an arbitrary mesh, no such a priori knowledge is available,
and cracks must be distinguished from intentional holes.
There are many possible approaches to attempting to clean up arbitrary meshes.
In this chapter, some of the key steps relevant to most approaches are described,
specifically:
1. Welding of vertices
2. Fixing of cracks between neighboring faces
3. Merging co-planar faces into a single face
4. Decomposition into convex (possibly triangular) pieces
Figure 12.1 illustrates how these steps can be used to clean up a polygon soup
model. In addition, this chapter describes methods for computing and holding adja-
cency information. This chapter ends with a discussion of some simple means of
quickly detecting bad input geometry.
Cleaning up arbitrary input geometry can be quite difficult overall. An interesting
account of the practical issues of mesh cleanup is found in [Erikson95].
12.1 Vertex Welding
Frequently, collision geometry suffers from being built from polygons whose vertices
should have been joined but were not. These duplicate representations of a single
vertex cause cracks between polygons. Although often invisible to the eye, these
cracks still cause problems for collision detection systems. For example, they may
cause collision queries, such as ray tests, to pass through what was supposed to be
solid geometry. Additionally, duplicate vertices ruin the possibility of maintaining
adjacency information between neighboring faces. Duplicate vertices also take up
unnecessary space. For example, a triangle mesh with duplicate vertices may require
nearly three times as much memory for storing the vertices as the same mesh without
duplicate vertices.
Fixing the problem involves finding all pairs or sets of vertices “near” each other
and joining them into a single vertex, a process known as vertex welding (also as vertex
shifting or vertex merging ). Vertices are considered near when they are within some
preset distance of each other, called the welding tolerance or the welding epsilon . The
space within the welding tolerance of a vertex is the welding neighborhood of the vertex.
Setting an appropriate welding distance is important. If the welding tolerance is
too small, not all vertices that should be welded will be welded. If the distance is
too large, vertices that should not be part of a welding operation may erroneously be
included, causing collapsing of edges or faces of the geometry. Figure 12.2 illustrates
both of these problems. User input is often required to set the welding distance, in
that automatically determining it is a difficult problem.
Search WWH ::




Custom Search