Terrain Simplification

I spent a year or two working on issues relating to terrain simplification. The result was a paper and the Terra/Scape programs. However, I've moved on to other topics. I'm currently focused on simplifying arbitrary polygonal models. To find out about my current research, you can visit my page on multiresolution modeling .

I have not done any real development on my terrain software since January 1996, and I am unlikely to have any time to work on it any time soon. However, I have made a few small improvements now and then.

NEW: A whole new system for simplifying arbitrary polygonal models. See "QSlim" below.

NEW: A slightly improved version of scape is available (see below for details).

IE4 Users: A few people have reported problems downloading files with multiple periods in the file names using Internet Explorer 4. The download section below has links to IE-friendly zip files.

Papers

The algorithms used in the Scape software package are described in the paper Fast Polygonal Approximation of Terrains and Height Fields, by Michael Garland and Paul Heckbert. Abstract. Postscript files: pages 1-36 (black & white), page 37 (color). Also available as a single PDF file.
Errata: The figures of Crater Lake incorrectly show the actual terrain flipped upside down.

      A related paper, Survey of Polygonal Surface Simplification Algorithms, by Paul Heckbert and Michael Garland, is also in the works. At one point, this was a companion paper for the one above which focused on various algorithms for terrain simplification. However, it has since evolved into a more general survey of surface simplification algorithms. It will be available by Summer 1997.

Software: QSlim

As I've mentioned above, it's been quite some time since I was actively developing my terrain simplification software. Instead, I have been working on the problem of simplifying arbitrary 3D polygonal models.

      In October 1997, I released the first version of my QSlim software. It is based on the technique of surface simplification using quadric error metrics. It is not as fast and not as space-efficient as Terra/Scape, but it can simplify a much broader range of models. I am still actively developing both the simplification algorithms and the software implementation of QSlim.

Software: Scape

The most recent version of Scape is version 1.2. It was released August 29, 1997. Scape is distributed in two pieces:

1. The source distribution contains both the Scape software and the Crater Lake sample terrain.
2. A collection of further samples is also available.

The following changes were made in Scape 1.2:

• The data-dependent triangulator now supports the Angle Between Normals (ABN) metric. This is primarily for comparison purposes. It can be a useful heuristic for smooth surfaces, but it does not perform particularly well on terrain surfaces.

• Fixed division-by-zero bug in data-independent triangle scan conversion. This didn't actually cause erroneous results; the result of the division by zero was never used. However, some systems halt with a floating point exception when it occurs.

The following changes were made in Scape 1.1 (released January 17, 1996):

• The EPS generated for mesh diagrams was very minimal and did not have the proper structured comments. It should now be more compliant.

• Important Fix: The Delaunay triangulator had a bug in the InsertSite routine which could cause exceedingly bizarre things to happen when near the boundaries. Due to the regular organization of points, this did not alter the resulting mesh. However, it did cause excessive useless computation. Note that this could result in incorrect behavior with arbitrary data sites. If you used this code in your own programs, use this new fix. See the file quadedge.C for details.

• Scape was being rather inconsistent about its choice of coordinate axes. The STM files should position (0,0) in the NW corner. The terrains were being displayed in world coordinates with (0,0) in the SW corner. This was resulting in "upside down" terrains. Consistency has certainly been improved, but there may be some lingering inconsistencies lurking around. Be careful!

• More conversion utilities are provided for using USGS DEMs. See the directory STM-tools/DEMutil.

• The TIN output format is not exactly a widely used standard. The program TIN-tools/tin2obj is a very simple-minded converter to create Wavefront .OBJ files from TIN files.

Software: Terra

In December 1995, I started working on an improved version of Scape, called Terra. This software is easier to use and easier to understand. The code is cleaner, and it actually supports some useful features that Scape does not.

      Terra was never actually finished, and I haven't had time to work on it for the past year. However, it should prove quite usable. You can find more details in the current documentation for Terra. If it sounds interesting, you're free to download the last snapshot of Terra 0.7 with the understanding that it is unfinished and may never be finished. You're free to use it, but you use it at your own risk.

Download Section