algorithm - 行进立方体效率 - 你可以减少 3/4rs 的边缘计算吗？

Question

普通行进立方体为每个立方体找到 12 条边，但您可以为每个立方体做 3 条边，将边保存在数组中，然后再次遍历立方体，引用相邻立方体的边而不是计算它们。

引用相邻立方体的过程在 Internet 上没有明确讨论，因此欢迎任何使用行进立方体的人帮助找到解决方案的详细信息。你知道一个实现了吗？

这是一张图片，显示了每个立方体所需的 3 条黄色边，而不是 12 条。

编辑-我刚刚找到了这个解决方案，尽管它只是其中的一部分:

想象一下 3 条边来自立方体具有最低坐标的角。然后所有其他边只属于其他立方体。如果我们的立方体坐标为 (x,y,z)，则相邻立方体的坐标为 (x+1,y,z), (x,y+1,z), (x,y,z+1), (x +1,y+1,z), (x+1,y,z+1), (x,y+1,z+1)。你可以把边想象成一个向量。然后立方体的角有边(1,0,0)，(0,1,0)，(0,0,1)。坐标为 (x+1,y,z) 的立方体的边 (0,1,0) 和 (0,0,1) 属于我们的立方体。立方体 (x+1,y+1,z) 只有一条边 (0,0,1) 属于我们的立方体。因此，如果您为立方体存储 4 个元素，您可以像这样访问它们:

edge1 = cube[x][y][z][0];
edge2 = cube[x][y][z][1];
edge3 = cube[x][y][z][2];
edge4 = cube[x+1][y][z][1];
edge5 = cube[x+1][y][z][2];
edge6 = cube[x][y+1][z][0];
edge7 = cube[x][y+1][z][2];
edge8 = cube[x][y][z+1][0];
edge9 = cube[x][y][z+1][1];
edge10 = cube[x+1][y+1][z][2];
edge11 = cube[x+1][y][z+1][1];
edge12 = cube[x][y+1][z+1][0];

现在 edge7 连接哪些点？答案是 (x,y+1,z) 和 (x,y+1,z)+(0,0,1)=(x,y+1,z+1)。

现在 edge7 连接了哪些立方体？它更难。我们看到坐标 z 沿边缘发生变化，这意味着相邻立方体具有相同的 z 坐标。现在所有其他坐标都改变了。我们有 +1 的地方，立方体有大坐标。在我们有 +0 的地方，立方体的坐标较小。所以边连接立方体 (x,y,z) 和 (x-1,y+1,z)。其他 2 个具有相同边的立方体是 (x,y+1,z) 和 (x-1,y,z)。

-=-=-=-=-=-=-=-=-=-=-=--=-=-=-=-=-=-=--=-=

编辑2-所以我正在这样做，它不是那么简单。我有一个循环，它同时计算 8 个点、12 个边、边的插值、位值和一个顶点的边值，所有这些都在一个循环中。

所以我在它之前做了一个新的循环来尽可能多地计算并将它放在数组中以便在复杂的循环中使用。

我可以在一个数组中沿边缘回收交点的插值，尽管我将不得不在复杂的循环中再次重新计算所有点，因为我用来决定引用值的位数的点的值在顶点表中。这让我很困惑!我想一旦我有了边交点值，我就可以直接使用它们来获取三角形表，而不必重新计算所有的点!

其实没有。不管怎样，这里有一些已经做过的人的信息，如果它是可读的就好了! http://www.new-npac.org/projects/sv2all/sv2/vtk/patented/vtkImageMarchingCubes.cxx滚动到这一行:立方体负责其最小面上的边缘。

Answer 1

以您建议的方式减少边缘计算的一种简单方法是一次计算一个轴对齐平面的立方体。

如果您将所有立方体及其边都保存在内存中，则很容易只计算每条边一次并通过索引找到相邻边。但是，由于空间要求，您通常不想一次将所有多维数据集保存在内存中。

对此的解决方案是一次计算一个立方体平面。即轴对齐的横截面，从一侧开始并前进到另一侧。然后，您一次最多只需要在内存中保留两个完整的立方体平面。当您穿过每个平面时，您可以引用前一个平面中的共享边和当前平面中先前计算的立方体。当您移动到下一架飞机时，您可以取消分配您不再需要的飞机。

编辑:这篇文章讨论了如何做我的建议: http://alphanew.net/index.php?section=articles&site=marchoptim&lang=eng