Contents |
|
3D
Mesh Simplification
To illustrate the algorithm, I'm using Mike Garland's
excellent simplification algorithms from . The software can be downloaded
from his site at http://graphics.cs.uiuc.edu/~garland
/software/qslim.html.
The nice thing about this simplification is that it is very fast and easy.
It can simplify highly detailed polygonal surface models automatically
into faithful approximations containing much fewer polygons. The core of
the algorithm employs an error metric called Quadric error metric to
provide a characterization of local surface shape. This metric is both
fast to evaluate and does not take up too much memory space. The details
of the algorithm can be found at http://graphics.cs.uiuc.edu/~garland/research/thesis.html.
![]() |
Figure 4. The
contraction of edge v1v2 will remove vertex v1 and it's adjacent
triangles (old triangles), thus creating a hole and retriangulation
is performed (new triangles are
formed). |
Propagating mapping information
Each simplification
step collapses an edge, removing one vertex and deleting the triangles
that surround the vertex and retriangulating the hole. In Figure 4, edge
v1v2 is collapsed and v1 is removed. In order to preserve some form of
mapping between adjacent levels, we are going to compute a 4-tuple (a, b,
g, T) that describes which new triangle T that v1 is going to associate
with. The (a, b, g) tuple is the barycentric coordinates of v1 within the
triangle T. To perform this association for each simplification step,
flatten the 1-ring (as shown in Figure 5) of v1 onto a 2D plane. This
planar flattening is achieved by computing the za map. It involves scaling
the angle sum subtend at v1 to 2p or p in the boundary case and raise the
length of each edge subtend at v1 to power a.
The 4-tuple can be calculated as in Figure 5:
![]() |
Figure 5. To
compute the 4-tuple, first flatten the 3D umbrella (1-ring) around
v1 onto a 2D plane. The scaling factor a is used to ensure the angle
sum is 2p, notice also that the length is scaled by the power a.
Once the umbrella is flattened, compute the location of v1 in the
new triangulation. |
Code Snippets
RemoveVertex( Vertex V )
{
PlanarFlatten( V
);
Valid = TryRetriangulate( V );
if ( Valid )
{
AssignParameter( V
);
Reparameterize( V
);
DoTriangulate( V );
};
};
The basic skeleton of the vertex removal is very simple. First perform a planar flattening to flatten the 3D 1-ring neighbors of vertex V (the umbrella) onto a 2D plane according to Figure 5 description, i.e. scaling the edge length and the angles subtended at vertex V. After flattening the umbrella use a retriangulation routine (e.g. a Delaunay triangulation) to remove the old triangles and try inserting new triangles. Make sure that the new triangles do not overlap with the existing triangles in the mesh, otherwise it will create topological inconsistencies and the mesh will not be a manifold (i.e. no more 2 triangles share an edge). If the new configuration is valid, proceed to compute the 4-tuple parameter for vertex V. The computation consists of two steps. The first step is to assign a new 4-tuple parameter for vertex V which involves the calculation of the barycentric coordinates and the associating triangle as indicated in Figure 6. The second step is to update the parameter values of those vertices which are currently associating with the old triangles. The function CalcNewParameters( Vi ) will perform the corresponding update according to Figure 7.
AssignParameter( Vertex V) {
Tuple =
CalcBaryCoord( V );
InsertTuple( V, Tuple
);
};
Reparameterize( Vertex V )
{
ForEachFaceAroundVertex( V , Fi )
{
ForEachAssociatedVertex(
Fi , Vi )
{
NewTuple
= CalcNewParameters( Vi );
UpdateTuple(
Vi , NewTuple
);
};
};
};
![]() |
Figure 6. In this
figure, v1 is mapped onto the green triangle, proceed to compute the
barycentric coordinates (a, b, g) and the new triangle that v1 will
be associated with. |
![]() |
Figure 7. When removing
the 1-ring triangles, be sure to update the parameter values of
those vertices which were previous associated to the new
triangulation. This example shows the reparameterization of the
white vertices onto the new
triangulation. |
If there are vertices which were associated with the old triangles, we also need to update their parameters due to the retriangulation (old triangles will be destroyed). The update can be computed in way similar to the previous step.
At the end of the simplification there will be a simple control mesh, called a base domain. For each vertex that was removed in the simplification hierarchy, it will have the 4-tuple indicating which base domain triangle it is associating with and its barycentric coordinates. This complete the first phase of the algorithm.
Examples
of running the algorithm
The following images show the results
of performing the first phase of the algorithm on a 3-holes torus.
Although this model is a bit simple, it does show the general ability of
the algorithm to handle a genus-3 object (containing 3 handles).
![]() |
![]() |
![]() |
![]() |
The first image shows the original triangular mesh, while the second image shows the base domain arrived at from the simplification routine. The third image demonstrates the visualization of mapping each vertex onto the base domain - thus shrink-wrapping the original mesh onto the base domain with each vertex having a 4-tuple association. The fourth image shows the result of subdividing the base domain and perturbing the new vertices to closely approximate the original mesh.