在您看来，GPU 可用的最快的 Delaunay 三角剖分算法是哪一种？或更一般地，并行
问问题
10308 次
2 回答
24
2D Delaunay 三角剖分
GPU-DT是 GPU 上最快的 2D Delaunay 实现。
它使用 GPU Parallel Banding Algorithm在 2D 中构建数字 Voronoi 图。接下来，它修复并对其进行二元化以获得 2D 三角剖分。最后，它在 GPU 上并行执行边缘翻转以获得 2D Delaunay 三角剖分。
3D Delaunay 三角剖分
gStar4D是用于 GPU 的快速且强大的 3D Delaunay 实现。
与 GPU-DT 类似，该算法首先构建 3D 数字 Voronoi 图。但是，在 3D 中，由于拓扑和几何问题，这不能二元化为三角剖分。相反，gStar4D 使用此图中的邻域信息来创建提升到 4D 的星星，并在 GPU 上有效地对它们执行星星展开。通过从中提取下船体，获得 3D Delaunay 三角剖分。
更快的替代方案是gDel3D，它是一种混合 GPU-CPU 算法。
它在 GPU 上执行并行插入和翻转。结果接近德劳内。然后，它在 CPU 上使用保守的星形展开方法修复此结果。
所有这些方法都很健壮，因此它们可以处理任何类型的退化输入。
于 2013-04-29T09:41:33.263 回答
11
小心使用 GPU：Delaunay 三角测量需要方向测试。这些在浮点运算中不能可靠地工作，使用 GPU 可能很难解决这个问题。内存管理也很重要。
您可能想尝试http://www.geom.at/fade2d/html/这是最快的健壮单线程实现之一。
于 2011-10-29T23:27:57.687 回答