About


XRT is a raytracing based programmable rendering system for photo-realistic image synthesis built around a plug-in architecture design.


Blog

Catmull-Clark subdivision surfaces: corners and creases

Posted: 28 May 2011 12:41
Tags: catmull clark subdivision surface

This post delves a bit further into the realm of subdivision surfaces. Building upon the lore gathered in the previous post, it describes extensions to the Catmull-Clark scheme for modeling fillets and blends.

Sharp features

Because smooth only surfaces are of limited use, Pixar people have introduced sharp features into Catmull-Clark subdivision surfaces[1]: corners and creases. A few more rules (let's call them sharp rules) have been added to the smooth subdivision rules.

If you remember my previous post, the subdivision produces three types of vertices:

  • face vertex. The vertex uses always the smooth rule
  • edge vertex. For each edge tagged as sharp, the new vertex is the average of the edge's endpoints. The new sub-edges are also tagged as sharp. The other edges use the smooth rule.
  • control vertex. For each control vertex of the mesh, the vertex is moved to a new location that depends on the number of sharp edges incident at the vertex.
    • If this number is less than 2, the vertex uses the smooth rule.
    • If the number equals 2, the vertex uses the crease vertex rule: the new vertex is a weighted average of the old vertex location (3/4) and of the two other endpoints of the incident creases (1/8).
    • If the number is more than 2, the vertex uses the corner rule: the vertex does not move under subdivision.
    • Of course, if a vertex is tagged as sharp, it uses the corner rule whatever is the number of incident sharp edges.

Here is a small example of how a surface changes, just by tagging edges or vertices. The control mesh is the same for each picture.

Smooth surface
Image Unavailable
wireframe control mesh, where smooth edges are yellow

Creases
Image Unavailable
creases edges are red

Corner
Image Unavailable
the upper right vertex is a corner

In this example, four edges meet at the same vertex, implicitely making a corner out of it.

Implicit corner
Image Unavailable

Semi-sharp features

In the real world, surfaces are never infinitely sharp. Anything when viewed sufficiently closely is smooth. Another refinement of the subdivision rules is needed to obtain semi-sharp features. For that purpose, sharp edges and corners are weighted by a sharpness parameter. This parameter is decreased by 1 at each iteration of the subdivision process and controls which rules are applied to sharp features.
* If the sharpness is greater or equal to 1, sharp subdivsion rules are applied
* If the sharpness is between 0 and 1, the result is a linear interpolation of the smooth rule and of the sharp rule using the sharpness value.
* If the sharpness is lower or equal to 0, smooth subdivision rules are applied.

This is a very intuitive mechanism which behaves like levels of detail. At coarser levels of the subdivision, features are sharp and become smooth at finer levels.

Here is how the smooth surface of the first paragraph is affected by various sharpness values.

Image Unavailable
sharpness = 1.0

Image Unavailable
sharpness = 2.0

Image Unavailable
sharpness = 3.0

In the following animation, the sharpness varies between 0 and 10 with a 0.1 step.

Notice that a crease does not need to be not a closed contour. In the next example, only three of the four upper edges are tagged as creases with a sharpness of 4.0.

Open crease
Image Unavailable

More to come

We are not yet done with subdivision surfaces. The next post will describe how to deal with holes in the control mesh and boundaries for open meshes.

Bibliography
1. 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.

Comments: 2, Rating: 0


Catmull-Clark subdivision surfaces: the basics

Posted: 04 May 2011 21:21
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

Comments: 0, Rating: 0