Poor Man's Bryce Part III
Volume Number: 14
Issue Number: 12
Column Tag: Programming Techniques
Poor Man's Bryce, Part III: Faster Terrains in
QuickDraw 3D
by Kas Thomas
Follow a few simple tips and you're guaranteed to get
better performance from QuickDraw 3D.
Apple's QuickDraw 3D library offers graphics programmers a powerful, flexible API
for implementing 3D graphics in a cross-platform manner. Using QD3D, you can get
interactive 3D graphics to happen on screen with relatively minimal effort. The
important concept here is "interactive": From the outset, QD3D's designers wanted
interactivity to be part of the 3D experience, which means the API has been
painstakingly optimized for speed. Unless you're modeling truly enormous objects
(i.e., with tens of thousands of polygons), almost anything you create with QD3D can
be manipulated onscreen (i.e., rotated, scaled, translated) in real time, fully textured
and smooth-shaded. This is far different from most raytracing environments, where
you wait from a few seconds to several hours for a single screen to draw.
But in QD3D programming - as in other types of graphics programming - you can
never have too much speed. It takes so much floating-point math to render a scene
(even if you're just doing shadowless, reflectionless flat-shaded objects) that it's not
hard at all to run into situations where there is a noticeable, annoying lag between
mouse movements and screen updates, even on a G3 machine with video acceleration.
In previous articles (MacTech, October and November 1998), I showed how to put
together a simple QD3D program, called PMB (for "Poor Man's Bryce"), that can
convert 2D imagery to 3D "terrain" using displacement mapping. (The full Code
Warrior projects are available online at ftp.mactech.com.) In Part I, we set up the
code to make a height-mapped 3D grid with vertices equal (or at least proportional) in
number to the number of pixels in the source image; and we presented code to render
this grid in wireframe, dots, or flat-shaded mode. The terrain objects we made this
way weren't particularly attractive, so in Part II we looked at some techniques for
"prettying up" our terrains. We talked, for example, about how to smooth out the
facets of the terrain by means of vertex-normal recalculation (giving true Gouraud
shading); and we showed how to overlay our grids with PICT images (honest-to-gosh
texture mapping). Surprisingly, we didn't take much of a speed hit along the way. It
turns out, for example, that by precalculating our vertex normals (in preparation for
Gouraud shading), we save QD3D's rendering engine from having to calculate normals
on the fly, which it would otherwise do.
Still, it would be nice if our terrains rendered a bit quicker, so that large terrains
(with, say, 10,000 polygons) could be swiveled, resized, etc. in snappier, more
"interactive" fashion. As it is, version 2.0 of our PMB app requires 25 ticks (about
four tenths of a second) to rotate an 8,000-polygon object 12 degrees around the
y-axis, and display it fully updated. This is for a fully textured (with a
360-by-360-pixel texture map) TriGrid, drawn into a 480x384 window in 32-bit
color, on a 250Mhz G3 machine. Mind you, that's two and a half frames per second,
which for some types of work is not so bad. Still, it's a long way from being
realtime-interactive.
I promised last time that there would be ways to speed up our code significantly. It's
time now to deliver on that promise. In the pages to follow, we'll see how it's possible
to achieve a better than five-to-one speedup of our program, with no loss of
functionality. Many of the techniques we'll discuss can be applied to other QD3D
programs, for similar speed gains. So fasten your seat belt, and get ready to rocket.
Choice of Geometry
Let's get right to the core of the matter and start with one of the most important speed
considerations, namely choice of geometry. As mentioned in Part 1 of this series,
QuickDraw 3D offers four freeform mesh primitives that can be used to represent
complex objects. They include the Mesh, the Trigrid, Polyhedron, and TriMesh. (Of
course, QD3D also accommodates NURB patches, but that's another story.) By way of
review, here are the main distinguishing features of these geometries:
• Mesh: This was the original "complex geometry" that shipped with
Version 1.0 of QuickDraw 3D. It's by far the most flexible geometry, because
it allows you to specify non-triangular polygons, with "holes" cut in them if
you desire, and you can attach any number of attributes (in any combination)
to any of a mesh's vertices, edges, faces, contours, or component groupings.
But precisely because of the mesh's flexibility and generality, it is the
slowest-rendering freeform primitive. The mesh, by its nature, brings with
it a lot of code overhead at render-time. It is the worst choice of primitive
where speed is concerned.
• TriGrid: This type of object differs from the Mesh in that it comprises a
lattice of connected triangles, with equal numbers of vertices in each row and
equal numbers of vertices in each column. Efficient sharing of vertices by
neighboring triangles makes the TriGrid a relatively efficient
(fast-rendering) object. It happens to be well-suited to our
terrain-generation task, since adjoining pixels in a 2D source image can
easily be mapped to adjoining vertices in a TriGrid. For more complex
modelling tasks, however, it is obviously somewhat limited, since not every
3D object lends itself to a fixed-lattice layout.
• Polyhedron: The Polyhedron uses a triangle list defined by indexes into
a vertex list. In other words, it's essentially an arbitrary array of triangles.
The triangles may share vertices, or they may not - it's totally up to the
programmer. This is a more orthodox type of "freeform mesh" object,
extremely flexible topologically, yet relatively efficient in terms of RAM
requirements and rendering speed. Unlike the Mesh, the Polyhedron can't
contain polygons with more than three vertices, nor can it contain nested
"component" regions or cutouts. But the Polyhedron's fast rendering speed
moots most such concerns. It's an efficient, easy-to-work-with primitive.
• TriMesh: The TriMesh is by far the fastest-rendering of QD3D's
freeform primitives (as we'll see in a moment). Structurally, it's a lot like
the Polyhedron in that it is essentially an array of triangles defined by indices
into an array of points. But there are some key differences. Whereas the
Polyhedron follows the QD3D tradition of allowing attributes to be
individually assigned to triangles, edges, and/or vertices, as well as the whole
object, the TriMesh imposes a "uniform attributes" requirement, such that if
one triangle has a transparency attribute (for example), all triangles have to
have a transparency attribute. That doesn't mean that you can't "nil out" the
transparencies of those triangles you don't want to be transparent, but you do
have to specify attribute storage for all triangles, regardless of what the
attribute value is for each one.
The TriMesh is like a Polyhedron in a straightjacket. It lacks some of the flexibility of
the Polyhedron (and other QD3D mesh primitives), and for that reason it is - not
surprisingly - a lot better-performing. Simply put, there is very little "special case
code overhead for the TriMesh. The renderer knows in advance what to do to make the
TriMesh show up onscreen. It doesn't have to stop and examine every attribute of every
face and vertex, because if a given attribute type is present for one face or vertex, it's
going to be present for all. Some very good rendering optimizations result.
The TriMesh is a "low level," performance-optimized object. Like many low-level
tools, it's a bit harder (and less forgiving) to use than the higher-level,
"programmer-centric" primitives. It takes some getting used to. But if your primary
need is speed, this is one animal you'll definitely want to spend time getting to know.
Conversion Code
One strategy that's worth considering (for almost any QD3D project) is using two
versions of a given object: an easy-to-code, offscreen, "working" version, and a
render-time version. The behind-the-scenes "working" version of the object might be
a TriGrid or Mesh, while the renderable version might be a TriMesh (for speed). All
you need is a routine that can convert from one version to the other. This is what I did
for Version 3.0 of our sample app, PMB (code available online). I added a menu option
under the Edit menu called "Swap Geometries," and when the user chooses this item, a
routine named DoTriMeshConversion() translates our TriGrid to a TriMesh (if it
hasn't been made already). In this way, the user can toggle back and forth between
TriGrid and TriMesh versions of the terrain very quickly.
At this point it might be a good idea to review the data structure describing a TriMesh.
typedef struct TQ3TriMeshData {
TQ3AttributeSet TriMeshAttributeSet;
unsigned long numTriangles;
TQ3TriMeshTriangleData *triangles;
unsigned long numTriangleAttributeTypes;
TQ3TriMeshAttributeData *triangleAttributeTypes;
unsigned long numEdges;
TQ3TriMeshEdgeData *edges;
unsigned long numEdgeAttributeTypes;
TQ3TriMeshAttributeData *edgeAttributeTypes;
unsigned long numPoints;
TQ3Point3D *points;
unsigned long numVertexAttributeTypes;
TQ3TriMeshAttributeData *vertexAttributeTypes;
TQ3BoundingBox bBox;
The code to translate our TriGrid to a TriMesh is, frankly, somewhat lengthy and ugly.
It comprises a separate (new) C module in our project, TriMeshConversion.c, which
contains roughly 300 lines of code divided among five routines. In terms of creating
the TriMesh, the main thing to keep in mind is that it's almost always possible to "nil
out" many of the TQ3TriMeshData structure's fields. For example, in PMB, we're not
applying an attribute set to the overall object, hence we can set the
triMeshAttributeSet field to nil. We also don't want to specify any triangle attributes,
per se, nor edges (nor edge attributes), so the relevant fields are all zeroed out.
(Frankly, if you start to use very many of these fields, the speed advantage of the
TriMesh quickly begins to evaporate.) We do have to specify a point list, of course, as
well as a triangle list consisting of indices into the point list, because this is how we
describe our geometry. The TriMesh also requires that we precalculate a bounding box
for the bBox field (which helps speed rendering). This is not hard to do: You simply
loop over all of the points in the TriMesh and find the minimum and maximum x,y, and
z coordinates of the points. It's very important to do this correctly, however, because
if you don't, you'll crash your computer.
Transcribing our geometry information from TriGrid form to TriMesh form is a snap.
Listing 1 shows how we copy our point list data.
Listing 1: ConvertVertices()
ConvertVertices()
Copy point list from trigrid into trimesh data.
void ConvertVertices( TQ3TriGridData *tgData,
TQ3TriMeshData *tm) {
long i;
tm->numPoints = tgData->numColumns * tgData->numRows;
tm->points = (TQ3Point3D *)NewPtr(sizeof(TQ3Point3D)
* tm->numPoints);
for (i = 0,tm->points != nil; i < tm->numPoints; i++)
tm->points[i] = tgData->vertices[i].point;
}
The number of points is just the number of rows of the TriGrid times the number of
columns. We allocate an appropriate amount of memory, then loop over all the vertices
in the TriGrid, copying point information directly into the new array. A piece of cake.
It's not at all hard, either, to copy triangle data from a TriGrid to a TriMesh (or to a
Polyhedron). Listing 2 shows how it is done.
Listing 2: ConvertGridTriangles()
ConvertGridTriangles ()
void ConvertGridTriangles( TQ3TriGridData *tgData,
TQ3TriMeshData *tm,
unsigned long *numTriangles)
unsigned long col,row,count,numCols,numRows;
unsigned long triangle_set = 0;
TQ3TriMeshTriangleData *ptd;
ptd = (TQ3TriMeshTriangleData *) NewPtr(