Localized delaunay refinement for sampling and meshing

T. K. Dey, J. A. Levine, A. Slatton

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.

Original languageEnglish (US)
Pages (from-to)1723-1732
Number of pages10
JournalEurographics Symposium on Geometry Processing
Volume29
Issue number5
StatePublished - 2010
Externally publishedYes

ASJC Scopus subject areas

  • Modeling and Simulation
  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Localized delaunay refinement for sampling and meshing'. Together they form a unique fingerprint.

Cite this