Scape 1.2

(released August 29, 1997)

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 moved on to broader simplification issues. In particular, I focused on simplifying arbitrary polygonal models. The result of that research was the QSlim simplification package.

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.

The newer QSlim package is based on my quadrics-based simplification algorithm. For any given terrain data set, the QSlim software is likely to be slower and use more memory than the Scape software. However, it is also likely to produce a higher-quality approximation. And of course it can also simplify a much broader range of surfaces: it can process any triangulated surface rather than just a regular grid of height samples.

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
• Text
• Color plate
• PDF

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. The most current version of this survey was published in the SIGGRAPH 97 course notes [PDF]

Version History

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.

New 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. 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 with the understanding that it is unfinished. You’re free to use it, but you use it at your own risk.

Download

I have the following software available for download:

• QSlim surface simplification software
• Scape 1.2 source distribution [tar.gz file] [zip file]
• Scape sample terrains [tar.gz file] [zip file]
• Terra 0.7 source distribution [tar.gz file] [zip file]