Decimate

Summary: This Lightwave modeller plugin uses a technique called triangle decimation in an attempt to reduce the number of polygons in a Lightwave object.

This plugin uses the triangle decimation routine found in the vtk library (The Visualization Toolkit, copyright 1993-1995 by Ken Martin, Will Schroeder, and Bill Lorensen). The campanion book for the vtk library is "The Visualization Toolkit, An Object-Oriented Approach to 3D Graphics" (Prentice Hall, ISBN 013199837-4). 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.

Introduction

Many 3D models contain a large number of polygons, especially algorithmically created models (such as those created by the isosurface construction technique known as marching cubes) and models created with 3D scanners and digitizers. Polygon reduction in these types of models is currently a very active research area in computer graphics. Obviously, rendering 3D scenes is much faster when the models contain a minimum number of polygons. Also with the current trend towards sharing 3D worlds over the internet using VRML, level of detail models (LOD) are becoming absolutely necessary for creating worlds in which the user can browse and interact in a reasonable manner.

This plugin uses a polygon reduction technique known as triangle decimation, which is intended to preserve the original topology of the object while still providing a good approximation to the original geometry. Decimation works by performing 3 basic steps on every point in a triangular mesh:

1. Classify the local geometry and topology for the given point
2. Use the decimation criterion to decide if the point can be deleted
3. If the point is deleted, re-triangulate the resulting hole

To achieve the best results from this plugin, this algorithm needs to be understood in order to provide the best parameters to the plugin. The sections that follow provide a detailed description of each of these steps. These sections also contain explanations of the terminology used in the parameters for this plugin.

Classification

The purpose for the classification step is to determine what type of vertex is currently being examined. This classification will be used to determine whether the vertex is a candidate for deletion.

One thing that needs to be defined before classifications are discussed is the Feature Edge. This term is used in the classification of interior edge and corner points.

A Feature Edge exists if the angle between the surface normals of 2 adjacent triangles is greater than a user specified "feature angle".

There are five possible classifications for a vertex: simple, complex, boundary, interior edge, or corner point. Here are some examples of each type:

Simple point (surrounded by a complete cycle of triangles, and each edge that uses the point is used by exactly 2 triangles).

Complex point (surrounded by a complete cycle of triangles, but at least one edge is not used by 2 triangles, or the point is used by another triangle not in the cycle of triangles).

Boundary point (within a semi-cycle of triangles, or in the case of Lightwave, on the boundary of a mesh determined by each surface name).

Interior edge point (a simple point used by 2 feature edges).

Corner point (a simple point used by 3 or more feature edges).

Complex points and corner points will not be deleted from the triangular mesh. All other points are candidates for deletion using the appropriate decimation criterion in the following step.

Decimation

Once the classification step determines that the point is a candidate for deletion, this step uses the classification to decide which of two error evaluation methods will be used. The appropriate error evaluation method then proceeds to estimate the error that will result if the vertex is deleted and replaced with another triangulation.

For simple points, the evaluation method used is a distance to plane calculation. The plane passing through the surrounding vertices is computed using a least-squares method, and the distance from the point to the plane (d) is used to determine whether the point will be deleted.

Boundary points and interior edge points use a distance to line error measure. The distance is calculated from the point to the line that joins the neighboring vertices, and that value (d) is used to determine whether the point will be deleted.

A point satisfies the decimation criterion if its distance measure (d) is less than the user specified error. That point is then deleted along with all triangles using that point, leaving a hole in the triangular mesh.

Triangulation

If the vertex was deleted in the decimation step, the resulting hole is re-triangulated during this stage. The VTK Toolkit uses a special recursive 3D divide and conquer technique to triangulate the hole. For more detail concerning this triangulation technique, refer to the book or paper referenced in the Summary section at the top of this page.

Conclusion

The algorithm described above is processed over the entire vertex list (this constitutes an iteration). Iterations proceed until a target reduction is reached or a maximum iteration count is exceeded, whichever comes first.

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). Subiterations 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.

Downloading and Installing Decimate

The Decimate plugin is currently available for the SGI, Intel and Alpha platform. If you compile this plugin for any other platform, please let me know and I will include it on this page along with a thanks for doing so.

• SGI Executable: decimate.tar.gz
  
  
• Intel Executable: decimi.zip
  
• Alpha Executable: decima.zip
  (Many thanks to Matthew Sorrels of Pontari Productions for compiling this plugin for the Intel and Alpha platform. Thanks Matthew, your time and assistance is greatly appreciated!!)
  
  
• Source Code: decimate_src.tar.gz
  (To compile the source code, you will need a C++ compiler and the VTK library pre-compiled for your particular architecture.)

To install Decimate, just copy the decimate.p file into your Lightwave plugins directory. Run the Lightwave Modeler and choose Objects->Custom->Add Plugin. After you select the decimate.p plugin from the file requester, you should now find a Decimate entry in the Objects->Custom pulldown menu.

Using Decimate

Make sure you have an object in the current foreground layer of Modeller. You will also need to have at least one empty layer, because the existing object is left alone, and the resulting decimated object will be placed in the first available empty layer. Choose Objects->Custom->Decimate and you will be presented with the following information requester.

Here is a brief description of each parameter in the Decimate Options requester:

• Desired Reduction:

  Desired reduction in the total number of polygons, expressed as a percentage of the original number of polygons in the mesh. Because of various constraints, this level of reduction may not be realizable.
  
  
  

• Maximum Iterations:

  Maximum number of iterations to attempt. If the desired reduction target is achieved first, this value will not be reached.
  
  
  

• Maximum Subiterations:

  Maximum number of subiterations to perform. Subiterations are iterations that are performed without changing the decimation criterion. If no triangles are deleted in a subiteration, the subiteration process is stopped.
  
  
  

• Initial Error:

  Specify the decimation error bounds expressed as a fraction of the longest side of the input data's bounding box.
  
  
  

• Error Increment:

  Value by which to increase the decimation error after each iteration.
  
  
  

• Maximum Error:

  Largest decimation error that can be achieved by incrementing error.
  
  
  

• Initial Angle:

  Specify the desired feature angle.
  
  
  

• Angle Increment:

  Increment by which to increase feature angle over each iteration.
  
  
  

• Maximum Angle:

  Maximum permissible feature angle.
  
  
  

• Preserve Feature Edges:

  Turn on/off the preservation of feature edges.
  
  
  

• Delete Boundary Vertices:

  Turn on/off the deletion of vertices on the boundary of a mesh.
  
  
  

• Maximum Aspect Ratio:

  Maximum aspect ratio allowed during re-triangulation process.
  
  
  

• Complex Triangle Degree:

  Number used to determine whether a vertex is considered complex, and is never deleted.
  
  
  

• Smooth Decimated Object:

  I threw this one in at the last minute, since the latest VTK Toolkit included this new routine. I wanted to experiment with this feature, therefore you can too! This option will adjust the decimated model's point coordinates using Laplacian smoothing. The effect is to "relax" the mesh, making the cells better shaped and the vertices more evenly distributed. If you choose Yes for this option, you will be presented with the Smoothing Options requester.
  

The following information requester is shown only if the Smooth Decimated Object was chosen in the first requester. More information about the algorithm used for this operation can be found in the vtkSmoothPolyFilter man page.

Here is a brief description of the parameters in the Smoothing Options requester:

• Convergence Criterion:

  Specify a convergence criterion for the iteration process. Smaller numbers result in more smoothing iterations.
  
  
  

• Number of Iterations:

  Specify the number of iterations for Laplacian smoothing.
  
  
  

• Contraction Factor:

  Specify the contraction factor for Laplacian smoothing. Contraction pass will only occur is this is a non-zero value.
  
  
  

• Expansion Factor:

  Specify the expansion factor for Laplacian smoothing. If this term is non-zero, then the contraction pass is followed by an expansion pass. Using contraction in combination with expansion tends to preserve the original "volume" of the mesh.
  
  
  

• Smooth Sharp Edges:

  Turn on/off smoothing along sharp interior edges.
  
  
  

• Feature Angle:

  Specify the feature angle for sharp edge identification.
  
  
  

• Edge Angle:

  Specify the edge angle to control smoothing along edges (either interior or boundary).
  
  
  

• Boundary Smoothing:

  Turn on/off the smoothing of vertices on the boundary of the mesh.
  

Well, that's it! If you have made it this far, Decimate is probably showing you a progress monitor while it creates the decimated object in the first available empty layer of Modeler.

Here is what is happening. First, your object is being copied to the first available empty layer, then all its polygons are being converted to triangles using Modeller's Triple function. Next all the vertices and polygons are converted into the VTK cell structure, so it can be operated on by the vtkDecimate routine. Each surface of the Lightwave object is then decimated separately, since we don't want to eliminate vertices that lie on the boundary between surfaces (those vertices that share different surface names). Once the decimation routine is finished, the Lightwave object that was copied into the empty layer is now deleted, and replaced by the decimated object returned from the vtkDecimate routine.

Because each surface is decimated separately, those vertices that originally were shared by multiple surfaces are now duplicated in the resulting decimated object. You probably want to do a Merge Points (Automatic) to eliminate these duplicated points along the edges of adjoining surfaces. Further reduction in the number of polygons might also be achieved by combining coplanar triangles into multi-sided polygons using Lightwave 5.0's Polygon Reduction tool.

If Decimate doesn't give you the results you are looking for, you might also want to check out the new plugin called qemLOSS. Decimate works well for objects I commonly encounter in the scientific visualization realm (e.g., medical 3D isosurface reconstructions), but I think qemLOSS gives better results for modelled objects and objects that will be used for level of detail type applications.

I am very interested in seeing how this plugin can be used. If you use it, send me some e-mail and let me know what kind of success or failure you achieved.