i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 625
Figure 13.49. The top row shows a control mesh, and the limit surface using the standard
Loop subdivision scheme. The bottom row shows piecewise smooth subdivision with
Loop’s scheme. The lower left image shows the control mesh with tagged edges (sharp)
shown in a light gray. The resulting surface is shown to the lower right, with corners,
darts, and creases marked. (Image courtesy of Hugues Hoppe.)
comparison of a standard Loop subdivision surface, and one with piecewise
smooth subdivision.
To actually be able to use such features on the surface the edges that we
want to be sharp are first tagged, so we know where to subdivide differently.
The number of sharp edges coming in at a vertex is denoted s. Then the
vertices are classified into: smooth (s =0),dart(s = 1), crease (s =2),
and corner (s>2). Therefore, a crease is a smooth curve on the surface,
where the continuity across the curve is C
0
. A dart is a nonboundary
vertex where a crease ends and smoothly blends into the surface. Finally, a
corner is a vertex where three or more creases come together. Boundaries
can be defined by marking each boundary edge as sharp.
i
i
i
i
i
i
i
i
626 13. Curves and Curved Surfaces
After classifying the various vertex types, Hoppe et al. use a table to
determine which mask to use for the various combinations. They also
show how to compute limit surface points and limit tangents. Biermann
et al. [86] present several improved subdivision rules. For example, when
extraordinary vertices are located on a boundary, the previous rules could
result in gaps. This is avoided with the new rules. Also, their rules make it
possible to specify a normal at a vertex, and the resulting surface will adapt
to get that normal at that point. DeRose et al. [250] present a technique for
creating soft creases. Basically, they allow an edge to first be subdivided
as sharp a number of times (including fractions), and after that, standard
subdivision is used.
13.5.6 Displaced Subdivision
Bump mapping (Section 6.7) is one way to add detail to otherwise smooth
surfaces. However, this is just an illusionary trick that changes the normal
or local occlusion at each pixel. The silhouette of an object looks the same
with or without bump mapping. The natural extension of bump mapping is
displacement mapping [194], where the surface is displaced. This is usually
done along the direction of the normal. So, if the point of the surface is p,
and its normalized normal is n, then the point on the displaced surface is
s = p + dn. (13.61)
The scalar d is the displacement at the point p. The displacement could
also be vector-valued [698].
In this section, the displaced subdivision surface [745] will be presented.
The general idea is to describe a displaced surface as a coarse control mesh
that is subdivided into a smooth surface that is then displaced along its
normals using a scalar field. In the context of displaced subdivision sur-
faces, p in Equation 13.61 is the limit point on the subdivision surface (of
the coarse control mesh), and n is the normalized normal at p, computed
as
n
= p
u
× p
v
,
n =
n
||n
||
.
(13.62)
In Equation 13.62, p
u
and p
v
are the first-order derivative of the subdi-
vision surface. Thus, they describe two tangents at p. Lee et al. [745] use
a Loop subdivision surface for the coarse control mesh, and its tangents
can be computed using Equation 13.53. Note that the notation is slightly
different here; we use p
u
and p
v
instead of t
u
and t
v
. Equation 13.61
describes the displaced position of the resulting surface, but we also need
i
i
i
i
i
i
i
i
13.5. Subdivision Surfaces 627
Figure 13.50. The masks for an ordinary vertex in Loop’s subdivision scheme. Note that
after using these masks, the resulting sum should be divided as shown. (Illustration
after Lee et al. [745].)
anormal,n
s
, on the displaced subdivision surface in order to render it
correctly. It is computed analytically as shown below [745]:
s
u
=
∂s
∂u
= p
u
+ d
u
n + dn
u
,
s
v
=
∂s
∂v
= p
v
+ d
v
n + dn
v
,
n
s
= s
u
× s
v
.
(13.63)
To simplify computations, Blinn [98] suggests that the third term can be
ignored if the displacements are small. Otherwise, the following expressions
can be used to compute n
u
(and similarly n
v
) [745]:
¯
n
u
= p
uu
× p
v
+ p
u
× p
uv
,
n
u
=
¯
n
u
− (
¯
n
u
· n)n
||n
||
.
(13.64)
Note that
¯
n
u
is not any new notation, it is merely a “temporary” vari-
able in the computations. For an ordinary vertex (valence n = 6), the
first and second order derivatives are particularly simple. Their masks are
shown in Figure 13.50. For an extraordinary vertex (valence n = 6), the
third term in rows one and two in Equation 13.63 is omitted.
The displacement map for one triangle in the coarse mesh is a scalar
field, that is, a heightfield. The storage requirements for one triangle is
one half of (2
k
+1)× (2
k
+1),wherek is the number of subdivisions that
the displacement map should be able to handle, which depends on the de-
sired accuracy. The displacement map uses the same parameterization as
the underlying subdivision mesh. So, for example, when one triangle is
subdivided, three new points are created. Displacements for these three
i
i
i
i
i
i
i
i
628 13. Curves and Curved Surfaces
Figure 13.51. To the left is a coarse mesh. In the middle, it is subdivided using Loop’s
subdivision scheme. The right image shows the displaced subdivision surface. (Image
courtesy Aaron Lee, Henry Moreton, and Hugues Hoppe.)
points are retrieved from the displacement map. This is done for k subdi-
vision levels. If subdivision continues past this maximum of k levels, the
displacement map is subdivided as well, using Loop’s subdivision scheme.
The subdivided displacement, d, is added using Equation 13.61. When the
object is farther away, the displacement map is pushed to the limit points,
and a mipmap pyramid of displacements is built as a preprocess and used.
The resulting displaced subdivision surface is C
1
everywhere, except at
extraordinary vertices, where it is C
0
. Remember that after sufficiently
many subdivision steps, there is only a small fraction of vertices that are
extraordinary. An example is shown in Figure 13.51.
When a displaced surface is far away from the viewer, standard bump
mapping could be used to give the illusion of this displacement. Doing
so saves on geometry processing. Some bump mapping schemes need a
tangent space coordinate system at the vertex, and the following can be
used for that: (b, t, n), where t = p
u
/||p
u
|| and b = n × t.
Lee et al. [745] also present how adaptive tessellation and backpatch
culling can be used to accelerate rendering. More importantly, they present
algorithms to derive the control mesh and the displacement field from a
detailed polygon mesh.
13.5.7 Normal, Texture, and Color Interpolation
In this section, we will present different strategies for dealing with normals,
texture coordinates and color per vertex.
As shown for Loop’s scheme in Section 13.5.1, and the MB scheme in
Section 13.5.2, limit tangents, and thus, limit normals can be computed
explicitly. This involves trigonometric functions that may be expensive to
evaluate. An approximating technique for the normals of Catmull-Clark
i
i
i
i
i
i
i
i
13.6. Efficient Tessellation 629
surfaces is mentioned in Section 13.6.5, where it can be seen that the normal
field is a higher degree “surface” than the actual surface itself. This implies
that merely computing limit normals (which are exact) at the vertices of
the control mesh, and then use the same subdivision scheme used for the
vertices to subdivide the normals is not likely to produce a normal field
with good quality. In addition, such a technique would increase storage,
and it is not obvious whether this is faster.
Assume that each vertex in a mesh has a texture coordinate and a color.
To be able to use these for subdivision surfaces, we also have to create colors
and texture coordinates for each newly generated vertex, too. The most
obvious way to do this is to use the same subdivision scheme as we used
for subdividing the polygon mesh. For example, you can treat the colors as
four-dimensional vectors (RGBA), and subdivide these to create new colors
for the new vertices [1160]. This is a reasonable way to do it, since the color
will have a continuous derivative (assuming the subdivision scheme is at
least C
1
), and thus abrupt changes in colors are avoided over the surface
The same can certainly be done for texture coordinates [250]. However, care
must be taken when there are boundaries in texture space. For example,
assume we have two patches sharing an edge but with different texture
coordinates along this edge. The geometry should be subdivided with the
surface rules as usual, but the texture coordinates should be subdivided
using boundary rules in this case.
A sophisticated scheme for texturing subdivision surfaces is given by
Piponi and Borshukov [1017].
13.6 Efficient Tessellation
To display a curved surface in a real-time rendering context, we usually
need to create a triangle mesh representation of the surface. This process
is known as tessellation. The simplest form of tessellation is called uniform
tessellation. Assume that we have a parametric B´ezier patch, p(u, v), as
described in Equation 13.28. We want to tessellate this patch by computing
11 points per patch side, resulting in 10 × 10 × 2 = 200 triangles. The
simplestwaytodothisistosampletheuv-space uniformly.Thus,we
evaluate p(u, v) for all (u
k
,v
l
)=(0.1k, 0.1l), where both k and l can be
any integer from 0 to 10. This can be done with two nested for-loops. Two
triangles can be created for the four surface points p(u
k
,v
l
), p(u
k+1
,v
l
),
p(u
k+1
,v
l+1
), and p(u
k
,v
l+1
).
While this certainly is straightforward, there are faster ways to do it.
Instead of sending tessellated surfaces, consisting of many triangles, over
the bus from the CPU to the GPU, it makes more sense to send the curved
surface representation to the GPU and let it handle the data expansion.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.