geometry - 适用于 GPU 的最快可用 Delaunay 三角剖分算法

Question

在您看来，哪种 GPU 可用的最快 Delaunay 三角剖分算法是？或者更一般的，并行

Answer 1

二维 Delaunay 三角剖分

GPU-DT 是 GPU 最快的 2D Delaunay 实现。

它使用 GPU 以 2D 形式构建数字 Voronoi 图并行 strip 算法 .接下来，它修复并二元化以获得二维三角剖分。最后，它在 GPU 上并行执行边缘翻转以获得 2D Delaunay 三角剖分。

3D Delaunay 三角剖分

gStar4D是 GPU 上 3D Delaunay 的快速而稳健的实现。

与 GPU-DT 类似，该算法首先构建 3D 数字 Voronoi 图。然而，在 3D 中，由于拓扑和几何问题，这不能被二元化为三角剖分。相反，gStar4D 使用此图中的邻域信息来创建提升到 4D 的恒星，并在 GPU 上有效地对它们执行恒星展开。通过从中提取下船体，获得 3D Delaunay 三角剖分。

更快的替代方法是 gDel3D ，这是一种混合 GPU-CPU 算法。

它在 GPU 上执行并行插入和翻转。结果接近德劳内。然后它在 CPU 上使用保守的星形展开方法修复这个结果。

所有这些方法都很稳健，因此它们可以处理任何类型的退化输入。