Building Your Own Subdivision Surfaces
Contents |
|
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 level-of-details
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 so-called semi-regular 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 semi-regular 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 levesl-of-detail or catering to different bandwidth and
computational requirements. Most of the time, there is trade-off 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 (semi-regular) 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 arc-length 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 mid-points (analogy to the mid-points 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.