Levels of Detail (LOD) in Terrains – Sample implementation

14 Nov 2009

Currently I’m developing a small sample application for a seminar in computational geometry. A fellow student and I are working on the article

On Levels of Detail in Terrains
Mark de Berg, Katrin T. G. Dobrindt
Utrecht University, April 1995

It describes a method to speed up terrain visualization by generating a hierarchy of terrains, each level with a smaller set of vertices and triangles. A level is generated by removing an independent set of vertices and all incident triangles from the triangulation of the last level. For each of these vertices the incident triangles form a star shaped polygon. All star shaped polygons are retriangulated to fill the resulting holes. To avoid triangles with small angles, the Delaunay triangulation of each star shaped polygon is calculated.

When the hierarchy is generated, we can extract a combination of triangles from different levels to form a new triangulation of the terrain. That triangulation is the Delaunay triangulation of the extracted set of points. The extraction process can make use of different criteria. An example would be the distance from the viewer: close regions of the terrain would be rendered with high detail, regions farther away with lower detail.

The current version of the software does not implement all aspects of the method, yet. Implemented are:

  • Generation of random terrains.

Generated terrain with ~66k vertices

  • Visualization of the terrains using Java3D.
  • Construction of different hierarchy levels using a simple triangulation algorithm of
    ‘A review of two simple polygon triangulation algorithms’ by Thomas Teußl, June 3, 1998

The use of a simple triangulation algorithm shows why the authors of the original article proposed the Delaunay triangulation. Consider the following terrain (~4k vertices):

Terrain with ~4k vertices

In the following screenshot you can see a coarser level of the hierarchy generated by the sample application. There are many narrow triangles with small angles. These lead to a disturbed surface, as you see in the next image.

Terrain LOD - 4k vertices - level 10 - simple triangulation. Note the disturbed surface.

Currently we are working on the implementation of the Delaunay criterion and on the optimization of the code. Future versions will hopefully implement more aspects of the considered method.

Finally, the download link (requires: Java Runtime Environment, Java3D):