Here is another piece of code I have wrapped up. This time it is the terra algorithm by Michael Garland (PhD at Carnegie Mellon University if I have seen right on his home page :-). Terra takes a regular grid of height samples and creates a mesh containing an approximation of this data.
http://graphics.cs.uiuc.edu/~garland/software/terra.html
The approximation is done by triangulation using a greedy insertion algorithm described in this paper:
http://graphics.cs.uiuc.edu/~garland/papers/scape.pdf
In short, the algorithm starts with an empty mesh and inserts single vertices until a criterion is met. The vertex that gets inserted at each loop is the one with the biggest error (difference in height between original data and current approximation). The criterion can be either that the vertex budget is reached, or that the current error is smaller than a given threshold.
The result is a triangulated irregular network (TIN), with much less vertices than the original heightfield. Some screenshots:
Screenshot (textured):
http://www.dachau.net/users/pfrogner/tin1.jpg
Screenshot (wireframe):
http://www.dachau.net/users/pfrogner/tin2.jpg
Screenshot (untextured):
http://www.dachau.net/users/pfrogner/tin3.jpg
Demo (source and win32 binaries):
http://www.dachau.net/users/pfrogner/Demo-TIN.zip
Usage is quite simple, just set some parameters and then call decimate with the target filename (32 bit grayscale image recommended) and the destination filename (the egg file to be created). The main parameters are the point limit and the maximum error, as described above.
import tin
# Parameters for decimation
tin.setPointLimit( 10000 )
tin.setMaxError( 0.0 )
# Scale
tin.setVerticalScale( 60.0 )
tin.setHorizontalScale( 1.0 )
# Additional data to be created
tin.createTexcoords( True )
tin.createFaceNormals( False )
tin.createVertexNormals( True )
tin.createBinormals( False )
# Run
tin.decimate( 'models/elevation.png', 'models/elevation.egg' )
I didn’t change Michael Garlands code a lot, just remove a few parts, port some vector math to Panda classes, and change input and output. Input now uses the PNMImage class, so it can read virtually all images. Output creates a Panda EGG file (y-up coordinate system).
I don’t know if this wrapper might be usefull for anybody, and I don’t recommend to use it for game applications, but I still want to share it. It is quite old, and reducing the vertex count is no longer as important as it used to be some years ago, on the other hand I was impressed by the fact that good looking results can be achieved at using only one or two percent of the original vertices.
PS: For those who want to tinker with the code: It is easy to pre-insert vertices along the edges of the terrain, for building skirts that connect several patches of terrain at different resolution levels.
enn0x