About
XRT is a raytracing based programmable rendering system for photorealistic image synthesis built around a plugin architecture design.
Blog
CatmullClark 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 CatmullClark scheme for modeling fillets and blends.
Sharp features
Because smooth only surfaces are of limited use, Pixar people have introduced sharp features into CatmullClark 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 subedges 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.



In this example, four edges meet at the same vertex, implicitely making a corner out of it.
Implicit corner 
Semisharp 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 semisharp 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.



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 
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.
Comments: 2, Rating: 0
CatmullClark subdivision surfaces: the basics
Posted: 04 May 2011 21:21
Tags: catmull clark subdivision surface
Introduction
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, DooSabin, …) but CatmullClark 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 highend renderers.
CatmullClark 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 (n2)/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 vertex^{1}.
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 CatmullClark subdivision surfaces, each face has an associated limit surface patch that is completely defined by the face and its 1neighborhood. 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 vertices^{2}.
 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 patch^{3}, 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 CatmullClark 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 CatmullClark 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 1neighborhood. 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 CatmullClark 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.