Premium
Localized Delaunay Refinement for Volumes
Author(s) -
Dey Tamal K,
Slatton Andrew G
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.02016.x
Subject(s) - delaunay triangulation , octree , computer science , bottleneck , polygon mesh , set (abstract data type) , ruppert's algorithm , consistency (knowledge bases) , theoretical computer science , bowyer–watson algorithm , algorithm , computer graphics (images) , computational science , artificial intelligence , programming language , embedded system
Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency . We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state‐of‐the‐art meshing tool provided by CGAL.