Subdivision surface
   HOME

TheInfoList



OR:

In the field of
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 ...
, a subdivision surface (commonly shortened to SubD surface or Subsurf) is a curved
surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...
represented by the specification of a coarser
polygon mesh In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedron, polyhedral object's surface. It simplifies Rendering (computer graphics), rendering, as in a wire-frame model. The fac ...
and produced by a
recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
algorithmic method. The curved surface, the underlying ''inner mesh'', can be calculated from the coarse mesh, known as the ''control cage'' or ''outer mesh'', as the functional limit of an iterative process of subdividing each
polygonal In geometry, a polygon () is a plane (mathematics), plane Shape, figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its ''edge (geometry), edges'' or ''sides''. The p ...
face The face is the front of the head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may affect th ...
into smaller faces that better approximate the final underlying curved surface. Less commonly, a simple algorithm is used to add geometry to a mesh by subdividing the faces into smaller ones without changing the overall shape or volume. The opposite is reducing polygons or un-subdividing.


Overview

A subdivision surface algorithm is
recursive Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
in nature. The process starts with a base level polygonal mesh. A refinement scheme is then applied to this mesh. This process takes that mesh and subdivides it, creating new vertices and new faces. The positions of the new vertices in the mesh are computed based on the positions of nearby old vertices, edges, and/or faces. In many refinement schemes, the positions of old vertices are also altered (possibly based on the positions of new vertices). This process produces a ''denser'' mesh than the original one, containing more polygonal faces (often by a factor of 4). This resulting mesh can be passed through the same refinement scheme again and again to produce more and more refined meshes. Each iteration is often called a subdivision ''level'', starting at zero (before any refinement occurs). The ''limit'' subdivision surface is the surface produced from this process being iteratively applied infinitely many times. In practical use however, this algorithm is only applied a limited, and fairly small (\leq 5), number of times. Mathematically, the
neighborhood A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of an ''extraordinary vertex'' (non-4- valent node for quad refined meshes) of a subdivision surface is a spline with a parametrically singular point.J. Peters and U. Reif: ''Subdivision Surfaces'', Springer series Geometry and Computing monograph 3, 2008
doi
/ref>


Refinement schemes

Subdivision surface refinement schemes can be broadly classified into two categories: ''interpolating'' and ''approximating''. * Interpolating schemes are required to match the original position of vertices in the original mesh. * Approximating schemes are not; they can and will adjust these positions as needed. In general, approximating schemes have greater smoothness, but the user has less overall control of the outcome. This is analogous to spline surfaces and curves, where
Bézier curve A Bézier curve ( , ) is a parametric equation, parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approxima ...
s are required to interpolate certain control points, while
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 ...
s are not (and are more approximate). Subdivision surface schemes can also be categorized by the type of polygon that they operate on: some function best for quadrilaterals (quads), while others primarily operate on triangles (tris).


Approximating schemes

''Approximating'' means that the limit surfaces approximate the initial meshes, and that after subdivision the newly generated control points are not in the limit surfaces. There are five approximating subdivision schemes: * Catmull and Clark (1978), Quads – generalizes 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 ...
knot insertion. For arbitrary initial meshes, this scheme generates limit surfaces that are C2 continuous everywhere except at extraordinary vertices where they are C1 continuous (Peters and Reif 1998).J. Peters and U. Reif: ''Analysis of generalized B-spline subdivision algorithms'', SIAM J of Numer. Anal. 32 (2) 1998, p.728-748 * Doo-Sabin (1978), Quads – The second subdivision scheme was developed by Doo and Sabin, who successfully extended Chaikin's corner-cutting method (George Chaikin, 1974) for curves to surfaces. They used the analytical expression of bi-quadratic uniform B-spline surface to generate their subdivision procedure to produce C1 limit surfaces with arbitrary topology for arbitrary initial meshes. An auxiliary point can improve the shape of Doo-Sabin subdivision.K. Karciauskas and J. Peters: ''Point-augmented biquadratic C1 subdivision surfaces'', Graphical Models, 77, p.18-2

/ref> After a subdivision, all vertices have '' Degree (graph theory), valence'' 4. * Loop (1987), Triangles – Loop proposed his subdivision scheme based on a quartic box-spline of six direction vectors to provide a rule to generate C2 continuous limit surfaces everywhere except at extraordinary vertices where they are C1 continuous (Zorin 1997). * Mid-Edge subdivision scheme (1997–1999) – The mid-edge subdivision scheme was proposed independently by Peters-Reif (1997)J. Peters and U. Reif: ''The simplest subdivision scheme for smoothing polyhedra'', ACM Transactions on Graphics 16(4) (October 1997) p.420-431
doi
/ref> and Habib-Warren (1999).A. Habib and J. Warren: ''Edge and vertex insertion for a class of C1 subdivision surfaces'', Computer Aided Geometric Design 16(4) (May 1999) p.223-247
doi
/ref> The former used the mid-point of each edge to build the new mesh. The latter used a four-directional box spline to build the scheme. This scheme generates C1 continuous limit surfaces on initial meshes with arbitrary topology. (Mid-Edge subdivision, which could be called "√2 subdivision" since two steps halve distances, could be considered the slowest.) *
√3 subdivision scheme The square root of 3 is the positive real number that, when multiplied by itself, gives the number 3 (number), 3. It is denoted mathematically as \sqrt or 3^. It is more precisely called the principal square root of 3 to distinguish it from the ...
(2000), Triangles – This scheme was developed by KobbeltL. Kobbelt: ''√3-subdivision'', 27th annual conference on Computer graphics and interactive techniques
doi
/ref> and offers several interesting features: it handles arbitrary triangular meshes, it is C2 continuous everywhere except at extraordinary vertices where it is C1 continuous and it offers a natural adaptive refinement when required. It exhibits at least two specificities: it is a ''Dual'' scheme for triangle meshes and it has a slower refinement rate than primal ones.


Interpolating schemes

After subdivision, the control points of the original mesh and the newly generated control points are interpolated on the limit surface. The earliest work was so-called " butterfly scheme" by Dyn, Levin and Gregory (1990), who extended the four-point interpolatory subdivision scheme for curves to a subdivision scheme for surface. Zorin, Schröder and Sweldens (1996) noticed that the butterfly scheme cannot generate smooth surfaces for irregular triangle meshes and thus modified this scheme. Kobbelt (1996) further generalized the four-point interpolatory subdivision scheme for curves to the tensor product subdivision scheme for surfaces. In 1991, Nasri proposed a scheme for interpolating Doo-Sabin; while in 1993 Halstead, Kass, and DeRose proposed one for Catmull-Clark. *
Butterfly Butterflies are winged insects from the lepidopteran superfamily Papilionoidea, characterized by large, often brightly coloured wings that often fold together when at rest, and a conspicuous, fluttering flight. The oldest butterfly fossi ...
(1990), Triangles – named after the scheme's shape * Modified Butterfly (1996), Quads – designed to overcome artifacts generated by irregular topology * Kobbelt (1996), Quads – a variational subdivision method that tries to overcome uniform subdivision drawbacks


Key developments

* 1978: Subdivision surfaces were described 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 (see Catmull-Clark subdivision surface), and by Daniel Doo and Malcom Sabin (see Doo-Sabin subdivision surfaces). * 1995: Ulrich Reif solved subdivision surface behaviour near extraordinary vertices.Ulrich Reif. 1995. A unified approach to subdivision algorithms near extraordinary vertices. ''Computer Aided Geometric Design''. 12(2)153–174 * 1998: Jos Stam contributed a method for exact evaluation for Catmull-Clark subdivision surfaces under arbitrary parameter values. Jos Stam, "Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values", Proceedings of SIGGRAPH'98. In Computer Graphics Proceedings, ACM SIGGRAPH, 1998, 395–404


See also

*''
Geri's Game ''Geri's Game'' is a 1997 American animated short film produced by Pixar and written and directed by Jan Pinkava. The film was Pixar's first film to feature a human as its main character. The character later made an appearance in ''Toy Story 2'' ...
'' (1997) – a Pixar movie which pioneered use of subdivision surfaces to represent human skin *
Non-uniform rational B-spline Non-uniform rational basis spline (NURBS) is a mathematical model using B-spline, basis splines (B-splines) that is commonly used in computer graphics for representing curves and Surface (mathematics), surfaces. It offers great flexibility and pr ...
(NURBS) surfaces – another method of representing curved surfaces


References

{{reflist


External links


Geri's Game
: Oscar winning animation by
Pixar Pixar (), doing business as Pixar Animation Studios, is an American animation studio based in Emeryville, California, known for its critically and commercially successful computer-animated feature films. Pixar is a subsidiary of Walt Disney ...
completed in 1997 that introduced subdivision surfaces using Catmull-Clark subdivision (along with cloth simulation)
Subdivision for Modeling and Animation
tutorial,
SIGGRAPH SIGGRAPH (Special Interest Group on Computer Graphics and Interactive Techniques) is an annual conference centered around computer graphics organized by ACM, starting in 1974 in Boulder, CO. The main conference has always been held in North ...
1999 course notes
Subdivision for Modeling and Animation
tutorial,
SIGGRAPH SIGGRAPH (Special Interest Group on Computer Graphics and Interactive Techniques) is an annual conference centered around computer graphics organized by ACM, starting in 1974 in Boulder, CO. The main conference has always been held in North ...
2000 course notes
A unified approach to subdivision algorithms near extraordinary vertices
Ulrich Reif (Computer Aided Geometric Design 12(2):153–174 March 1995)

software to perform subdivision using the most popular schemes
Surface Subdivision Methods in CGAL, the Computational Geometry Algorithms Library
3D computer graphics Multivariate interpolation