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.
________________________________________________________
Geometry
Resampling
|
|
|
|
Features
