Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Continuous LOD Terrain Meshing Using Adaptive Quadtrees
View All     RSS
September 18, 2019
arrowPress Releases
September 18, 2019
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Continuous LOD Terrain Meshing Using Adaptive Quadtrees


February 28, 2000 Article Start Previous Page 4 of 4
 

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 [email protected] 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 [email protected].


Article Start Previous Page 4 of 4

Related Jobs

Incredible Technologies
Incredible Technologies — Vernon HIlls, Illinois, United States
[09.17.19]

Game Programmer
Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Engine Programmer
Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Server Programmer
Daybreak Games
Daybreak Games — Austin, Texas, United States
[09.16.19]

Senior Tools Programmer





Loading Comments

loader image