Localized Delaunay Refinement for Meshing
Home

People

Research

Publications





Meshing
Home
We design algorithms to generate Delaunay meshes of smooth surfaces and the volumes bounded by them which have theoretical gurantees on the topology and geometry of the output mesh. We also can handle piecewise smooth complexes including non-manifolds. The key feature of these algorithms is their ability to avoid memory thrashing while generating very large meshes, and this is accomplished via a technique that we call "localized Delaunay refinement". The usual Delaunay refinement suffers from memory thrashing for generating large meshes with vertices in the tune of few millions because it maintains the 3D Delaunay triangulation of the entire sample. We reduce the memory footprint by dividing the sample set with an octree and meshing each node individually. Mesh consistency across nodes is maintained by reprocessing any node whose point set is encroached by a newly inserted point. Termination is guaranteed by a careful point insertion strategy.

See the paper [DLS10] for surface meshing and [DS11] for volume meshing, and finally [DS13] for piecewise smooth complex meshing. LocDel software for the first two and LocPSC for the third available.
Mesh consistency: Boxes on the top show inconsistencies in the mesh prior to termination. Boxes on the bottom show mesh at termination with inconsistencies resolved.

The theoretical guarantees of the algorithms draw upon recent work in sampling theory, namely:
  • N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete & Comput. Geom. 1999.
  • J.-D. Boissonnat and S. Oudot. Provably good surface sampling and meshing of surfaces.  Graphical Models, 2005.
  • T. K. Dey. Curve and Surface Reconstruction: algorithms with mathematical analysis.  Cambridge U. Press, 2006.
  • S.-W. Cheng, T. K. Dey, E. A. Ramos, and T. Ray. Sampling and meshing a surface with guaranteed topology and geometry. SIAM J. Computing,  2007.
A comprehensive coverage of the ideas behind the sampling theory can be found in the book Delaunay Mesh Generation.

The three papers listed below describe the algorithms in detail and provide theoretical and experimental results.

[DLS10] T. K. Dey, J. A. Levine, and A. G. Slatton. Localized Delaunay refinement for sampling and meshing. Computer Graphics Forum. Vol. 29 (5)(2010), 1723--1732.  Specail issue of Proc. Eurographics Sympos. Geometry Processing. (SGP 2010).

[DS11] T. K. Dey and A. G. Slatton. Localized Delaunay refinement for volumes. Computer Graphics Forum. (2011). Special issue of Eurographics Sympos. Geometry Processing. 2011.

[DS13] T. K. Dey and A. G. Slatton. Localized Delaunay refinement for piecewise-smooth complexes. Proc. 29th Annu. Sympos. Comput. Geom. (2013).

 
Localized surface meshing with guaranteed topology and geometry Localized volume meshing with guaranteed topology and geometry Localized piecewise smooth complex meshing

The LocDel and LocPSC  software based on these results are available.


This research has been supported partially by NSF grants CCF 0830467 and CCF 0915996.