This page has moved
I left CMU at the end of July 1999 and am now an
assistant professor in the
Department of Computer Science
at the University of Illinois at Urbana-Champaign.
This page has been relocated to:
http://www.uiuc.edu/~garland/software/scape.html
While this page page will continue to be available at this location,
it will no longer be updated.
Terrain Simplification
The image above generates an interesting optical illusion. The
terrain in the middle is tilted (as per the offical Carnegie Mellon
logo). The surrounding black rectangle is an axis-aligned rectangle. But,
it looks slanted too. Nifty!
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:
- The source distribution contains both
the Scape software and the Crater Lake sample terrain.
- 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.
I have the following software available for download:
Michael Garland
garland@cs.cmu.edu
Last modified: Fri May 29 11:13:43 EDT 1998
|