UNC-Chapel Hill COMP 281 Computational Geometry Final Project
Real-time Rendering of Large-scale Terrain based on Levels of Detail (LOD)
- An implementation with Quad-Tree structure
Due to the geometric complexity of 3D object models, it is difficult to render a scene with a certain level of realism in real time.
Level of Detail is introduced to solve this problem. It takes advantage of the characteristics of human vision - when a 3D object is so far from the point of view that it counts for only a very small region in the whole sight, it would be very hard for human vision to distinguish all the details of the original object. Therefore, it is unnecessary to render all the details of that object in just a few pixel area of the entire screen in the first place. This idea can substantially reduce the rendering time. One way to achieve this is that we build several models for a single object at different levels of detail, like the model for a man's head in Figure 1. The rightmost column is with most simplification, while the leftmost column has the highest resolution. This technique can also be used in terrain rendering, and we call the idea Multi-Resolution Terrain.
Figure 1. Multi-resolution models of a man's head. (figure from: gts.sourceforge.net/gallery.html )
These models at different resolutions can either be created offline or on the fly. Starting from a model at full resolution, a series of simplifications are conducted to generate models at lower resolutions. There are basically three types of simplifications: (1) vertex deletion; (2) edge collapsing and (3) face compression . After simplification, we can choose proper models at certain levels of detail for specific situations.
As a special type of 3D object, terrain has its own features and tricks that worth taking note of. Since a terrain is usually in the form of regular rectangle meshes, the simplification process can be further classified into two categories: (1) regular simplification, and (2) irregular simplification.
For regular simplification, people often resort to “top-down”, and “divide-and-conquer” strategies. Starting from the lowest resolution, the algorithm then refines details on demand. Typical structures are quad tree and binary tree etc.
For irregular simplification, people usually turn to “bottom-up” strategy. However, practical implementations are rarely seen in this case. Figure 2 shows the appearance of these two kinds of simplifications.
Figure 2. Regular Simplification (Left) and irregular simplification (Right).
When we generate the simplified model on the fly, beside the decision on how to simplify the model, we also have to decide when to simplify the model, or in other words, at a specific time, how to choose from models at different resolutions to properly represent the object. In this case, we have to construct an “Evaluating Module”. Basically this module should take into account the distance from the viewer to the objects being rendered, and the roughness of the object itself.
Another key problem in LOD rendering is “Geomorphing”. Since we throw some details away to simplify the model, it is very possible that these once neglected details suddenly “pop” out while we move closer to the object so that we have to switch to a finer level presentation. Though it is very difficult to completely solve this problem, we have to minimize it to an acceptable degree.
We will give a brief review of related researches in Section 2, followed by specifications of data structures and storage in our actual program in Section 3. In Section 4, we discuss the “Node Evaluating Module”. Section 5 deals with how to generate LOD meshes continuously on the fly and some optimizations to achieve real-time rendering. Section 6 is the architecture and specifications of our program. System evaluation and further discussions are in Section 7. Finally, Section 8 summarizes the whole project.
2. Related Work
Bryan Turner mentioned in his paper  that the rules for LOD terrain rendering can be summarized with three excellent papers. They are , , and . In , Hoppe describes a bottom-up Progressive Mesh model. In , Lindstrom uses a top-down quad tree model to recursively tessellate the terrain and to build an approximate height map. In , Duchaineau describes a structure based on a binary tree over the set of triangles, and builds a Real-time Optimally Adapting Meshes (ROAM). All patches in the mesh are isosceles right-angle triangles. Each one of them can be recursively refined by splitting from the right angle vertex to the mid-point of the hypotenuse. Hopper’s method falls into the category of irregular simplification, and it can delete details from any arbitrary existing triangles in the mesh. However, most of practical programs tend to use methods introduced in the last two papers, which both resort to regular simplification.
Innovative as all three papers are, these methods are complicated to implement. When building our program for the project, we refer to yet another two papers  and . They both use the basic ideas of quad tree derived from Lindstrom’s paper, but they are much simpler and fast. Also  provides an efficient “vertex evaluation module” to determine how well a certain patch should be tessellated.
Unfortunately, a complete memory-efficient data structure is not mentioned in above papers. Thatcher Ulrich, from the angle of a developer of the PC game Soul Ride, describes in his paper  an efficient structure based on quad tree. Compared with approaches in academic papers, game developers emphasize to treat problems in more efficient ways.
3. LOD Algorithm
3.1 Basic Idea
First of all, some assumptions should be made: our terrain at highest resolution must be a square region. It must be at the size of and uniformly sampled.
As shown in Figure 3, we use a quad tree representation to describe a multi-resolution terrain. Every square is a node in the quad tree. From the map at the lowest resolution, we recursively subdivide the terrain into four equal-area squares. The deeper this procedure goes the finer the resolution becomes. In other words, sampling rate to the map doubles as the sub-division goes one level deeper, as demonstrated in Figure 3 on the right.
One of the advantages using quad tree representation is pruning as shown in Figure 3. Since only the pink region is visible from the point of view encompassed by the green squares, we do not have to consider the white squares at all. Therefore, we can ignore the invisible white square nodes at very early phase of node recursive subdivision. After we get the logic representation of the terrain, we have to construct a “node evaluation module” in order to decide whether we have to further subdivide the node and whether we should delete it (not like pruning phase). If a node does not need to be further subdivided nor deleted, it is sent to the rendering pipeline.
Figure 4 shows all the information we have to store in one node. We will see in Section 4 how to use it to render the region covered by the node. There are nine vertices related with one tree node – one center vertex, four edge vertices and four corner vertices.
3.2 Data Storage
Terrain data are usually stored in height maps on disk, and in a 2D array in memory. Similar to representations of a binary tree in memory, a quad tree can also be stored in an array structure. The only difference is that the array now is 2 dimensional. To be more specific, we store the full resolution height map in a 2D array. For the quad tree, we construct another 2D array of the same size, which indicate the status of the quad tree nodes. Information related to the nine vertices for a quad tree node can thus be directly referred to in the 2D full resolution height map array. If a node needs to be further subdivided, we mark it as 1, otherwise 0, as shown in Figure 5. The question marks in the array denote the undetermined state of the node, which means they are not yet visited.
4. Node Evaluation Module
We have to construct a node evaluation module to decide if we have to further subdivide the current node when we traverse to it. This issue can be separated into two parts: (1) view-dependence; (2) roughness of the terrain. Although pruning of the tree is theoretically part of node evaluation module, considering its uniqueness, we postpone the discussion on that topic until the next section.
First of all, we hope to see more details in the region near the viewer, and fewer details in distance. We also have to take into account the size of the node (related to the depth from root to the node itself) when considering its distance to the point of view. Therefore, with the help of Figure 6, we have the following formula:
where l is the distance from the center of the node to the point of view, d is the size of the node, and C1 is a tunable factor, which controls the detail level. When this expression is satisfied, we have to further subdivide the node. So the larger C1 is, the more details we have in this region.
Secondly, we hope to display more details on geometrically more complicated terrain surfaces, like those have more bumps and ridges per unit area, and vise versa. As shown in Figure 7, we first consider the center vertex and its four edge vertices. The height value at these five positions will vary a little bit before and after the subdivision. These values denoted by dh0 to dh4 in Figure 7, are related to the roughness of this node. The larger these values are, the rougher the region is. Beside this, we have to consider the roughness of the four children of this node too, which are denoted by dh5 to dh8 in Figure 7. (We don’t have to consider the children when we have reached the leaves) We define the roughness r of the node as follows:
Obviously, the definition of the roughness is a recursive process. Because of the complexity of computation as well as the invariance of these values to a given terrain model, it is reasonable to pre-compute these values and store them in yet another 2D array.
Figure 7. Measuring the roughness of the terrain. Five pieces of roughness information related with one node is depicted on the left; The roughness information with one node and that of its four children’s are on the right.
We now introduce the second evaluation formula, namely the roughness evaluation formula:
where r is derived from exp. (2) and C2 is another tunable factor controlling the roughness. When this expression is satisfied, we have to further subdivide the node. The larger C2 is, the more details we have in this region.
Combining exp. (1) and exp. (3), we have the final node evaluation expression:
The means of variables in exp. (4) are the same as former expressions. When f is smaller than 1, we have to subdivide the node.
Although so far we have completed the node evaluation module, we have not treated the “Geomorphing” problem, which leads to the “popping out” and “disappearing” of details at distance. There are ways such as interpolation  tackling this problem, but it is computationally expensive and not very practical in real systems. Other approaches tend to project the roughness value that we have just computed onto the viewing plane, which is then called “projected pixel error” . But after experiments, we found that this is not a good solution either. Therefore, in our program, we do not use the concept of “pixel error”. As a matter of fact, we do not use any explicit approach to eliminate this effect. We try to properly tune values of C1 and C2 to decrease the visual effect of Geomorphing, and keep it at an acceptable level.
5. Terrain Rendering and Optimization
The rendering process of the terrain mesh is also achieved recursively. This indicates the possibility that we combine the tree construction process and rendering process together. Actually, it is how we do it in practice - we construct the quad tree until we find a leaf, which is indicated by the fact that the node does not require further subdivision. We then send that leaf to the rendering pipeline, and we only render leaves in the quad tree.
There are more that we can do. We need not render all of the invisible leaf nodes. Therefore, we embed the culling operation into the tree construction process.
On the implementation level, OpenGL provides a culling mechanism, but it is implemented after the view and perspective transformation. However, here we need a method to cull the vertices before the transformations are done, meanwhile, the culling must be able to be performed on the quad-tree node. In the program, we implement a “Viewing Frustum Culling” explicitly in the world frame, not using the OpenGL standard interface.
In the projection from 3D to 2D, we define a viewing frustum, only the vertices in the frustum are visible.
Figure 8. View Frustum in world frame and the projected frustum
Specifically, a frustum is composed of six planes, each plane equation has the form: Ax + By + Cz + D = 0 , we define the direction to the interior of the frustum as the positive direction of the plane. To determine whether a 3D point lies inside the frustum, we only need to check the sign of the six plane equations with that point. That is to say, if all of the signs are positive, the point lies inside of the frustum, and we need to transform and render this point.
According to the frustum range in Figure 8, the six plane equations in the projected space can be derived as following.
Let the transformation be T, the plane before the transformation be Ax + By + Cz + D = 0 , and the plane after the transformation be A'x + B'y + C'z + D' = 0. Then:
Here we get the six frustum planes in the world frame.
With these equations, given a vertex, we can easily determine whether this vertex is visible. But as to our quad tree data structure, we need to determine whether a region (nodes in quad tree) is visible, therefore, additional calculation is necessary. In figure 9, we illustrate the three kinds of relationships between the region and the frustum.
The region of our node is not regular, so we define a bounding box for each node. The bounding box is then used to determine the visibility of the node.
Figure 9. Relationship between frustum and region
6. Program Specification
Main classes and functions in this program are listed below.
7. Further Discussion
You might have noticed that at the boundary of two triangles with different resolution, there will be a “T” crevasse. As shown in Figure 10. It is not obvious in the frame displaying mode, but really cause a problem in surface shading mode with textures.
Figure 10. Problems in rendering
There are a few ways to eliminate this problem. In Figure 10(c), we add a new edge at the crevasse, so that we split the larger triangle into two smaller ones, and the common boundaries now merger together. Another solution is as shown in Figure 10(d) that instead of adding a new edge, we delete an edge. It is more complicated to implement the first method, but it is conservative, because the levels of detail between the two sides of the crevasse could be arbitrarily large.
The second method constrains that the difference of the levels of detail between two neighboring patches should be no more than 1. But this method is much simpler and more regular to implement. We tend to use the second approach in our program. And we have worked out a scheme to achieve this. But due to the time limit, we have not plugged the idea in the code, and it would be in the next version of our program.
Figure 11 describes an example that how we will render the triangle fan without having crevasses. In the figure, the grey area is now actually being rendered. First it is guaranteed that the four corner vertices of the current node are rendered in the triangle fan. For the four edge vertices, we have to check the neighboring node of the current node, because the edge is shared among the nodes. If the neighboring node is a leaf, we would not use this edge node in the triangle fan as shown in the edge marked with “x”.
Figure 11. Render nodes as triangle fan
Now we have to update the quad tree. Different from the solution given in Section 4 and 5, we now have a new constraint. That is for any neighboring nodes, depth in the tree should not be larger than 1, otherwise we will have crevasses at the region boundary defined by the two nodes. Figure 12(a) is a legal quad tree example, while Figure 12(b) is not.
Figure 12. Legal and illegal quad tree.
The most common way to maintain the correctness of the quad tree, we have to traverse the nodes twice, with the second pass change the incorrect nodes.
However, we propose a more efficient way – width-first traverse over the tree. To be more specific, we generate all nodes at the same depth level at the same time. We have to keep two queues, one of which stores the list of nodes being processed at current time, and the other queue keeps all child nodes generated by processing the current nodes in the first queue. After all the nodes in one level have been processed, we swap the two queues and move to the next level. So we only have to traverse the tree once, and this pass can also be combined with rendering process, which is more efficient. For nodes at finest resolution or nodes that do not need to be further subdivided, we can directly send them down to rendering pipeline. For invisible nodes, we prune them away by simple deletion.
In this final project, after a larger amount of reading and survey over current technologies on terrain rendering, we use a quad-tree based LOD algorithm to reduce the rendering of triangles. Although there are many papers on this issue, the choice between these methods to fit the specific application requires thorough consideration. Also it takes time to combine all the techniques together. We introduce some other technologies such as view- dependent culling to improve the rendering rate without decreasing realism. Due to the time limit the proposal in section 7 dealing with the crevasse problem has not been implemented in LOD version 1.0. But we are sure that this idea works, and will definitely add it into the next version of this program. We have learned a lot through this project such as how to put theories such as data structure and Computational Geometry algorithms into practical applications.
 Computer Graphics, Chapter 4, Tsinghua University Tele-education.
 Bryan Turner, Realtime Dynamic LOD Terrain Render With ROAM
 Hugues Hoppe, Smooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering, Microsoft Research
 P.Lindstrom and V.Pascucci, Terrain Simplification Simplified: A General Framework for View-Dependent Out-of-Core, Lawrence Livermore National Laboratory May 8, 2002
 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
 Stefan Röttger , Wolfgang Heidrich and Philipp Slusalleck,Hans-Peter Seidel, Real-Time Generation of Continuous Levels of Detail for Height Fields , University Erlangen-Nürnberg
 Louis Castle, Jonathan Lanier and James McNeill, Real-time continuous level of detail (LOD) for PCs and Consoles, Technical Presentation GDC 2000
 Thatcher Ulrich, Continuous LOD Terrain Meshing Using Adaptive Quad-trees www.Gamasutra.com
 P Lindstrom and V.Pascucci, Visualization of Large Terrains Made Easy, Lawrence Livermore National Laboratory August 7, 2001
( The program has been tested under Windows XP system, with OpenGL and MFC 6.0 )
1. Run the program
2. Open a Terrain Image
3. Terrain Trackball
4. Terrain Interface
5. Here are some screen clips of the application