Early Terrain Investigations

Early in the SceneGraph project, it was recognized that quality terrain loading and rendering was a requirement. This section shows the early progress of loading a DEM terrain, as capabilities were added to the Scene Graph. (Much of the technology that was developed for terrain loading was later advanced and adapted to perform as a terrain loader for the Carbon Graphics GEO modeler. Therefore, most terrain loading is now done via the GEO loader.) The terrain was converted from DEM to a raw heightmap, using a utility I wrote as part of another project. The raw height map (16-bit values per height sample) were loaded using a height map loader in the Scene Graph. Most of the work seen in the following images was done by the loader at load time. With terrain, this would normally be done with a terrain editor, but this offers a certain level of flexibility, but expense at load time. The terrain is a DEM of part of Cleveland, sub-divided into cells which are 50x50, resulting in 400 cells. A god's eye view of the terrain is below, and the same view with the bounding sphere's of the cells visible.

After loading the terrain, static shadows and sun lighting were added as per vertex colors.	Then a desert texture was added modulated with the lighting information.
Next, the vertex normals smoothing was added to help hide some of the gouraud shading/lighting artifacts.	Finally a sky dome was added for effect.

Static Detail Algorithm: Delauney Triangulation

At the end of this first phase, the entire terrain was 2 million triangles, and the view shown was culled down to 678k triangles, all in triangle strips. Since we were not taking advantage of the regular nature of the terrain sampling (like ROAM would), it made sense to reduce our triangle count, by eliminating the redundant triangles.

Delauney triangulation was added to the loader. Vertices are added to the triangulation if their height differs from the last one added in the x and y directions by more than a specific threshold. (Differences in color/texture should also be considered but it hasn't been added yet.) Each cell is triangulated independently, and the all of the border vertices are kept in the triangulation, to avoid T-vertices and cracking between cells.

The wireframe view shows the triangle irregular network, resulting from the height map simplification and delauney triangulation process. A cell boundary is visible on the left side of the screen heading off into the scene.

The same view as the final view in phase 1, except with less than 1/3rd the triangles. 210k triangles.

As the results above show, the terrain was reduce to 694k triangles from 2 million, using a rather small height difference threshold (3 height units.) The results look pretty good and perform well. Delauney triangulation has a couple short comings. One, it takes a little bit of time to compute, so it isn't best used at load time, but it doesn't take that long. Two, it produces triangles, which increases the amount of vertices transformed. To minimize this last point, the heightmap loader uses the Scene Graph's Strip Builder object to generate triangle strips out of the Delaunay triangulations.

Dynamic Detail Algorithm: ROAM

An implementation of the ROAM algorithm, influenced by the work of Seumas McNally, was added to the scene graph. The algorithm uses a variance metric and distance to the eye point to determine whether to split or not. The terrain is reset and resplit each frame, using the culling engine to eliminate the cells that don't need to be split that frame.

Dynamic ROAM tessellation resulting in 69k polygons.	The same 69k polygons rendered with sunlight and texturing. Some detail has been sacrificed, but this is controlled by the variance parameter.
A higher quality ROAM tessellation, producing 198k polygons.

The ROAM algorithm allows increasing the quality of the terrain based upon machine, and scenario. The triangle budget for a frame is spent on closer and more important triangles than in a static detail agorithm. The splitting for each frame is offset by the reduced number of triangles that need to be rendered.

The regular sampling nature of ROAM, like Quad-tree approaches, restricts some of the usefulness of the algorithm. It is well suited for gaming where exact precision is not required and databases/features can be tweaked to get the desired results. GIS applications with feature data, and their precision needs, will probably not find as much use for ROAM. TINs and their specific LOD techniques are more applicable to those applications.

Next Phases: Future work in this area will include view dependent progressive meshing, and comparing a few TIN LOD techniques.

glenn@raudins.com