Poor Man's Bryce Part I
Volume Number: 14
Issue Number: 10
Column Tag: Power Graphics
Poor Man's Bryce (Part I): Terrain Generation in
Quickdraw 3D
by Kas Thomas
Displacement mapping is easy to do in QD3D and is a good
way to learn about freeform mesh geometries
In a previous article (MacTech, July 1998), we saw how Apple's cross-platform
Quickdraw 3D API - which is now part of QuickTime 3.0 - gives programmers easy
access to a comprehensive set of highly optimized 3D graphics routines. With the aid of
QD3D, you no longer need to be a math whiz or a graphics professional to put
world-class 3D graphics onscreen and give your end user a powerful interactive 3D
experience. What ordinary Quickdraw did for 2D graphics, Quickdraw 3D does for 3D
graphics - and it does it in cross-platform fashion. (QD3D code ports easily to
Windows, because the "device layer" has been abstracted out in elegant fashion.)
This month we're going to show how QD3D's freeform Mesh primitives can be used to
visualize 2D data three-dimensionally. In particular, we're going to take a crack at
terrain generation - making topographic grids on the fly, based on 2D input. Our
sample app, PMB (which stands for "Poor Man's Bryce"), will let you convert any
PICT, TIFF, GIF, JPEG, or Photoshop 3 image into a fully shaded three-dimensional
terrain grid that can be rotated, scaled, or "flown through" like some of the NASA
graphics of the surface of Mars that you may have seen on TV. The basic technique
we're going to use is displacement mapping, which is a popular method of getting 3D
effects from 2D input (used in many high-end 3D animation and graphics packages).
In this article, we'll show how to set up the core geometry, do the elevation mapping,
and accomplish some basic colorizing. In followup articles, we'll talk about how to do
texture mapping, vertex-normal recalculation (to eliminate faceting), and various
tricks for making terrains look more "realistic." Along the way, we'll discuss speed
issues (always a concern in 3D work), human interface considerations, and a zoo of
other topics. In the process, we'll learn a lot more about Quickdraw 3D.
There's plenty to do. Let's start by talking about mesh geometries.
Major Freeform Geometries
In Quickdraw 3D, there are currently four major freeform primitives to choose from:
the Mesh, TriGrid, TriMesh, and Polyhedron. Of these, the Mesh and TriGrid have been
around since QD3D version 1.0; the others came along in version 1.5. The details of
working with the four mesh geometries were discussed in a develop #28 article by
Philip J. Schneider ("New Quickdraw 3D Geometries"); I won't rehash any of that
material here. If you're interested in knowing more about the mesh geometries, you
should definitely consult Schneider's article as well as Chapter 4 of 3D Graphics
Programming With Quickdraw 3D (the official documentation for QD3D, available
online at Apple's web site). In the meantime, it might be a good idea for us to review
some of the basic design issues associated with the four major mesh types before going
on, since the choice of geometry will have tremendous ramifications later, when we get
into our "terrain modelling" project. (Choosing the right geometry is essential in this
as in any 3D programming project.)
Mesh
In the beginning, there was the Mesh. This geometry was designed from the outset to be
(and remains, today) the most powerful and flexible of QD3D's freeform geometries.
It's also the only geometry that has no explicit data structure: If you look through the
QD3DGeometry.h header file, you'll find no TQ3MeshData struct or typedef. The
structure is private, known only to QD3D's internals. How do you create one, then?
The trivial answer is: You call Q3Mesh_New(). That will give you an empty Mesh. You
go about building the Mesh by adding vertices and faces (lists of vertices comprising
polygons in the Mesh) using functions Q3Mesh_VertexNew() and Q3Mesh_FaceNew().
The key thing to note is that the Mesh was designed for iterative construction and
editing. That is to say, you construct it bit by bit; and you can edit it, on the fly, bit by
bit. Thus, you'll want to use the Mesh if you intend to give your user realtime,
interactive geometry-editing capability (as in a modelling program). This is not to
say that QD3D's other mesh types can never be used in an interactive editing scenario;
it's just a lot less convenient to use the other freeform geometries this way, because
you typically have to retrieve and reorder large vertex arrays, which may involve
memory reallocation and a host of bookkeeping concerns. With the Mesh, you don't have
to worry about any of this because QD3D takes care of everything behind-the-scenes,
so to speak. All you have to do is tell QD3D which Mesh parts you want to work on (the
API provides literally dozens of part-editing and traversal routines) and QD3D takes
care of memory allocation, reordering of edges, clockwise vertex numbering, etc. (And
incidentally, the polygons that comprise a Mesh's faces do not have to be triangles -
they can have any number of points. They don't even have to be planar, strictly
speaking, although you'll probably get rendering artifacts if you don't at least ensure
that your Mesh faces are planar).
The drawbacks of the Mesh are worth noting. Largely because it is such an immensely
powerful, flexible, easy to use primitive, the Mesh is extremely "greedy" when it
comes to memory usage. The reason for this is that in order to enable the Mesh's
powerful topological editing and traversal functions, a Mesh's parts (vertices, faces,
edges, contours, and "mesh component" groupings) have to contain pointers not only to
their own building blocks, but also to the parental components of which they are parts.
In a large, complex Mesh (think of a Jurassic Park T. rex), the connectivity
information can take up as much as 75% of the memory required to store the model.
This not only means poor I/O performance but a big rendering speed hit, too, since the
entire structure has to be decomposed in orderly fashion at render time.
Fortunately, QD3D provides a couple of more streamlined freeform geometries that
you can use for representing large models efficiently. The Mesh remains a useful
primitive for many purposes - it's still the best one to use for realtime interactive
editing - but when fast rendering is a priority, it's usually best to start out with a
different primitive (or translate data back and forth between the Mesh and other
primitives at edit time versus render time).
TriGrid
The TriGrid was included in Quickdraw 3D version 1.0 in order to give programmers a
kind of "hot rod" version of the Mesh: i.e., a freeform primitive suitable for
representing large, complex models, but capable of efficient memory usage and fast
rendering. Unlike the Mesh, the TriGrid has a straightforward public data structure:
typedef struct TQ3TriGridData {
unsigned long numRows;
unsigned long numColumns;
TQ3Vertex3D *vertices;
TQ3AttributeSet *faceAttributeSet;
TQ3AttributeSet *TriGridAttributeSet;
To create a TriGrid, you fill in the fields of the data structure, then pass a pointer to
the structure to Q3TriGrid_New().
The TriGrid has an inherently rectilinear topology, as you can see from the first two
fields in the TQ3TriGridData data structure. (The one-dimensional vertices array is
analogous to the baseAddr field in a PixMap.) So if, for example, you know that your
3D model can be built with 400 vertices in a 20-by-20 lattice, it probably makes
sense to implement the model as a TriGrid.
At first glance, the TriGrid might not seem particularly flexible, since it doesn't allow
rows or columns with arbitrary numbers of points. The TriGrid is obviously perfect
for flags and billboards. But what else can you do with it? Actually, you can implement
a surprising number of objects with TriGrids, including spheres, cylinders, cones,
tori, and helices (plus lots more). The key is to remember that although there has to
be an equal number of points in each row of the grid, the points don't have to be equally
spaced. (They can even overlap.) You'd be surprised how many shapes you can wrap a
TriGrid around.
We'll get deeper into the subject of attributes later, but for now suffice it to say that
the TriGrid (like most QD3D objects) can have its own attribute set; and the faces can
have separate attributes of their own. (Although it's not obvious, the vertices in a
TriGrid can also have their own attributes.)
The fixed topology of the TriGrid means that interactive insertion/deletion of points or
faces is (for all intents) impossible. But there are compensating virtues. First of all,
Quickdraw 3D implements the TriGrid as strips of triangles, which means that
rendering is extremely fast and there is never any concern about "tears" or rendering
artifacts caused by nonplanar polygons. Secondly, the triangles share vertices in an
optimal manner, cutting storage requirements and speeding up I/O. (Note that in a
large TriGrid, there is effectively a 1:1 ratio of vertices to triangles.) A third
advantage of the TriGrid topology, which may not be of particularly obvious
importance at the moment, is that it lends itself to easy UV parametrization. (UV
parametrization is a technique for mapping 2D surfaces or functions onto
"three-space." We'll talk more about this when we get into texture-mapping.)
The TriGrid may not be as flexible as the Mesh, but what it lacks in flexibility it
makes up for in efficiency. Good rendering speed, efficient memory use, and fast I/O
characterize the TriGrid. When a model lends itself to implementation as a TriGrid,
you can't go wrong choosing this primitive.
TriMesh
The TriMesh, which made its debut in QD3D version 1.5, is one of the most widely used
freeform primitives (because it's generally conceded to be the fastest). It's also the
most controversial. Many QD3D programmers disdain the TriMesh, however, because
it results (in many instances) in code that's bloated and/or hard to read and maintain.
The reason is simple. The TriMesh was designed from the beginning to be a low-level,
high performance freeform primitive, optimized for rendering speed, not for
programmer convenience. It's the SR-71 of Mesh primitives: costly to build and
maintain, but faster than anything else out there.
Similar to the TriGrid (but unlike the Mesh), the TriMesh has an explicit public data
structure and is created by passing a pointer to the data structure to
Q3TriMesh_New(). The data structure looks like this:
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 TQ3TriMeshData structure consists of an attribute set for the overall TriMesh;
five parallel arrays describing the mutual relationships of the object's points, edges,
faces (triangles), and attributes; and a bounding box. The precalculated bounding box
helps speed up rendering. The parallel arrays work more or less as you'd expect; some
of them (the edges and attribute arrays) are optional. As with the TriGrid, the
underlying polygon type here is the triangle, but whereas the vertex/triangle
memberships are implicit in the TriGrid layout, those relationships are explicit in
the case of the TriMesh. They have to be, because the TriMesh lets you specify any
number of points in completely arbitrary order.
Why is the TriMesh so disdained by some (but not all) QD3D programmers? First,
there's the uniform-attributes requirement. This means that if you want one of the
faces in your TriMesh to have a transparency attribute, they all have to have a
transparency attribute. (The same holds true for vertex and edge attributes.) This is
counter to the way attributes are handled in all other Quickdraw 3D primitives.
Another awkward feature of the TriMesh is that attributes are not closely linked to the
actual objects they apply to. (Again, this runs counter to the rest of the API.) If you
want to change the vertex normal for, say vertex number 99, you have to retrieve the
99th element of the array of vertex normals. The vertex normals might, in turn, be
just one subarray of the vertexAttributeTypes (which may very well hold arrays,
also, for diffuse color and transparency). Adding new attribute types at runtime, or
enabling interactive editing of geometry, can require memory reallocation and
bookkeeping; and the risk of explosive data growth at runtime is significant because of
the uniform-attributes requirement. (In a 10,000-polygon TriGrid with faces set to
red, white, or blue, all you have to do is set each attribute pointer to one of three
addresses. The same model implemented as a TriMesh would require 12 5 10,000 =
120,000 bytes of extra array storage. Want the blue faces to be transparent? Add
another 120,000 bytes. Want one of the red faces to have an amber specular
highlight? Add 120,000 bytes. And so on.)
Another down side to working with the TriMesh is that there are no accessor functions