A Greedy, Bottom-Up, Algorithm Using Quadtrees for Decimating Topologies via Steiner Triangular Meshes

by Jack Perdue


This project started out a great many years ago as quest for a visual representation of the Mandelbrot set that you could "fly" through. Although the Mandelbrot set is infinitly complex in places, I just wanted something that would be a bit more emersive than a flat image. Since the game Quake offers a fast rendering engine at a fairly low price (that I had already paid to play the game), and since I'm somewhat familiar with the construction of Quake maps (see BMP2MAP and BB32CTF0) I thought I'd try to create a Quake map of the Mandelbrot set.

Generating a grid of Mandelbrot set data was easy enough (done that one enough times). The question then became how to use these "elevations" (actually the number of iterations before divergence) to create a 3D landscape. Triangles from a grid are a pretty common approach so I started in that direction. I figured I could triangulate the grid and then create convex "brushes" (brushes are defined by an enclosing region of half-planes -- convex because that's a requirement of Quake) by using the triangles as the topmost face of a five sided brush (top/3sides/bottom). Of course, creating a complete (Steiner) triangulation with lines between each point on the grid was going to create way too many triangles/brushes for Quake.

So, given a grid of Mandelbrot set "elevations", how to create a triangulation of the "terrain" that would bring the triangle count down to an acceptable level.

I did a little research. Read a paper by Schroeder, Zarge and Lorensen entitled Decimation of Triangle Meshes. Looked at a decimation project out on the web. Read a paper by Garland and Heckbert entitled Fast Polygonal Approximation of Terrains and Height Fields.

Everything I looked at seemed a bit more complicated than what I needed (silly me). It seemed to me that if you started with a square grid fully triangluated, you could just repeatedly try to combine triangles that shared a similar plane until no combinations could be done without violating a prespecified tolerance for error.

So, how to do this simply? For now, the best explanation starts in the documentation of the Mesh class. The "See Also:" links provide further information.

The end result (after 500+ hours spent in two months time writing a half a million bytes of source code -- thus the "silly me" above) is what I believe to be a linear time mesh decimation algorithm. It doesn't have the best end results, but it does guarantee a level of accuracy and it is fast. Since it relies upon a recursive algorithm using quadtrees and makes locally greedy decisions, I believe it to be ideal for a parallel environment. Although not currently coded that way, it should take a minimum amount of effort to fork off the mesh creation algorithm to 4, 16, 64 or 256 processors. Because the structure is a quadtree, the generation of an image can be forked off in the same way. By creating a pipeline of images of decreasing error between the mesh decimator and the mesh renderer, new unprocessed (raw) terrain data could be quickly put on the screen at increasing levels of detail.

It has one problem to work out at the moment in that the locally greedy part of the algorithm creates "seams" between neighboring meshes. I'm presently working on a linear time fix for this, though it has one little tiny bug at the moment (which may or may not make it possible).

I originally coded the triangle decimation algorithm and Quake map conversion in C because: a) I'm more comfortable with my 10 years of C programming than my 4 months of Java coding, and b) I had preexisting C Quake map code that could easily be converted for this project. I wrote a simple triangle viewer in Java that allowed me to see the triangulations. Once the map conversion was working, I could look at the results in a Quake map editor. But I wanted this to be able to be run over the Internet, and I had the algorithm working for the most part, so I converted it over to Java. Once I had it working for the Mandelbrot set I adapted it to handle other terrain data as well, specifically 5-minute elevation data from NOAA (see below).

See the Documentation link below for complete (javadoc created) documentation of every variable/method/class/interface/package of this program.

There are screen shots of the program and a sample Quake level at the very bottom of this page if you are Java/Quake-less.

Known bugs/issues

Sample Data

Memory Requirements

Although this algorithm uses what I believe to be linear space, each point on the grid requires about 300 bytes of memory. On my system (48MB RAM/128+ swap), grid sizes of more than 257x257 cause excessive swapping. Grids in excess of 129x129 require the use of the "-mx" option on the Java Interpreter. I've been typing "java -mx64m Mesh00" to run this at home. If you use appletviewer, you can use the command line below. Have no idea of the limitations or workarounds of/for Netscape Navigator 4, but the 257x257 grid seems to work without any problems.

Viewing Quake .MAPs

On Unix, you might try ICE, an X Quake .MAP editor. Under Win95, see the Essential Files link at that ol' Ag Redwood's Page Personally, I use WorldCraft.


Complete documentation of this program is available here (stored offsite to comply with deparmental web quota).

How to Run

Detailed instructions on running this program are available here.
Last updated: July 12, 1998
Jack Perdue/
Department of Computer Science
College of Engineering
Texas A&M University

Screen shot  - Mesh00 - The Mandelbrot Set Screen shot - Quake - The Mandelbrot Set Screen shot - Mesh00 - padova65 Screen shot - POVRay - padova65 from above Screen shot - POVRay - padova65 looking northwest from the sea Screen shot - Mesh00 - texas257a Screen shot - Mesh00 - About Mesh00