Will, a computational scientist at GE's R&D Center, can be contacted at [email protected]. Tom, an adjunct assistant professor at Rensselaer Polytechnic Institute, can be reached at [email protected].
Computer-generated, interactive 3-D graphics is growing in importance and application. Many games and even sophisticated user interfaces are based on 3-D graphics technology. For example, Doom and Quake use 3-D graphics in combination with texture maps to create vivid, adrenaline-producing games. Web-based technology, such as VRML, enables users to fly through virtual worlds or interact with databases. The use of 3-D graphics is likely to explode as new software tools and graphics accelerators are introduced into the marketplace.
Unfortunately, a limiting factor in the use of 3-D graphics is the amount of data that must be processed, transmitted, and rendered. In our work environment, we bump into this limitation regularly: One of our applications involves visualizing the internals of aircraft engines and other mechanical devices. In this environment the database ranges in size from 10-100 million triangles, with the desired goal of flying through the data at 3-30 frames per second. You may have experienced similar limitations if you've ever tried to use VRML applications or to view VRML content on the Web. Many of these applications are far from interactive.
To address this problem, a relatively new field has emerged in computer graphics, often referred to as "triangle decimation" or "polygon reduction." The aim of these techniques is to reduce the number of polygons in a mesh while maintaining a good approximation of the original data. The focus of these algorithms is on polygons -- especially triangles -- because 3-D graphics accelerators are designed to process these geometric primitives. Triangles are used because surface primitives, such as polygons or splines, are triangulated before being handed off to the graphics hardware.
In this article, we will focus on a decimation algorithm that is fast, widely used, and for which source code is available. We will also show how it is used, and how to create a decimated VRML file.
Polygon Reduction Algorithms
Polygon reduction algorithms can be classified in two ways: whether they modify the geometry of a mesh, and whether they modify the topology of the mesh. When we say "mesh geometry," we mean the x-, y-, and z-coordinates of the vertices, while mesh topology refers to features like holes or handles (imagine a torus). Algorithms that modify the geometry of a mesh will create new vertices, or possibly move existing vertices to new positions. The advantage of modifying geometry is that vertices can be repositioned to give a better approximation of the original mesh. The disadvantage is that if attribute information like texture coordinates or color is associated with the vertices, it must be mapped to new values when the vertex location changes. Unfortunately, both the calculation of new vertex positions and attribute mapping tend to be expensive operations.
Algorithms that modify topology will close holes (imagine removing rivet holes in sheet metal), add holes or split the mesh, or even introduce nonmanifold attachments. An example of a nonmanifold edge is an edge shared by three or more triangles, rather than the usual two (interior edge) or one (boundary edge).
Most polygon reduction algorithms will preserve the topology of a mesh, but it is common to modify the mesh geometry. The decimation algorithm described here preserves both the geometry and topology of a mesh.
The Decimation Algorithm
The decimation algorithm performs a series of local operations on a mesh to gradually reduce the number of triangles and vertices. These operations are performed until the desired reduction is achieved, or until no more operations are possible due to topological or other constraints. As Figure 1 illustrates, there are three major steps in the process:
1. Classify a vertex according to its local geometry and topology. Classification also involves estimating the potential error introduced into the mesh if the vertex is deleted in steps 2 and 3.
2. Delete the vertex if it is of appropriate classification and if its error measure is less than some threshold value. Vertex deletion causes the removal of all triangles using the deleted vertex, and results in a "hole" in the mesh.
3. Patch the hole with a new triangulation. The net effect is two fewer triangles if the vertex is in the interior of the mesh; or one less triangle if the vertex is on the boundary.
The classification of a vertex depends upon both the local geometry and topology. For example, vertices that have an edge that is used by more than two triangles are considered nonmanifold. This is a topological classification. Feature edges are used for geometric classification. Feature edges are found when the normals of the two triangles on each side of the edge form an angle greater than a user-specified feature angle.
Vertex classification is important because, if done correctly, it can help preserve sharp edges and corners (edges and corners of a cube, for example). Feature edges are identified and the triangulation of the hole is controlled to preserve these sharp edges. Also, certain vertices, like nonmanifold vertices, are not deleted to ensure that the topology of the mesh is not modified.
An important feature of this algorithm is how the error is estimated. One simple measure of error is computing the distance from the original mesh to the decimated mesh after vertex deletion (essentially a measure of distance to plane). Obviously, if the triangles around a vertex all lie in the same plane, then the deletion of the vertex introduces no error. Or, if the vertex lies on the boundary of the mesh, the error measure is the distance of the new mesh edge to the deleted vertex (distance to edge). For more information on this algorithm, see "Decimation Of Triangle Meshes," by W.J. Schroeder, J. Zarge, W. E. Lorensen, Proceedings of Siggraph '91.
Applications
To demonstrate the application of decimation, we'll use the Visualization Toolkit (vtk) available at http://www.cs.rpi.edu/~martink/. Vtk is a C++ class library with a built-in Tcl/Tk interpreter for visualization and 3-D graphics, and includes source code, data, and many examples. The software runs on UNIX and Windows 95/NT. For more information, refer to The Visualization Toolkit: An Object-Oriented Approach to 3-D Graphics, by Will Schroeder, Ken Martin, and Bill Lorensen (Prentice-Hall, 1996 ). [Editor's Note: The Visualization Toolkit was reviewed in "Programmer's Bookshelf," DDJ, June 1997.]
In our first example, we'll decimate a CAD part that consists of 11,036 triangles. Listing One is the Tcl script that creates the results in Figure 2. Note that vtk uses a dataflow approach, or series of filters, to process the data. The first filter is a stereo-lithography reader. (Stereo lithography is a 3-D triangle format for reading and generating 3-D plastic parts.) Then, the decimation filter processes the triangles. Finally a mapper is connected to an actor, which represents the object in the rendered scene. The decimator is able to reduce the number of triangles to 1876, a total reduction of 83 percent. Note that the surface is rendered flat shaded to exaggerate the effects of the decimation.
An instance of the vtkDecimate class in Listing One is inserted into the visualization pipeline immediately after the reader object. Three important attributes to this class are the TargetReduction, ErrorIncrement, and MaximumIterations instance variables. TargetReduction specifies the reduction level desired. The algorithm attempts to meet this level of reduction, but, in some cases, topology limitations or error limits prevent it. The ErrorIncrement ivar is the amount the allowable error is incremented each iteration of the algorithm. Finally, the MaximumIterations limits algorithm execution in case the requested reduction cannot be achieved.
In the next example, we'll decimate a range image derived from a 3-D Cyberware laser digitizer. The digitizer can generate meshes of 1 million triangles in 15-30 seconds. It also captures the color of the surface which is applied as a texture map. (The data shown is a scan of our friend Fran's face when he happened to wander into the lab one day.) Figure 3(a), the original mesh, consists of 52,260 triangles, while Figure 3(b), the final one, consists of 2562 triangles -- a 95 percent reduction. Figure 3(c) shows the edges of the triangles. In the original mesh, the edges were so dense that even a wireframe rendering of the surface appeared solid. Listing Two is a Tcl script that creates the images.
This example demonstrates the ability of surface texture to hide low-resolution geometry. Most interactive games make extensive use of texture to add detail to images. In fact, many 3-D graphics boards available on the PC are targeted toward low polygon count/textured surfaces. These boards do not perform well when the polygon count becomes large, since point transformation is often not accelerated.
In our final example, we'll parse a VRML 1.0 file, decimate the geometry, and then export the geometry using the vtkVRMLExporter. The parser was built using the QvLib parsing code developed by Gavin Bell and Paul Straus of SGI. The code currently reads in a VRML 1.0 file and creates an in-memory scene graph of the geometry. The system will decimate any IndexFaceSet geometry nodes that exist in the file by placing a vtkDecimate object in the final rendering pipeline. The system then collects all geometry nodes, triangles and others, displays the resultant decimated geometry and outputs a VRML 2.0 file if specified on the command line.
The main function of the system is to translate the VRML scene graph into an object-oriented vtk scene. The translation encapsulates the scene graph by moving properties and transforms from hierarchical scene graph dependencies into encapsulated object pointers. This allows objects to implicitly represent themselves to external manipulators, an important feature for large-scale object systems that have many objects with multiple manipulators.
As these IndexFaceSet nodes are rendered in the object-oriented model, the decimate object takes the original triangles and outputs the decimated equivalent. Other shape nodes, such as Cones and Cubes, are ignored since the browser is responsible for generating an optimal rendering solution for the specific shape.
Testing has shown that some VRML polygonal models can be reduced by 20-60 percent with little apparent visual change. Decimation can be used to automate the generation of multiple representations of an object for the VRML level of detail node. The result of one decimation is in Figure 4, which shows the original and decimated versions in SGI's Cosmo VRML viewer.
You can find the VRML decimator code at http://www.rpi.edu/~citrit/, plus additional examples and results. There are options to set parameters for the decimation algorithm via the command line. The code is available as a C++ distribution and requires vtk to be preinstalled. If you do use the VRML decimator, you will need a VRML browser to view the resulting models.
Conclusion
Triangle decimation algorithms play an important role in maintaining the responsiveness of 3-D graphics systems. By reducing data size, these algorithms minimize the amount of data to be stored on disk or in memory, transmitted across the network, and rendered by the graphics system. By compressing 3-D graphics data using triangle decimation, you can often squeeze out the last ounce of performance, which can make the difference between an engaging interactive system or one that annoys users.
Listing One
catch {load vtktcl}# get the interactor ui
source vtkInt.tcl
# Read in CAD part
#
vtkSTLReader sr
sr SetFileName "../../data/42400-IDGH.stl"
vtkDecimate deci
deci SetInput [sr GetOutput]
deci SetTargetReduction 0.9
deci SetErrorIncrement 0.002
deci SetMaximumIterations 8
deci DebugOn
vtkPolyMapper stlMapper
stlMapper SetInput [deci GetOutput]
vtkLODActor stlActor
stlActor SetMapper stlMapper
</p>
# Create graphics stuff
vtkRenderMaster rm
</p>
# Now create the RenderWindow, Renderer and both Actors
set renWin [rm MakeRenderWindow]
set ren1 [$renWin MakeRenderer]
set iren [$renWin MakeRenderWindowInteractor]
# Add the actors to the renderer, set the background and size
$ren1 AddActors stlActor
$ren1 SetBackground 0.1 0.2 0.4
$renWin SetSize 450 450
</p>
vtkCamera cam
cam SetClippingRange 2.21973 110.986
cam SetFocalPoint 128.766 86.0079 224.742
cam SetPosition 133.866 68.8423 211.626
cam SetViewAngle 30
cam SetViewPlaneNormal 0.2298 -0.773329 -0.590893
cam SetViewUp -0.0185622 0.603548 -0.797111
$ren1 SetActiveCamera cam
</p>
# render the image
$iren SetUserMethod {wm deiconify .vtkInteract}
$iren Initialize
</p>
# prevent the tk window from showing up then start the event loop
wm withdraw .
Listing Two
catch {load vtktcl}
</p>
# this is a tcl version to decimate fran's face
# get the interactor gui
source vtkInt.tcl
</p>
# create visualization pipeline
# create decimated model with surface normals
vtkCyberReader cyber
cyber SetFileName "../../data/fran_cut"
vtkDecimate deci
deci SetInput [cyber GetOutput]
deci SetTargetReduction 0.95
</p>
deci SetErrorIncrement 0.002
deci SetMaximumIterations 8
deci DebugOn
vtkPolyNormals normals
normals SetInput [deci GetOutput]
</p>
# ingest image and apply as texture map
vtkPNMReader pnm
pnm SetFileName fran_cut.ppm
vtkTexture aTexture
aTexture SetInput [pnm GetOutput]
aTexture InterpolateOn
</p>
# map to graphics system
vtkPolyMapper cyberMapper
cyberMapper SetInput [normals GetOutput]
vtkActor cyberActor
cyberActor SetMapper cyberMapper
cyberActor SetTexture aTexture
</p>
# Create graphics objects
vtkRenderMaster rm
</p>
# Create the RenderWindow, Renderer and both Actors
set renWin [rm MakeRenderWindow]
set ren1 [$renWin MakeRenderer]
set iren [$renWin MakeRenderWindowInteractor]
</p>
# Add the actors to the renderer, set the background and size
$ren1 AddActors cyberActor
$ren1 SetBackground 1 1 1
$renWin SetSize 450 450
</p>
# Define method to invoke when "u" is pressed in graphics window
$iren SetUserMethod {wm deiconify .vtkInteract}
</p>
# Define nice view
vtkCamera cam1
cam1 SetClippingRange 0.0475572 2.37786
cam1 SetFocalPoint 0.052665 -0.129454 -0.0573973
cam1 SetPosition 0.327637 -0.116299 -0.256418
cam1 CalcViewPlaneNormal
cam1 SetViewUp -0.0225386 0.999137 0.034901
$ren1 SetActiveCamera cam1
</p>
$iren Initialize
</p>
# prevent the tk window from showing up then start the event loop
wm withdraw .
</p>
</p>
DDJ
Copyright © 1997, Dr. Dobb's Journal
