最快的GPU Delaunay三角剖分算法

Question

在您看来哪个GPU最快的Delaunay三角剖分算法？或者更一般,并行

Answer 1

2D Delaunay三角剖分

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

它使用GPU 并行条带算法在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上执行并行插入和翻转.结果接近Delaunay.然后,它使用CPU上的保守星形展开方法修复此结果.

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

Answer 2

小心GPU:Delaunay三角测量需要定向测试.这些不能与浮点运算可靠地工作,并且使用GPU可能很难处理该问题.内存管理也很重要.

您可能想要尝试http://www.geom.at/fade2d/html/,这是最强大的单线程实现之一.