Building Your Own Subdivision Surfaces
September 8, 2000 Page 3 of 3
At this point, the mapping computation is finished. One way to look
at the mapping is consider that each vertex has a 4tuple 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
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!
Page 3 of 3