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
with vertices in the tune of few millions because it maintains the 3D
triangulation of the entire sample. We reduce the memory footprint by
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
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.
A comprehensive coverage of the ideas behind the sampling theory can be found in the book Delaunay Mesh Generation.
- 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.
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.
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.
[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.