The strategy we use for reducing the complexity of our triangle mesh is a combination of a few techniques which we will highlight. First our primary decimation algorithm is partially adopted from Schroeder [24]. A useful property of this algorithm is that the reduced mesh's vertices are a subset of the original vertex set. We are given a triangle mesh with an arbitrary number of vertices and this mesh object is passed to the decimation function, where an abstraction is created of that mesh. The abstraction is an object composed of the mesh's topology with added information on the type of vertices (edge, corner, simple, complex, or boundary) and neighborhood (each vertex has a set of neighboring vertices and faces) connectivity. Type is computed by visiting the faces that share that vertex in clockwise order and calculating the angles between the normals of those faces. Only vertices of type simple and boundary will be considered for deletion.

     This new dynamic mesh object has the property that when a vertex is deleted, the object will heal the hole left by that deletion. When a vertex is eliminated, it is thought to conceptually collapse (these collapses are explicitly recorder for later use) to a neighboring vertex. This triangulation is generated by recursive loop splitting algorithm. This procedure will remove the vertex and the appropriate faces from the dynamic mesh. The deleted vertex index will also be stored in the new face that now contains that vertex (we do this for later color processing). Now a priority queue PQ (based on a binary heap structure) is created from this dynamic mesh. The PQ is composed of objects containing the current error (the key value) and index of each vertex. Another array of indices is created to keep track of the position of a particular vertex in the PQ. This is needed because when a vertex is deleted, its neighboring vertices get their errors changed, and those corresponding errors need to be expressed in the PQ. The PQ used is a modified version of the standard PQ, because the key values (error) change dynamically. We have introduced a function to modify this value in O(log n) time. When queried the PQ will tell us what is the next vertex to attempt to delete. The error for each vertex is a function of its neighborhood. Each vertex is capable of recommitting its own error value if its neighborhood is in any way modified.

     Vertex local error is computed by finding the average plane through the neighborhood of the vertex and then calculating the the distance of the vertex to that average plane. The average plane is delimited via the average weighted (the weight being the area of the face) normals of the neighboring vertices, and the average point along that normal among the neighboring vertices. Border vertices are treated differently in that the square root of the area of he border triangle is used as error. Global error comes from the distribution of local error. When a vertex is deleted its error is added to the the error of its neighboring vertices. Through this, the error is actually a global error bounds. The PQ is queried and the vertex index it returns will be attempted to be deleted from the mesh. With recursive loop splitting a proper triangulation is not guaranteed, if the triangulation fails the vertex will not be deleted at that time. Decimation will continue until a pre-specified number of iterations is reached or pre-specified number of faces is deleted from the mesh.