Remember Quake? Back when it was first released, consumer-level 3D acceleration was nearly unheard of, and id's software renderer scaled in speed with the clock speed of your Pentium processor.

During the few years since then, though, our market has reached a point of stratification with non-accelerated Pentium "Classic" machines on the low end and the latest and greatest pixel crunchers on the high end. The range is enormous. As game developers, it's important to support high-end consumers, and yet we'd prefer not to abandon the low-end players. From this desire was a new industry trend born: scalable geometry.

Scalable Geometry

Scalable geometry is any kind of geometry that can be adapted to run either faster with decreased visual quality or slower with increased visual quality. There are a number of ways of doing this, so we'll briefly cover the more popular methods.

One of the earliest methods used in games to scale geometry involved hand-generated level-of-detail models. You can see this principle at work in games like Battlezone and Grand Prix Legends. In the case of a race car, artists create a very high-detail model of the car, then a lower-detail model, and then continue down to a very low-detail model. Then, at run time, factors like the speed of the machine and the distance of the car to the viewer determine which model you use each frame. One of the benefits that hand-tuned LOD models have over other approaches is that the models can have more actual polygonal detail at the higher levels, since they're created by hand. There are many drawbacks, though. For instance, the switch from one model to another can manifest itself as an abrupt visual "popping", and can therefore be distracting to the viewer. A solution to this is to increase the number of LOD models, but this exposes another drawback: it takes a lot of an artist's time to make several versions of every object.

Another method of implementing scalable geometry is in using dynamic mesh reduction techniques. Shiny's, Messiah, uses a technique like this for their character animation system. The idea here is that you store one high-detail version of a model. Then, based on the distance of the model from the viewer and the desired framerate, you use some kind of detail reduction algorithm to generate an appropriate mesh. There are a number of ways to perform the detail reduction; if the high-detail model is stored as a polygon mesh, algorithms like the quadric error metrics described by Garland and Heckbert are perfect for the task. The advantages to dynamic mesh reduction are that many of the techniques can be very fast with some precalculation, and it can produce very good-looking results. There are, again, a number of drawbacks. It can be tricky to get texture coordinates to reduce with the mesh without making the texture slide around on the model. Also, algorithmically reducing a model from 10,000 polygons to 50 polygons still generally won't look as good as a 50-polygon model hand-crafted by an artist.

Curved Surfaces

The final method we'll mention, then, is the topic of this article. Curved surfaces are one of the most popular ways of implementing scalable geometry. There is a good reason for that, too; in games we've seen them in, they look fantastic. Unreal's characters looked smooth whether they were a hundred yards away, or coming down on top of you. Quake 3: Arena screenshots show organic levels with stunning smooth, curved walls and tubes. There are a number of benefits to using curved surfaces. Implementations can be very fast, and the space required to store the curved surfaces is generally much smaller than the space required to store either a number of LOD models or a very high-detail model.

Quake 3: Arena is one of the first games to take advantage of curved surfaces in a real-time 3D setting.

The downside of curves and curved surfaces is that they are perhaps the most difficult of the three methods to learn and understand. There's a lot of reference material out there, but a lot of it is not easy reading, even if you know the material and are just using the books for reference. Therefore, in this article, we'll look at the basics of curves and curved surfaces. We'll cover the concept of the basic polynomial curve, and then onto two example curve representations: Hermite curves and Bézier curves. From there, we'll move onto surfaces, covering the Bézier patch. In this article, we'll take the most straightforward approach possible to rendering the curves and patches. While this does mean that our implementations will be very slow, they will hopefully be more legible for it. Next month, we'll continue our examination of patches by delving into optimization techniques to make them truly useful.

Remedial Curve Concepts

Just to be absolutely sure we all start off on the same wavelength, we'll start by reviewing some of the basic math principles that we need as a foundation for working with curves and curved surfaces. Feel free to skip this section if this is remedial.

At its core, any of the curves we'll discuss can be represented as a parametric polynomial function. Following convention, we'll use the parameter u. Our curves will look something like this:

Generally, we'll refer to f(u), which is the 3D point on the curve at u. Now, as long as at least one of c0, c4, and c8 are non-zero, the curve will be a cubic curve, and cubic curves are the ones we're most interested in. After all, since we'd like to keep computation to a minimum, we'd like to use the lowest-degree curve possible (since a higher degree requires more multiplication every time it's evaluated). So, we might try using a zero-degree curve (which would be fast to compute). But a zero-degree curve is simply a point, which doesn't do us too much good.

Moving on, a one-dimensional curve is simply a line. It's pretty clear that lines are insufficient for our purposes. So, we move on to quadratic curves. These are parabolas, which might seem sufficient for representing curves and curved surfaces. Unfortunately, second-degree curves will always lie in a plane, and we're working in three dimensions, so it would be better to have a space curve, a curve that isn't confined to two dimensions or less. Therefore, our cubic curve is the curve of choice.