Subdivision surface
From Wikipedia, the free encyclopedia
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. 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.
Subdivision surfaces have, in the past 5 years, replaced NURBS surfaces as the preferred method of modeling character and scene geometry in the film and television visual effects industries.
Contents |
[edit] 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 position of the new vertices in the mesh are computed based on the positions of nearby old vertices. In some refinement schemes, the position of old vertices is also altered based on the positions of new vertices.
This process produces a new mesh containing many more polygonal faces than the original one did. The resulting mesh can be passed through the same refinement scheme again, this allowing for greater refinement.
The ultimate goal of iteratively applying a refinement scheme is to take the a given mesh and make it smoother.
[edit] 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.
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.
[edit] 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:
- Doo-Sabin - The first 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 suface to generate their subdivision procedure to produce C1 limit surfaces with arbitrary topology for arbitrary initial meshes.
- Catmull-Clark - Catmull and Clark (1978) generalized bi-cubic uniform B-spline to produce their subdivision scheme. For arbitrary initial meshes, this schemes generate limit surfaces that are C2 continuous everywhere except at extraordinay vertices where they are C1 continuous (Peters and Reif 1998).
- Loop, Triangles - Loop (1987) 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 t extraordinay vertices where they are C1 continuous (Zorin 1997).
- 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 C1 continuous limit surfaces on initial meshes with arbitrary topology.
[edit] Interpolating Schemces
After subdivision, the control points of the original mesh and the new generated control points are interpolated on the limit suface. 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.
- Doo-Sabin, Quads - generalization of bi-quadratic uniform B-splines
- Butterfly, Triangles - named after the scheme's shape
- Midedge, Quads
- Kobbelt, Quads - a variational subdivision method that tries to overcome uniform subdivision drawbacks
[edit] Benefits over NURBS surfaces
The main benefits of subdivision surfaces over NURBS subdivision surfaces from an artist's perspective are:
- They support complex topologies
- The artist has local control over surface smoothness
- The artist can specify the degree of surface refinement
- They can be rendered directly (there is no need to tessellate a polygonal surface as a precursor to rendering.)
[edit] Disadvantages over NURBS surfaces
- Flat sections in the original mesh are prone to having subtle waves, particularly after many iterations.
- Some approximating algorithms can over-smooth a surface, removing specific details after several iterations.
[edit] Key developments
- 1978: Subdivision surfaces were discovered simultaneously by Edwin Catmull 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 [1].
- 1998: Jos Stam contributed a method for exact evaluation for Catmull-Clark subdivision surfaces under arbitrary parameter values [2].
[edit] 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 2000 course notes
- A unified approach to subdivision algorithms near extraordinary vertices, Ulrich Reif (Computer Aided Geometric Design 12(2):153-174 March 1995)
[edit] References
- ^ Ulrich Reif. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design. 12(2)153-174
- ^ 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
Doo,D and Sabin, M. 1978. Behavior of recurcive division surfaces near extraordinary points. Computer-Aided Desing. 10(6)356-360