Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Surfaces of R³ are ubiquitous in science and engineering, and estimating the local differential properties of a surface discretized as a point cloud or a triangle mesh is a central building block in computer graphics, computer aided design, computational geometry, and computer vision. One strategy to perform such an estimation consists of resorting to polynomial fitting, either interpolation or approximation, but this route is difficult for several reasons: choice of the coordinate system, numerical handling of the fitting problem, and extraction of the differential properties.

This article presents a generic C++ software package solving these problems. On the theoretical side and as established in a companion paper, the interpolation and approximation methods provided achieve the best asymptotic error bounds known to date. On the implementation side and following state-of-the-art coding rules in computational geometry, genericity of the package is achieved thanks to four template classes accounting for, (a) the type of the input points, (b) the internal geometric computations, (c) a conversion mechanism between these two geometries, and (d) the linear algebra operations. An instantiation within the Computational Geometry Algorithms Library (CGAL, version 3.3) and using LAPACK is also provided.

REFERENCES

• 1: V. Borrelli , F. Cazals , J.-M. Morvan, On the angular defect of triangulations and the pointwise approximation of curvatures, Computer Aided Geometric Design, v.20 n.6, p.319-341, September 2003 [doi>10.1016/S0167-8396(03)00077-3]
• 2: F. Cazals , M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Computer Aided Geometric Design, v.22 n.2, p.121-146, February 2005 [doi>10.1016/j.cagd.2004.09.004]
• 3: Cazals, F. and Pouget, M. 2005b. Topology driven algorithms for ridge extraction on meshes. Rapport de recherche 5526, INRIA.
• 4: David Cohen-Steiner , Jean-Marie Morvan, Restricted delaunay triangulations and normal cycle, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777839]
• 5: de Carmo, M. 1976. Differential Geometry of Curves and Surfaces. Prentice Hall, Englewood Cliffs, NJ.
• 6: Golub, G. and van Loan, C. 1983. Matrix Computations. Johns Hopkins Univ. Press, Baltimore, MA.
• 7: Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, H.-C. Hege and K. Polthier, Eds. Springer-Verlag, Heidelberg, 35--57.
• 8: Sylvain Petitjean, A survey of methods for recovering quadrics in triangle meshes, ACM Computing Surveys (CSUR), v.34 n.2, p.211-262, June 2002 [doi>10.1145/508352.508354]
• 9: Pinkall, U. and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Exper. Math. 2, 1, 15--36.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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

General Terms:
Algorithms, Design, Documentation

Keywords:
Approximation, C++ design, computational geometry, differential geometry, interpolation, numerical linear algebra, sampled surfaces