Piecewise smooth subdivision surfaces with normal control

ABSTRACT

In this paper we introduce improved rules for Catmull-Clark and Loop subdivision that overcome several problems with the original schemes, namely, lack of smoothness at extraordinary boundary vertices and folds near concave corners. In addition, our approach to rule modification allows the generation of surfaces with prescribed normals, both on the boundary and in the interior, which considerably improves control of the shape of surfaces.

REFERENCES

• 1: Subdivision for modeling and animation. SIGGRAPH 2000 Course Notes.
• 2: Ed Catmull and James Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer Aided Design, 10(6):350-355, 1978.
• 3: Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.85-94, July 1998 [doi>10.1145/280814.280826]
• 4: D. Doo. A subdivision algorithm for smoothing down irregularly shaped polyhedrons. In Proceedings on Interactive Techniques in Computer Aided Design, pages 157-165, Bologna, 1978.
• 5: D. Doo and M. Sabin. Analysis of the behaviour of recursive division surfaces near extraordinary points. Computer Aided Design, 10(6):356-360, 1978.
• 6: Ayman Habib , Joe Warren, Edge and vertex insertion for a class of C1 subdivision surfaces, Computer Aided Geometric Design, v.16 n.4, p.223-247, May 1999 [doi>10.1016/S0167-8396(98)00045-4]
• 7: Mark Halstead , Michael Kass , Tony DeRose, Efficient, fair interpolation using Catmull-Clark surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.35-44, September 1993 [doi>10.1145/166117.166121]
• 8: Hugues Hoppe , Tony DeRose , Tom Duchamp , Mark Halstead , Hubert Jin , John McDonald , Jean Schweitzer , Werner Stuetzle, Piecewise smooth surface reconstruction, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.295-302, July 1994 [doi>10.1145/192161.192233]
• 9: Adi Levin, Interpolating nets of curves by smooth subdivision surfaces, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.57-64, July 1999 [doi>10.1145/311535.311541]
• 10: Charles Loop. Smooth subdivision surfaces based on triangles. Master's thesis, University of Utah, Department of Mathematics, 1987.
• 11: A. Nasri. Interpolation of open B-spline curves by recursive subdivision surfaces. In Tim Goodman and Ralph Martin, editors, Mathematics of Surfaces VII, pages 173 -188. Institute of mathematics and its applications, Information Geometers, 1997.
• 12: Ahmad H. Nasri, Polyhedral subdivision methods for free-form surfaces, ACM Transactions on Graphics (TOG), v.6 n.1, p.29-73, Jan. 1987 [doi>10.1145/27625.27628]
• 13: A. H. Nasri, Boundary-corner control in recursive-subdivision surfaces, Computer-Aided Design, v.23 n.6, p.405-410, July/Aug. 1991 [doi>10.1016/0010-4485(91)90008-K]
• 14: Ahmad H. Nasri, Surface interpolation on irregular networks with normal conditions, Computer Aided Geometric Design, v.8 n.1, p.89-96, Feb. 1991 [doi>10.1016/0167-8396(91)90051-C]
• 15: Jörg Peters , Ulrich Reif, Analysis of Algorithms Generalizing B-Spline Subdivision, SIAM Journal on Numerical Analysis, v.35 n.2, p.728-748, April 1998 [doi>10.1137/S0036142996304346]
• 16: Hartmut Prautzsch , Georg Umlauf, A G2-Subdivision Algorithm, Geometric Modelling, Dagstuhl, Germany, 1996, p.217-224, January 1998
• 17: Hartmut Prautzsch and Ulrich Reif. Degree estimates for C k -piecewise polynomial subdivision surfaces. Adv. Comput. Math., 10(2):209-217, 1999.
• 18: Ulrich Reif, A unified approach to subdivision algorithms near extraordinary vertices, Computer Aided Geometric Design, v.12 n.2, p.153-174, March 1995 [doi>10.1016/0167-8396(94)00007-F]
• 19: Jean Elaine Schweitzer , Anthony D. Derose, Analysis and application of subdivision surfaces, 1996
• 20: Thomas W. Sederberg , Jianmin Zheng , David Sewell , Malcolm Sabin, Non-uniform recursive subdivision surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.387-394, July 1998 [doi>10.1145/280814.280942]
• 21: Jos Stam, Exact evaluation of Catmull-Clark subdivision surfaces at arbitrary parameter values, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.395-404, July 1998 [doi>10.1145/280814.280945]
• 22: Joe Warren. Subdivision methods for geometric design. Unpublished manuscript, November 1995.
• 23: Denis Zorin, A Method for Analysis of C¹-Continuity of Subdivision Surfaces, SIAM Journal on Numerical Analysis, v.37 n.5, p.1677-1708, 2000 [doi>10.1137/S003614299834263X]
• 24: Denis Zorin. Smoothness of subdivision on irregular meshes. Constructive Approximation, 16(3), 2000.
• 25: Denis Zorin, Tom Duchamp, and H. Biermann. Smoothness of subdivision surfaces on the boundary. Technical report, New York University, Dept. of Computer Scinece, 2000.
• 26: Denis N. Zorin, Stationary subdivision and multiresolution surface representations, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
boundary control, subdivision surfaces