carrier image

Dynamic Parallel 3D Delaunay Triangulation

Foteinos, Panagiotis, Nikos Chrisochoides

20th International Meshing Roundtable, Springer-Verlag, pp.3-20, October 23-26 2011


20th International Meshing Roundtable
Paris, France
October 23-26, 2011

Department of Computer Science, College of William and Mary, Department of Computer Science, Old Dominion University,

Delaunay meshing is a popular technique for mesh generation. Usually, the mesh has to be refined so that certain fidelity and quality criteria are met. Delaunay refinement is achieved by dynamically inserting and removing points in/from a Delaunay triangulation. In this paper, we present a robust parallel algorithm for computing Delaunay triangulations in three dimensions. Our triangulator offers fully dynamic parallel insertions and removals of points and is thus suitable for mesh refinement. As far as we know, ours is the first method that parallelizes point removals, an operation that significantly slows refinement down. Our shared memory implementation makes use of a custom memory manager and light-weight locks which greatly reduce the communication and synchronization cost. We also employ a contention policy which is able to accelerate the execution times even in the presence of high number of rollbacks. Evaluation on synthetic and real data shows the effectiveness of our method on widely used multi-core SMPs.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article