"Subdiv" redirects here. For submarine divisions, seeSUBDIV.
"SubD" redirects here. For the subminiature connector, seeD-Sub.
In the field of3D computer graphics, asubdivision surface (commonly shortened toSubD surface orSubsurf) is a curvedsurface represented by the specification of a coarserpolygon mesh and produced by arecursive algorithmic method. The curved surface, the underlyinginner mesh,[1] can be calculated from the coarse mesh, known as thecontrol cage orouter mesh, as the functionallimit of an iterative process of subdividing eachpolygonalface 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.
Simple subdivision of a cube up to 3Atessellation pipeline using a subdivision method
A subdivision surface algorithm isrecursive in nature. The process starts with a base level polygonal mesh. Arefinement 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 adenser 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 subdivisionlevel, starting at zero (before any refinement occurs).
Thelimit 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 (), number of times.
Mathematically, theneighborhood of anextraordinary vertex (non-4-valent node for quad refined meshes) of a subdivision surface is aspline with a parametricallysingular point.[3]
Subdivision surface refinement schemes can be broadly classified into two categories:interpolating andapproximating.
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 tospline surfaces and curves, whereBézier curves are required to interpolate certain control points, whileB-Splines 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 means that the limit surfaces approximate the initial meshes, and that after subdivision the newly generated control points are not in the limit surfaces.[clarification needed] There are five approximating subdivision schemes:
Catmull and Clark (1978), Quads – generalizesbi-cubicuniformB-spline knot insertion. For arbitrary initial meshes, this scheme generates limit surfaces that areC2 continuous everywhere except at extraordinary vertices where they areC1 continuous (Peters and Reif 1998).[4]
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[5]) for curves to surfaces. They used the analytical expression ofbi-quadratic uniform B-spline surface to generate their subdivision procedure to produceC1 limit surfaces with arbitrary topology for arbitrary initial meshes. An auxiliary point can improve the shape of Doo-Sabin subdivision.[6] After a subdivision, all vertices havevalence 4.[7]
Loop (1987), Triangles – Loop proposed his subdivision scheme based on a quarticbox-spline of six direction vectors to provide a rule to generateC2 continuous limit surfaces everywhere except at extraordinary vertices where they areC1 continuous (Zorin 1997).
Mid-Edge subdivision scheme (1997–1999) – The mid-edge subdivision scheme was proposed independently by Peters-Reif (1997)[8] and Habib-Warren (1999).[9] The former used the mid-point of each edge to build the new mesh. The latter used a four-directionalbox spline to build the scheme. This scheme generatesC1 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 (2000), Triangles – This scheme was developed by Kobbelt[10] and offers several interesting features: it handles arbitrary triangular meshes, it isC2 continuous everywhere except at extraordinary vertices where it isC1 continuous and it offers a natural adaptive refinement when required. It exhibits at least two specificities: it is aDual scheme for triangle meshes and it has a slower refinement rate than primal ones.
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;[11] while in 1993 Halstead, Kass, and DeRose proposed one for Catmull-Clark.[12]
Butterfly (1990), Triangles – named after the scheme's shape
Modified Butterfly (1996), Quads[13] – designed to overcome artifacts generated by irregular topology
Kobbelt (1996), Quads – a variational subdivision method that tries to overcome uniform subdivision drawbacks
^K. Karciauskas and J. Peters:Point-augmented biquadratic C1 subdivision surfaces, Graphical Models, 77, p.18-26[1][permanent dead link]
^Joy, Ken (1996–2000)."DOO-SABIN SURFACES"(PDF).On-Line Geometric Modeling Notes – via UC Davis.
^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 ofC1 subdivision surfaces, Computer Aided Geometric Design 16(4) (May 1999) p.223-247,doi
^L. Kobbelt:√3-subdivision, 27th annual conference on Computer graphics and interactive techniques,doi
^Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991), 89–96.
^Halstead, M., Kass, M., and DeRose, T. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph
.png)
