Contents |
|
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