Subdivision surface

Last updated March 20, 2024

In the field of 3D computer graphics, a subdivision surface (commonly shortened to SubD surface or Subsurf) is a curved surface represented by the specification of a coarser polygon mesh and produced by a recursive algorithmic method. The curved surface, the underlying inner mesh,^[1] 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 face 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.

Overview

A subdivision surface algorithm is recursive 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 of an extraordinary vertex (non-4-valent node for quad refined meshes) of a subdivision surface is a spline with a parametrically singular point.^[3]

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 curves are required to interpolate certain control points, while B-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 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.^{[ clarification needed ]} There are five approximating subdivision schemes:

Catmull and Clark (1978), Quads – generalizes bi-cubic uniform B-spline knot insertion. 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).^[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 of bi-quadratic uniform B-spline surface to generate their subdivision procedure to produce C¹ 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 have valence 4.^[7]
Loop (1987), Triangles – Loop 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).
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-directional box spline to build the scheme. This scheme generates C¹ 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 is C² continuous everywhere except at extraordinary vertices where it is C¹ 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.

Subdivision Schemes

Catmull–Clark

Doo–Sabin

Loop

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;^[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

Key developments

1978: Subdivision surfaces were described 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.^[14]
1998: Jos Stam contributed a method for exact evaluation for Catmull-Clark subdivision surfaces under arbitrary parameter values.^[15]

Related Research Articles

<span class="mw-page-title-main">Gouraud shading</span> Interpolation method in computer graphics

Gouraud shading, named after Henri Gouraud, is an interpolation method used in computer graphics to produce continuous shading of surfaces represented by polygon meshes. In practice, Gouraud shading is most often used to achieve continuous lighting on triangle meshes by computing the lighting at the corners of each triangle and linearly interpolating the resulting colours for each pixel covered by the triangle. Gouraud first published the technique in 1971. However, enhanced hardware support for superior shading models has yielded Gouraud shading largely obsolete in modern rendering.

Texture mapping is a method for mapping a texture on a computer-generated graphic. Texture here can be high frequency detail, surface texture, or color.

Edwin Earl Catmull 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, including the 2019 ACM Turing Award.

<span class="mw-page-title-main">Geometric primitive</span> Basic shapes represented in vector graphics

In vector computer graphics, CAD systems, and geographic information systems, geometric primitive is the simplest geometric shape that the system can handle. Sometimes the subroutines that draw the corresponding objects are called "geometric primitives" as well. The most "primitive" primitives are point and straight line segment, which were all that early vector graphics systems had.

In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the corresponding domain interval.

In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.

The Catmull–Clark algorithm is a technique used in 3D computer graphics to create curved surfaces by using subdivision surface modeling. It was devised by Edwin Catmull and Jim Clark in 1978 as a generalization of bi-cubic uniform B-spline surfaces to arbitrary topology.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

<span class="mw-page-title-main">Marching cubes</span> Computer graphics algorithm

Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline, for extracting a polygonal mesh of an isosurface from a three-dimensional discrete scalar field. The applications of this algorithm are mainly concerned with medical visualizations such as CT and MRI scan data images, and special effects or 3-D modelling with what is usually called metaballs or other metasurfaces. The marching cubes algorithm is meant to be used for 3-D; the 2-D version of this algorithm is called the marching squares algorithm.

In 3D computer graphics, polygonal modeling is an approach for modeling objects by representing or approximating their surfaces using polygon meshes. Polygonal modeling is well suited to scanline rendering and is therefore the method of choice for real-time computer graphics. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surfaces, and equation-based representations used in ray tracers.

<span class="mw-page-title-main">Lloyd's algorithm</span> Algorithm used for points in euclidean space

In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

In computer graphics, a triangle mesh is a type of polygon mesh. It comprises a set of triangles that are connected by their common edges or vertices.

In 3D computer graphics, a Doo–Sabin subdivision surface is a type of subdivision surface based on a generalization of bi-quadratic uniform B-splines, whereas Catmull-Clark was based on generalized bi-cubic uniform B-splines. The subdivision refinement algorithm was developed in 1978 by Daniel Doo and Malcolm Sabin.

In computer graphics, the Loop method for subdivision surfaces is an approximating subdivision scheme developed by Charles Loop in 1987 for triangular meshes. Prior methods, namely Catmull-Clark and Doo-Sabin (1978), focused on quad meshes.

In mesh generation, Delaunay refinements are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulation of the augmented input to meet the quality requirements of the meshing application. Delaunay refinement methods include methods by Chew and by Ruppert.

In computer graphics, a T-spline is a mathematical model for defining freeform surfaces. A T-spline surface is a type of surface defined by a network of control points where a row of control points is allowed to terminate without traversing the entire surface. The control net at a terminated row resembles the letter "T".

In computer graphics, tessellation is the dividing of datasets of polygons presenting objects in a scene into suitable structures for rendering. Especially for real-time rendering, data is tessellated into triangles, for example in OpenGL 4.0 and Direct3D 11.

This is a glossary of terms relating to computer graphics.

References

↑ "Subdivision Surfaces". nevercenter.com. Retrieved 19 January 2021.
↑ Blender: Reduce Polygons – Simply Explained
↑ J. Peters and U. Reif: Subdivision Surfaces, Springer series Geometry and Computing monograph 3, 2008, doi
↑ J. Peters and U. Reif: Analysis of generalized B-spline subdivision algorithms, SIAM J of Numer. Anal. 32 (2) 1998, p.728-748
↑ "Chaikin Curves in Processing".
↑ K. Karciauskas and J. Peters: Point-augmented biquadratic C¹ subdivision surfaces, Graphical Models, 77, p.18-26 ^[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 of C¹ 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
↑ Zorin, Denis; Schröder, Peter; Sweldens, Wim (1996). "Interpolating Subdivision for Meshes with Arbitrary Topology" (PDF). Department of Computer Science, California Institute of Technology, Pasadena, CA 91125.
↑ 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

External links

Geri's Game : Oscar winning animation by Pixar completed in 1997 that introduced subdivision surfaces using Catmull-Clark subdivision (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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Subdivision Surfaces". nevercenter.com. Retrieved 19 January 2021.

[2] Blender: Reduce Polygons – Simply Explained

[PetersBook-3] J. Peters and U. Reif: Subdivision Surfaces, Springer series Geometry and Computing monograph 3, 2008, doi

[PetersAnalysis-4] J. Peters and U. Reif: Analysis of generalized B-spline subdivision algorithms, SIAM J of Numer. Anal. 32 (2) 1998, p.728-748

[5] "Chaikin Curves in Processing".

[Karciauskas-6] K. Karciauskas and J. Peters: Point-augmented biquadratic C¹ subdivision surfaces, Graphical Models, 77, p.18-26 ^[permanent dead link ]

[7] Joy, Ken (1996–2000). "DOO-SABIN SURFACES" (PDF). On-Line Geometric Modeling Notes– via UC Davis.

[Peters-8] J. Peters and U. Reif: The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics 16(4) (October 1997) p.420-431, doi

[Habib-9] 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.223-247, doi

[Kobbelt-10] L. Kobbelt: √3-subdivision, 27th annual conference on Computer graphics and interactive techniques, doi

[11] Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991), 89–96.

[12] Halstead, M., Kass, M., and DeRose, T. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph

[13] Zorin, Denis; Schröder, Peter; Sweldens, Wim (1996). "Interpolating Subdivision for Meshes with Arbitrary Topology" (PDF). Department of Computer Science, California Institute of Technology, Pasadena, CA 91125.

[Reif-14] Ulrich Reif. 1995. A unified approach to subdivision algorithms near extraordinary vertices. Computer Aided Geometric Design. 12(2)153–174

[Stam-15] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]