Catmull–Clark subdivision surface

First three steps of Catmull–Clark subdivision of a cube with subdivision surface below

The Catmull–Clark algorithm is a technique used in computer graphics to create smooth surfaces by 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.[1] In 2005, Edwin Catmull received an Academy Award for Technical Achievement together with Tony DeRose and Jos Stam for their invention and application of subdivision surfaces.

Recursive evaluation

Catmull–Clark surfaces are defined recursively, using the following refinement scheme:[1]

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

\frac{F + 2R + (n-3)P}{n}.
This is the barycenter of P, R and F with respective weights (n − 3), 2 and 1.

The new mesh will consist only of quadrilaterals, which in general will not be planar. The new mesh will generally look smoother than the old mesh.

Repeated subdivision results in smoother meshes. It can be shown that the limit surface obtained by this refinement process is at least \mathcal{C}^1 at extraordinary vertices and \mathcal{C}^2 everywhere else (when n indicates how many derivatives are continuous, we speak of \mathcal{C}^n continuity). After one iteration, the number of extraordinary points on the surface remains constant.

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 Catmull and Clark do go to great lengths to rigorously show that the method converges to bicubic B-spline surfaces.[1]

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.[2] This method reformulates the recursive refinement process into a matrix exponential problem, which can be solved directly by means of matrix diagonalization.

Software using Catmull–Clark subdivision surfaces

See also

References

  1. 1 2 3 Catmull, E.; Clark, J. (1978). "Recursively generated B-spline surfaces on arbitrary topological meshes" (PDF). Computer-Aided Design 10 (6): 350. doi:10.1016/0010-4485(78)90110-0.
  2. Stam, J. (1998). "Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values". Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98 (PDF). pp. 395–404. doi:10.1145/280814.280945. ISBN 0-89791-999-8.
  3. Manuel Kraemer (2014). "OpenSubdiv: Interoperating GPU Compute and Drawing". In Martin Watt, Erwin Coumans, George ElKoura, Ronald Henderson, Manuel Kraemer, Jeff Lait, James Reinders. Multithreading for Visual Effects. CRC Press. pp. 163–199. ISBN 978-1-4822-4356-7.
  4. https://www.youtube.com/watch?v=xFZazwvYc5o
  5. http://www.fxguide.com/featured/pixars-opensubdiv-v2-a-detailed-look/
  6. http://on-demand.gputechconf.com/gtc/2014/video/S4856-subdivision-surfaces-industry-standard.mp4
  7. https://www.youtube.com/watch?v=dzIl_S-qHIQ

Further reading

This article is issued from Wikipedia - version of the Monday, April 11, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.