对于计算三维 Delaunay 三角剖分（实际上是四面体化），TetGen是一个常用的库。

为方便起见，这里有一个小基准，用于计算从单位立方体中计算多个随机点的三面体化需要多长时间。对于 100,000 点，在旧的 Pentium M 上需要 4.5 秒。

^{（这是通过 Mathematica 的 TetGen 接口完成的。我不知道它引入了多少开销。）}

关于您的另一个问题：如果您已经有了 Voronoi 细分，那么获得 Delaunay 三角剖分是一个相对简单的转换。

gStar4D是一种用于 GPU 的快速且强大的 3D Delaunay 算法。它使用 CUDA 实现并在 NVIDIA GPU 上运行。

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

最快的 3D Delaunay 实现是gDel3D，它是一种混合 GPU-CPU 算法。

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

这两种方法都很健壮，因此它们可以处理任何类型的退化输入。如果你有足够大的 GPU 内存来保存中间数据结构，它们可以处理数百万个点。

披露：我是这些算法和实现的作者 :)

我建议尝试 CGAL http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3/Chapter_main.html#Section_39.2 ，正如 Paul 上面所建议的那样。CGAL 是一个健壮且得到良好支持的库，已经存在了很长一段时间。过去我很高兴地使用它，即使在具有共线和共面点的点集上也是如此。我不知道它是否是今天最快的，但它肯定是一个很好的起点。

上面的链接还包括一些性能数据：它可以在大约 10 秒内完成一百万个点，在大约 1.5 分钟内完成一千万个点。

如果您已经有了一组点的 voronoi 图，那么计算 Delaunay 三角剖分只需要 O(n)。等效地，给定一个 voronoi 点，您可以在 O(1) 中获得其 Delaunay 三角形。它们是双重的，所以尽可能尝试利用这种情况。