Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼


Decimating Polygon Meshes

Dr. Dobb's Journal July 1997: Decimating Polygon Meshes

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.


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.


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

# Create graphics stuff
vtkRenderMaster rm

# 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

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

# render the image
$iren SetUserMethod {wm deiconify .vtkInteract}
$iren Initialize

# prevent the tk window from showing up then start the event loop
wm withdraw .

Back to Article

Listing Two

catch {load vtktcl}

# this is a tcl version to decimate fran's face
# get the interactor gui
source vtkInt.tcl

# 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

    deci SetErrorIncrement 0.002
    deci SetMaximumIterations 8
    deci DebugOn
vtkPolyNormals normals
    normals SetInput [deci GetOutput]

# ingest image and apply as texture map
vtkPNMReader pnm
    pnm SetFileName fran_cut.ppm
vtkTexture aTexture
  aTexture SetInput [pnm GetOutput]
  aTexture InterpolateOn

# map to graphics system
vtkPolyMapper cyberMapper
    cyberMapper SetInput [normals GetOutput]
vtkActor cyberActor
    cyberActor SetMapper cyberMapper
    cyberActor SetTexture aTexture

# Create graphics objects
vtkRenderMaster rm

# 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 cyberActor
$ren1 SetBackground 1 1 1
$renWin SetSize 450 450

# Define method to invoke when "u" is pressed in graphics window
$iren SetUserMethod {wm deiconify .vtkInteract}

# 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

$iren Initialize

# prevent the tk window from showing up then start the event loop
wm withdraw .



Back to Article


Copyright © 1997, Dr. Dobb's Journal

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.