Catmull-Clark subdivision surfaces: the basics

Posted: 1304544077|%e %B %Y, %H:%M|agohover
Tags: catmull clark subdivision surface

Introduction

Subdiv.jpg

The basic idea of subdivision surface is to construct a surface from an arbitrary polyhedron (the control mesh) by repeatedly subdividing each of the faces. If the subdivision is done appropriately, the limit of this subdivision process will be a smooth surface. Many subdivision schemes (or set of rules) have been defined over the years (Loop, Doo-Sabin, …) but Catmull-Clark scheme [1] and its extensions [2] are by far the most popular.

Why do modelers prefer subdivision surfaces over NURBS ?

A NURBS surface, like any other parametric surface, is limited to representing surfaces which are topologically equivalent to a sheet, a cylinder or a torus. Because the control mesh is rectangular, refining a NURBS affects the whole surface. By contrast, subdivision surfaces can be refined locally by adding points to the control mesh, giving more freedom to the modeler. Therefore, support for this primitive is now ubiquitous in all high-end renderers.

Catmull-Clark scheme

This subdivision produces three types of vertices:

  • face vertex. For each face, the new vertex is the average of the face's vertices
  • edge vertex. For each edge, the new vertex is the average of the edge's endpoints and the new face vertices of the two faces that share the edge.
  • control vertex. For each control vertex of the mesh, the vertex is moved to a new location that is (n-2)/n times the old vertex location, plus 1/n times the average of the n adjacent new edge vertex positions, plus 1/n times the average of the n adjacent new face vertex positions, where n is the valence of the vertex1.

For each face, new faces are created by connecting these new vertices as follows: each new face vertex is connected to the new edge vertices of the boundary of the face; each new control vertex is connected to the new edge vertices created for the edges incident with the old control vertex.

These rules are valid only for closed meshes (which have no boundaries). They must be extended for open meshes. This will be the subject for another post.

A few nice properties

This looks complicated and really is. Studying how these rules work, a number of properties can be observed:

  • For Catmull-Clark subdivision surfaces, each face has an associated limit surface patch that is completely defined by the face and its 1-neighborhood. That means a subdivision surface can be broken down into individual components that are rendered separately, just like a polygon mesh can be rendered as individual polygons.
  • Each new face is rectangular with two edge vertices, one control vertex and one face vertex.
  • The face vertices corresponding to the original non rectangular faces are extraordinary vertices2.
  • The new control vertices keep their valence.
  • Since there are only rectangular faces after the first iteration, the number of extraordinary vertices remain constant and there is at most one extraordinary vertex per face from the second iteration onward .
  • When subdividing an irregular patch3, the result is another irregular patch whose extraordinary vertex has the same valence and three regular patches.

Rendering

Rendering subdivision surfaces is difficult: it is not too hard to implement subdivision rules but the limit surface has no analytical expression and the control mesh can have any arbitrary topology. There are different schools of thought: some tesselate away the control mesh using subdivision rules until the resulting polygons are small enough at the expense of considerable memory usage (at each iteration, a Catmull-Clark scheme quadruples the number of polygons), others try to approximate the surface using bicubic patches.

XRT implements a third approach advocated in [3]. The subdivision is performed on the fly with the required precision which saves memory and avoids artifacts but increases rendering times.

Algorithm outline

The algorithm makes use of the Catmull-Clark scheme properties to simplify the topology of the control mesh. It performs one or two levels of subdivision to obtain a control mesh made of quads with at most one extraordinary vertex (this cuts down drastically the number of special cases) and breaks down the mesh into individual faces with their 1-neighborhood. In most cases, these are regular patches with 16 control points. During the intersection calculation, if the ray misses the patch bounding box, the patch is discarded, otherwise it is subdivided until it looks flat or small enough. The face can then be safely approximated as a bilinear patch which is checked for intersection.

Holger Dammertz's thesis is rather sketchy and only details regular patch subdivision. Nevertheless, the algorithm can be extended to handle open meshes with corners and creases.

Conclusion

This post has been rather long and technical. It was needed to setup the foundations. Next posts will describe the incremental changes required for a full fledged implementation of Catmull-Clark subdivision surfaces.

For now, XRT only supports closed meshes: open meshes require a set of additional rules which are being implemented. Many thanks to Kevin Beason for putting its subdivision software in the public domain. It has been a great starting point to build upon.

Bibliography
1. E. Catmull and J. Clark. "Recursively generated B-spline surfaces on arbitrary topological meshes." Computer Aided Design,10(6):350–355, 1978.
2. Tony Derose, Michael Kass, and Tien Truong. "Subdivision surfaces in character animation." In Proceedings of the SIGGRAPH 1999 annual conference on Computer graphics, pages 85-94, Los Angeles, CA, USA,August 1999.
3. Holger Dammertz, "Floating-Point Precision Ray Tracing of Free-Form Surfaces", Diplomarbeit, 2005

Rate this post:

rating: 0+x

Comments: 0