Alternatives
to Polygonal Models
Despite
the widespread use of polygonal models for representing 3D geometry,
the quest goes on to find suitable alternatives, particularly since
the limitations of polygonal data have become glaringly obvious to currentgeneration
developers. Because PC developers need to create content that scales
across many levels of processor performance (including both host processors
and 3D graphics accelerators), they're forced to either create multiple
models or to use mesh reduction algorithms for dynamically producing
the lower detail models. Creating multiple models clearly taxes the
efforts of 3D artists, who must spend even more time modeling, manipulating,
and animating models composed of large numbers of polygons. As games
become more content intensive (not just in terms of the levels of detail,
but more actual game content), the time required to produce the content
grows considerably. Alternatives to polygonal models offer artists an
acceptable means to streamline the creation process and save time along
the way.
This article deals with one of the more promising alternatives to polygonal
modeling: NURBS (NonUniform Rational BSpline) surfaces. First, I'll
introduce you to the concepts and terminology associated with parametric
curves and surfaces. Next, I'll describe in detail how to render NURBS
surfaces and discuss some of the difficulties encountered when using
NURBS surfaces in place of polygonal models. Finally, if I've done my
job well, this article will whet your appetite for the exciting types
of 3D content that can be created using parametric surfaces and inspire
you to investigate developing this type of content.
Parametric
Curve Basics
Let's
start with the basics. Normal "functions," as presented in
algebra or calculus (or whatever mathematics course we've taken recently
or not so recently) are defined as the dependent variable (often y)
given as a function of the independent variable (usually x) so that
we have an equation such as: y = 2x^2  2x + 1. By plugging in
various values for x we can calculate corresponding values for y. We
can create a graph of the function by plotting the corresponding x and
y values on a twodimensional grid, as shown in Figure 1.

Figure
1. An ordinary function.

Parametric
functions also match values of x with values of y, but
the difference is that both x and y are given as functions
of a third variable (often represented by u) called the parameter.
So we could have a set of equations expressed as follows:
y
= 2u^2  2u +1
x = u
These
equations produce the same curve that the "implicit" function
given above produces. An additional restriction often added to parametric
functions is that the functions are only defined for a given set of
values of the parameter. In our simple example, u could be any real
number but for many sets of equations, the equations will only be considered
valid on a range such as 0 <= u <= 1.
Once you
understand the nature of a parametric function, we can examine how this
pertains to parametric curves and surfaces. In simplest terms, a parametric
curve is the plot of a set of parametric functions over the valid parameter
range. Our previous example has two functions (one for x and
one for y) that when plotted for 0 <= u <= 1 create
the graph in Figure 1. We can easily add a third function for z
(such as: z = 2u) and then we have a set of parametric functions
that create a curve in 3space.
That's
all well and good, you might be thinking, but how do these parametric
functions get chosen in a way that is useful to software developers?
Essentially, typical "parametric" curves and surfaces are
more than just a set (or sets) of parametric functions. Let's take the
earlier description one step further so that we can see how parametric
curves and surfaces originate.

Figure
2. A set of 2dimensional points.


Figure
3. The same set of points, connected linearly.

Consider
the set of 2dimensional points in Figure 2 as well as the linear connection
of these points shown in Figure 3. We can think of these points as representing
a linear approximation of a curve that starts at the first point (0,1)
and ends at the last point (3,1). Another way of looking at this: as
x goes from 0 to 1, y goes from 1 to 2. As x goes from 1 to 2, y stays
at 2, and as x goes from 2 to 3, y goes from 2 down to 1. In mathematical
terms, the "curve" in Figure 3 can be defined as a "blending"
of four points: P0 = (0,1), P1 = (1,2), P2 = (2,2),
and P3 = (3,1). The points are blended by a set of functions
defined as follows:
F0(u) 
= u if 0
<= u < 1 

= 0 otherwise 
F1(u) 
= 1u if
0 <= u < 1 

= 1 if 1
<= u < 2 

= 0 otherwise 
F2(u) 
= 1 if 1
<= u < 2 

= u2 if
2 <= u £ 3 

= 0 otherwise 
F3(u) 
= u2 if
2 <= u £ 3 

= 0 otherwise 
Now, the
curve (we'll call it C) can be defined as:
C(u)
= F0(u)*P0 + F1(u)*P1 + F2(u)*P2 + F3(u)*P3
This gives
us a twodimensional curve (C) defined as a linear combination
of four twodimensional points (P0,P1,P2,P3) and four scalar
parametric blending functions (F0,F1,F2,F3) valid in the closed interval
[0,3].
Are you
excited, yet? Probably not, but I am because here's the kicker: by creatively
choosing these blending functions, we can change the look and smoothness
of the curve both in terms of visual appearance and mathematical continuity.
You may
still be wondering how we'll come up with these blending functions more
easily. Well, part of the secret lies in the concept of a knot vector.
A knot vector is simply a vector (which is a list of one or more real
numbers) that describes the "knots" of the curve. Think of
a knot as a point where the blending functions change. In the previous
example, the blending functions change at 0 (where they start), 1, and
2. This is apparent from the conditions on the functions (such as 1
<= u < 2). An example of a knot vector would be: {0, 1, 2, 3}.
We'll call this knot vector U and denote each of the terms in
it as u0,u1,u2,u3 so that u0=0, u1=1, u2=2, and u3=3.
Knot vectors
have the following characteristics:
 The
values must be nondecreasing. This means that ui+1 >= ui
for all i. This also means that values can be repeated so that
{0,1,1,2,3} is a valid knot vector.
 The
spacing of the "knots" (that is, the difference between
successive knot values ui and ui+1) can either be "uniform"
(the same for all uI and ui+1 pairs) or "nonuniform".
We'll talk about this later in the article.
 The
number of elements, m, in a knot vector must be defined by
m = p + n + 1 where n is the number of control points
and p is the degree of the desired blending function (as shown
in a later example).