Everyone
who loves Quake 3 is impressed by the high quality graphics,
light maps, and character animations. Although they have done an excellent
job in painting the textual details, most of their characters consist
of only several hundred triangles which cannot capture highly detailed
geometry. In recent years, subdivision surfaces have received a lot
of attention from both academics and industry professionals, people
in the movie industry even apply subdivision techniques to create complex
characters and produce highly detailed, smooth animation. This article
examines how to convert triangular meshes (which is one of the most
popular data representations) into subdivision surfaces.
What
are Subdivision Surfaces?
The idea of subdivision surfaces was first introduced by Catmull &
Clark and Doo & Sabin in 1978. Unlike traditional spline surfaces,
subdivision surfaces are defined algorithmically. Recently there has
been a lot of activity in the computer graphics research community and
significant advances have been made in rendering, texture mapping, animation
and compression of subdivision surfaces. They were also used in the
production of Geri's Game and A Bug's Life. Geri's hands,
head, jacket, and pants were each modeled using a single subdivision
surface. The faces and the hands of Flick and Hopper were also modeled
with subdivision surfaces. Momentum is building in the computer assisted
geometric design (CAGD) to make subdivision surfaces one of the modeling
primitives.
Why Subdivision Surfaces?
Subdivision surfaces lie somewhere in between polygon meshes and patch
surfaces, and offer some of the best attributes of each. The well defined
surface normal allows them to be rendered smoothly without the faceted
look of low polygon count polygonal geometry, and they can represent
smooth surfaces with arbitrary topology (with holes or boundaries) without
the restriction in patches where the number of columns and rows has
to be identical before two patches can be merged. Secondly, subdivision
surfaces are constructed easily through recursive splitting and averaging:
splitting involves creating four new faces by removing one old face,
averaging involves taking a weighted average of neighboring vertices
for the new vertices. Because the basic operations are so simple, they
are very easy to implement and efficient to execute. Also because of
the recursive nature, subdivision naturally accommodates levelofdetails
control through adaptive subdivision. This allows triangle budgets to
be spent in regions where more details are needed by subdividing further.
What are the challenges?
The simple splitting process usually starts from a coarse control mesh,
iterating this process several times will produce socalled semiregular
meshes. A vertex is regular if it has six neighbors (in triangle mesh)
or four neighbors (in quadrilateral mesh). Vertices which are not regular
are called extraordinary. Meshes that are coming from standard modeling
packages or 3D scanning devices usually do no have a regular structure,
hence there is a need to convert these irregular meshes into semiregular
meshes, a process known as remeshing. This article presents an algorithm
that maps the original mesh onto a simple control mesh  base domain,
thus deriving the parameterization for the original mesh. Having this
mapping information (parameterization) allows us to perform the remeshing
efficiently by subdividing the base domain and perturbing the new vertices
to approximate the original geometry. From a signal processing point
of view, we can treat it as a geometry resampling process. The beauty
of this algorithm is that it is very simple and easy to implement.
Preparation Before Programming
Before explaining the algorithms, lets take a look at input. Input can
be any arbitrary triangulated manifold mesh. By arbitrary we mean the
mesh can have holes or boundaries, triangulated means the surface is
approximated/discretized by a list of triangles. Manifold means it does
not contain topological inconsistencies. Topological inconsistencies
include more than two triangles sharing an edge or more than two corners
meeting at one vertex. Make sure you have good, clean geometries.
Overview of Algorithm
The conversion algorithm contains two major steps. The first step is
called mesh simplification. Mesh simplification has been well known
to the game developers for creating leveslofdetail or catering to
different bandwidth and computational requirements. Most of the time,
there is tradeoff between model complexity and interactivity  i.e.
a higher frame rate requirement usually is translated into simpler/coarser
model. In this algorithm, mesh simplification is used only as a tool
to derive a base domain so that resampling/remeshing can be acomplished.
Developers are free to choose their favorite mesh simplification algorithm,
I recommend Michael Garland's error quadrics simplification algorithm
because it is open source and simple to understand. The second step
is called remeshing; the goal is to create a subdivision connectivity
(semiregular) mesh with geometry sampled from the original mesh. As
was mentioned earlier, subdividing the control mesh does not add any
extra information to the mesh but only increases the complexity of the
model. Hence there is a need to use the mapping information from the
first step so that we know how to perturb these vertices to approximate
the original mesh. (Figure 1).

Figure
1. The algorithm consists of two major steps. The first is mesh
simplification, which allows us to derive the control mesh (base
domain) and compute the mapping (parameterization of the original
mesh) with respect to this base domain. The second step is geometry
resampling (or remeshing). The goal is to obtain a subdivision
connectivity mesh (through subdividing the base domain) and at
the same time approximate the original mesh.

The
2D Case
Before diving into the 3D mapping algorithm, a look at the 2D curve
case might be in order. The notion of subdivision connectivity does
not make much sense here, but the conversion process can be treated
as a regular sampling at the dyadic points. Simplification (removing
alternating vertices in each step  as shown in Figure 2) is used to
derive a simple line segment (base domain in red). Mid points are then
inserted in the middle of each line segment by performing a linear interpolation
between the two closest points (equivalent to the geometry resampling
process) to complete the second phase (as show in Figure 3).

Figure
2. This figure shows the result of applying the first phase of
the algorithm. The idea is to do a simplification of the curve
by removing every other vertex. At each simplification step, the
removed vertex is mapped onto the simplified curve governed by
the arclength ratio. The end result would be a curve which maps
onto a simple base line segment.


Figure
3. This shows the second phase of the conversion algorithm in
2D. The yellow circles are the midpoints (analogy to the midpoints
in the triangle subdivision case) of the base domain line segments.
Their coordinates are computed from the linear interpolation of
the two adjacent green vertices.

The 2D
curve resampling process is computed as follows:
Insert
a midpoint (yellow circle  dyadic point) on the red line segment (in
Figure 3) and find out the two closest points (green circles) that were
mapped from the original curve onto the red line segment. Then compute
the ratio of the yellow circle within the two green circles. Based on
the original geometry of the green circles and this ratio, we can linearly
interpolate the coordinates and obtain the resample geometry of this
yellow circle on the original curve.
Now with
this simple idea, let's extend it to 3D.