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.