thumbnail|Catmull–Clark level-3 subdivision of a cube with the limit [[subdivision surface shown below. (Note that although it looks like the bi-cubic interpolation approaches a sphere, an actual sphere is quadric.)]]

thumb|Visual difference between sphere (green) and Catmull-Clark subdivision surface (magenta) from a cube

The Catmull–Clark algorithm is a technique used in 3D computer graphics to create curved surfaces by using subdivision surface modeling. It was devised by Edwin Catmull and Jim Clark in 1978 as a generalization of bi-cubic uniform B-spline surfaces to arbitrary topology.

Start with a mesh of an arbitrary polyhedron. All the vertices in this mesh shall be called original points.

  • For each face, add a face point
  • Set each face point to be the average of all original points for the respective facenone|thumb|220x220px|Face points (blue spheres)
  • For each edge, add an edge point.
  • Set each edge point to be the average of the two neighbouring face points (A,F) and the two endpoints of the edge (M,E) <math>\frac{A+F+M+E}{4}</math>none|thumb|220x220px|Edge points (magenta cubes)
  • For each original point (P), take the average (F) of all n (recently created) face points for faces touching P, and take the average (R) of all n edge midpoints for original edges touching P, where each edge midpoint is the average of its two endpoint vertices (not to be confused with new edge points above). (Note that from the perspective of a vertex P, the number of edges neighboring P is also the number of adjacent faces, hence n)
  • Move each original point to the new vertex point <math>\frac{F + 2R + (n-3)P}{n}</math> (This is the barycenter of P, R and F with respective weights (n − 3), 2 and 1)none|thumb|220x220px|New vertex points (green cones)
  • Form edges and faces in the new mesh
  • Connect each new face point to the new edge points of all original edges defining the original facenone|thumb|220x220px|New edges, 4 per face point
  • Connect each new vertex point to the new edge points of all original edges incident on the original vertex none|thumb|220x220px|3 new edges per vertex point of shifted original vertices
  • Define new faces as enclosed by edges none|thumb|220x220px|Final faces to the mesh

Properties

The new mesh will consist only of quadrilaterals, which in general will not be planar. The new mesh will generally look "smoother" (i.e. less "jagged" or "pointy") than the old mesh. Repeated subdivision results in meshes that are more and more rounded.

The arbitrary-looking barycenter formula was chosen by Catmull and Clark based on the aesthetic appearance of the resulting surfaces rather than on a mathematical derivation, although they do go to great lengths to rigorously show that the method converges to bicubic B-spline surfaces. (when n indicates how many derivatives are continuous, we speak of <math>\mathcal{C}^n</math> continuity). After one iteration, the number of extraordinary points on the surface remains constant.

Exact evaluation

The limit surface of Catmull–Clark subdivision surfaces can also be evaluated directly, without any recursive refinement. This can be accomplished by means of the technique of Jos Stam (1998). This method reformulates the recursive refinement process into a matrix exponential problem, which can be solved directly by means of matrix diagonalization.

Extensions

Semi-sharp creases

Catmull–Clark surfaces were extended to support semi-sharp creases by using different subdivision rules for a fixed number of iterations determined by a sharpness value. This approach, introduced by Tony DeRose et al. in 1998, allows for a controllable transition from sharp to smooth subdivision rules.

Software using the algorithm

  • 3ds Max
  • 3D-Coat
  • AC3D
  • Anim8or
  • AutoCAD
  • Blender
  • Carrara
  • CATIA (Imagine and Shape)
  • CGAL
  • Cheetah3D
  • Cinema4D
  • Clara.io
  • Creo (Freestyle)
  • Daz Studio, 2.0
  • DeleD Community Edition
  • DeleD Designer
  • Hammer
  • Hexagon
  • Houdini

<!--* JPatch-->

  • LightWave 3D, version 9
  • Makehuman
  • Maya
  • Metasequoia
  • MODO
  • Mudbox
  • Power Surfacing add-in for SolidWorks
  • Pixar's OpenSubdiv
  • PRMan
  • Realsoft3D
  • Remo 3D
  • Shade
  • Rhinoceros 3D - Grasshopper 3D Plugin - Weaverbird Plugin
  • Silo
  • SketchUp - Requires a Plugin.
  • Softimage XSI
  • Strata 3D CX

<!--* Vue 9-->

  • Wings 3D
  • Zbrush

<!--* TopoGun-->

<!--* CREO 1.0 - PTC - (Freestyle)-->

See also

  • Conway polyhedron notation - A set of related topological polyhedron and polygonal mesh operators.
  • Doo-Sabin subdivision surface
  • Loop subdivision surface

References

Further reading

  • preprint
  • Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose, "Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces", ACM Transactions on Graphics Volume 31 Issue 1, January 2012, , demo
  • Nießner, Matthias; Loop, Charles; Greiner, Günther: Efficient Evaluation of Semi-Smooth Creases in Catmull-Clark Subdivision Surfaces: Eurographics 2012 Annex: Short Papers (Eurographics 2012, Cagliary). 2012, pp 41–44.
  • Wade Brainerd, Tessellation in Call of Duty: Ghosts also presented as a SIGGRAPH2014 tutorial [http://advances.realtimerendering.com/s2014/wade/]
  • D. Doo and M. Sabin: Behavior of recursive division surfaces near extraordinary points, Computer-Aided Design, 10 (6) 356&ndash;360 (1978), (doi, pdf)