i
i
i
i
i
i
i
i
Chapter 13
Curves and Curved Surfaces
“Where there is matter, there is geometry.”
—Johannes Kepler
The triangle is a basic atomic rendering primitive. It is what graphics
hardware is tuned to rapidly turn into lit and textured fragments and put
into the frame buffer. However, objects and animation paths that are
created in modeling systems can have many different underlying geometric
descriptions. Curves and curved surfaces can be described precisely by
equations. These equations are evaluated and sets of triangles are then
created and sent down the pipeline to be rendered.
The beauty of using curves and curved surfaces is at least fourfold:
(1) they have a more compact representation than a set of polygons, (2)
they provide scalable geometric primitives, (3) they provide smoother and
more continuous primitives than straight lines and planar polygons, and
(4) animation and collision detection may become simpler and faster.
Compact curve representation offers a number of advantages for real-
time rendering. First, there is a savings in memory for model storage
(and so some gain in memory cache efficiency). This is especially useful
for game consoles, which typically have little memory compared to a PC.
Transforming curved surfaces generally involves fewer matrix multiplica-
tions than transforming a mesh representing the surface. If the graphics
hardware can accept such curved surface descriptions directly, the amount
of data the host CPU has to send to the graphics hardware is usually much
less than sending a polygon mesh.
Curved model descriptions such as N-patches and subdivision surfaces
have the interesting property that a model with few polygons can be made
more convincing and realistic. The individual polygons are treated as
curved surfaces, so creating more vertices on the surface. The result of
a higher vertex density is better lighting of the surface and silhouette edges
with higher quality.
Another major advantage of curved surfaces is that they are scalable. A
curved surface description could be turned into 2 triangles or 2000. Curved
575
i
i
i
i
i
i
i
i
576 13. Curves and Curved Surfaces
surfaces are a natural form of on the fly level of detail modeling: When the
curved object is close, generate more triangles from its equations. Also, if
an application is found to have a bottleneck in the rasterizer, then turning
up the level of detail may increase quality while not hurting performance.
Alternately, if the transform and lighting stage is the bottleneck, the tessel-
lation rate can be turned down to increase the frame rate. However, with
a unified shader architecture, such as the Xbox 360 (Section 18.4.1), these
types of optimizations do not apply.
In terms of animation, curved surfaces have the advantage that a much
smaller number of points needs to be animated. These points can then
be used to form a curved surface and a smooth surface can be generated.
Also, collision detection can potentially be more efficient and more accurate
[699, 700].
The topic of curves and curved surfaces has been the subject of entire
books [332, 569, 905, 1072, 1328]. Our goal here is to cover curves and
surfaces that are finding common use in real-time rendering. In particular,
a number of surface types are likely to become or have become a part of
graphics APIs and have direct accelerator support.
Curves and surfaces have the potential for making real-time computer
graphics applications faster, simpler to code, and last longer (i.e., survive
a number of generations of graphics hardware). With the advent of geom-
etry shaders, the programmer even gets control of deriving new primitives
in the shader. A possible problem with using this type of shader can be
that some CPU-side algorithms rely on knowing the exact geometry. For
example, the shadow volume method (Section 9.1.3) needs to use the sil-
houette edge of a model in order to generate projected quadrilaterals. If
the CPU is creating these quadrilaterals, a curve description has to also be
evaluated on the CPU to find the silhouette edges. Even with such lim-
itations, the potential quality and speed improvements offered by curved
surface descriptions makes them useful today, and future graphics hardware
promises to be more powerful and flexible.
13.1 Parametric Curves
In this section we will introduce parametric curves. These are used in many
different contexts and are implemented using a great many different meth-
ods. For real-time graphics, parametric curves are often used to move the
viewer or some object along a predefined path. This may involve changing
both the position and the orientation; however, in this chapter, we con-
sider only positional paths. See Section 4.3.2 on page 77 for information
on orientation interpolation. Another use could be to render hair, as seen
in Figure 13.1.
i
i
i
i
i
i
i
i
13.1. Parametric Cur ves 577
Figure 13.1. Hair rendering using tessellated cubic curves [929]. (Image from “Nalu”
demo courtesy of NVIDIA Corporation.)
Say you want to move the camera from one point to another in a certain
amount of time, independent of the performance of the underlying hard-
ware. As an example, assume that the camera should move between these
points in one second, and that the rendering of one frame takes 50 ms. This
means that we will be able to render 20 frames along the way during that
second. On a faster computer, one frame might take only 25 ms, which
would be equal to 40 frames per second, and so we would want to move the
camera to 40 different locations. Finding either set of points is possible to
do with parametric curves.
A parametric curve describes points using some formula as a function of
a parameter t. Mathematically, we write this as p(t), which means that this
function delivers a point for each value of t. The parameter t may belong
to some interval, called the domain, e.g., t ∈ [a, b]. The generated points
are continuous, that is, as → 0thenp(t + ) → p(t). Loosely speaking,
this means that if is a very small number, then p(t)andp(t + )aretwo
points very close to each other.
In the next section, we will start with an intuitive and geometrical
description of B´ezier curves, a common form of parametric curves, and
i
i
i
i
i
i
i
i
578 13. Curves and Curved Surfaces
then put this into a mathematical setting. Then we discuss how to use
piecewise B´ezier curves and explain the concept of continuity for curves.
In Section 13.1.4 and 13.1.5, we will present two other useful curves, namely
cubic hermites and Kochanek-Bartels splines. Finally, we cover rendering
of B´ezier curves using the GPU in Section 13.1.2.
13.1.1 B
´
ezier Curves
Linear interpolation traces out a path, which is a straight line, between two
points, p
0
and p
1
. This is as simple as it gets. See the left illustration in
Figure 13.2. Given these points, the following function describes a linearly
interpolated point p(t), where t is the curve parameter, and t ∈ [0, 1]:
p(t)=p
0
+ t(p
1
− p
0
)=(1− t)p
0
+ tp
1
. (13.1)
The parameter t controls where on the line the point p(t) will land;
p(0) = p
0
, p(1) = p
1
,and0<t<1 gives us a point on the straight line
between p
0
and p
1
. So if we would like to move the camera from p
0
to
p
1
linearly in 20 steps during 1 second, then we would use t
i
= i/(20 − 1),
where i is the frame number (starting from 0).
When you are interpolating between only two points, linear interpola-
tion may suffice, but for more points on a path, it often does not. For
example, when several points are interpolated, the sudden changes at the
points (also called joints) that connect two segments become unacceptable.
This is shown at the right of Figure 13.2.
To solve this, we take the approach of linear interpolation one step
further, and linearly interpolate repeatedly. By doing this, we arrive at
Figure 13.2. Linear interpolation between two points is the path on a straight line (left).
For seven points, linear interpolation is shown at the upper right, and some sort of
smoother interpolation is shown at the lower right. What is most objectionable about
using linear interpolation are the discontinuous changes (sudden jerks) at the joints
between the linear segments.
i
i
i
i
i
i
i
i
13.1. Parametric Cur ves 579
Figure 13.3. Repeated linear interpolation gives a B´ezier curve. This curve is defined
by three control points, a, b,andc. Assuming we want to find the point on the curve
for the parameter t =1/3, we first linearly interpolate between a and b to get d.Next,
e is interpolated from b and c. The final point, p(1/3) = f is found by interpolating
between d and e.
the geometrical construction of the B´ezier (pronounced beh-zee-eh) curve.
1
First, to be able to repeat the interpolation, we have to add more points.
For example, three points, a, b,andc, called the control points,could
be used. Say we want to find p(1/3), that is, the point on the curve for
t =1/3. We compute two new points d and e by linear interpolation from
a & b and b & c using t =1/3. See Figure 13.3. Finally, we compute f by
linear interpolation from d and e again using t =1/3. We define p(t)=f .
Using this technique, we get the following relationship:
p(t)=(1− t)d + te
=(1− t)[(1 − t)a + tb]+t[(1 − t)b + tc]
=(1− t)
2
a +2(1− t)tb + t
2
c,
(13.2)
which is a parabola since the maximum degree of t is two (quadratic). In
fact, given n + 1 control points, it turns out that the degree of the curve is
n. This means that more control points gives more degrees of freedom for
the curve. A second degree curve is also called a quadratic,athirddegree
curve is called a cubic, a fourth degree curve is called a quartic,andsoon.
This kind of repeated or recursive linear interpolation is often referred
to as the de Casteljau algorithm [332, 569]. An example of what this looks
like when using five control points is shown in Figure 13.4. To generalize,
instead of using points a–f, as in this example, the following notation is
used. The control points are denoted p
i
, so in the example, p
0
= a,
p
1
= b,andp
2
= c. Then, after linear interpolation has been applied
k times, intermediate control points p
k
i
are obtained. In our example, we
have p
1
0
= d, p
1
1
= e,andp
2
0
= f.TheB´ezier curve for n + 1 control points
1
As a historical note, the B´ezier curves were developed independently by Paul de
Casteljau and Pierre B´ezier for use in the French car industry. They are called B´ezier
curves because B´ezier was able to make his research publicly available before de Castel-
jau, even though de Casteljau wrote his technical report before B´ezier [332].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.