Contents

What are Subdivision Surfaces? 3D Mesh Simplification Geometry Resampling

Geometry resampling

At this point, the mapping computation is finished. One way to look at the mapping is consider that each vertex has a 4-tuple parameter which tells which base domain triangle it is associating with and it's location (given by the barycentric coordinates) within this base domain triangle. Another way to visualize the mapping is to imagine collapsing/wrapping the original mesh triangulation (treated as a graph) on top of the base domain.

Control mesh subdivision

To create a mesh with subdivision connectivity, simply subdivide the control mesh a few times by splitting an old triangle into four new triangles. The new edge vertices are called dyadic points. Notice that this 1-4 split produces vertices with 6 neighbors. All of the new vertices introduced are regular. The most common subdivision schemes are Loop subdivision and Catmull-Clark subdivision. Loop subdivision is a scheme for triangular meshes while Catmull-Clark subdivision is for quadrilateral meshes. This article demonstrates the Loop subdivision method, as it's a natural choice for triangle meshes. The limit surface of the subdivision will be a smooth surface with C2 continuity everywhere except at the extraordinary vertices. The next step is to perturb the vertices in such a way that the subdivision mesh can approximate the original mesh. This is what is called the geometry resampling.

Perturbing vertex coordinates

Before examining how to move these subdivision vertices to approximate our original mesh geometry, there is a need to fix on some notations and introduce the edge terminology so that the algorithims can be explained. Basically, an edge in the mesh is represented as a directional edge containing pointers to its origin vertex (e.Org), destination vertex (e.Dest), previous edge from its destination vertex (e.Dprev) and next edge from its origin vertex (e.Onext), as show in Figure 8.

Figure 8. Directional edge notation and its pointers to neighboring data structures.

Once we define the edge algebra we can proceed to the next step: perturbing the vertex coordinates.

 

Code Snippets

To compute the vertex coordinates for the subdivision vertices, first find the triangle in the flatten mesh on the base domain which contains the dyadic points (similar to the 2D case in Figure 3 where we locate the two green circles). The triangle location problem is reduced to a point location problem. M denotes the flattened original mesh on the base domain, and V is the red dyadic vertex. The white triangle containing V can be located using the routine in listing 1.

Once the triangle in the collapsed original mesh containing the dyadic points is found a linear interpolation can be used to find the resample location:

Where P is the dyadic point, Triangle ABC is the collapsed original triangle with original geometry. (a, b, g) is the barycentric coordinates of P within the triangle ABC in the collapsed graph. Hence P will be a resample point on the piecewise linear original mesh geometry. Repeating this process for all new vertices allows the perturbing of the subdivision connectivity mesh to approximate the original geometry. The following examples show the results.

Horse and Venus Results

Figure 9. The first picture shows the original horse model with irregular connectivity. The second picture shows the result of geometry resampling, the third picture illustrates the base domain (as a result of mesh simplification) while the fourth picture demonstrates the parameterization of the original mesh with respect to the base domain.

 

Figure 10. Another example (the Venus head) of running our algorithm. The second pictures shows the subdivision connectivity patch structure (color patches) with the base domain and visualization of the parameterization.

To sum up, this article presents a simple algorithm to convert triangular meshes into subdivision surfaces. The algorithm is both easy to understand and implement, the main idea being to recast the problem as geometry resampling and compute the mapping (parameterization of the original mesh) with respect to a simple base domain. Subdivision surfaces open the doors of opportunity to character animation, free form surface design and efficient rendering. The next part of this article looks at applying subdivision surfaces techniques to these tasks. Stay tuned!

Discuss this article in Gamasutra's discussion forums

________________________________________________________

[Back To] What are Subdivision Surfaces?