Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

July 18, 2019
July 18, 2019
Press Releases
July 18, 2019
Games Press

If you enjoy reading this site, you might also want to check out these UBM Tech sites:

# 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

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.

Page 2 of 3

### Related Jobs

Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.18.19]

Senior Animation Programmer
Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.18.19]

Gameplay Networking Programmer - All Levels
Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.18.19]

Senior Gameplay Programmer
Build A Rocket Boy Games — Edinburgh, Scotland, United Kingdom
[07.18.19]