“NURBS with extraordinary points: high-degree, non-uniform, rational subdivision schemes” by Cashman, Augsdörfer, Dodgson and Sabin

  • ©Thomas J. Cashman, Ursula H. Augsdörfer, Neil A. Dodgson, and Malcolm Sabin




    NURBS with extraordinary points: high-degree, non-uniform, rational subdivision schemes



    We present a subdivision framework that adds extraordinary vertices to NURBS of arbitrarily high degree. The surfaces can represent any odd degree NURBS patch exactly. Our rules handle non-uniform knot vectors, and are not restricted to midpoint knot insertion. In the absence of multiple knots at extraordinary points, the limit surfaces have bounded curvature.


    1. Augsdörfer, U. H., Dodgson, N. A., and Sabin, M. A. 2006. Tuning Subdivision by Minimising Gaussian Curvature Variation Near Extraordinary Vertices. Comp. Graph. Forum 25, 3, 263–272.Google ScholarCross Ref
    2. Augsdörfer, U. H., Cashman, T. J., Dodgson, N. A., and Sabin, M. A. 2009. Numerical Checking of C1 for Arbitrary Degree Quadrilateral Subdivision Schemes. In 13th IMA Conference on the Mathematics of Surfaces, Springer. To appear. Google ScholarDigital Library
    3. Barthe, L., and Kobbelt, L. 2004. Subdivision scheme tuning around extraordinary vertices. CAGD 21, 6, 561–583. Google ScholarDigital Library
    4. Boehm, W. 1980. Inserting new knots into B-spline curves. Computer-Aided Design 12, 4, 199–201.Google ScholarCross Ref
    5. Cashman, T. J., Dodgson, N. A., and Sabin, M. A. 2009. Selective knot insertion for symmetric, non-uniform refine and smooth B-spline subdivision. CAGD 26, 4, 472–479. Google ScholarDigital Library
    6. Catmull, E., and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10, 6, 350–355.Google ScholarCross Ref
    7. Cohen, E., Lyche, T., and Riesenfeld, R. 1980. Discrete B-splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics. Computer Graphics and Image Processing 14, 2, 87–111.Google ScholarCross Ref
    8. DeRose, T., Kass, M., and Truong, T. 1998. Subdivision surfaces in character animation. In Proc. SIGGRAPH 98, 85–94. Google ScholarDigital Library
    9. Farin, G. 2001. Curves and Surfaces for CAGD: A Practical Guide, 5th ed. Morgan Kaufmann. Google ScholarDigital Library
    10. Galil, Z., and Italiano, G. 1991. Data structures and algorithms for disjoint set union problems. ACM Computing Surveys 23, 3, 319–344. Google ScholarDigital Library
    11. Ginkel, I., and Umlauf, G. 2006. Loop subdivision with curvature control. In Eurographics Symposium on Geom. Proc., Eurographics, K. Polthier and A. Sheffer, Eds., 163–171. Google ScholarDigital Library
    12. Gonsor, D., and Neamtu, M. 2001. Subdivision Surfaces — Can they be Useful for Geometric Modeling Applications? Tech. Rep. 01–011, The Boeing Company.Google Scholar
    13. Holt, F. 1996. Toward a curvature-continuous stationary subdivision algorithm. Zeitschrift für angewandte Mathematik und Mechanik 76, 423–424.Google Scholar
    14. Karciauskas, K., Peters, J., and Reif, U. 2004. Shape characterization of subdivision surfaces-case studies. CAGD 21, 6, 601–614. Google ScholarDigital Library
    15. Lane, J. M., and Riesenfeld, R. F. 1980. A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces. IEEE Trans. PAMI 2, 1, 35–46.Google ScholarDigital Library
    16. Levin, A. 2006. Modified subdivision surfaces with continuous curvature. ACM Trans. Graph. 25, 3, 1035–1040. Google ScholarDigital Library
    17. Loop, C. 2002. Bounded curvature triangle mesh subdivision with the convex hull property. The Visual Computer 18, 316–325.Google ScholarCross Ref
    18. Ma, W. 2005. Subdivision surfaces for CAD—an overview. Computer-Aided Design 37, 7, 693–709. Google ScholarDigital Library
    19. Müller, K., Reusche, L., and Fellner, D. 2006. Extended subdivision surfaces: Building a bridge between NURBS and Catmull-Clark surfaces. ACM Trans. Graph. 25, 2, 268–292. Google ScholarDigital Library
    20. Peters, J., and Reif, U. 2008. Subdivision Surfaces. Springer. Google ScholarDigital Library
    21. Prautzsch, H. 1997. Freeform splines. CAGD 14, 3, 201–206. Google ScholarDigital Library
    22. Prautzsch, H. 1998. Smoothness of subdivision surfaces at extraordinary points. Adv. in Comp. Math. 9, 3, 377–389.Google ScholarCross Ref
    23. Ramshaw, L. 1989. Blossoms are polar forms. CAGD 6, 4, 323–358. Google ScholarDigital Library
    24. Reif, U. 1996. A Degree Estimate for Subdivision Surfaces of Higher Regularity. Proc. Amer. Math. Soc. 124, 7, 2167–2174.Google ScholarCross Ref
    25. Reif, U. 1998. TURBS—Topologically Unrestricted Rational B-Splines. Constructive Approximation 14, 1, 57–77.Google ScholarCross Ref
    26. Sabin, M. A., Dodgson, N. A., Hassan, M. F., and Ivrissimtzis, I. P. 2003. Curvature behaviours at extraordinary points of subdivision surfaces. Computer-Aided Design 35, 11, 1047–1051.Google ScholarCross Ref
    27. Sabin, M. 1991. Cubic recursive division with bounded curvature. In Curves and surfaces, Academic Press, 411–414. Google ScholarDigital Library
    28. Schaefer, S., and Goldman, R. 2009. Non-uniform Subdivision for B-splines of Arbitrary Degree. CAGD 26, 1, 75–81. Google ScholarDigital Library
    29. Sederberg, T. W., Zheng, J., Sewell, D., and Sabin, M. 1998. Non-Uniform Recursive Subdivision Surfaces. In Proc. SIGGRAPH 98, 387–394. Google ScholarDigital Library
    30. Sederberg, T. W., Zheng, J., Bakenov, A., and Nasri, A. 2003. T-splines and T-NURCCs. ACM Trans. Graph. 22, 3, 477–484. Google ScholarDigital Library
    31. Stam, J. 1998. Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values. In Proc. SIGGRAPH 98, 395–404. Google ScholarDigital Library
    32. Stam, J. 2001. On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree. CAGD 18, 5, 383–396. Google ScholarDigital Library
    33. Warren, J., and Weimer, H. 2001. Subdivision Methods for Geometric Design. Morgan Kaufmann. Google ScholarDigital Library
    34. Zorin, D., and Schröder, P. 2001. A unified framework for primal/dual quadrilateral subdivision schemes. CAGD 18, 5, 429–454. Google ScholarDigital Library

ACM Digital Library Publication: