Fastest available Delaunay triangulation algorithm for GPU
Which is in your opinion the fastest available Delaunay triangulation algorithm for GPU? Or more general, in parallel
Answer
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.