i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 635
Figure 13.59. To the left, a crack is visible between the two regions. This is because
the right has a higher tessellation rate than the left. The problem lies in that the right
region has evaluated the surface where there is a black circle, and the left region has
not. The standard solution is shown to the right.
algorithms that adapt the tessellation rate depending on some measure (for
example curvature, triangle edge length, or some screen size measure). Care
must be taken to avoid cracks that can appear between different tessellated
regions. See Figure 13.59. In this section, we will first describe a three-pass
algorithm for computing adaptive tessellation using tessellation hardware,
fractional rates, and evaluation shaders. Furthermore, we present some
general techniques that can be used to compute fractional tessellation rates
or decide when to terminate further tessellation.
A Three-Pass Technique for Adaptive Tessellation
Tatarchuk [1252] describes a technique for computing the fractional tes-
sellation factors, and how to instruct the hardware to render tessellated
surfaces using these factors.
In the first pass, the vertices of the original mesh are first displaced
(if such a technique is used). Then, these are transformed into camera
space, rendered out as points into a two-dimensional texture. Here, it is
assumed that each vertex has a unique vertex ID, and the position of the
vertex in the texture is computed from this ID. It is important that each
base triangle here outputs all three vertices, i.e., you cannot use indexed
primitives. The reasons for this will be clear later on. Note that the result
of this pass is only a two-dimensional texture containing the vertices in
camera space.
The second pass computes the fractional tessellation factors, and out-
puts them to a two-dimensional texture as well. This pass sends all the
vertices of the original mesh through the pipeline, and we use the vertex ID
to access the transformed vertex in the texture from the first pass. Now,
assume that each vertex shall compute a fractional tessellation factor as
well. The vertices of a triangle, Δv
0
v
1
v
2
, will be fed to the vertex shader
in order. For the first vertex, v
0
, we want to compute a tessellation factor,
f
0
, based on v
0
and v
1
. Similarly, f
1
should be based on v
1
and v
2
,andf
2
should be derived from v
2
and v
0
. Since we are using non-indexed prim-
i
i
i
i
i
i
i
i
636 13. Curves and Curved Surfaces
itives, we can easily find the transformed edge vertices from the texture
from the first pass by using the vertex ID. When this is done, we compute
a fractional tessellation factor, f
i
, and write it out to a two-dimensional
texture as well. Techniques for this are described in the next subsection,
called Terminating Adaptive Tessellation. Note that since a tessellation
factor is computed based solely on the edge’s two vertices, and because
fractional tessellation is symmetric, there cannot be any cracks with this
technique. The entire system has been designed to avoid such issues. How-
ever, the developer has to take care that edges always are treated with the
same vertex order, because floating-point imprecision may create cracks if
the same order is not preserved.
In the final pass, we use the two textures from the first and second
passes as input data to the tessellation hardware, which automatically uses
on each edge the correct fractional tessellation factor, computed in the
previous pass. After tessellation, the vertex shader program evaluates the
curved surface, possibly with displacement as well, and then the triangles
are rendered. An example of the results is shown in Figure 13.57.
Terminating Adaptive Tessellation
To provide adaptive tessellation, we need to determine when to stop the
tessellation, or equivalently how to compute fractional tessellation factors.
Either you can use only the information of an edge to determine if tessel-
lation should be terminated, or use information from an entire triangle, or
a combination.
It should also be noted that with adaptive tessellation, one can get
swimming or popping artifacts from frame to frame if the tessellation fac-
tors for a certain edge change too much from one frame to the next. This
may be a factor to take into consideration when computing tessellation
factors as well.
Givenanedge,(a, b), with an associated curve, we can try to estimate
how flat the curve is between a and b. See Figure 13.60. The midpoint, m,
in parametric space between a and b, is found, and its three-dimensional
counterpart, c, is computed. Finally, the length, l, between c and its
projection, d, onto the line between a and b, is computed. This length,
Figure 13.60. The points a and b have already been generated on this surface. The
question is: Should a new point, that is c, be generated on the surface?
i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 637
l, is used to determine whether the curve segment on that edge if flat
enough. If l is small enough, it is considered flat. Note that this method
may falsely consider an S-shaped curve segment to be flat. A solution to
this is to randomly perturb the parametric sample point [343] or even to
use multiple randomly perturbed sample points [1300]. An alternative to
using just l is to use the ratio l/||a − b|| [294]. Note that this technique
can be extended to consider a triangle as well: Just compute the surface
point in the middle of the triangle and use the distance from that point to
the triangle’s plane. To be certain that this type of algorithm terminates,
it is common to set some upper limit on how many subdivisions can be
made. When that limit is reached, the subdivision ends. For fractional
tessellation, the vector from c to d can be projected onto the screen, and
its (scaled) length used as a tessellation rate.
So far we have discussed how to determine the tessellation rate from
only the shape of the surface. Other factors that typically are used for
on-the-fly tessellation include whether the local neighborhood of a vertex
is [561, 1392]:
1. Inside the view frustum,
2. Frontfacing,
3. Occupying a large area in screen space,
4. Close to the silhouette of the object, and
5. Illuminated by a significant amount of specular lighting.
These factors will be discussed in turn here. For view frustum culling,
one can place a sphere to enclose the edge. This sphere is then tested
against the view frustum. If it is outside, we do not subdivide that edge
further.
For face culling, the normals at a, b, and possibly c can be computed
from the surface description. These normals, together with a, b,andc,
define three planes. If all are backfacing, it is likely that no further subdi-
vision is needed for that edge.
There are many different ways to implement screen-space coverage (see
also Section 14.7.2). All methods project some simple object onto the
screen and estimate the length or area in screen space. A large area or
length implies that tessellation should proceed. A fast estimation of the
screen-space projection of a line segment from a to b is shown in Fig-
ure 13.61. First, the line segment is translated so that its midpoint is on
the view ray. Then, the line segment is assumed to be parallel to the near
plane, n, and the screen-space projection, s, is computed from this line
i
i
i
i
i
i
i
i
638 13. Curves and Curved Surfaces
Figure 13.61. Estimation of the screen-space projection, s, of the line segment.
segment. Using the points of the line segment a
and b
to the right in the
illustration, the screen-space projection is then
s =
(a
− b
) · (a
− b
)
v · (a
− e)
. (13.65)
The numerator simply the length of the line segment. This is divided by
the distance from the eye, e, to the line segment’s midpoint. The computed
screen-space projection, s, is then compared to a threshold, t,representing
the maximum edge length in screen space. Rewriting the previous equation
to avoid computing the square root, if the following condition is true, the
tessellation should continue:
s>t ⇐⇒ (a
− b
) · (a
− b
) >t
2
(v · (a
− e)). (13.66)
Note that t
2
is a constant and so can be precomputed. For fractional
tessellation, s from Equation 13.65 can be used as tessellation rate, possibly
with a scaling factor applied.
Increasing the tessellation rate for the silhouettes is important, since
they play an important role for the perceived quality of the object. Finding
if a triangle is near the silhouette edge can be done by testing whether the
dot product between the normal at a and the vector from the eye to a is
close to zero. If this is true for any of a, b,orc, further tessellation should
be done.
Specular illumination changes rapidly on a surface, and so shading arti-
facts appear most frequently with it (see Figure 5.17 on page 116). There-
fore, it makes sense to increase the tessellation in regions where the specular
highlight appears. Test if the dot product between the light vector reflected
around the normal at a point and the vector from the point to the eye is
close to one. If so, then the specular highlight is strong at that point and
the tessellation should continue there. This could again be done for points
a, b,andc.
i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 639
It is hard to say what methods will work in all applications. The best
advice is to test several of the presented heuristics, and combinations of
them.
Another more common method for adaptive tessellation is to do it on a
quad basis. Assume that a rectangular patch is used. Then start a recur-
sive routine with the entire parametric domain, i.e., the square from (0, 0)
to (1, 1). Using the subdivision criteria just described, test whether the sur-
face is tessellated enough. If it is, then terminate tessellation. Otherwise,
split this domain into four different equally large squares and call the rou-
tine recursively for each of the four subsquares. Continue recursively until
the surface is tessellated enough or a predefined recursion level is reached.
The nature of this algorithm implies that a quadtree is recursively created
during tessellation. However, this will give cracks if adjacent subsquares
are tessellated to different levels. The standard solution is to ensure that
two adjacent subsquares only differ in one level at most. This is called a
restricted quadtree. Then the technique shown to the right in Figure 13.59
is used to fill in the cracks. The disadvantage with this method is that the
bookkeeping is more involved.
Lindstrom et al. [779] and Sharp [1158] present different variations of
algorithms for avoiding cracks. Bookkeeping in these algorithms is more
involved. Also, Lindstrom [779] presents a geometric screen-space flatness
test for heightfields, which Hoppe [561] generalizes to arbitrary geometry.
Both these tests are designed for mesh simplification. Eberly describes
many different flatness tests, both for curves and surfaces [294]. Chhugani
and Kumar [173] present an algorithm for adaptive tessellation of spline
surfaces, where tessellation is view-dependent.
13.6.5 Catmull-Clark Surfaces with
Hardware Tessellation
Catmull-Clark surfaces (Section 13.5.4) are frequently used in modeling
software and in feature film rendering, and hence it would be attractive to
be able to render these efficiently using graphics hardware as well. Loop
and Schaefer [790] present a technique to convert Catmull-Clark surfaces
into a representation that can be forwarded to the hardware tessellator,
and with a fast evaluation in the vertex shader (without the need to know
the polygons’ neighbors). Their method will be described in this section,
as it is likely to have a large impact on real-time rendering of high-quality
surfaces.
As mentioned in Section 13.5.4, the Catmull-Clark surface can be de-
scribed as many small B-spline surfaces when all vertices are ordinary.
Loop and Schaefer convert a quadrilateral (quad) polygon in the origi-
nal Catmull-Clark subdivision mesh to a bi-cubic B´ezier surface (see Sec-
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.