Hierarchical triangular splines

ABSTRACT

Smooth parametric surfaces interpolating triangular meshes are very useful for modeling surfaces of arbitrary topology. Several interpolants based on these kind of surfaces have been developed over the last fifteen years. However, with current 3D acquisition equipments, models are becoming more and more complex. Since previous interpolation methods lack a local refinement property, there is no way to locally adapt the level of detail. In this article, we introduce a hierarchical triangular surface model. The surface is overall tangent plane continuous and is defined parametrically as a piecewise quintic polynomial. It can be adaptively refined while preserving the overall tangent plane continuity. This model enables designers to create a complex smooth surface of arbitrary topology composed of a small number of patches to which details can be added by locally refining the patches until an arbitrary small size is reached. It is implemented as a hierarchical data structure where the top layer describes a coarse, smooth base surface and the lower levels encode the details in local frame coordinates.

REFERENCES

• 1: Alkalai, N. and Dyn, N. 2004. Optimising 3d triangulations: improving the initial triangulation for the butterfly subdivision scheme. In Advances in Multiresolution for Geometric Modeling, N. Dodson, M. Sabin, and M. Floater Eds. Springer-Verlag.
• 2: Andrew Certain , Jovan Popovic , Tony DeRose , Tom Duchamp , David Salesin , Werner Stuetzle, Interactive multiresolution surface viewing, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.91-98, August 1996 [doi>10.1145/237170.237213]
• 3: T. D. DeRose, Necessary and sufficient conditions for tangent plane continuity of Be´zier surfaces, Computer Aided Geometric Design, v.7 n.1-4, p.165-179, Jun. 1990 [doi>10.1016/0167-8396(90)90028-P]
• 4: 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]
• 5: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 6: David R. Forsey , Richard H. Bartels, Hierarchical B-spline refinement, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.205-212, June 1988
• 7: Goldman, R. N. 1983. Subdivision algorithms for Bézier triangles. Computer-Aided Design 22, 3, 159--166.
• 8: Carlos Gonzalez-Ochoa , Jorg Peters, Localized-hierarchy surface splines (LeSS), Proceedings of the 1999 symposium on Interactive 3D graphics, p.7-15, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300524]
• 9: Gregory, J. A. 1986. N-sided surface patches. In The Mathematics of Surfaces, J. A. Gregory, Ed. Clarendon Press, Oxford, UK. 217--232.
• 10: Stefanie Hahmann , Georges-Pierre Bonneau, Polynomial Surfaces Interpolating Arbitrary Triangulations, IEEE Transactions on Visualization and Computer Graphics, v.9 n.1, p.99-109, January 2003 [doi>10.1109/TVCG.2003.1175100]
• 11: Hahmann, S., Bonneau, G.-P., and Yvart, A. 2003. Subdivision invariant polynomial interpolation. In Visualization and Mathematics III, K. P. e. H. C. Hege, Ed. Mathematics and Visualization. Springer, Springer-Verlag, 191--202.
• 12: Jensen, T. 1987. Assembling triangular and rectangular patches and multivariate splines. In Geometric Modeling: Algorithms and New Trends, G. Farin, Ed. SIAM, 203--220.
• 13: 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]
• 14: Charles Loop, A G1 triangular spline surface of arbitrary topological type, Computer Aided Geometric Design, v.11 n.3, p.303-330, June 1994 [doi>10.1016/0167-8396(94)90005-1]
• 15: Charles T. Loop , Tony D. DeRose, A multisided generalization of Bézier surfaces, ACM Transactions on Graphics (TOG), v.8 n.3, p.204-234, July 1989 [doi>10.1145/77055.77059]
• 16: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 17: Mann, S., Loop, C., Lounsbery, M., Meyers, D. J., Painter T. D., and Sloan, K. 1992. A survey of parametric scattered data fitting using triangular interpolants. In Curve and Surface Design, H. Hagen, Ed. SIAM, 145--172.
• 18: Jörg Peters, C1-surface splines, SIAM Journal on Numerical Analysis, v.32 n.2, p.645-666, April 1995 [doi>10.1137/0732029]
• 19: Peters, J. 2002. Geometric continuity. In Handbook of Computer Aided Geometric Design. Elsevier, 193--229.
• 20: Piper, B. 1987. Visually smooth interpolation with triangular Bézier patches. In Geometric Modeling: Algorithms and New Trends, G. Farin, Ed. SIAM, 221--233.
• 21: Ramon F. Sarraga, G1 interpolation of generally unrestricted cubic Be´zier curves, Computer Aided Geometric Design, v.4 n.1-2, p.23-39, July 1987 [doi>10.1016/0167-8396(87)90022-7]
• 22: Schröder, P. and Zorin, D. 1998. Subdivision for modeling and animation. Course notes of Siggraph 98. ACM SIGGRAPH.
• 23: Shirman, L. A. and Sequin, C. H. 1987. Local surface interpolation with Bézier patches. Comput. Aided Geom. Des. 4, 279--295.
• 24: 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]
• 25: J J Van Wijk, Bicubic patches for approximating non-rectangular control-point meshes, Computer Aided Geometric Design, v.3 n.1, p.1-13, May 1986 [doi>10.1016/0167-8396(86)90021-X]
• 26: Alex Vlachos , Jörg Peters , Chas Boyd , Jason L. Mitchell, Curved PN triangles, Proceedings of the 2001 symposium on Interactive 3D graphics, p.159-166, March 2001 [doi>10.1145/364338.364387]
• 27: Watkins, M. A. 1988. Problems in geometric continuity. Comput. Aided Des. 20, 8, 499--502.
• 28: 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
      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: Spline and piecewise polynomial interpolation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations; Object hierarchies

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Keywords:
Bézier patches, G¹-continuity, Geometric modeling, arbitrary topology, hierarchical splines, interpolation, local frames, multiresolution, triangular meshes