Smooth subdivision of tetrahedral meshes

ABSTRACT

We describe a new subdivision scheme for unstructured tetrahedral meshes. Previous tetrahedral schemes based on generalizations of box splines have encoded arbitrary directional preferences in their associated subdivision rules that were not reflected in tetrahedral base mesh. Our method avoids this choice of preferred directions resulting a scheme that is simple to implement via repeated smoothing. In an extended appendix, we analyze this tetrahedral scheme and prove that the scheme generates C² deformations everywhere except along edges of the tetrahedral base mesh. Along edges shared by four or more tetrahedra in the base mesh, we present strong evidence that the scheme generates C¹ deformations.

REFERENCES

• 1: {BSWX02} Bajaj C., Schaefer S., Warren J., Xu G.: A smooth subdivision scheme for hexahedral meshes. In The Visual Computer (2002), vol. 18, pp. 409--420.
• 2: Yu-Sung Chang , Kevin T. McDonnell , Hong Qin, A new solid subdivision scheme based on box splines, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566316]
• 3: 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]
• 4: {LL03} Levin A., Levin D.: Analysis of quasi uniform subdivision. Applied and Computational Harmonic Analysis 15(1) (2003), 18--32.
• 5: {Loo87} Loop C.: Smooth subdivision surfaces based on triangles, 1987.
• 6: Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996 [doi>10.1145/237170.237247]
• 7: 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]
• 8: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.151-160, August 1986
• 9: {Sta01} Stam J.: On subdivision schemes generalizing uniform b-spline surfaces of arbitrary degree. In Computer Aided Geometric Design (2001), vol. 18, pp. 383--396.
• 10: {War95} Warren J.: Subdivision methods for geometric design. unpublished manuscript, 1995.
• 11: {ZS01} Zorin D., Schroder P.: A unified framework for primal/dual subdivision schemes. In Computer Aided Geometric Design (2001), vol. 18, pp. 429--454.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling