IBM Data Explorer modules such as Rubbersheet and Isosurface generate polygonal meshes (vertices connected by quads or triangles). Many times these meshes contain a very large number of polygons, and it becomes desirable to reduce the number of polygons before final rendering. This module will reduce the number of triangles in a triangle mesh, providing a good approximation to the original geometry while preserving the original topology of the object.
This module uses the triangle decimation routine found in the vtk library (The Visualization Toolkit, copyright 1993-1995 by Ken Martin, Will Schroeder, and Bill Lorensen). You will need to build the vtk library before attempting to compile this module. The original paper describing the decimation algorithm, "Decimation of Triangle Meshes" by Schroeder, Zarge, and Lorensen, can be found in the July 1992 issue of Computer Graphics (SIGGRAPH '92 Conference Proceedings) on page 65. The campanion book for the vtk library, "The Visualization Toolkit, An Object-Oriented Approach to 3D Graphics" (Prentice Hall, ISBN 013199837-4), should be in print by Feb. 1996.
You will need a C++ compiler to build the libvtk software and the vtkDecimateDX module. The Makefile in this archive may have to be modified to support your particular workstation and software installation. Such modifications should be fairly straightforward; consult the DX Programmer's Manual for more information.
The description of this algorithm is taken directly from the vtkDecimate man page included with the libvtk distribution.
Each vertex in the triangle list is evaluated for local planarity (i.e., the triangles using the vertex are gathered and compared to an "average" plane). If the region is locally planar, that is if the target vertex is within a certain distance of the average plane (i.e., the error), and there are no edges radiating from the vertex that have a dihedral angle greater than a user-specified edge angle (i.e., feature angle), and topology is not altered, then that vertex is deleted. The resulting hole is then patched by re-triangulation. The process creates over the entire vertex list (this constitutes an iteration). Iterations proceed until a target reduction is reached or a maximum iteration count is exceeded.
There are a number of additional parameters you can set to control the decimation algorithm. The error may be increased over each iteration with the error increment. Edge preservation may be disabled or enabled. You can turn on/off edge vertex deletion. (Edge vertices are vertices that lie along boundaries of meshes). Sub iterations are iterations that are performed without changing the decimation criterion. The aspect ratio controls the shape of the triangles that are created, and is the ratio of maximum edge length to minimum edge length. The degree is the number of triangles using a single vertex. Vertices of high degree are considered "complex" and are never deleted.
This implementation has been adapted for a global error bound decimation criterion. That is, the error is a global bounds on distance to original surface.
The following is a brief description of the input and output connections found in the vtkDecimateDX module. For detailed information, refer to the article in Computer Graphics referenced in the Overview section above.
Here is the screen dump of a sample DX network used to decimate and render a terrain model created with USGS DEM data and the Rubbersheet module.
