Voronoi-Delaunay duality and Delaunay meshes

ABSTRACT

We define a Delaunay mesh to be a manifold triangle mesh whose edges form an intrinsic Delaunay triangulation or iDT of its vertices, where the triangulated domain is the piecewise flat mesh surface. We show that meshes constructed from a smooth surface by taking an iDT or a restricted Delaunay triangulation, do not in general yield a Delaunay mesh.

We establish a precise dual relationship between the iDT and the Voronoi tessellation of the vertices of a piecewise flat (pwf) surface and exploit this duality to demonstrate criteria which ensure the existence of a proper Delaunay triangulation.

REFERENCES

• 1: Aleksandrov, A. D., and Zalgaller, V. A. 1967. Intrinsic Geometry of Surfaces, vol. 15 of Transactions of mathematical monographs. AMS.
• 2: Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276889]
• 3: N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
• 4: Bobenko, A. I., and Springborn, B. A. 2005. A discrete Laplace-Beltrami operator for simplicial surfaces. arXiv:math.DG/0503219 v1.
• 5: 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]
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: Desbrun, M., Meyer, M., and Alliez, P. 2002. Intrinsic parameterizations of surface meshes. In Proceedings of Eurographics, 209--218.
• 8: Do Carmo, M. P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall.
• 9: Dyer, R., Zhang, H., and Möller, T. 2007. On Voronoi- Delaunay duality and Delaunay meshes. Tech. Rep. TR 2007--04, Simon Fraser University.
• 10: 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]
• 11: Matthew Fisher , Boris Springborn , Alexander I. Bobenko , Peter Schroder, An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing, ACM SIGGRAPH 2006 Courses, July 30-August 03, 2006, Boston, Massachusetts [doi>10.1145/1185657.1185668]
• 12: Floater, M. S. 1998. Parametric tilings and scattered data approximation. Int. J. of Shape Modeling 4, 165--182.
• 13: 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]
• 14: 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. Springer-Verlag, 35--57.
• 15: Onishi, K., and Itoh, J. 2003. Estimation of the necessary number of points in Riemannian Voronoi diagram. In Proc. 15th Canadian Conf. Comput. Geom., 19--24.
• 16: Peyré, G., and Cohen, L. 2003. Geodesic Remeshing Using Front Propagation. In Proceedings VLSM, 33--40.
• 17: Jonathan Richard Shewchuk , Gary L. Miller , David R. O'Hallaron, Delaunay refinement mesh generation, Carnegie Mellon University, Pittsburgh, PA, 1997
• 18: Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.289-298, July 1991

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, Delaunay triangulation (DT), Voronoi diagram, intrinsic DT, restricted DT