Gabriel meshes and Delaunay edge flips

ABSTRACT

We undertake a study of the local properties of 2-Gabriel meshes: manifold triangle meshes each of whose faces has an open Euclidean diametric ball that contains no mesh vertices. We show that, under mild constraints on the dihedral angles, such meshes are Delaunay meshes: the open geodesic circumdisk of each face contains no mesh vertex.

The analysis is done by means of the Delaunay edge flipping algorithm and it reveals the details of the distinction between these two mesh structures. In particular we observe that the obstructions which prohibit the existence of Gabriel meshes as homeomorphic representatives of smooth surfaces do not hinder the construction of Delaunay meshes.

REFERENCES

• 1: Adamy, U., Giesen, J., and John, M. 2000. New techniques for topologically correct surface reconstruction. In IEEE Visualization, 373--380.
• 2: Amenta, N., Choi, S., Dey, T. K., and Leekha, N. 2000. A Simple Algorithm for Homeomorphic Surface Reconstruction. In Symp. Comp. Geom., 213--222.
• 3: Attene, M., and Spagnuolo, M. 2000. Automatic surface reconstruction from point sets in space. Computer Graphics Forum 19, 457--465.
• 4: Bobenko, A. I., and Springborn, B. A. 2007. A discrete Laplace-Beltrami operator for simplicial surfaces. Discrete and Computational Geometry 38, 4, 740--756.
• 5: Chaine, R. 2003. A geometric convection approach of 3-D reconstruction. In Symp. Geometry Processing, 218--229.
• 6: Cheng, S.-W., and Dey, T. K., 2007. Delaunay edge flips in dense surface triangulations. arXiv.org:0712.1959v1.
• 7: Desbrun, M., Hirani, A. N., Leok, M., and Marsden, J. E. 2005. Discrete exterior calculus. arXiv:math.DG/0508341.
• 8: Dey, T. 2007. Curve and Surface Reconstruction; Algorithms with Mathematical Analysis. Cambridge University Press.
• 9: Dyer, R., Zhang, H., and Möller, T. 2007. Delaunay mesh construction. In Symp. Geometry Processing, 271--282.
• 10: Dyer, R., Zhang, H., and Möller, T. 2008. Observations on Gabriel meshes and Delaunay edge flips. Tech. Rep. TR 2008-22, Simon Fraser University. SFU-CMPT.
• 11: Edelsbrunner, H., and Shah, N. R. 1994. Triangulating topological spaces. In Symp. Comp. Geom., 285--292.
• 12: Fisher, M., Springborn, B., Bobenko, A. I., and Schröder, P. 2006. An algorithm for the construction of intrinsic Delaunay triangulations with applications to digital geometry processing. In SIGGRAPH Courses, 69--74.
• 13: Glickenstein, D., 2005. Geometric triangulations and discrete Laplacians on manifolds. arxiv:math.MG/0508188v1.
• 14: Petitjean, S., and Boyer, E. 2001. Regular and non-regular point sets: Properties and reconstruction. Computational Geometry: Theory and Applications 19, 2--3, 101--126.
• 15: Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15--36.
• 16: Wardetzky, M., Mathur, S., Kälberer, F., and Grinspun, E. 2007. Discrete Laplace operators: no free lunch. In Symp. Geometry Processing, 33--37.

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

Keywords:
Delaunay mesh, Gabriel complex, manifold triangle mesh