Building Your Own Subdivision Surfaces
September 8, 2000 Page 2 of 3
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
The 4tuple can be calculated as in Figure 5:
Figure
5. To compute the 4tuple, first flatten the 3D umbrella (1ring)
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 1ring 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 4tuple parameter for vertex V. The computation consists of two steps. The first step is to assign a new 4tuple 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 1ring 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 4tuple 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 3holes torus. Although this model is a bit simple,
it does show the general ability of the algorithm to handle a genus3
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 shrinkwrapping the original mesh onto the base domain with each vertex having a 4tuple association. The fourth image shows the result of subdividing the base domain and perturbing the new vertices to closely approximate the original mesh.
Page 2 of 3