适用于 GPU 的最快可用 Delaunay 三角测量算法
您认为哪种 GPU 可用的速度最快的 Delaunay 三角剖分算法？或者更一般地说，并行
Which is in your opinion the fastest available Delaunay triangulation algorithm for GPU? Or more general, in parallel
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
2D Delaunay 三角剖分
GPU-DT 是 GPU 上最快的 2D Delaunay 实现。
它使用 GPU 并行分段算法构建 2D 数字 Voronoi 图。接下来，它修复并二元化它以获得二维三角测量。最后，它在 GPU 上并行执行边缘翻转以获得 2D Delaunay 三角剖分。
3D Delaunay 三角剖分
gStar4D 是一种快速且强大的为 GPU 实现 3D Delaunay。
与GPU-DT类似，该算法首先构建3D数字Voronoi图。然而，在 3D 中，由于拓扑和几何问题，这不能对偶为三角测量。相反，gStar4D 使用此图中的邻域信息来创建提升为 4D 的星体，并在 GPU 上高效地对它们执行星体展开。通过从中提取下壳，获得 3D Delaunay 三角剖分。
更快的替代方案是 gDel3D，它是一种混合 GPU-CPU 算法。
它在 GPU 上执行并行插入和翻转。结果接近 Delaunay。然后，它在 CPU 上使用保守的星形展开方法来修复此结果。
所有这些方法都很稳健，因此它们可以处理任何类型的简并输入。
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.
请小心 GPU：Delaunay 三角测量需要方向测试。这些不能可靠地与浮点运算一起工作，并且可能很难应对
使用 GPU 时出现问题。内存管理也至关重要。
您可能想尝试 http://www.geom.at/fade2d/html/ 这是最快的鲁棒之一
单线程实现。
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.