View source for Catmull–Clark subdivision surface

{{short description|Technique in 3D computer graphics}}
[[File:Catmull-Clark subdivision of a cube.svg|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]].)]]
[[File:Catmull-Clark_limit_surface_of_Cube_(compare_sphere).png|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]] [[3D modeling|modeling]]. It was devised by [[Edwin Catmull]] and [[James H. Clark|Jim Clark]] in 1978 as a generalization of [[bi-cubic]] ''[[Spline (mathematics)#Definition|uniform]]'' [[B-spline]] surfaces to arbitrary [[topology]].<ref name=CatmullClark/>

In 2005/06, Edwin Catmull, together with [[Tony DeRose]] and [[Jos Stam]], received an [[Academy Award for Technical Achievement]] for their invention and application of subdivision surfaces. DeRose wrote about "efficient, fair interpolation" and character animation. Stam described a technique for a direct evaluation of the limit surface without recursion.

== Recursive evaluation ==
Catmull–Clark surfaces are defined [[Recursion|recursively]], using the following ''refinement scheme.''<ref name=CatmullClark>{{Cite journal | last1 = Catmull | first1 = E. | author-link1= Edwin Catmull| last2 = Clark | first2 = J. |author-link2 = James H. Clark| doi = 10.1016/0010-4485(78)90110-0 | title = Recursively generated B-spline surfaces on arbitrary topological meshes | journal = Computer-Aided Design | volume = 10 | issue = 6 | pages = 350 | year = 1978 | s2cid = 121149868 | url = http://www.cs.berkeley.edu/~sequin/CS284/PAPERS/CatmullClark_SDSurf.pdf}}</ref>

Start with a [[Polygon mesh|mesh]] of an arbitrary [[polyhedron]]. All the [[vertex (geometry)|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 face[[File:Catmull-Clark Recursive Step 1.png|none|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><ref>{{Cite web|title=Catmull–Clark subdivision surface - Rosetta Code|url=https://rosettacode.org/wiki/Catmull%E2%80%93Clark_subdivision_surface|access-date=2022-01-13|website=rosettacode.org}}</ref>[[File:Catmull-Clark Recursive Step 2.png|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)[[File:Catmull-Clark Recursive Step 3.png|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 face[[File:Catmull-Clark Recursive Step 4.png|none|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 [[File:Catmull-Clark Recursive Step 5.png|none|thumb|220x220px|3 new edges per vertex point of shifted original vertices]]
** Define new faces as enclosed by edges [[File:Catmull-Clark recursive step 6.png|none|thumb|220x220px|Final faces to the mesh]]

=== Properties ===
The new mesh will consist only of [[quadrilateral]]s, which in general will ''not'' be [[Plane (mathematics)|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 [[Aesthetics|aesthetic appearance]] of the resulting surfaces rather than on a [[Mathematical proof|mathematical derivation]], although they do go to great lengths to rigorously show that the method [[Convergence (math)|converges]] to bicubic B-spline surfaces.<ref name="CatmullClark" />

It can be shown that the limit surface obtained by this refinement process is at least <math>\mathcal{C}^1</math> at extraordinary vertices and <math>\mathcal{C}^2</math> everywhere else (when ''n'' indicates [[Smooth function#Differentiability classes|how many derivatives are continuous]], we speak of <math>\mathcal{C}^n</math> [[Continuously differentiable|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).<ref name="Stam">{{cite book| last1 = Stam| first1 = J.| author1-link = Jos Stam| chapter = Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values| doi = 10.1145/280814.280945| title = Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98| chapter-url = http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/sig98.pdf| pages = [https://archive.org/details/computergraphics1998sigg/page/395 395–404]| year = 1998| isbn = 978-0-89791-999-9| citeseerx = 10.1.1.20.7798| s2cid = 2771758| url = https://archive.org/details/computergraphics1998sigg/page/395}}</ref> This method reformulates the recursive refinement process into a [[matrix exponential]] problem, which can be solved directly by means of [[matrix diagonalization]].

== Software using the algorithm ==
{{More citations needed section|date=April 2013}}
{{colbegin|colwidth=20em}}
* [[Autodesk 3ds Max|3ds Max]]
* [[3D-Coat]]
* [[AC3D]]
* [[Anim8or]]
* [[AutoCAD]]
* [[Blender (software)|Blender]]<ref>{{Cite web | url=https://docs.blender.org/manual/en/latest/modeling/modifiers/generate/subdivision_surface.html | title=Subdivision Surface Modifier| date=2020-01-15}}</ref>
* [[Carrara (software)|Carrara]]
* [[CATIA|CATIA (Imagine and Shape)]]
* [[CGAL]]
* [[Cheetah3D]]
* [[Cinema4D]]
* [[Clara.io]]
* [[PTC Creo|Creo (Freestyle)]]<ref>{{Cite web |url=http://www.ptc.com/File%20Library/Community/Academic%20Program/College_Student_Primer_Creo_2.pdf |title=Archived copy |access-date=2016-12-04 |archive-url=https://web.archive.org/web/20161123062105/http://www.ptc.com/File%20Library/Community/Academic%20Program/College_Student_Primer_Creo_2.pdf |archive-date=2016-11-23 |url-status=dead }}</ref>
* [[Daz Studio|Daz Studio, 2.0]]
* [[DeleD Community Edition]]
* [[DeleD Designer]]
* [[Valve Hammer Editor|Hammer]]
* [[Hexagon (software)|Hexagon]]
* [[Houdini (software)|Houdini]]
<!--* JPatch-->
* [[LightWave|LightWave 3D, version 9]]
* [[Makehuman]]
* [[Maya (software)|Maya]]
* [[Metasequoia (software)|Metasequoia]]
* [[Modo (software)|MODO]]
* [[Mudbox]]
* [[NPowerSoftware Power Surfacing|Power Surfacing add-in for SolidWorks]]
* Pixar's [[OpenSubdiv]]<ref name="WattCoumans2014">{{cite book|editor=Martin Watt |editor2=Erwin Coumans |editor3=George ElKoura |editor4=Ronald Henderson |editor5=Manuel Kraemer |editor6=Jeff Lait |editor7=James Reinders |display-editors=3 |title=Multithreading for Visual Effects|year=2014|publisher=CRC Press|isbn=978-1-4822-4356-7|pages=163–199|author=Manuel Kraemer|chapter=OpenSubdiv: Interoperating GPU Compute and Drawing}}</ref><ref>{{cite AV media |url-status = live |archive-url = https://ghostarchive.org/varchive/youtube/20211211/xFZazwvYc5o |archive-date = 2021-12-11| url = https://www.youtube.com/watch?v=xFZazwvYc5o |title = Meet the Experts: Pixar Animation Studios, The OpenSubdiv Project |website=[[YouTube]]}}{{cbignore}}</ref><ref>{{Cite web | url=http://www.fxguide.com/featured/pixars-opensubdiv-v2-a-detailed-look/ | title=Pixar's OpenSubdiv V2: A detailed look| date=2013-09-18}}</ref><ref>[http://on-demand.gputechconf.com/gtc/2014/video/S4856-subdivision-surfaces-industry-standard.mp4 AV Media] gputechconf.com</ref><ref>{{cite AV media |url-status = live |archive-url = https://ghostarchive.org/varchive/youtube/20211211/dzIl_S-qHIQ |archive-date = 2021-12-11| url = https://www.youtube.com/watch?v=dzIl_S-qHIQ |title = OpenSubdiv Blender demo |website=[[YouTube]]}}{{cbignore}}</ref>
* [[PhotoRealistic RenderMan|PRMan]]
* [[Realsoft3D]]
* [[Remo 3D]]
* [[Shade 3D|Shade]]
* [[Rhinoceros 3D]] - Grasshopper 3D Plugin - Weaverbird Plugin
* [[Silo (software)|Silo]]
* [[SketchUp]] - Requires a Plugin.
* [[Softimage XSI]]
* [[Strata 3D|Strata 3D CX]]
<!--* Vue 9-->
* [[Wings 3D]]
* [[Zbrush]]
<!--* TopoGun-->
<!--* CREO 1.0 - PTC - (Freestyle)-->
{{colend}}

== See also ==
* [[Conway polyhedron notation]] - A set of related topological polyhedron and polygonal mesh operators.
*[[Doo–Sabin subdivision surface|Doo-Sabin subdivision surface]]
*[[Loop subdivision surface]]

== References ==
{{reflist}}

==Further reading==
* {{Cite book| doi = 10.1145/280814.280826| chapter = Subdivision surfaces in character animation| title = Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98| pages = [https://archive.org/details/computergraphics1998sigg/page/85 85]| year = 1998| last1 = Derose| first1 = T.| last2 = Kass| first2 = M.| last3 = Truong| first3 = T.| isbn = 978-0897919999| chapter-url = http://graphics.pixar.com/library/Geri/paper.pdf| citeseerx = 10.1.1.679.1198| s2cid = 1221330| url = https://archive.org/details/computergraphics1998sigg/page/85}}
* {{Cite journal | doi = 10.1145/1330511.1330519| title = Approximating Catmull-Clark subdivision surfaces with bicubic patches| journal = ACM Transactions on Graphics| volume = 27| pages = 1–11| year = 2008| last1 = Loop | first1 = C. | last2 = Schaefer | first2 = S. | url = http://research.microsoft.com/en-us/um/people/cloop/accTOG.pdf| citeseerx = 10.1.1.153.2047| s2cid = 6068564}}
* {{Cite journal | doi = 10.1109/TVCG.2010.31| pmid = 20616390| title = Real-Time Creased Approximate Subdivision Surfaces with Displacements| journal = IEEE Transactions on Visualization and Computer Graphics| volume = 16| issue = 5| pages = 742–51| year = 2010| last1 = Kovacs | first1 = D. | last2 = Mitchell | first2 = J. | last3 = Drone | first3 = S. | last4 = Zorin | first4 = D. | s2cid = 17138394| url = http://www.computer.org/csdl/trans/tg/2010/05/ttg2010050742.pdf}} [http://mrl.nyu.edu/~dzorin/papers/kovacs2010rcs.pdf preprint]
* Matthias Nießner, Charles Loop, Mark Meyer, Tony DeRose, "[http://research.microsoft.com/en-us/um/people/cloop/tog2012.pdf Feature Adaptive GPU Rendering of Catmull-Clark Subdivision Surfaces]", ACM Transactions on Graphics Volume 31 Issue 1, January 2012, {{doi|10.1145/2077341.2077347}}, [https://www.youtube.com/watch?v=uogAzQoVdNU demo]
* Nießner, Matthias; Loop, Charles; Greiner, Günther: [http://research.microsoft.com/en-us/um/people/cloop/EG2012.pdf 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, [https://archive.org/details/GDC2014Brainerd 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), ([https://dx.doi.org/10.1016/0010-4485(78)90111-2 doi], [http://www.cs.caltech.edu/~cs175/cs175-02/resources/DS.pdf pdf])

{{DEFAULTSORT:Catmull-Clark Subdivision Surface}}
[[Category:3D computer graphics]]
[[Category:Multivariate interpolation]]