A local coordinate system on a surface

ABSTRACT

Coordinate systems associated to a finite set of sample points have been extensively studied, especially in the context of interpolation of multivariate scattered data. Notably, Sibson proposed the so-called natural neighbor coordinates that are defined from the Voronoi diagram of the sample points. A drawback of those coordinate systems is that their definition domain is restricted to the convex hull of the sample points. This make them difficult to use when the sample points belong to a surface. To overcome this difficulty, we propose a new system of coordinates. Given a closed surface, i.e. a manifold of, the coordinate system is defined everywhere on the surface, is continuous, and is local even if the sampling density is finite. Moreover, it is inherently 1-dimensional while the previous systems are dimensional. No assumption is made about the ordering, the connectivity or topology of the sample points nor of the surface. We illustrate our results with an application to interpolation over a surface.

REFERENCES

• 1: Marc Alexa , Johannes Behr , Daniel Cohen-Or , Shachar Fleishman , David Levin , Claudio T. Silva, Point set surfaces, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 2: Peter Alfeld , Marian Neamtu , Larry L. Schumaker, Bernstein-Be´zier polynomials on spheres and sphere-like surfaces, Computer Aided Geometric Design, v.13 n.4, p.333-349, June 1996 [doi>10.1016/0167-8396(95)00030-5]
• 3: Peter Alfeld , Marian Neamtu , Larry L. Schumaker, Fitting scattered data on sphere-like surfaces using spherical splines, Journal of Computational and Applied Mathematics, v.73 n.1-2, p.5-43, Oct. 5, 1996 [doi>10.1016/0377-0427(96)00034-9]
• 4: Nina Amenta and Marshall Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22(4):481--504, 1999
• 5: F. Aurenhammer. Linear combinations from power domains. Geom. Dedicata, 28:45--52, 1988
• 6: R. Barnhill, B. Piper, and K. Rescorla. Interpolation to arbitrary data on a surface. In G. Farin, editor,. Geometric Modeling: Algorithms and New Trends, pages 281--289. SIAM, Philadelphia, 1987
• 7: J-D. Boissonnat and F. Cazals. Natural neighbor coordinates of points on a surface. Computational Geometry: Theory and Applications, 19(2-3):155--173, 2001
• 8: Jean-Daniel Boissonnat and Julia Flototto. A local coordinate system on a surface. Technical Report, 2002
• 9: Jean-Daniel Boissonnat , Mariette Yvinec, Algorithmic geometry, Cambridge University Press, New York, NY, 1998
• 10: J. L. Brown, Natural neighbor interpolation on the sphere, An international conference on curves and surfaces on Wavelets, images, and surface fitting, p.67-74, July 1994, Chamonix-Mont-Blanc, France
• 11: J. L. Brown, Systems of coordinates associated with points scattered in the plane, Computer Aided Geometric Design, v.14 n.6, p.547-559, Aug. 1997 [doi>10.1016/S0167-8396(96)00045-3]
• 12: The CGAL reference manual, August 2001. Release 2.3
• 13: L. Paul Chew, Guaranteed-quality mesh generation for curved surfaces, Proceedings of the ninth annual symposium on Computational geometry, p.274-280, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161150]
• 14: Tamal K. Dey, Stefan Funke, and Edgar A. Ramos. Surface reconstruction in almost linear time under locally uniform sampling. In Abstracts 17th European Workshop Comput. Geom., pages 129--132. Freie Universitat Berlin, 2001
• 15: Manfredo P. do Carmo. Differential geometry of curves and surfaces. Prentice-Hall, 1976
• 16: Herbert Edelsbrunner , Nimish R. Shah, Triangulating topological spaces, Proceedings of the tenth annual symposium on Computational geometry, p.285-292, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178010]
• 17: G. Farin, Surfaces over Dirichlet Tessellations, Computer Aided Geometric Design, v.7 n.1-4, p.281-292, Jun. 1990 [doi>10.1016/0167-8396(90)90036-Q]
• 18: Gregory E. Fasshauer , Larry L. Schumaker, Scattered data fitting on the sphere, Proceedings of the international conference on Mathematical methods for curves and surfaces II Lillehammer, 1997, p.117-166, June 1998, Lillehammer, Norway
• 19: T. Foley. Interpolation to scattered data on a spherical domain. In J. C. Mason and M. G. Cox, editors. Algorithms for Approximation II, pages 303--310. Chapman and Hall (London), 1990
• 20: T. A. Foley , D. A. Lane , G. M. Nielson , R. Franke , H. Hagen, Interpolation of scattered data on closed surfaces, Computer Aided Geometric Design, v.7 n.1-4, p.303-312, Jun. 1990 [doi>10.1016/0167-8396(90)90038-S]
• 21: Hisamoto Hiyoshi , Kokichi Sugihara, Voronoi-based interpolation with higher continuity, Proceedings of the sixteenth annual symposium on Computational geometry, p.242-250, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336210]
• 22: Greg Leibon , David Letscher, Delaunay triangulations and Voronoi diagrams for Riemannian manifolds, Proceedings of the sixteenth annual symposium on Computational geometry, p.341-349, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336221]
• 23: Marian Neamtu. Splines on surfaces. http://citeseer.nj.nec.com/neamtu01splines.html, 2001
• 24: B. Piper, Properties of local coordinates based on Dirichlet tessellations, Geometric modelling, Springer-Verlag, London, 1993
• 25: R. Sibson. A vector identity for the Dirichlet tesselation. Math. Proc. Camb. Phil. Soc., 87:151--155, 1980
• 26: R. Sibson. A brief description of natural neighbour interpolation. In Vic Barnet, editor. Interpreting Multivariate Data, pages 21--36. John Wiley & Sons, Chichester, 1981
• 27: F. E. Wolter. Cut locus and medial axis in global shape interrogation and representation. Technical Report 92-2, MIT, Dept. Ocean Engg., Design Lab, Cambridge, MA 02139, USA, January 1992

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:
  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

General Terms:
Algorithms, Design, Theory