Next: Implementation
Up: The Decimation Program
Previous: The Decimation Program
Contents
Subsections
The easiest way to implement the decimation algorithm is to create a
ring structure[#shroeder##1###]. This consists of a data structure in which
triangles know which vertices they use (Figure ), and vertices know which triangles they
are a part of (Figure ). This leads to a ring structure that allows the decimation
algorithm to remove vertices and reconstruct the triangle mesh with ease.
Figure:
The Triangle data structure has a list of 3 Vertex objects.

Figure:
The Vertex data structure has a list of Triangle objects.

Figure:
The distance to plane formula.

Step 1, Figure : Get the average plane, in point
normal form (Figure ).
Figure:
Find the average plane.

Figure:
The average plane in pointnormal form.

Step 2, Figure : Get the distance from the vertex
to a point on the plane. This is the distance to the plane, and can be expressed
as Equation .
Figure:
Calculate the distance from the vertex to the plane

Step 1, Figure : Find the best candidate in the
model. Our algorithm iterates through the entire list of vertices and finds the
Vertex that has the smallest distance to the plane, which we previously defined
as 'd'.
Figure:
Candidate for vertex removal

Step 2, Figure : Get the list of neighbors from
the best candidate vertex. This can be accomplished easily, since our Vertex
data structure keeps a current list of its neighbors in an easily iterated STL
set.
Figure:
Locate the neighbors

Step 3, Figure : Retriangulate. Our
retriangulation algorithm is basic. It exploits a given in manifold models. The
given is that if you replace the best candidate vertex with one of its
neighbors in all of the neighbors two things happen. The model remains manifold,
and two triangles are removed. In the previous image there were five triangles.
In this image there are three.
Figure:
Retriangulate neighbors, pointing to one neighbor and removing some
triangles

Step 4, Figure : Finally we remove the vertex from
the model. The model now has one less vertex and two less triangles.
Figure:
Remove the vertex

Next: Implementation
Up: The Decimation Program
Previous: The Decimation Program
Contents
Tim Garthwaite
20020203