Subdivision surface

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 recursive subdivision of each polygonal face into smaller faces that better approximate the smooth surface.

First three steps of Catmull–Clark subdivision of a cube with subdivision surface below

Overview

Subdivision surfaces are defined recursively. 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 finer 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 number of times. The limit surface can also be calculated directly for most subdivision surfaces using the technique of Jos Stam,[1] which eliminates the need for recursive refinement. Subdivision surfaces and T-Splines are competing technologies. Mathematically, subdivision surfaces are spline surfaces with singularities.[2]

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 editing applications that allow users to set exact surface constraints require an optimization step.

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. Examples of approximating subdivision schemes are:

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 the 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. Deng and Ma (2013) further generalized the four-point interpolatory subdivision scheme to arbitrary degree.

Editing a subdivision surface

Subdivision surfaces can be naturally edited at different levels of subdivision. Starting with basic shapes you can use binary operators to create the correct topology. Then edit the coarse mesh to create the basic shape, then edit the offsets for the next subdivision step, then repeat this at finer and finer levels. You can always see how your edits affect the limit surface via GPU evaluation of the surface.

A surface designer may also start with a scanned in object or one created from a NURBS surface. The same basic optimization algorithms are used to create a coarse base mesh with the correct topology and then add details at each level so that the object may be edited at different levels. These types of surfaces may be difficult to work with because the base mesh does not have control points in the locations that a human designer would place them. With a scanned object this surface is easier to work with than a raw triangle mesh, but a NURBS object probably had well laid out control points which behave less intuitively after the conversion than before.

See also

Key developments

References

  1. 1 2 Stam, J. (1998). "Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values". Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98 (PDF). pp. 395–404. doi:10.1145/280814.280945. ISBN 0-89791-999-8. (downloadable eigenstructures)
  2. 1 2 Peters, J. R.; Reif, U. (2008). "Subdivision Surfaces". Geometry and Computing. 3. doi:10.1007/978-3-540-76406-9. ISBN 978-3-540-76405-2.
  3. ↑ http://dl.acm.org/citation.cfm?id=2487231
  4. ↑ Reif, U. (1995). "A unified approach to subdivision algorithms near extraordinary vertices". Computer Aided Geometric Design. 12 (2): 153–201. doi:10.1016/0167-8396(94)00007-F.
  • Peters, J.; Reif, U. (October 1997). "The simplest subdivision scheme for smoothing polyhedra". ACM Transactions on Graphics. 16 (4): 420–431. doi:10.1145/263834.263851. 
  • Habib, A.; Warren, J. (May 1999). "Edge and vertex insertion for a class C1 of subdivision surfaces". Computer Aided Geometric Design. 16 (4): 223–247. doi:10.1016/S0167-8396(98)00045-4. 
  • Kobbelt, L. (2000). "√3-subdivision". Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00. pp. 103–112. doi:10.1145/344779.344835. ISBN 1-58113-208-5. 

Further reading

External links

This article is issued from Wikipedia - version of the 9/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.