Design

Data Structures

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.

Algorithm

Our decimation algorithm works by removing vertices from areas of the mesh that are relatively flat. A vertex has a list of vertices called neighbors. We define neighbors as other vertices in the entire vertex list that are connected to the vertex by an edge of a triangle. An average plane can be calculated from these neighbors. This is the plane that is closest approximation to all of the neighbors in point-normal form. The point is the average point of the neighbors (P), and the normal is the average of their normals (N). p is found by averaging each component of the neighbors (x, y, and z); N is found by averaging each component of their normals (x, y, and z).

After the average plane has been found, the distance between the removal candidate vertex (from which the neighbors were found, and which the average plane did not take into account) and the plane is calculated. If the distance is within a threshold range, the vertex is removed. The distance is found using the formula in Equation , where V is the candidate vertex for removal, p is the projection of this point onto the plane, and N is the unit normal of the plane.

Figure: The distance to plane formula.

Diagrams

Following is a series of images that depict how the distance to a plane is calculated.

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

Figure: Find the average plane.

Figure: The average plane in point-normal 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

Our algorithm calculates the distance to the plane for each vertex initially upon loading of the file, and anytime one of its neighboring vertices are removed. Anytime a neighboring vertex is removed from the list of vertices, the average plane has been modified, and the distance needs to be recalculated using the new average plane. The reason we recalculate the distance when a neighboring vertex is removed is so that the distance will always be current. The following is a series of images that depict the method used to remove a single vertex from the list of vertices.

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

The steps depicted above are of one complete cycle. This cycle is repeated for the number of vertices the user wants to remove. The repetition is known as decimation.

Brief Algorithm Comparison

Unlike previous methods discussed in our literature review[#!hoppe96progressive!#], our program is lossy. This means that no information about removed vertices or triangles is maintained. Our algorithm chooses the best candidate based solely on the distance to the average plane. We would have liked to incorporate appearance based vertex removal[#!hoppe96progressive!#] in our algorithm had time permitted.

Other algorithms we researched performed base vertex removal on volume[#!garland!#,#!hoppe93mesh!#]. One algorithm incorporated textures to aid in the viewing of an optimized mesh[#!garland!#], and some will alter the positions of other vertices to make the removal appear less severe[#!garland!#,#!hoppe93mesh!#,#!lindstrom!#].

Interface

The command line interface, commonly referred to as CLI, gives the user two options for decimation. We designed the CLI so a user can run the program without the need for a graphical user interface or user input. This means it can be run from a terminal, and all the testing can be automated with a script.

The ideas for the two methods are trivial when dealing with an optimization program. If the user wants to remove a certain amount of vertices, then the user can explicitly tell the program the number of vertices to remove. If the user is not sure of how many, but wants to remove a specific percentage, our program also satisfies that requirement.

We designed a graphical user interface, commonly referred to as GUI, for the program as well. This interface allows a user to use keyboard commands and a pointing device such as a mouse to view a visual representation of the model before and after decimation. This interface was designed with only one option to decimate the models in a scene because of a limitation in the library we used to implement this interface (see the next section). This option is similar to a user giving the command line option for decimation to a specific percentage. In this case, the algorithm runs until only the given percentage of vertices are removed from the model.

Our program offers many features that allow the user to analyze the program graphically. Using the mouse a user can change three other sets of options.

The first set of options include settings for the model. The options include viewing the normals at the center of the triangle or at each vertex in the mesh. This is helpful to see where there are triangles, and how many there are. The user has the option of turning the lighting on or off. This can be used to see the normals better. There are then options to turn on or off certain features of the model. There are three distinct features of any model: triangles, edges, and points. Correspondingly there are options to allow each one to render in any combination. This is useful when a user may need to see if certain vertices have been removed. In this case the user would select the "render points" and de-select all the others. If the user then wants to view the mesh in wire frame mode, the user can de-select "render points" to turn them off, and select "render edges."

The second set of options are used for adding or subtracting viewports. When you add a viewport the program displays the original mesh in the same window, and automatically resizes to fit both viewports. There is a limit of four viewports that can be displayed at any one time. Multiple viewports are useful for giving a before-and-after view, using the model options described above, or for seeing the model from more than one viewpoint. In this set of options the user can also remove viewports; this only works if there is more than one viewport.

The third set of options are used for the navigation control of the model. The default option is to have "model control." This is analogous to grabbing an object and twisting it around its center. The other option is "eye control." This option is similar to first person shooter computer games. In this option you are the navigator and move around the model, similar to walking around a real-world object. This option is a little harder to control but allows a better perspective in some cases.