使用一组随机点构建四面体 - 四面体剖分

Question

我有一组点（100万个，未来可能会更多，如10或100百万个），在3D空间中形成一个球体（它们填充了球体-它们不仅仅在表面上），我想建立连接每个球体与其第一邻居的四面体...到目前为止，我找到的都是四面体网格化算法，但它们填充了空白区域，而我的点是固定的。我该怎么做呢？

2014-08-09首先，感谢大家的建议！我正在度假，只是路过来看看是否有人回答...我并没有失望！！！:-) 我想我会先尝试CGAL，然后再看看其他的。我对同一组点进行了O(n2)的其他数据计算，预计需要大约1周的时间，所以几个小时也不会太糟糕。几分钟就是梦想成真！

- user22744

---

四面体剖分...我的舌头缩回了一个黑暗的角落，开始哭泣... - bolov

http://lcni.uoregon.edu/~dow/Projects/Brain_casting/Point_cloud_to_mesh.html 可能是一个不错的起点。根据您的需求，3D凸包可能已经足够了。 - parapura rajkumar

你可能想先看一下类似的二维问题（用三角形填充）：Delaunay 三角剖分。 - Raedwald

使用四面体 Marching Tetrahedra 算法怎么样？它类似于 Marching Cubes，而且实现起来非常容易。 - Jaa-c

@Jaa-c 那个不是用来寻找水平面集的吗？你需要一个四面体空间。OP正试图首先创建这样的四面体空间。 - emsr

Answer 1

你似乎在寻找一个三维空间中的Delaunay三角剖分算法。

我希望你不介意等待一段时间，因为对于一亿个点的Delaunay三角剖分需要相当长的时间。

qhull有一个n维Delaunay实现，你可以尝试一下。CGAL也有类似的实现。这两个软件包都能以O(n log(n))的渐近时间计算Delaunay三角剖分，而CGAL可以通过适当选择几何核心，在数值上进行稳健的计算。（也就是说，它可以自动切换到精确算法，以避免不确定结果的产生。）

我不建议自己尝试实现快速的Delaunay三角剖分，即使是在二维情况下。当你需要在算术结果上评估谓词时，可能会发生可怕的事情。

- tmyklebu

---

在二维中使用dt并不难，毕竟它只涉及到一点几何学。 - Micromega

@Phpdna：在精确算术中这很容易。但如果你想让代码运行得更快，就不能使用精确算术。使用浮点数算术时，你会遇到一个根本性的问题，那就是你需要以一种一致的方式对算术结果进行谓词计算。解决这个问题并不容易。（换句话说：“我敢打赌我能毁掉你的Delaunay三角剖分代码。”） - tmyklebu

你也可以修复错误的三角剖分吗？ - Micromega

@Phpdna：如何做？如果这不是三角剖分怎么办？如何检测“糟糕”的部分？ - tmyklebu

@tmyklebu：只是为了澄清一下——CGAL和qhull都实现了快速的O(nlog(n))算法。CGAL还具有“健壮性”——使用精确算术和符号扰动（必要时），确保始终生成有效的DT，即使输入是退化的。在实践中，DT算法通常表现出O(n)的缩放性，因此对于100百万个点进行镶嵌的时间可能不会像您想象的那样糟糕，尽管肯定需要几分钟而不是几秒钟（http://doc.cgal.org/latest/Triangulation_3/）。 - Darren Engwirda

Answer 2

我在一个项目中使用tetgen进行四面体网格化。它的效果相当不错，速度也足够快。

- Guangming Mao