Editing Subdivision surface (section)

==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 (mathematics)|spline]] surfaces and curves, where [[Bézier curve]]s are required to interpolate certain control points, while [[B-Spline]]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.{{Clarify|reason=in the limit surface?|date=January 2021}} There are five approximating subdivision schemes:
* [[Catmull-Clark subdivision surface|Catmull and Clark]] (1978), Quads – generalizes [[bi-cubic]] [[Spline (mathematics)#Definition|uniform]] [[B-spline]] knot insertion. For arbitrary initial meshes, this scheme generates limit surfaces that are [[Parametric continuity|C<sup>2</sup>]] continuous everywhere except at extraordinary vertices where they are [[Parametric continuity|C<sup>1</sup>]] continuous (Peters and Reif 1998).<ref name=PetersAnalysis>J. Peters and U. Reif: ''Analysis of generalized B-spline subdivision algorithms'', SIAM J of Numer. Anal. 32 (2) 1998, p.728-748</ref>
* [[Doo-Sabin subdivision surface|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<ref>{{cite web|title=Chaikin Curves in Processing|url=https://sighack.com/post/chaikin-curves}}</ref>) for curves to surfaces. They used the analytical expression of [[Biquadratic|bi-quadratic]] uniform B-spline surface to generate their subdivision procedure to produce [[Parametric continuity|C<sup>1</sup>]] limit surfaces with arbitrary topology for arbitrary initial meshes. An auxiliary point can improve the shape of Doo-Sabin subdivision.<ref name="Karciauskas">K. Karciauskas and J. Peters: ''Point-augmented biquadratic C<sup>1</sup> subdivision surfaces'', Graphical Models, 77, p.18-26 [http://doi:10.1016/j.gmod.2014.10.003]{{Dead link|date=February 2024 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> After a subdivision, all vertices have ''[[Degree (graph theory)|valence]]'' 4.<ref>{{Cite journal|last=Joy|first=Ken|date=1996–2000|title=DOO-SABIN SURFACES|url=https://www.cs.unc.edu/~dm/UNC/COMP258/LECTURES/Doo-Sabin.pdf|journal=On-Line Geometric Modeling Notes|via=UC Davis}}</ref>
* [[Loop subdivision surface|Loop]] (1987), Triangles – Loop proposed his subdivision scheme based on a quartic [[box-spline]] of six direction vectors to provide a rule to generate [[Parametric continuity|C<sup>2</sup>]] continuous limit surfaces everywhere except at extraordinary vertices where they are [[Parametric continuity|C<sup>1</sup>]] continuous (Zorin 1997). 
* [[Mid-Edge subdivision scheme]] (1997–1999) <!-- Quads? Triangles? --> – The mid-edge subdivision scheme was proposed independently by Peters-Reif (1997)<ref name=Peters>J. Peters and U. Reif: ''The simplest subdivision scheme for smoothing polyhedra'', ACM Transactions on Graphics 16(4) (October 1997) p.420-431, [http://doi.acm.org/10.1145/263834.263851 doi]</ref> and Habib-Warren (1999).<ref name=Habib>A. Habib and J. Warren: ''Edge and vertex insertion for a class of [[Parametric continuity|C<sup>1</sup>]] subdivision surfaces'', Computer Aided Geometric Design 16(4) (May 1999) p.223-247, [http://dx.doi.org/10.1016/S0167-8396(98)00045-4 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 [[Parametric continuity|C<sup>1</sup>]] 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<ref name=Kobbelt>L. Kobbelt: ''√3-subdivision'', 27th annual conference on Computer graphics and interactive techniques, [http://doi.acm.org/10.1145/344779.344835 doi]</ref> and offers several interesting features: it handles arbitrary triangular meshes, it is [[Parametric continuity|C<sup>2</sup>]] continuous everywhere except at extraordinary vertices where it is [[Parametric continuity|C<sup>1</sup>]] 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.
{{multiple image
| align = none
| total_width = 1000
| header = Subdivision Schemes
| image1 = Catmull-Clark subdivision 4 planes levels 0-3.png
| caption1 = [[Catmull-Clark subdivision surface|Catmull–Clark]]
| image2 = DooSabin subdivision colorized.png
| caption2 = [[Doo-Sabin subdivision surface|Doo–Sabin]]
| image3 = Loop Subdivision Icosahedron Levels 1 and 2.png
| caption3 = [[Loop subdivision surface|Loop]]
| direction = 
| alt1 = 
}}

===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;<ref>Nasri, A. H. Surface interpolation on irregular networks with normal conditions. Computer Aided Geometric Design 8 (1991), 89–96.</ref> while in 1993 Halstead, Kass, and DeRose proposed one for Catmull-Clark.<ref>Halstead, M., Kass, M., and DeRose, T. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. In Computer Graphics Proceedings (1993), Annual Conference Series, ACM Siggraph</ref>
<!-- * [[Doo-Sabin subdivision surface|Doo-Sabin]], Quads - generalization of bi-quadratic uniform [[B-spline]]s -->
* [[Butterfly subdivision surfaces|Butterfly]] (1990), Triangles – named after the scheme's shape
* [[Midedge|Modified Butterfly]] (1996), Quads<ref>{{Cite journal|last=Zorin|first=Denis|last2=Schröder|first2=Peter|last3=Sweldens|first3=Wim|year=1996|title=Interpolating Subdivision for Meshes with Arbitrary Topology|url=https://cims.nyu.edu/gcl/papers/zorin1996ism.pdf|journal=Department of Computer Science, California Institute of Technology, Pasadena, CA 91125}}</ref> – designed to overcome artifacts generated by irregular topology
* [[Kobbelt]] (1996), Quads – a variational subdivision method that tries to overcome uniform subdivision drawbacks