i
i
i
i
i
i
i
i
546 12. Polygonal Techniques
number of reasons. They can highlight an area of the model made of a
set of polygons or can help in creating a nonphotorealistic rendering. Be-
cause they provide important visual cues, such edges are often favored to
avoid being simplified by progressive mesh algorithms (see Section 12.5).
Figure 12.10 shows surfaces with crease edges displayed.
Reasonable crease edges and vertex normals can usually be derived
with some success from an oriented mesh. Once the orientation is consis-
tent and the adjacency graph is derived, vertex normals can be generated
by smoothing techniques. Smoothing information is something that the
model’s format may provide by specifying smoothing groups for the poly-
gons, or by providing a crease angle. Smoothing group values are used
to explicitly define which polygons in a group belong together to make
up a curved surface. A crease angle is used when there is no smoothing
group information. In this case, if two polygons’ dihedral angle is found to
be within the specified angle, then these two polygons are made to share
vertex normals along their common edge. If the dihedral angle between
the polygons is greater than the crease angle, then the edge between the
polygons is made a crease edge. This technique is sometimes called edge
preservation.
Once a smoothing group is found, vertex normals can be computed.
The standard textbook solution for finding the vertex normal is to average
the surface normals of the polygons sharing the vertex [406, 407]. However,
this method can lead to inconsistent and poorly weighted results. Th¨urmer
and W¨uthrich [1266] present an alternate method, in which each polygon
normal’s contribution is weighted by the angle it forms at the vertex. This
method has the desirable property of giving the same result whether a
polygon sharing a vertex is triangulated or not. If the tessellated polygon
turned into, say, two triangles sharing the vertex, the equal weight method
would then give twice the weight to the two triangles as it would to the
original polygon. See Figure 12.11.
Max [828] gives a different weighting method, based on the assumption
that long edges form polygons that should affect the normal less. This
type of smoothing may be superior when using simplification techniques,
as larger polygons formed will be less likely to follow the surface’s curvature.
The algorithm is
n =
n−1
i=0
e
i
× e
i+1
||e
i
||
2
||e
i+1
||
2
(12.1)
for n counterclockwise-oriented polygons sharing a vertex. The e
i
vectors
are formed by the edges from the center vertex location v, e.g., e
2
is equal
to v
2
−v. Modulo arithmetic is used for the edge vertices, i.e., if i+1 equals
n, use 0. The numerator computes the normal for each pair of edges, and
i
i
i
i
i
i
i
i
12.4. Triangle Fans, Strips, and Meshes 547
Figure 12.11. On the left, the surface normals of a rectangle and two triangles are
averaged to give a vertex normal. In the middle, the square has been triangulated. This
results in the average normal shifting, since each polygon’s normal is weighted equally.
On the right, Th¨urmer and W¨uthrich’s method weights each normal’s contribution by
its angle between the pair of edges forming it, so triangulation does not shift the normal.
the squared length terms in the denominator make this normal’s effect less
for larger polygons. The resulting normal n is then normalized.
For heightfields, Shankel [1155] shows how taking the difference in
heights of the neighbors along each axis can be used to rapidly approximate
smoothing using the angle-weighted method. For a given point p and four
neighboring points, p
X−1
and p
X+1
on the X-axis of the heightfield, p
Y −1
and p
Y +1
on the Y , a close approximation of the (unnormalized) normal
at p is
n
x
= p
X+1
x
− p
X−1
x
,
n
y
= p
Y +1
y
− p
Y −1
y
,
n
z
=2.
(12.2)
Using a smoothing angle can sometimes give an improper amount of
smoothing, rounding edges that should be creased, or vice versa. However,
even smoothing groups can have their own problems. Imagine the curved
surface of a cone made of polygons. All the polygons are in the same
smoothing group. But at the tip of the cone, there should actually be
many normals at a single vertex. Simply smoothing gives the peculiar
result that the tip has one normal pointing directly out along the cone’s
axis. The cone tip is a singularity; either the faceter has to provide the
vertex normals, or the modeler sometimes cuts off the very tip, thereby
providing separate vertices to receive these normals properly.
12.4 Triangle Fans, Strips , and Meshes
A standard way to increase graphics performance is to send groups of tri-
angles that share vertices to the graphics pipeline. The benefits of this are
i
i
i
i
i
i
i
i
548 12. Polygonal Techniques
quite obvious: fewer points and normals need to be transformed, fewer line
clips need to be performed, less lighting needs to be computed, etc. How-
ever, if the bottleneck of an application is the fill rate (i.e., the number of
pixels that can be filled per second), little or no performance gain is to be
expected from such savings. A variety of methods that share data, namely
triangle fans, strips, and meshes, are described in this section.
12.4.1 Fans
Figure 12.12 shows a triangle fan. This type of data structure shows how we
can form triangles and have each use an average of less than three vertices.
The vertex shared by all triangles is called the center vertex and is
vertex 0 in the figure. For the starting triangle 0, send vertices 0, 1, and
2 (in that order). For subsequent triangles, the center vertex (number
0) is always used together with the previously sent vertex and the vertex
currently being sent. Triangle 1 is formed merely by sending vertex 3,
thereby creating a triangle defined by vertices 0 (always included), 2 (the
previously sent vertex), and 3. Further on, triangle 2 is constructed by
sending vertex 4. Subsequent triangles are formed in the same manner.
A triangle fan of n vertices is defined as an ordered vertex list
{v
0
, v
1
,...,v
n−1
} (12.3)
(where v
0
is the center vertex), with a structure imposed upon the list
indicating that triangle i is
v
0
v
i+1
v
i+2
,
(12.4)
where 0 ≤ i<n− 2.
Figure 12.12. The left figure illustrates the concept of a triangle fan. Triangle T
0
sends
vertices v
0
(the center vertex), v
1
,andv
2
. The subsequent triangles, T
i
(i>0), send
only vertex v
i+2
. The right figure shows a convex polygon, which can always be turned
into one triangle fan.
i
i
i
i
i
i
i
i
12.4. Triangle Fans, Strips, and Meshes 549
If a triangle fan consists of m triangles, then three vertices are sent for
the first one, followed by one more for each of the remaining m−1 triangles.
This means that the average number of vertices, v
a
, sent for a sequential
triangle strip of length m, can be expressed as
v
a
=
3+(m − 1)
m
=1+
2
m
. (12.5)
As can easily be seen, v
a
→ 1asm →∞. This might not seem to have
much relevance for real-world cases, but consider a more reasonable value.
If m =5,thenv
a
=1.4, which means that, on average, only 1.4 vertices
are sent per triangle.
Fans are a basic primitive in a number of terrain rendering algorithms
[1074, 1132]. A general convex polygon
2
is trivial to represent as a triangle
fan. Any triangle fan can be converted into a triangle strip, but not vice
versa.
12.4.2 Strips
Triangle strips are like triangle fans, in that vertices in previous triangles
are reused. Instead of a single center point and previous vertex getting
reused, it is the vertices of the previous triangle that help form the next
triangle. Consider Figure 12.13, in which connected triangles are shown. If
these are treated as a triangle strip, then a more compact way of sending
them to the rendering pipeline is possible. For the first triangle (denoted
T
0
), all three vertices (denoted v
0
, v
1
,andv
2
) are sent in that order.
Figure 12.13. A sequence of triangles that can be represented as one triangle strip. Note
that the orientation changes from triangle to triangle in the strip, and that the first
triangle in the strip sets the orientation of all triangles. Internally, counterclockwise
order is kept consistent by traversing vertices 0-1-2, 1-3-2, 2-3-4, 3-5-4, and so on.
2
Convexity testing is discussed, and code is given, by Schorn and Fisher [1133].
i
i
i
i
i
i
i
i
550 12. Polygonal Techniques
For subsequent triangles in this strip, only one vertex has to be sent, since
the other two have already been sent with the previous triangle. For exam-
ple, sending triangle T
0
,onlyvertexv
3
is sent, and the vertices v
1
and v
2
from triangle T
0
are used to form triangle T
1
. For triangle T
2
,onlyvertex
v
4
is sent, and so on through the rest of the strip.
A sequential triangle strip of n vertices is defined as an ordered ver-
tex list
{v
0
, v
1
,...,v
n−1
}, (12.6)
with a structure imposed upon it indicating that triangle i is
v
i
v
i+1
v
i+2
,
(12.7)
where 0 ≤ i<n− 2. This sort of strip is called sequential because the
vertices are sent in the above mentioned sequence. The definition implies
that a sequential triangle strip of n vertices has n − 2 triangles; we call it
a triangle strip of length n −2.
The analysis of the average number of vertices for a triangle strip of
length m (i.e., consisting of m triangles), also denoted v
a
,isthesameas
for triangle fans (see Equation 12.5), since they have the same start-up
phase and then send only one vertex per new triangle. Similarly, when
m →∞, v
a
for triangle strips naturally also tends toward one vertex per
triangle. For m = 20, v
a
=1.1,whichismuchbetterthan3andiscloseto
the limit of 1.0. As with triangle fans, the start-up cost for the first triangle
(always costing three vertices) is amortized over the subsequent triangles.
The attractiveness of triangle strips stems from this fact. Depending
on where the bottleneck is located in the rendering pipeline, there is a
potential for saving two-thirds of the time spent rendering without sequen-
tial triangle strips. The speedup is due to avoiding redundant operations,
i.e., sending each vertex twice to the graphics hardware, then performing
matrix transformations, lighting calculations, clipping, etc. on each.
By not imposing a strict sequence on the triangles, as was done for the
sequential triangle strips, one can create longer, and thus more efficient,
strips. These are called generalized triangle strips [242]. To be able to use
such strips, there must be some kind of vertex cache on the graphics card
that holds transformed and lit vertices. This is called the post-transform
cache.
3
The vertices in this cache can be accessed and replaced by sending
short bit codes. As will be seen in the next section, this idea has been
generalized to allow the efficient processing of triangle meshes.
A way to generalize sequential triangle strips a bit is to introduce a swap
operation, which swaps the order of the two latest vertices. In Iris GL [588],
3
Vertex caches are also occasionally called vertex buffers in the literature. We avoid
this term here, as vertex buffer is used in DirectX to mean a primitive consisting of a
set of vertices.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.