A subdivision surface, in the field of 3D computer graphics, is a method of representing a smooth surface via the specification of a coarser piecewise linear polygon mesh. 3D computer graphics (in contrast to 2D computer graphics) are graphics that use a three-dimensional representation of geometric data that is stored in the computer In Mathematics, specifically in Topology, a surface is a Two-dimensional Manifold. Piecewise linear may refer to Piecewise linear function Piecewise linear manifold A polygon mesh or Unstructured grid is a collection of vertices edges and faces that defines the shape of a polyhedral object in 3D computer The smooth surface can be calculated from the coarse mesh as the limit of an iterative process of subdividing each polygonal face into smaller faces that better approximate the smooth surface. In Mathematics, the concept of a " limit " is used to describe the Behavior of a function as its argument either "gets close" In Geometry, a face of a Polyhedron is any of the Polygons that make up its boundaries

First three steps of Catmull-clark subdivision of a cube with subdivision surface below

Overview

The subdivision surfaces algorithm is recursive in nature. The process starts with a given 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. In some refinement schemes, the positions of old vertices might also be altered (possibly based on the positions of new vertices).

This process produces a denser mesh than the original one, containing more polygonal faces. This resulting mesh can be passed through the same refinement scheme again and so on.

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 usually fairly small, number of times.

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 splines are required to interpolate certain control points, while B-Splines are not. In the mathematical field of Numerical analysis, a spline is a special function defined Piecewise by Polynomials In interpolating In the mathematical field of Numerical analysis, a Bézier curve is a Parametric curve important in Computer graphics and related fields In the mathematical subfield of Numerical analysis, a B-spline is a spline function that has minimal support with respect to a given degree

There is another division in subdivision surface schemes as well: the type of polygon that they operate on. Some function for quadrilaterals (quads), while others operate on triangles.

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 four approximating subdivision schemes:

• Catmull and Clark (1978) generalized bi-cubic uniform B-spline to produce their subdivision scheme. For arbitrary initial meshes, this scheme generates limit surfaces that are C² continuous everywhere except at extraordinary vertices where they are C¹ continuous (Peters and Reif 1998). Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve
• Doo-Sabin - The second subdivision scheme was developed by Doo and Sabin (1978) who successfully extended Chaikin's corner-cutting method for curves to surfaces. They used the analytical expression of bi-quadratic uniform B-spline surface to generate their subdivision procedure to produce C¹ limit surfaces with arbitrary topology for arbitrary initial meshes. Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve
• Loop, Triangles - Loop (1987) proposed his subdivision scheme based on a quartic box-spline of six direction vectors to provide a rule to generate C² continuous limit surfaces everywhere except at extraordinary vertices where they are C¹ continuous (Zorin 1997). In Computer graphics, Loop Subdivision surface is a subdivision scheme developed by Charles Loop in 1987 for triangular meshes. Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve
• Mid-Edge subdivision scheme - The mid-edge subdivision scheme was proposed independently by Peters-Reif (1997) and Habib-Warren (1999). 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 C¹ continuous limit surfaces on initial meshes with arbitrary topology. Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve
• √3 subdivision scheme - This scheme has been developed by Kobbelt (2000) and offers several interesting features: it handles arbitrary triangular meshes, it is C² continuous everywhere except at extraordinary vertices where it is C¹ continuous and it offers a natural adaptive refinement when required. Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve 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 new 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 Swelden (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.

• Butterfly, Triangles - named after the scheme's shape
• Midedge, Quads
• Kobbelt, Quads - a variational subdivision method that tries to overcome uniform subdivision drawbacks

Key developments

• 1978: Subdivision surfaces were discovered simultaneously by Edwin Catmull and Jim Clark (see Catmull-Clark subdivision surface). Edwin Catmull, PhD (born 1945 in Parkersburg, West Virginia) is an Academy Award winning Computer scientist and current president of Walt In the same year, Daniel Doo and Malcom Sabin published a paper building on this work (see Doo-Sabin subdivision surfaces. )
• 1995: Ulrich Reif solved subdivision surface behaviour near extraordinary vertices ^[1].
• 1998: Jos Stam contributed a method for exact evaluation for Catmull-Clark subdivision surfaces under arbitrary parameter values ^[2]. Jos Stam is a leading researcher in the field of Computer graphics, focusing on Subdivision surfaces, rendering algorithms and the simulation of natural physical phenomena

External links

• Resources about Subdvisions
• Geri's Game : Oscar winning animation by Pixar completed in 1997 that introduced subdivision surfaces (along with cloth simulation)
• Subdivision for Modeling and Animation tutorial, SIGGRAPH 1999 course notes
• Subdivision for Modeling and Animation tutorial, SIGGRAPH 2000 course notes
• A unified approach to subdivision algorithms near extraordinary vertices, Ulrich Reif (Computer Aided Geometric Design 12(2):153-174 March 1995)
• Subdivision of Surface and Volumetric Meshes, software to perform subdivision using the most popular schemes
• Surface Subdivision Methods in CGAL, the Computational Geometry Algorithms Library

References

1. ^ Ulrich Reif. Pixar Animation Studios is a CGI animation production company based in Emeryville California. SIGGRAPH (short for S pecial I nterest G roup on GRAPH ics and Interactive Techniques is the name of the annual conference on Computer graphics SIGGRAPH (short for S pecial I nterest G roup on GRAPH ics and Interactive Techniques is the name of the annual conference on Computer graphics 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design. 12(2)153-174
2. ^ 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

• J. Peters and U. Reif: The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics 16(4) (October 1997) p. 420-431, doi.
• A. Habib and J. Warren: Edge and vertex insertion for a class of C¹ subdivision surfaces, Computer Aided Geometric Design 16(4) (May 1999) p. Parametric continuity is a concept applied to Parametric curves describing the smoothness of the parameter's value with distance along the curve 223-247, doi.
• L. Kobbelt: √3-subdivision, 27th annual conference on Computer graphics and interactive techniques, doi.