Generalized Delaunay Mesh Refinement: From Scalar to Parallel

Proceedings, 15th International Meshing Roundtable, Springer-Verlag, pp.563-579, September 17-20 2006

MESHING
RESEARCH
CORNER

15th International Meshing Roundtable
Birmingham, Alabama, U.S.A.
September 17-20, 2006

Department of Computer Science
College of William and Mary
Williamsburg, VA 23185
{ancher,nikos}@cs.wm.edu

Abstract
The contribution of the current paper is three-fold. First, we generalize the existing sequential point placement strategies for guaranteed quality Delaunay refinement: instead of a specific position for a new point, we derive a selection disk inside the circumdisk of a poor quality triangle. We prove that any point placement algorithm that inserts a point inside the selection disk of a poor quality triangle will terminate and produce a size-optimal mesh. Second, we extend our theoretical foundation for the parallel Delaunay refinement. Our new parallel algorithm can be used in conjunction with any sequential point placement strategy that chooses a point within the selection disk. Third, we implemented our algorithm in C++ for shared memory architectures and present the experimental results. Our data show that even on workstations with a few cores, which are now in common use, our implementation is significantly faster the best sequential counterpart.

Download Full Paper (PDF Format)