(Released January 19, 1996)
This software is in the public domain and is provided AS IS. Use it at YOUR OWN RISK.
This is Terra, the successor to Scape. Not only is this software UNSUPPORTED, but it is incomplete and may still have bugs. However, the basic mechanisms do function properly; I have run several large terrains through Terra, and the results were correct.
For the latest releases of Terra, Scape, and related packages, see:
This is Terra, a program for generating polygonal approximations of terrains and other height fields. It is based on algorithms described in:
Fast Polygonal Approximation of Terrains and Height Fields
by Michael Garland and Paul Heckbert (Technical Report CMU-CS-95-181).
A color plate is included separately.
The Scape package is the companion software for this paper. It was written with speed and memory efficiency as the primary concerns. Although it was designed strictly for the testing of the algorithms described in our paper, we made it available so that people interested in our results could examine it. We also hoped that it might be of interest to people who were attempting to build terrain approximations. However, Scape is not particularly easy to use and the code is definitely less than aesthetically pleasing.
I wrote Terra because I was dissatisfied with Scape. I wanted code which was better structured and programs which were easier to use.
Disclaimer: Please remember that both Terra and Scape are unsupported programs.
Terra uses the PGM file format for data input. At first, this might seem odd; however, it has several advantages. PGM is a standard format which provides for both textual (i.e., human editable) and binary data files. Since PGM is an image file format, height field data is directly viewable with most available image viewers. Plus, there are many programs available to perform various manipulations on PGM files.
In particular, many of the tools provided by the NetPBM package can be used to manipulate PGM terrain data. The NetPBM package can be found online at:
or by anonymous ftp to:
Terra can output its approximations in several different formats. The supported formats are described below.
Terra supports preinsertion scripts and importance masks. See below for details on what these are and how they work.
The interactive program,
xterra, uses the GLUT library for
windowing and OpenGL for rendering. In theory, this should make it
portable to machines other than SGI’s.
All these features are currently missing. Ideally, I would like to include these and other features. In reality, what gets done and how fast it gets done might be highly variable.
xvprogram will insert a comment in the PGM file citing itself as the creator of the file. You will need to remove this comment from the file.
In order to compile the interactive version of Terra (
must obtain the GLUT library. It can be found at:
or by anonymous ftp at:
NOTE: For proper viewing,
xterra needs to set the aspect ratio of
its windows. This is currently not supported via GLUT. Therefore,
I’ve had to hack things a bit by accessing GLUT internals. The file
gui.cc includes the glutint.h header. This is not installed by GLUT.
You must install this manually. Again, this is only of importance if
you want to build
Edit the Makefile for local customization. Basically, you should set
the compilation flags, the libraries you need, and the location of
GLUT if you are compiling
make‘ will build both
xterra. However, you
can selectively compile either of them (e.g., ‘
The Terra software provides two programs:
terra, a simple batch
xterra, an interactive application which uses OpenGL to
display the surface approximation being constructed. Both programs
utilize the same command line interface;
xterra simply layers an
interactive interface on top of
terra. This section contains an
outline of the operation of
terra. All this information applies to
xterra as well.
The operation of Terra goes through a simple series of phases:
Currently, all the information Terra needs to run is communicated on the command line. The correct usage of Terra is:
usage: terra <options> filename where <options> is some combination of: -e <thresh> Sets the tolerable error threshold -p <count> Sets the maximum number of allowable points -o <file> <type> When finished, output the approximation to <file>. Valid types: tin, eps, dem, obj -m <file> Load the importance mask from <file> -s <file> Execute preinsertion script from <file>
The error threshold and point limit set the termination criteria. Terra will continue adding points as long as it it below the point limit and above the error threshold. The default error threshold is 0; the default point limit is the total number of points in the input grid.
The type of output desired is also specified on the command line. The
eps output format simply generates an Encapsulated PostScript
rendering of the approximation mesh. The
dem output format creates an
approximate DEM from the approximate mesh. This can be useful for
comparison with the original. Both the
obj output formats
generate 3D surfaces. The
obj format is just the Wavefront
tin format is a very simple model description; it is a
series of lines where each line is of the form:
t x1 y1 z1 x2 y2 z2 x3 y3 z3
Each such line describes a triangle with the three corners (x1,y1,z1) (x2,y2,z2) (x3,y3,z3). The remaining options, involving importance masks and preinsertion scripts, are described in detail below.
xterra accepts the same options as
terra and operates in much the
same way. It introduces one extra command line option:
-h <factor> Sets the height scaling factor. For example, if grid points are 25m apart, use a factor of 0.04
This is used to properly scale the display of the height field in 3D. The input to Terra is specified in pixel coordinates; data samples are taken at integral pixel coordinates. However, the height values are probably not given in pixel coordinates. So, for display purposes, the height values are scaled by a constant factor to account for this loss of units in Terra.
xterra starts up, it performs any preinsertion actions that you
request, and then it displays two windows: a mesh view and a surface
view. It does not perform greedy insertion until told to do so. The mesh
view provides a 2D view of the triangulation being generated for the
approximation of the height field. The surface view displays the
approximate surface in 3D. The interaction with these windows is
currently quite simple. Here
is an outline of how they work at the moment:
Surface view: Left mouse drag : spin the surface Middle mouse drag : translate the camera side to side Right mouse drag : move the camera in and out Mesh view: Left mouse click : insert a point at the mouse location Middle mouse click : run greedy insertion until goal is met Right mouse click : popup menu -- allows output
As stated above, Terra uses PGM files to read and write height field
data. Unfortunately, Terra does not as yet provide any direct means of
acquiring PGM data. For now, you will have to use the conversion
software provided with Scape. The
distributed with Scape can convert Scape’s STM file format into PGM’s
appropriate for use with Terra. Given an STM file,
stm2pgm sample.stm exact > sample.pgm
will generate a PGM file. Note that the keyword
exact is very
important. Don’t forget it! The resulting file will be textual, so you
can even edit by hand if you need to.
One of the new features in Terra not found in Scape is the use of importance masks. In order to determine the next point for insertion, Terra ranks the available points by an importance measure. Importance masks allow you to bias this ranking. For each data point, the mask assigns a weight in the range [0..1] which multiplies the computed importance value.
Importance masks are PGM files, just like the height field input. However, their interpretation is slightly different. The input values are all integers. They are scaled such that their maximum value will be mapped to 1. One significant point is that this maximum value is taken from the PGM header, not determined from the data. Therefore, by controlling the stated “maximum”, you have much greater flexibility over the mapping of PGM pixel values to importance mask weights.
Currently, no means for constructing importance masks is provided.
The other new feature of Terra is its support for preinsertion scripts. An important feature of the greedy insertion algorithm is that essentially provides for progressive refinement of the approximation. Thus, the initial approximation can be arbitrary. The preinsertion scripts allow you set up an approximation before greedy insertion begins.
A preinsertion script is a series of lines, each of the form:
<op> X Y
The values for
Y are the coordinates of a particular data
point. The currently supported opcodes are:
s – Select this point for use in the approximation and insert
it into the current mesh.
i -- Mark this point as one to be ignored. Terra will never process this point for insertion or evaluation. u -- Mark the height value at this point as unknown.
Currently, Terra makes no distinction between points to be ignored and points whose height value is unknown; it ignores them equally.