Fastest available Delaunay triangulation algorithm for GPU

Question

Which is in your opinion the fastest available Delaunay triangulation algorithm for GPU? Or more general, in parallel

Answer 1

2D Delaunay triangulation

GPU-DT is the fastest 2D Delaunay implementation for the GPU.

It constructs a digital Voronoi diagram in 2D using the GPU Parallel Banding Algorithm. Next it fixes and dualizes this to obtain a 2D triangulation. Finally, it performs edge-flipping in parallel on the GPU to obtain the 2D Delaunay triangulation.

3D Delaunay triangulation

gStar4D is a fast and robust implementation of 3D Delaunay for the GPU.

Similar to GPU-DT, this algorithm constructs the 3D digital Voronoi diagram first. However, in 3D this cannot be dualized to a triangulation due to topological and geometrical problems. Instead, gStar4D uses the neighborhood information from this diagram to create stars lifted to 4D and performs star splaying on them efficiently on the GPU. By extracting the lower hull from this, the 3D Delaunay triangulation is obtained.

A faster alternative is gDel3D, which is a hybrid GPU-CPU algorithm.

It performs parallel insertion and flipping on the GPU. The result is close to Delaunay. It then fixes this result using a conservative star splaying method on the CPU.

All these methods are robust, so they can handle any kind of degenerate input.

Answer 2

Be careful with GPU's: Delaunay Triangulations require orientation tests. These do not work reliably with floating point arithmetic, and it might be hard to cope with that problem using a GPU. Also the memory management is crucial.

You might want to try http://www.geom.at/fade2d/html/ which is among the fastest robust single threaded implementations.