用于GPU的最快Delaunay三角剖分算法

Question

您认为哪种GPU最快的Delaunay三角剖分算法？或者更一般，并行

Answer 1

小心使用GPU：Delaunay Triangulations需要定位测试。这些在浮点运算中无法可靠地工作，并且可能很难应付使用GPU的那个问题。内存管理也很重要。

您可能想尝试http://www.geom.at/fade2d/html/，它是最快速稳健的 单线程实现之一。

Answer 2

二维Delaunay三角

GPU-DT是最快的二维Delaunay实现了GPU。

它使用GPU构建2D数字Voronoi图并行绑定算法。接下来，它修复并将其二元化以获得二维三角测量。最后，它在GPU上并行执行边缘翻转以获得2D Delaunay三角测量。

3D Delaunay三角

gStar4D是针对GPU快速而强大的实施3D德劳内。

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

更快的选择是gDel3D，这是一种混合GPU-CPU算法。

它在GPU上执行并行插入和翻转操作。结果接近德劳内。然后在CPU上使用一种保守的星型划分方法来修正这个结果。

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