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
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 14 split produces vertices with 6 neighbors. All of the new vertices
introduced are regular. The most common subdivision schemes are Loop
subdivision and CatmullClark subdivision. Loop subdivision is a scheme
for triangular meshes while CatmullClark 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
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!