## Description

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

• There is a flaw in my analysis of runtime, but I haven't figured it out yet. There is no way this is linear time but my several approaches at analyzing keep coming back to that so there is something fundementally wrong in my analysis.
• Seams aren't perfect... still working on it. I think I'm going to have to be less greedy (i.e. not) in the "fix seams" stage.
• The mesh panel doesn't always completely repaint itself after a dialog box has been displayed. Resizing the frame is a simple fix for now.
• The Quake .MAP conversion has been implemented but, depending upon the parameters you use in the program, QBSP.EXE may or may not like the created .MAP. This is going to require some input from someone more familiar with the working of QBSP.EXE and the Quake engine than I. Hopefully someone can make some recommendations on how to improve the resulting .MAP. I haven't actually solicited help on this yet since I want to see how the seam fix affects the problem (and basically lock-down the code) before seeking suggestions.

## Sample Data

• Previously generated sample data that was here is gone... there's sample data built in now. Depending upon your system, the larger data files (ending in "257") may seriously slow down your system. See Memory Requirements below.
• You can decimate any part of the world via data available at NOAA's National Geophysical Data Center (again, see memory requirements below). You have to use the ASCII format (not the default).
• Since this program works on square grids of size 2^k+1, you'll want to try to specify latitudes and longitudes such that the minimum sized side is just over a power of 2. Since there are 12 "five-minute" points per degree, I've found that a delta of 22 degrees longitude/latitude makes for nice 257x257 grids. I used delta = 11 for 127x127 grids.
• Once you've generated the ASCII file, you can read it directly from NOAA's ftp server via the applet's Open URL menu.

## 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.

## Documentation

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/jack@cs.tamu.edu
Department of Computer Science
College of Engineering
Texas A&M University