√3-subdivision

ABSTRACT

A new stationary subdivision scheme is presented which performs slower topological refinement than the usual dyadic split operation. The number of triangles increases in every step by a factor of 3 instead of 4. Applying the subdivision operator twice causes a uniform refinement with tri-section of every original edge (hence the name √3-subdivision) while two dyadic splits would quad-sect every original edge. Besides the finer gradation of the hierarchy levels, the new scheme has several important properties: The stencils for the subdivision rules have minimum size and maximum symmetry. The smoothness of the limit surface is C2 everywhere except for the extraordinary points where it is C1. The convergence analysis of the scheme is presented based on a new general technique which also applies to the analysis of other subdivision schemes. The new splitting operation enables locally adaptive refinement under built-in preservation of the mesh consistency without temporary crack-fixing between neighboring faces from different refinement levels. The size of the surrounding mesh area which is affected by selective refinement is smaller than for the dyadic split operation. We further present a simple extension of the new subdivision scheme which makes it applicable to meshes with boundary and allows us to generate sharp feature lines.

REFERENCES

• BLZ99: H. Biermann, A. Levin, D. Zorin, Piecewise smooth subdivision sur-faces with normal control, Preprint
• CC78: E. Catmull, J. Clark, Recursively generated B-spline surfaces on arbi-trary topological meshes, CAD 10 (1978), 350-355
• CDM91: Alfred S. Cavaretta , Charles A. Micchelli , Wolfgang Dahmen, Stationary Subdivision, American Mathematical Society, Boston, MA, 1991
• DS78: D. Doo, M. Sabin, Behaviour of recursive division surfaces near ex-traordinary points, CAD 10 (1978), 356-360
• DGL90: Nira Dyn , David Levine , John A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Transactions on Graphics (TOG), v.9 n.2, p.160-169, April 1990 [doi>10.1145/78956.78958]
• Dyn91: N. Dyn, Subdivision Schemes in Computer Aided Geometric Design, Advances in Numerical Analysis II, Wavelets, Subdivisions and Radial Functions, W.A. Light ed., Oxford University Press, 1991, pp: 36-104.
• GSS99: Igor Guskov , Wim Sweldens , Peter Schröder, Multiresolution signal processing for meshes, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.325-334, July 1999 [doi>10.1145/311535.311577]
• GvL96: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• GZZ93: M. Griebel, C. Zenger, S. Zimmer, Multilevel Gauss-Seidel-Algorithms for Full and Sparse Grid Problems, Computing 50, 1993, pp. 127-148
• Gus98: I. Guskov, Multivariate subdivision schemes and divided differences, Preprint, Princeton University, 1998
• Hac85: W. Hackbusch, Multi-Grid Methods and Applications, Springer, Berlin, 1985
• HDD+94: 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]
• Kob96: L. Kobbelt, Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology, Computer Graphics Forum 15 (1996), Eurographics '96 Conference Issue, pp. 409-420
• KDS98: L. Kobbelt, K. Daubert, H-P. Seidel, Ray-tracing of subdivision sur-faces, 9th Eurographics Workshop on Rendering Proceedings, 1998, pp. 69 - 80
• KCVS98: Leif Kobbelt , Swen Campagna , Jens Vorsatz , Hans-Peter Seidel, Interactive multi-resolution modeling on arbitrary meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.105-114, July 1998 [doi>10.1145/280814.280831]
• Lev99: 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]
• Loo87: C. Loop, Smooth subdivision surfaces based on triangles, Master The-sis, Utah University, USA, 1987
• Pra98: H. Prautzsch, Smoothness of subdivision surfaces at extraordinary points, Adv. Comp. Math. 14 (1998), pp. 377 - 390
• Rei95: 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]
• RP98: Jörg Peters , Ulrich Reif, The simplest subdivision scheme for smoothing polyhedra, ACM Transactions on Graphics (TOG), v.16 n.4, p.420-431, Oct. 1997 [doi>10.1145/263834.263851]
• Sab87: M. Sabin, Recursive Division, in The Mathematics of Surfaces, Claren-don Press, 1986, pp. 269 - 282
• Sta98: 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]
• VG99: L. Velho, J. Gomes, Quasi-stationary subdivision using four directional meshes, Preprint
• VG00: L. Velho, J. Gomes, Semi-regular 4-8 refinement and box spline sur-faces, Preprint
• VT92: M. Vasilescu, D. Terzopoulos, Adaptive meshes and shells: Irregular triangulation, discontinuities and hierarchical subdivision, Proceedings of the Computer Vision and Pattern Recognition Conference, 1992, 829 - 832
• Ver96: R. Verf~ urth, A review of a posteriori error estimation and adaptive mesh refinement techniques, Wiley-Teubner, 1996
• War00: Joe Warren , Joseph D. Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• ZSS96: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]
• Zor97: D.Zorin, C k Continuity of Subdivision Surfaces, Thesis, California In-stitute of Technology, 1997
• ZSS97: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Smoothing
      G.1.7 Ordinary Differential Equations
          Subjects: Convergence and stability

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

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