The Inner Product, August 2002
Jonathan Blow (firstname.lastname@example.org)
Last updated 16 January 2004
Rendering Level-of-Detail Forecast
Rendering LOD, Part 1
Unified Rendering LOD, Part 2 (April 2003)
Unified Rendering LOD, Part 3 (May 2003)
Unified Rendering LOD, Part 4 (June 2003)
Unified Rendering LOD, Part 5 (July 2003)
Note: This article is currently missing its figures.
We will attempt to remedy this situation in the future.
This month I'm going to talk about rendering level-of-detail (LOD) algorithms, and make some recommendations about what to in the game you're currently designing.
Just now I was careful to say "rendering level-of-detail", by which I mean reducing the number of triangles that are used to visually represent a 3D scene, at runtime, in a way that tries to put most of the geometric detail where it will be most effective. From now on I will just say "LOD" to be brief. It used to be a given that if you said "LOD" you meant "rendering LOD", but these days, we often talk about LOD for a number of different systems, like AI and physics. So don't be lulled into thinking that, if you solve the rendering LOD problem, your game is golden; other LOD-style problems may still be lurking.
For rendering LOD, we have a number of types of system to choose from. We can use a Continuous Level-Of-Detail (CLOD) system, progressive meshes, or the old low-tech solution whereby we have a number of precomputed levels of detail for each mesh, and we just switch meshes based on viewpoint distance criteria ("static mesh substitution"). The conclusion of this article is that you ought to be as low-tech as possible and use static mesh substitution. I'll give more detail eventually, but first I will justify this conclusion by criticizing the other methods of LOD. I'll start with CLOD, since that's what I have worked with the most.
A basic property of LOD
To see how CLOD schemes are flawed, let's take a look at the basic nature of LOD'd geometry. Figure 1 shows some screenshots from a terrain project I worked on a couple of years ago. Figure 1a shows the rendered image, and 1b shows a wireframe representation of the terrain geometry; I have circled groups of triangles in the scene based on their distance from the viewer. The triangles circled in red are very close to the camera; yellow indicates triangles in the middle distance, and green indicates triangles that are very far away.
In this image, roughly half the triangles on the screen are close to the viewpoint. This is the expected case for LOD'd geometry, assuming that the world is shaped mostly two-dimensionally (like a terrain, or most first-person shooter maps) and that the idealized geometry does not consist of large, flat surfaces. By "idealized geometry", I mean the geometry of your world at the maximum level of detail, which might even contain infinitely fine features (if your surfaces are fractally shaped, for example).
You can do some simple math showing that this behavior is expected. You start by writing down the constraint that your LOD algorithm uses in order to split triangles (usually it bounds the screenspace-projected length of some world-space distance, like Lindstrom-Koller's delta values or ROAM's wedgies). Assuming that the average value of this world-space distance is proportional to the length of a triangle's edge (meaning that detail does not diminish with scale), you can see that the LOD algorithm is trying to make the triangles projected to the screen be of roughly the same size. Then, do some trig: since the map is mostly 2D, idealize it as an infinite plane being projected to the screen. Imagine a frustum with a 90-degree vertical field of view, so that the vector from the eye through the bottom of the screen is pointing at your feet in worldspace, and the vector through top of the screen is pointing toward the horizon. Then, if your eye is a height 'h' from the ground, half the triangles on the screen are within distance 'h' of your feet! Now, a 90 degree vertical field of view is pretty excessive, and you don't usually walk around in such a way that you can see your feet, so this result is a little bit high. But if you play around with this on a piece of paper, you'll see that the numbers don't get all that much better as you tweak the parameters.
The problem with CLOD algorithms
So now I use this fact to harsh on CLOD. Most CLOD algorithms maintain a persistent mesh that they take great pains to update incrementally, under the misconception that these meshes will not change quickly. As the ROAM paper says: "ROAM execution time is proportionate to the number of triangle changes per frame, which is typically a few percent of the output mesh size, hence ROAM performance is insensitive to the resolution and extent of the input terrain". There's a contradiction inherent in that sentence.
If you, the avatar in a game world, are two meters tall, half your tessellated mesh is within two meters of you. By definition then, if you move two meters forward, most of the active tessellation will have to be recomputed. How much time does it take you to walk two meters in real life? How long does it take in a game world, where we often move at unrealistic speeds?
Most CLOD algorithms do a lot of bookkeeping to continuously change the mesh; that bookkeeping is much slower than the clean "discard this, use that" approach of static mesh substitution. When your terrain is detailed enough, and you move quickly enough, these algorithms drown in their own bookkeeping.
These problems don't usually arise in the research papers that present CLOD algorithms, because those papers use relatively low-density tessellations, low viewpoint speeds, and viewpoints that are very far from the terrain being viewed (without corresponding enlargement of the viewable terrain distance). But anyone who tries to render a 70,000-triangle CLOD terrain will need to sweat very hard to make the system run acceptably. At the same time, though, you can render a 500,000 triangle terrain with static mesh substitution, and you don't even need to think much; you need maybe 1/5th of the software engineering effort to get the program working, and afterward, the program is much easier to maintain.
In addition, CLOD systems usually impose topology constraints that we don't want (e.g. the terrain algorithms require the input data to be a height map, so you can't have overhangs or holes). And I have a lot of arguments about how nobody's even shown that CLOD algorithms provide good tessellation efficiency, which would supposedly have been the whole point of using them. But there's not enough space in the magazine for that particular rant.
The only time I can recommend use of a CLOD system is when your data set is constantly changing (like ocean waves during a storm) and you use a non-persistent form of CLOD, like Seumas McNally's "split-only ROAM".
Once upon a time when I was very enthusiastic about CLOD, I had an email conversation with Charles Bloom and Tom Forsythe. They were proponents of using VIPM, a certain kind of progressive mesh, to represent terrains, ;ut I was convinced that CLOD was better. Well, I've clearly changed my mind about CLOD, but I don't think progressive meshes are very good either, so I will now spend some time dissing them too.
The problem with progressive meshes
Like CLOD terrain, progressive meshes have a certain technological wow-factor, because they also provide a continuum of sorts: you can adjust the level-of-detail of a rendered object to a granularity of 1 triangle. And with certain progressive mesh implementations, like the VIPM implementation shown to me by Tom and Charles, you can render those objects efficiently with modern 3D hardware.
But when rendering an object in a game, like a character or a vehicle, we just don't need fine-grained control of the object's triangle count. When our total triangle budget is in the millions, small changes in triangle count are completely in the noise. When building static levels of detail, the number of triangles we want to discard is usually proportional to the number of triangles in the mesh. If you're building static LOD for a 5000-triangle object, it makes sense to build a reduced mesh at 2500 triangles, but building a mesh at 4900 triangles would be silly.
One might think that the single-vertex-at-a-time path provided by progressive meshes would help with tasks like geomorphing. But it doesn't; when geomorphing, you need to be able to skip across large numbers of collapses, because otherwise you're limiting the speed at which you can adjust the object's detail. This results in poor system behavior.
So progressive meshes do not provide a concrete benefit over static substitution. But they're more complicated, so they incur more software engineering overhead, making your game harder to finish. When approaching problems like building normal maps to augment geometry, with static meshes, you can consider each different-resolutioned mesh in isolation and get good results. With progressive meshes, triangles of different detail levels overlap in uv-space, so you have to write more complicated code to solve the problem.
So if you're designing an LOD system for your next game, my recommendation is to switch between precomputed static meshes, just like we did in the mid-1990s. Back then, because of the low triangle counts, we would usually have art guys hand-create the low-res meshes. These days, there is no good reason to do that. High-quality mesh reduction algorithms, like Garland-Heckbert Error Quadric Simplification, do a good job of generating low-resolution meshes, and your artists' time is valuable.
I've recently been playing around with the normal-map generation technique put to good use in Doom 3. Using this technique we can render meshes that appear to have a large amount of geometric detail, but that really consist of a moderate number of triangles. But aside from just looking good, this technique helps make LOD more effective than it has been in the past. LOD is about removing vertices from a mesh, but historically, we have tended to color objects with vertex-based lighting, so the LOD was removing the maxima and minima of our lighting functions. This caused a lot of popping.
With dot3 normal mapping, we can greatly reduce the extent to which the object's appearance depends on individual vertex positions, and thus the popping decreases. This is a case where static mesh switching benefits tremendously, yet the more-complex CLOD systems find it very difficult to leverage this technique, so they are left further behind.
What about the map?
So that's what I recommend for objects, but what about big things, like terrains or office complexes?
Casey Muratori and I tend to make the same predictions about future environment LOD. There will be a unification, with the same kind of system used for indoors and outdoors. It'll involve chopping the world up into a bunch of blocks. We then perform a process like mipmapping, where each of these blocks of geometry is like a texel from a texture map. To get a lower level of detail for the whole world, combine every 4 neighboring blocks and detail-reduce the resulting mesh (4 blocks if the world mostly extends through 2 dimensions; it should be 8 blocks if the world is more volumetric). Keep doing this until you get all the way down to 1 block representing the entire world.
At runtime, you start near the camera, rendering high-resolution blocks; then, as you traverse the scene and go further from the viewpoint, you switch to lower-resolution blocks. At places where the resolution transitions occur, you will need to stitch together blocks of neighboring detail levels, or else cracks will appear in the scene. This stitching is trivial for the case of a height map; it becomes more difficult with arbitrary topologies crossing the detail boundaries, but the solution is largely a matter of bookeeping. Since your algorithm performed the detail-reduction steps for the blocks, it can effectively trace backward along that sequence of reductions to see how edges should match up.
Thatcher Ulrich implemented something like this for terrain rendering. Sometime soon, I plan to do it for triangle soups; drop me a line if you beat me to it.
Mark Duchaineau et al, "ROAMing Terrain: Real-time Optimally Adapting Meshes", Proceedings of IEEE Visualization 1997.
Seamus McNally, "The Tread Marks Engine", part of "Two Advanced Terrain Rendering Systems", Game Developers Conference 2000.
The Virtual Terrain Project, http://vterrain.org.
Thatcher Ulrich, "Chunking LOD", http://tulrich.com/geekstuff/chunklod.html.
Michael Garland and Paul Heckbert, "Surface Simplification Using Quadric Error Metrics", Siggraph 1997. http://graphics.cs.uiuc.edu/~garland/research/quadrics.html.
Figures (currently missing)
Figure 1a: A rendered terrain.
Figure 1b: A wireframe of that terrain, with triangles grouped by distance.