“Non-uniform recursive subdivision surfaces” by Sederberg, Zheng, Sewell and Sabin

  • ©Thomas (Tom) W. Sederberg, Jianmin Zheng, David Sewell, and Malcolm Sabin




    Non-uniform recursive subdivision surfaces



    Doo-Sabin and Catmull-Clark subdivision surfaces are based on the notion of repeated knot insertion of uniform tensor product B-spline surfaces. This paper develops rules for non-uniform Doo-Sabin and Catmull-Clark surfaces that generalize non-uniform tensor product B-spline surfaces to arbitrary topologies. This added flexibility allows, among other things, the natural introduction of features such as cusps, creases, and darts, while elsewhere maintaining the same order of continuity as their uniform counterparts.


    1. A A Ball and D J T Storry. Recursively Generated B- spline Surfaces. Proc. CAD84, pages 112-119, 1984. ISBN 0408 01 4407.
    2. A A Ball and D J T Storry. Conditions For Tangent Plane Continuity Over Recursively Generated B-spline Surfaces. ACM ToG, 7:83-102, 1988.
    3. W Boehm. Inserting New Knots Into B-spline Curves. Computer-Aided Design, 12:199-201, 1980.
    4. E Catmull and J Clark. Recursively Generated B-spline Surfaces On Arbitrary Topological Meshes. Computer- Aided Design, 10:350-355, 1978.
    5. G Chaikin. An Algorithm For High-speed Curve Generation. Computer Graphics and Image Processing, 3:346-349, 1974.
    6. E Cohen, T Lyche, and R F Riesenfeld. Discrete B-splines And Subdivision Techniques In Computer Aided Design And Computer Graphics. Computer Graphics and Image Processing, 14:87-111, 1980.
    7. C de Boor. Cutting Corners Always Works. Computer Aided Geometric Design, 4:125-131, 1987.
    8. D Doo and M Sabin. Behaviour Of Recursive Division Surfaces Near Extraordinary Points. Computer-Aided Design, 10:356-360, 1978.
    9. N Dyn, D Levin, and J A Gregory. A 4-point Interpolatory Subdivision Scheme For Curve Design. Computer Aided Geometric Design, 4:257-268, 1987.
    10. G Farin. Designing C1 Surfaces Consisting Of Triangular Cubic Patches. Computer-Aided Design, 14:253- 256, 1982.
    11. A R Forrest. Notes On Chaikin’s Algorithm. Technical Report Memo CGP74/1, University of East Anglia, Norwich, UK, 1974.
    12. M Halstead, M Kass, and T DeRose. Efficient, Fair Interpolation Using Catmull-Clark Surfaces. Computer Graphics (SIGGRAPH 93 Conference Proceedings), 27:35-44, 1993.
    13. H Hoppe, T DeRose, T Duchamp, M Halstead, H Jin, J McDonald, J Schweitzer, and W Stuetzle. Piecewise Smooth Surface Reconstruction. Computer Graphics (SIGGRAPH 94 Conference Proceedings), 28:295- 302, 1994.
    14. L Kobbelt. Interpolatory Subdivision On Open Quadrilateral Nets With Arbitrary Topology. Computer Graphics Forum (Eurographics 96), 1996.
    15. C Loop. Smooth Subdivision Surfaces Based On Triangles. Master’s thesis, University of Utah, Dept. of Mathematics, 1987.
    16. C Loop. Smooth Spline Surfaces Over Irregular Meshes. Computer Graphics (SIGGRAPH 94 Conference Proceedings), 28:303-310, 1994.
    17. A Nasri. Polyhedral Subdivision Methods For Freeform Surfaces. PhD thesis, University of East Anglia, 1984.
    18. A Nasri. Polyhedral Subdivision Methods For Freeform Surfaces. ACM ToG, 6:29-73, 1987.
    19. A Nasri. Surface Interpolation On Irregular Network With Normal Conditions. Computer Aided Geometric Design, 8:89-96, 1991.
    20. A Nasri. Curve Interpolation In Recursively Generated B-spline Surfaces Over Arbitrary Topology. Computer Aided Geometric Design, 14:13-30, 1997.
    21. J Peters. Joining Smooth Patches Around A Vertex To Form A Ck Surface. Computer Aided Geometric Design, 9:387-411, 1992.
    22. J Peters. Smooth Free-form Surfaces Over Irregular Meshes Generalizing Quadratic Splines. Computer Aided Geometric Design, 10:347-361, 1993.
    23. J Peters. C1 Surface Splines. SlAM J Num Anal, 32:645-666, 1995.
    24. H Prautzsch. Freeform Splines. Computer Aided Geometric Design, 14:201-206, 1997.
    25. U. Reif. A Unified Approach To Subdivision Algorithms Near Extraordinary Vertices. Computer Aided Geometric Design, 12:153-174, 1995.
    26. R F Riesenfeld. On Chaikin’s Algorithm. Computer Graphics and Image Processing, 4:304-310, 1975.
    27. M A Sabin. Recursive Division. In J Gregory, editor, The Mathematics of Surfaces, pages 269-282. Clarendon Press, Oxford, 1986. ISBN 0 19 853609 7.
    28. M A Sabin. Cubic Recursive Division With Bounded Curvature. In P J Laurent, Ale Mehaute, and L L Schumaker, editors, Curves and Surfaces, pages 411-414. Academic Press, 1991. ISBN 0 12 438660 1.
    29. D J T Storry and A A Ball. Design Of An N-sided Surface Patch From Hermite Boundary Data. Computer Aided Geometric Design, 6:111-120, 1989.
    30. J Zheng, T Sederberg, and M A Sabin. Eigenanalysis Of Non-Uniform Doo-Sabin Surfaces. Technical report, Brigham Young University, Department of Computer Science (appears as an appendix in the electronic version of this paper), November 1997.
    31. D Zorin, P Schr6der, and W Sweldens. Interpolating Subdivision For Meshes With Arbitrary Topology. Computer Graphics (SIGGRAPH 96 Conference Proceedings), 30:189-192, 1996.

ACM Digital Library Publication: