i
i
i
i
i
i
i
i
12.3. Consolidation 541
The process of fixing these cracks is called edge stitching. The goal is
to make sure that all vertices along the shared edge are shared by both
spline surfaces, so that no cracks appear. See Figure 12.7. Section 13.6.4
discusses using adaptive tessellation to avoid cracking for spline surfaces.
A related problem encountered when joining flat surfaces is that of T-
vertices. This sort of problem can appear whenever two models’ edges
meet, but do not share all vertices along them. Even though the edges
should theoretically meet perfectly, if the renderer does not have enough
precision in representing vertex locations on the screen, cracks can appear.
Modern graphics hardware uses subpixel addressing [736], which mostly
solves the problem, though gaps can still occur. More obvious are the
shading artifacts that can appear [73]. Figure 12.8 shows the problem,
which can be fixed by finding such edges and making sure to share common
vertices with bordering faces. Lengyel [760] discusses how to find such
vertices and provides code to properly retriangulate convex polygons. For
example, in the figure, if the quadrilateral abcd had been triangulated
into triangles abc and acd, the T-vertex problem would not be solved.
Cignoni et al. [178] describe a method to avoid creating degenerate (zero-
area) triangles when the T-vertices’ locations are known. Their algorithm
is O(n) and is guaranteed to produce at most one triangle strip and fan.
12.3 Consolidation
Once a model has passed through any tessellation algorithms needed, we
are left with a set of polygons to render. There are a few operations that
may be useful for displaying this data. The simplest is checking whether
the polygon itself is properly formed, that it does not have identical vertices
next to each other in its vertex list, and that it has at least three unique
vertices. A more elaborate operation is merging, which finds shared vertices
among faces. Another common operation is called orientation,whereall
polygons forming a surface are made to face the same direction. Once
orientation is performed, checking whether a mesh forms a solid surface is
important for its use by a number of different algorithms. Feature edge
detection can be done to enhance data by finding graphically significant
edges. Related to this operation is vertex normal generation, where surfaces
are made to look smooth. We call these types of techniques consolidation
algorithms.
12.3.1 Merging
Some data comes in the form of disconnected polygons, often termed a
polygon soup. Storing separate polygons wastes memory, and displaying
i
i
i
i
i
i
i
i
542 12. Polygonal Techniques
separate polygons is extremely inefficient. For these reasons separate poly-
gons are usually merged into a polygon mesh. At its simplest, a polygon
mesh consists of a list of vertices and a set of outlines. Each vertex con-
tains a position and other additional data, such as diffuse and specular
colors, shading normal, texture coordinates, etc. Each polygon outline has
a list of integer indices. Each index is a number from 0 to n − 1, where
n is the number of vertices and so points to a vertex in the list. In this
way, each vertex can be stored just once and shared by any number of
polygons. A triangle mesh is simply a polygon mesh that contains only
triangles.
Given a set of disconnected polygons, merging can be done in any num-
ber of ways. One simple method is to use hashing. Initialize the current
vertex index to zero. For each polygon, attempt to add each of its vertices
in turn to a hash table. If a vertex is not already in the table, store it
there, along with the current vertex index, which is then incremented; also
store the vertex in the final vertex list. If instead the vertex is found in
the hash table, retrieve its stored index. Save the polygon with the indices
used to point to the vertices. Once all polygons are processed, the vertex
and index lists are complete.
Model data sometimes comes in with separate polygons’ vertices being
extremely close, but not identical. The process of merging such vertices
is called welding. See Glassner’s article [407] for one method of welding
vertices.
There are more elaborate polygon mesh data structures possible. For
example, a cube has 8 vertex positions and 6 face normals. If each necessary
vertex position/normal is stored separately, 24 separate vertices are needed
(4 per face). An alternate way to store this data is to keep two separate
lists, one of positions, one of normals. Then each polygon outline stores
two indices per vertex, selecting the position and normal. Hoppe [562]
discusses memory-efficient ways to share vertex-face information while re-
taining surface-surface connectivity.
12.3.2 Orientation
One quality-related problem with model data is face orientation. Some
model data comes in oriented properly, with surface normals either explic-
itly or implicitly pointing in the correct directions. For example, in CAD
work, the standard is that the vertices in the polygon outline proceed in
a counterclockwise direction when the frontface is viewed. This is called a
right-handed orientation (which is independent of the left-handed or right-
handed viewing or modeling orientation used): Think of the fingers of your
right hand wrapping around the polygon’s vertices in counterclockwise or-
der. Your thumb then points in the direction of the polygon’s normal.
i
i
i
i
i
i
i
i
12.3. Consolidation 543
There are a number of conditions necessary to ensure that a surface
can be successfully oriented. Each polygon edge should be shared by at
most two polygons in the mesh. For example, if two cubes touched along
an edge and were a part of the same mesh, that edge would be shared by
four polygons. This makes simple orientation computation more difficult.
Also, one-sided objects such as M¨obius strips will of course not be able to
be oriented.
Given a reasonable model, here is one approach to orient a polygonal
mesh:
1. Form edge-face structures for all polygons.
2. Sort or hash the edges to find which edges match.
3. Find groups of polygons that touch each other.
4. For each group, flip faces to obtain consistency.
The first step is to create a set of half-edge objects. A half-edge is an
edge of a polygon, with a pointer to its associated face (polygon). Since
an edge is normally shared by two polygons, this data structure is called
a half-edge. Create each half-edge with its first vertex stored before the
second vertex, using sorting order. One vertex comes before another in
sorting order if its x-coordinate value is smaller. If the x-coordinates are
equal, then the y-value is used; if these match, then z is used. For example,
vertex (−3, 5, 2) comes before vertex (−3, 6, −8); the −3s match, but 5 < 6.
The goal is to find which edges are identical. Since each edge is stored
such that the first vertex is less than the second, comparing edges is sim-
ply a matter of comparing first to first and second to second vertices; no
permutations such as comparing one edge’s first vertex to another’s second
vertex are needed. A hash table can be used to find matching edges [8, 407].
If all vertices have previously been merged, so that half-edges use the same
vertex indices, then each half-edge can be matched by putting it on a tem-
porary list associated with its first vertex index. A vertex has an average
of 6 edges attached to it, making edge matching extremely rapid [1063].
Once the edges are matched, connections among neighboring polygons
are known, forming an adjacency graph. For a triangle mesh, an adjacency
graph can be represented as a list of (up to) three triangle indices associ-
ated with each triangle, its neighbors. Boundary edges can be determined
from adjacency: Any edge that does not have two neighboring polygons
is a boundary edge. The set of polygons that touch each other forms a
continuous group. A single data set can have more than one continuous
group. For example, a teapot can have two groups, the pot and the lid.
The next step is to give the mesh orientation consistency, e.g., we may
want all polygons to have counterclockwise outlines. For each continuous
i
i
i
i
i
i
i
i
544 12. Polygonal Techniques
Figure 12.9. A starting polygon S is chosen and its neighbors are checked. Because the
vertices in the edge shared by S and B are traversed in the same order (from x to y),
theoutlineforB needs to be reversed.
group of polygons, choose an arbitrary starting polygon. Check each of its
neighboring polygons and determine whether the orientation is consistent.
Orientation checking is simple: If the direction of traversal for the edge is
the same for both polygons, then the neighboring polygon must be flipped.
See Figure 12.9. Recursively check the neighbors of these neighbors, until
all polygons in a continuous group are tested once.
Although all the faces are properly oriented at this point, they could
all be oriented inward. In most cases we want them facing outward. The
test for whether all faces should be flipped is to take the signed volume
of the group and check the sign; if it is negative, reverse all the loops and
normals.
The way to get the signed volume is as follows. First, get the center
point of the group’s bounding box. Then compute the signed volume of
each volume formed by joining the center point to each polygon (e.g., for
a triangle and a point, a tetrahedron is formed). The volume is equal to
one-third the distance of the center point from the polygon’s plane, times
the polygon’s area. The 1/3 term can be dropped, since we need only the
sign of the summed volume. The calculation of the area of a triangle is
given in Appendix A.
This method is not foolproof. If the object is not solid, but simply a
surface description, it is certainly possible for the orientation still to be
incorrect. Human intervention is needed in such cases. Even solids can be
oriented incorrectly in special cases. For example, if the object is a room,
the user wants its normals to face inward toward the camera.
12.3.3 Solidity
Informally, a mesh forms a solid if it is oriented and all the polygons visible
from the outside have the same orientation. In other words, only one
i
i
i
i
i
i
i
i
12.3. Consolidation 545
side of the mesh is visible. Such polygonal meshes are called closed or
watertight.
Knowing an object is solid means backface culling can be used to im-
prove display efficiency, as discussed in Section 14.2. Solidity is also a
critical property for objects casting shadow volumes (Section 9.1.3) and for
a number of other algorithms. Stereolithography is the process of taking
a computer-generated model and creating a physical prototype, and there,
models without solidity are unusable.
The simplest test for solidity is to check if every polygon edge in the
mesh is shared by exactly two polygons. This test is sufficient for most data
sets. Such a surface is loosely referred to as being manifold, specifically, two-
manifold. Technically, a manifold surface is one without any topological
inconsistencies, such as having three or more polygons sharing an edge or
two or more corners touching each other. A continuous surface forming a
solid is a manifold without boundaries.
12.3.4 Normal Smoothing and Crease Edges
Some polygon meshes form curved surfaces, but the polygon vertices do
not have normal vectors, so they cannot be rendered with the illusion of
curvature. See Figure 12.10.
Many model formats do not provide surface edge information. See Sec-
tion 11.2 for the various types of edges. These edges are important for a
Figure 12.10. The object on the left does not have normals per vertex; the one on the
right does.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.