Working
Code
The
Soul Rider
engine is closed source for the forseeable future, but I did re-implement
the essentials of this algorithm as a companion demo
for this article. The
demo source is freely available for you to examine, experiment
with, and modify and incorporate into your own commercial
or non-commercial projects. I
only ask that if you do incorporate the demo source into
a project, please acknowledge me in the credits!
I
didn't sweat the data-packing issue in the demo code. That would be a good area to experiment with.
Also, I didn't implement frustum culling of squares,
but all the necessary data is readily available.
The
data included with the demo comes from USGS 7.5-minute DEMs of
the Grand Canyon (USGS). At
Slingshot we have a proprietary tool that crunches the USGS
data and stitches neighboring DEMs together; I collected
36 datasets and resampled them at a lower resolution to make
the heightfield. I made the
texture in a few minutes in Photoshop, by loading an 8-bits
per sample version of the heightfield as raw data, running
the Emboss filter on it to create shading, and adding some noise and
tinting. The texture is just
one big 1024x1024 image, stretched over the entire terrain.
The
data-loading code should be fairly self explanatory, so if you
have some of your own data you want to try, it should be easy
to get it in there.
The
program uses OpenGL and GLUT for 3D, window setup, and input. I developed it under Win98 using
a TNT2 card, but I tried to avoid Windows-isms so it should
be easy to port to other systems that support GLUT.
Exercises
for the Reader
In
addition to the tighter data packing I mentioned, there are a few
other things in the Soul Ride engine which aren't in the
article demo. The big one is a unique-full-surface texturing
system, the details of which are beyond the scope of this
article. But I will mention
that good multi-resolution texturing, especially containing lighting,
is extremely beneficial for exploiting the unique features of
the quadtree terrain algorithm.
One
thing I haven't yet experimented with, but looking at the demo
code would be fairly easy to hack in, is on-demand procedural
detail. In my view, on-demand procedural detail looms large
in the future of computer graphics.
There just doesn't seem to be any other good way to
store and model virtual worlds to the detail and extent where they
really have the visual richness of the real world.
Fortunately, the problem is completely tractable,
if complicated. I think this
quadtree algorithm, because of its scalability, can be helpful
to other programmers working on on-demand procedural detail.
Yet
another cool extension would be demand-paging of tree subsections. It actually doesn't seem too difficult; basically
you'd flag certain quadsquares at any desired spot in the
hierarchy as being "special"; they'd contain links
to a whole giant sub-tree stored on disk, with the max-error
for the sub-tree precomputed and stored in the regular tree.
Whenever Update() would try to enable a "special"
square, it would actually go off and load the sub-tree and link
it in before continuing. Getting
it to all stream in in the background without hitching would
be a little interesting, but I I think doable.
It would result in basically an infinite paging framework. On-demand procedural detail could exploit the
same basic idea; instead of chugging the disk drive to get
pre-made data, you'd run a terrain-generation algorithm to
make the data on the fly.
And
another suggestion for further work would be to identifying and
eliminating performance bottlenecks.
I suspect that there's some headroom in the code for
making better use of the graphics API interface.
Acknowledgements
In
addition to the authors of the papers (listed below under References)
which this work is based on, I would also like to send shout-outs
to Jonathan Blow, Seumas McNally and Ben Discoe for their
various thought-provoking emails and comments, and also to
the participants in the algorithms@3dgamedev.com
mailing list, where I've learned a lot of extremely interesting
stuff from other programmers about different approaches and
the ins-and-outs of terrain rendering.
References
[1]
Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges,
Nick Faust and Gregory A. Turner.
"Real-Time, Continuous Level of Detail Rendering
of Height Fields". In SIGGRAPH
96 Conference Proceedings,
pp. 109-118, Aug 1996.
[2]
Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller,
Charles Aldrich and Mark B. Mineev-Weinstein.
"ROAMing Terrain: Real-time, Optimally Adapting
Meshes." Proceedings
of the Conference
on Visualization '97,
pp. 81-88, Oct 1997.
[3]
Stefan Röttger, Wolfgang Heidrich, Philipp Slusallek, Hans-Peter
Seidel. Real-Time Generation of Continuous Levels
of Detail for Height
Fields. Technical Report
13/1997, Universität Erlangen-Nürnberg.
[4]
Seumas McNally. http://www.LongbowDigitalArts.com/seumas/progbintri.html
. This is a good
practical introduction to Binary Triangle Trees from [2]. Also see http://www.TreadMarks.com
, a game which uses methods from [2].
[5]
Ben Discoe, http://www.vterrain.org
. This web site is an excellent
survey of algorithms, implementations, tools and techniques related
to terrain rendering.
Thatcher
Ulrich is the lead programmer for Slingshot Game Technology www.sshot.com,
which is working hard to make a snowboarding game that doesn't suck.
You can gaze at Thatcher's vacation photos at www.tulrich.com,
or email him at tu@tulrich.com.
_____________________________________________________________
[Back
to] The Problems
|
|
|
|
Features
