如何加速Marching Cubes算法？

Question

我正在使用这个 marching cube 算法绘制3D等值面（移植到C#，输出MeshGeometry3D，但其他方面相同）。生成的表面看起来很好，但计算时间很长。

有什么方法可以加速 marching cubes 算法吗？最明显的方法是简单地减少空间采样率，但这会降低生成网格的质量。我想避免这种情况。

我正在考虑一个两步系统，第一步对空间进行更粗略的采样，消除场强明显低于我的等值线的体积。这样做明智吗？有哪些风险？

编辑：代码已经进行了分析，大部分 CPU 时间都分配在 marching cubes 程序本身和每个网格单元角的场强计算上。场强计算超出了我的控制范围，因此加速立方体程序是我的唯一选择...

我仍然倾向于尝试消除死空间，因为这将显著减少对两个系统的调用次数。

- Dan Vinton

Answer 1

我知道这个问题有点过时了，但我最近根据类似的源代码实现了Marching Cubes。这里存在许多低效率的地方。如果你正在进行以下操作：

for (int x=0; x<densityArrayWidth; x++)
  for (int z=0; z<densityArrayLength; z++)
    for (int y=0; y<densityArrayHeight; y++)
      Polygonize(Gridcell, isolevel, Triangles)

看一下你会重新分配edgeTable和Tritable的次数！这些需要立即移动到整个类中。我也放弃了gridCell对象，直接从点/值转移到三角形中。

简而言之，这不仅是算法复杂度的问题，内存分配（在基础部分有大量）也需要时间。

- Will Gore

Answer 2

以防其他人也会看到这里，通过较粗的采样率消除死区几乎没有任何区别。 任何远程安全的（即：允许采样伪影的边框）更粗略的采样最终都会在任何相对非平凡的领域中捕获大多数网格。

加速底层场评估（使用重度记忆化）似乎“主要”解决了性能问题。

- Dan Vinton

Answer 3

每个立方体都有12条边，如果你遍历每个立方体并找到12个交点，那么你会做4倍于所需的交点计算 - 你只需要使用每个立方体左下角的3条边，在区域右上角使用额外的一行，然后使用特殊升级来访问您找到的所有值。我将在这个主题上进行讨论，因为它需要被讨论，而且很复杂。

此外，通过使用Octree评估ISO级别并跳过远离ISO级别的区域，测试需要多边形的空间区域。

我研究了传播，但它并不是那么可靠和高效。

- bandybabboon

Answer 4

尝试使用四面体算法代替 -- 数学更简单，使您能够考虑每个单元格的情况更少。

- Crashworks

---

我认为这不是一个好主意……虽然数学更简单，但对于给定的网格分辨率，你将不得不处理比立方体多得多的四面体。这里有一篇调查论文的链接，其中包含可能的优化指针等内容。它有点旧（2006年），但我认为最近并没有太多革命性的研究。http://graphics.ethz.ch/teaching/scivis_common/Literature/Newman06.pdf - user168715

更多的四面体，但每个四面体的计算量更少，依赖操作更少，可能更容易并行化。事实上我不知道；我提到这个因为我们正在计划用 marching-tetras 替换 marching-cubes 进行一项实验，我很好奇是否有其他人尝试过并进行了测量。 - Crashworks

刚刚尝试了一下我下载的C#端口并进行了测试。对于立方体，用时3秒；对于四面体，用时11秒。我不确定是否可以改变四面体的网格大小以使其更快且更美观。 - Grant M