Roam Engine Qualifiers
Platform: Win98, AMD K6-2 450 Mhz, 96 Mb RAM, NVIDIA GeForce 256 DDR video.
Resolution: 640x480, 32 bit color
Note on Variance: Variance is the single most important variable in this engine. It has been glossed over in this article to present the overall framework. Try modifying the calculation used for the variance tree, or the tree's depth. Specifically, set depth to an extremely small value like 3, then try a large one like 13, note the difference in rendering quality.
The variance is also used during tessellation. Adjust the calculation for the current node to ignore distances entirely. Then try it based purely on distance, ignoring the value from the variance tree. It will be up to you to find calculations which work best for your application.
Roam Engine Qualifiers
Desired # of
Other Engines in the Industry
In the process of writing this article, I contacted several developers in industry for comments and poked a few questions about their engines.
Starseige: Tribes (www.Dynamix.com)
Starseige Tribes is an online-only game of fast-paced squad warfare. The game is played seamlessly between indoor and outdoor environments where terrain features are extremely strategic to the success of a mission. Long distance kills are commonplace and enemies may hide behind hills to avoid detection. Mark Frohnmayer responded to questions about Starseige Tribes for this article.
On Height Maps: [responses edited for length] Mark Frohnmayer: "The heights in Tribes 1 are stored on a regular 8m square grid. Tribes 2 grid size is selectable by mission."
On the Engine: Mark Frohnmayer: "The Tribes 1 terrain engine used a distance-based quad tree algorithm created by Tim Gift. For Tribes 2 we came up with a new approach to screen-error based on edge traversal. Our approach makes up for the limitations of current published algorithms, including texturing with a bin-tree approach and seaming up edges between squares in quadtree algorithms."
They chose a Quad Tree algorithm, see  for reference on the basics of this system. I'm puzzled over the new screen error metric, however from the screenshots of Tribes 2, it works amazingly well! Perhaps in the coming months they will enlighten us with more details.
Other Comments: Mark Frohnmayer: "Texturing has been the single biggest headache with landscapes in the game - allowing the mission editor to select a texture for every square and dynamically generate the combination textures for squares that are at a lower detail level, as well as automatically texturing the terrain based on vertex material. The most interesting problem was coming up with the algorithm to detail the terrain mesh that solved all of our requirements."
I mentioned before the shear depth of the landscape visualization field, and Mark's comment hints at this. The included engine is only a drop in the bucket. Be sure to check out a good technical library or the many online sites devoted to this topic.
Mark goes on to say that their engine is not frame-coherent, requiring a rebuild of the Quad Tree each frame. This is required for their view metric and clipping code.
Outcast is a deeply designed action/adventure game with exquisite role-play elements. The unique look and feel of Outcast plays beautifully into the alien landscapes and immersive storyline. Christophe Chaudy responded to questions about Outcast for this article
On Height Maps: [responses edited for clarity & length] Christophe Chaudy: "We are using tiled heightmaps. Each heightmap's instance contains its specific scale, offset and some color modifiers. With only 150 or 200 unique heightmaps we can build a huge world with more than 3600 tiles of 10x10 meters. It was difficult to deal with map continuity at tile edges but that's the price to pay - and our graphics people rock!"
On the Engine: Christophe Chaudy: "We started with the software voxel engine. During the production of Outcast, seeing the explosion of 3D HW market, we looked at polygon terrain rendering algorithms but:
So, we stayed with the software rendering approach. There were a lot of drawbacks but finally, even if the terrain renderer is not perfect, it's something that looks different And that was a very important criteria in Outcast production."
Other Comments: Christophe Chaudy: "Voxel rendering is very constraining; very CPU intensive, strong modeling constraints, low resolution, poor quality on low-end computer, etc. But the landscape in Outcast is unique. Even today, I don't see a polygon engine that can reproduce such geometric complexity. But, under the market pressure, we are designing a totally new system for outdoor visualization. It will of course use today 3D hardware rendering. In the future, when the CPU is faster, the ray-casting algorithm on voxel heightmaps could come back."
Outcast is by far the most unique looking game on the market. If you have not seen or experienced the world of Outcast, make sure to swing by the homepage. Also take a look at the presentation on the rendering technology of Outcast from last year's Game Developer's Conference (see the Bibliography for a link).
As promised, here are a few hints and tips for advanced optimizations and features. Each could be its own article, so I've attempted to distill the most important aspects into a few short paragraphs on each topic.
Triangle Fanning:Triangle Fanning is an optimization you can use when triangles all share a central vertex. It allows you to specify fewer vertexes for the same number of triangles, giving an improvement in overall speed. Triangle Fans in OpenGL flow clockwise, as do the points in each of the triangles. You will have to switch which side is the triangle face or OpenGL will cull out all your triangles!
In order to get the correct output of triangles, it helps to switch the order in which child nodes are visited at each level of rendering. Thus if we visit the Left Child first at level 1, then visit the Right Child first for level 2, then back to the Left Child for level 3.
The order of the vertexes is important too. The first vertex specified must be the central point around which the other triangles 'fan' out. This is done by passing down a reference to one of the triangle's vertexes as the "best center vertex". At each level, this value is switched to point to a new best vertex. When a leaf is found it is added to a small buffer of vertexes with the "best vertex" first and the others in clockwise order.
At the next leaf node, we need only compare the "best vertex" to the first vertex in the buffer. If they differ, output the fan to OpenGL and start over. However, if the two vertexes are equal, then test the last vertex in the buffer equal to the next clockwise vertex in the triangle. Again, if they differ, output the fan to OpenGL and start over. Otherwise append the last vertex of the triangle to the end of the vertex buffer.
Fan lengths cannot be more than 8 triangles using this method, however average lengths are more commonly 3-4 triangles per fan.
GeoMorphing:An unfortunate side effect of rendering with dynamic levels of detail is the sudden visual 'pop' that occurs when triangles are inserted or removed from the mesh. This distortion can be reduced to nearly unnoticeable amounts by Vertex Morphing, also called GeoMorphing. GeoMorphing is the gradual rise or fall of a vertex's height from the un-split position to its new split position over the course of several frames. \
GeoMorphing is not difficult, but has a lot of tricky aspects. Essentially, a value may be stored in the TriTreeNode during tessellation which contains the amount of 'morph' this triangle has. This morph value should be in the range 0.0 - 1.0. Then during rendering, transmute from the interpolated height value to the actual Height Field value using the following function:
MorphedZ = (fMorph * actualZ) + ((1-fMorph) * interpolatedZ);
Frame Coherence:Frame Coherence is the most advanced optimization under ROAM. With frame coherence, the mesh which was created last frame can be used again. This feature also enables dynamic frame timing, allowing you to continue to improve the mesh for the current frame right up to the frame's deadline.
In a fast-action game, this means you don't have to spend all the overhead to tessellate the landscape. Instead, deal with the most important fast-action components first, then tessellate the landscape for the rest of the frame time, and render what you have at the end. So if a player is in the middle of a firefight, the landscape will dynamically render at lower detail to save time.
It is beyond the space for this article to explain the implementation of Frame Coherence. However, a few tips for the traveler: Add a 'Parent' pointer to TriTreeNode. Create a Merge() function which undoes one Split() operation. Use a priority queue or other priority structure which contains all leaf nodes in the entire mesh. During the tessellation, merge any nodes which are too detailed for this frame followed by splitting all the nodes which are too coarse for the frame (or until time runs out).
Supporting Larger Topologies: The included engine is structured to simplify the creation of very large worlds. By loading separate height maps for each Landscape class and then rendering each Landscape, there is no limit to its size! There are other limits however, like RAM and computational power.
The Landscape class was designed to hold a paged-in piece of the world, along with other Landscape classes holding other blocks. Each Landscape must link its patches to those in the other Landscapes nearby. This is done in Patch::Reset(), instead of setting the Neighbor pointers for edge nodes to NULL, lookup the correct patch in the Landscape which borders that side.
Speculations on the Future
The future of landscape rendering is wide open. No doubt the polygon count will continue to rise as will the detail of environments and the distances to be viewed. Also, the current LOD algorithms are not designed to take advantage of the new graphics cards which offload triangle setup calculations. This reduces the algorithm's gains for certain applications.
Additionally, OpenGL display lists might be used to render an entire landscape, then sent to the graphics card in one fell swoop each frame. This is feasible for small terrains like this demo and the faster memory busses of the future. We may even see a re-emergence of software rendered voxel landscapes, given the availability of fast CPUs and the inherent advantages of voxel displays.
This article was inspired by many people and many projects I have seen. First and foremost are Seumas McNally and the Tread Marks engine, from which this project was modeled after. Visit http://www.LongbowDigitalArts.com to join in the lively programming forum or learn more about Tread Marks.
I would also like to thank the many terrain visualization projects in the public domain, including ROAM.C by C. Cookson. Also, the many great programming articles in the Gamasutra Features archive, and the super-programmers of the Gamasutra Connections board (I didn't even have to ask questions, the answers were already there!).
And to the industry gurus who reviewed this article and made suggestions, thanks again for the input. It is my sincerest desire to see more outdoor games and epic journeys in the coming years. I hope this article may inspire new projects for the genre.
Bibliography and References
1. Hoppe, H. "Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering" (http://www.research.microsoft.com/~hoppe)
2. Lindstrom, P., Koller, D., Ribarsky, W., Hodges, L., Faust, N., Turner, G., "Real-Time Continuous Level of Detail Rendering of Height Fields" (http://www.cc.gatech.edu/gvu/people/peter.lindstrom/papers/siggraph96)
3. Duchaineau, M., Wolinski, M., Sigeti, D., Miller, M., Aldrich, C., and Mineev-Weinstein, M. "ROAMing Terrain: Real-time Optimally Adapting Meshes" (http://www.llnl.gov/graphics/ROAM)
4. Binary Triangle Tree Article (http://www.longbowdigitalarts.com/seumas/progbintri.html)
5. VTerrain.org Engine Comparison List (http://vterrain.org/LOD/runtime-reg.html)
6. Outcast Engine Technology Presentation for GDC (http://www.appeal.be/products/page1/Outcast_GDC/outcast_gdc_1.htm)
7. Longbow Digital Arts Programming Discussion Forum (http://www.LongbowDigitalArts.com)
8. Gamasutra Features Archive (http://www.Gamasutra.com)
9. GameDev Programming Archives (http://www.GameDev.net)
On Tuesday, March 21st 2000, Seumas McNally lost his battle with Hodgkins Lymphoma.
My sincerest condolences go out to his surviving family; Jim, Wendy and Philippe. I never had the chance to meet Seumas personally, nor thank him for the encouragement and free exchange of ideas he gave. His passing is a great loss to our community of developers. May his commitment, determination, and unfailing humanity live on as an example for us all. Goodbye, Seamus - and Thank You.
Bryan Turner is a freelance research programmer continually in search of cutting-edge technologies. If you would like to contact him, e-mail [email protected].