The Catmull–Clark

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

is a technique used in

3D computer graphics 3D computer graphics, sometimes called Computer-generated imagery, CGI, 3D-CGI or three-dimensional Computer-generated imagery, computer graphics, are graphics that use a three-dimensional representation of geometric data (often Cartesian coor ...

to create curved surfaces by using

subdivision surface In the field of 3D computer graphics, a subdivision surface (commonly shortened to SubD surface or Subsurf) is a curved Computer representation of surfaces, surface represented by the specification of a coarser polygon mesh and produced by a re ...

modeling. It was devised by

Edwin Catmull Edwin Earl Catmull (born March 31, 1945) is an American computer scientist and animator who served as the co-founder of Pixar and the President of Walt Disney Animation Studios. He has been honored for his contributions to 3D computer graphics, ...

and

Jim Clark James Clark (4 March 1936 – 7 April 1968) was a British racing driver from Scotland, who competed in Formula One from to . Clark won two Formula One World Drivers' Championship titles with Lotus, and—at the time of his death—held the ...

in 1978 as a generalization of bi-cubic ''

uniform A uniform is a variety of costume worn by members of an organization while usually participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency serv ...

B-spline In numerical analysis, a B-spline (short for basis spline) is a type of Spline (mathematics), spline function designed to have minimal Support (mathematics), support (overlap) for a given Degree of a polynomial, degree, smoothness, and set of bre ...

surfaces to arbitrary

topology Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...

. In 2005/06, Edwin Catmull, together with Tony DeRose and Jos Stam, received an

Academy Award for Technical Achievement The Technical Achievement Award is one of three Scientific and Technical Awards given from time to time by the Academy of Motion Picture Arts and Sciences. (The other two awards are the Scientific and Engineering Award and the Academy Award of M ...

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 recursively, using the following ''refinement scheme.'' Start with a

mesh Medical Subject Headings (MeSH) is a comprehensive controlled vocabulary for the purpose of indexing journal articles and books in the life sciences. It serves as a thesaurus of index terms that facilitates searching. Created and updated by th ...

of an arbitrary

polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal Face (geometry), faces, straight Edge (geometry), edges and sharp corners or Vertex (geometry), vertices. The term "polyhedron" may refer ...

. 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 In colloquial, ordinary language, an average is a single number or value that best represents a set of data. The type of average taken as most typically representative of a list of numbers is the arithmetic mean the sum of the numbers divided by ...

of all ''original points'' for the respective face Catmull-Clark Recursive Step 1

* 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)''

\frac

* 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''

\frac

(This is the

barycenter In astronomy, the barycenter (or barycentre; ) is the center of mass of two or more bodies that orbit one another and is the point about which the bodies orbit. A barycenter is a dynamical point, not a physical object. It is an important con ...

of ''P'', ''R'' and ''F'' with respective weights (''n'' − 3), 2 and 1) Catmull-Clark Recursive Step 3

*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 Catmull-Clark Recursive Step 4

** Connect each new ''vertex point'' to the new ''edge points'' of all original edges incident on the original vertex Catmull-Clark Recursive Step 5

** Define new faces as enclosed by edges Catmull-Clark recursive step 6

Properties

The new mesh will consist only of

quadrilateral In Euclidean geometry, geometry a quadrilateral is a four-sided polygon, having four Edge (geometry), edges (sides) and four Vertex (geometry), corners (vertices). The word is derived from the Latin words ''quadri'', a variant of four, and ''l ...

s, 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

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. It can be shown that the limit surface obtained by this refinement process is at least

\mathcal^1

at extraordinary vertices and

\mathcal^2

everywhere else (when ''n'' indicates how many derivatives are continuous, we speak of

\mathcal^n

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 In mathematics, the matrix exponential is a matrix function on square matrix, square matrices analogous to the ordinary exponential function. It is used to solve systems of linear differential equations. In the theory of Lie groups, the matrix exp ...

problem, which can be solved directly by means of

matrix diagonalization In linear algebra, a square matrix A is called diagonalizable or non-defective if it is similar to a diagonal matrix. That is, if there exists an invertible matrix P and a diagonal matrix D such that . This is equivalent to (Such D are not ...

Software using the algorithm

3ds Max Autodesk 3ds Max, formerly 3D Studio and 3D Studio Max, is a professional 3D computer graphics program for making 3D animations, models, games and images. It is developed and produced by Autodesk Media and Entertainment. It has modeling capab ...

* 3D-Coat * AC3D * Anim8or *

AutoCAD AutoCAD is a 2D and 3D computer-aided design (CAD) software application developed by Autodesk. It was first released in December 1982 for the CP/M and IBM PC platforms as a desktop app running on microcomputers with internal graphics control ...

Blender A blender (sometimes called a mixer (from Latin ''mixus, the PPP of miscere eng. to Mix)'' or liquidiser in British English) is a kitchen and laboratory appliance used to mix, crush, purée or emulsify food and other substances. A stationary ...

Carrara Carrara ( ; ; , ) is a town and ''comune'' in Tuscany, in central Italy, of the province of Massa and Carrara, and notable for the white or blue-grey Carrara marble, marble quarried there. It is on the Carrione River, some Boxing the compass, ...

* CATIA (Imagine and Shape) * CGAL * Cheetah3D *

Cinema4D Cinema 4D is a 3D software suite developed by the German company Maxon. Overview As of R21, only a single version of Cinema 4D is available. It replaces all previous variants, including BodyPaint 3D, and includes all features of the past 'Stu ...

Clara.io Clara.io is web-based freemium 3D computer graphics software developed by Exocortex, a Canadian software company. The free or "Basic" component of their freemium offering, however, places severe restrictions, such as on saving models and importing ...

* Creo (Freestyle) * Daz Studio, 2.0 * DeleD Community Edition * DeleD Designer *

Hammer A hammer is a tool, most often a hand tool, consisting of a weighted "head" fixed to a long handle that is swung to deliver an impact to a small area of an object. This can be, for example, to drive nail (fastener), nails into wood, to sh ...

Hexagon In geometry, a hexagon (from Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A regular hexagon is de ...

Houdini Erik Weisz (March 24, 1874 – October 31, 1926), known professionally as Harry Houdini ( ), was a Hungarian-American escapologist, illusionist, and stunt performer noted for his escape acts. Houdini first attracted notice in vaudeville in ...

* LightWave 3D, version 9 * Makehuman *

Maya Maya may refer to: Ethnic groups * Maya peoples, of southern Mexico and northern Central America ** Maya civilization, the historical civilization of the Maya peoples ** Mayan languages, the languages of the Maya peoples * Maya (East Africa), a p ...

Metasequoia ''Metasequoia'', or dawn redwood, is a genus of fast-growing coniferous trees. It contains one extant (living) species, ''Metasequoia glyptostroboides'', which is one of three extant species of conifers known as redwoods in the world. ''Metaseq ...

* MODO *

Mudbox Mudbox is a proprietary computer-based 3D sculpting and painting tool. developed by Autodesk, Mudbox was created by Skymatter, founded by Tibor Madjar, David Cardwell and Andrew Camenisch, former artists of Weta Digital, where the tool was f ...

* Power Surfacing add-in for SolidWorks * Pixar's OpenSubdiv * PRMan * Realsoft3D * Remo 3D *

Shade Shade, Shades or Shading may refer to: * Shade (color), a mixture of a color with black (often generalized as any variety of a color) * Shade (shadow), the blocking of sunlight * Shades or sunglasses * Shading, a process used in art and graphic ...

Rhinoceros 3D Rhinoceros (typically abbreviated Rhino or Rhino3D) is a commercial 3D computer graphics and computer-aided design (CAD) application software that was developed by TLM, Inc, dba Robert McNeel & Associates, an American, privately held, and employ ...

- Grasshopper 3D Plugin - Weaverbird Plugin *

Silo A silo () is a structure for storing Bulk material handling, bulk materials. Silos are commonly used for bulk storage of grain, coal, cement, carbon black, woodchips, food products and sawdust. Three types of silos are in widespread use toda ...

SketchUp SketchUp is a proprietary 3D modeling software that is used to create and manipulate 3D models. It is used in architecture and interior design. SketchUp is owned by Trimble (company), Trimble Inc. The software has a free web-based version, and ...

- Requires a Plugin. * Softimage XSI * Strata 3D CX * Wings 3D * Zbrush

Recursive evaluation

Properties

Exact evaluation

Software using the algorithm

See also

References

Further reading