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 current-generation 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.

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 two-dimensional 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 3-space.

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 2-dimensional points.

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

Consider the set of 2-dimensional 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:

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 two-dimensional curve (C) defined as a linear combination of four two-dimensional 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:

1. The values must be non-decreasing. 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.
   
2. 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 "non-uniform". We'll talk about this later in the article.
   
3. 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).