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.