Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications

ABSTRACT

A simplicial surface provides its carrier with a natural triangulation whose vertex set includes the cone points and the corners of the boundary. However, this triangulation is not intrinsically distinguished from other triangulations with the same vertex set, it is not preserved under isometric deformations of the surface. Delaunay tessellations of polyhedral surfaces are defined intrinsically in terms of empty discs on surfaces. The edges of Delaunay tessellations are geodesics on the original polyhedral surface (and not necessarily straight edges in the 3-space). For any polyhedral surface there exists a unique Delaunay tessellation. It is not necessarily strongly regular, i.e. the intersection of two closed cells may not be a single closed cell.

For discretization of notions of Riemannian geometry it is natural to deal with intrinsic tessellations. We define a discrete Laplace-Beltrami operator for simplicial surfaces. It depends only on the intrinsic geometry of the surface and its edge weights are positive. The intrinsic Laplace-Beltrami operator is based on an intrinsic Delaunay triangulation of the surface. We describe an incremental flipping algorithm to construct such triangulations together with an overlay structure which captures the relationship between the extrinsic and intrinsic triangulations. We demonstrate some numerical benefits of the intrinsic Laplace-Beltrami operator.

This talk is based on the original results obtained in [1] and [2].

REFERENCES

• 1: Alexander I. Bobenko , Boris A. Springborn, A Discrete Laplace–Beltrami Operator for Simplicial Surfaces, Discrete & Computational Geometry, v.38 n.4, p.740-756, December 2007 [doi>10.1007/s00454-007-9006-1]
• 2: M. Fisher , B. Springborn , P. Schröder , A. I. Bobenko, An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing, Computing, v.81 n.2-3, p.199-213, November 2007 [doi>10.1007/s00607-007-0249-8]

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.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
Delaunay triangulation, Lapace operator, dirichlet energy, discrete differential geometry, flipping algorithm