Marching Cubes 效率 - 您可以减少 3/4 的边缘计算吗?

3
普通的 marching cubes 每个立方体有 12 条边,但你可以每个立方体只保留 3 条边,并将这些边保存在一个数组中。然后再次遍历所有的立方体时,引用相邻立方体的边而不是重新计算它们。
如何引用相邻立方体的过程并没有在网上清楚地讨论,因此任何使用 marching cubes 的人都可以帮助找到解决方案的细节。你知道是否已经有实现了吗?
下面是一张图片,黄色部分显示了每个立方体所需的 3 条边,而不是 12 条。 Image 编辑- 我刚刚找到了这个解决方案,虽然它只是其中的一部分:
想象一下从具有最低坐标的立方体角落出发的 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)。另外两个具有相同边缘的立方体是(x,y+1,z)和(x-1,y,z)。
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
编辑2- 所以我正在做这件事,它并不简单。我有一个循环同时计算8个点、12个边、边缘插值、位值和顶点边缘值,所有这些都在一个循环中。
因此,我正在做一个新的循环来尽可能地计算并将其放置在数组中,以在复杂的循环中使用。
我可以回收沿边缘交点插值的值,并将其存储在一个数组中,尽管我将不得不重新计算所有点的值,因为我用于决定位数的点的值引用了顶点表中的值。这让我很困惑!我以为一旦我有了边缘相交的值,我就可以直接使用它们来获取三角形表,而无需重新计算所有点的值!
事实上不是。 无论如何,下面是另一个已经完成此操作的人提供的信息,如果只是可读的话! http://www.new-npac.org/projects/sv2all/sv2/vtk/patented/vtkImageMarchingCubes.cxx 向此行滚动:Cubes are responsible for edges on their min faces.

所以我正在做这个,但它并不简单。我有一个循环,同时计算8个点、12条边、边的插值、位值和一个顶点的边值,所有这些都在一个循环中完成。 - bandybabboon
解决方案是在 XYZ 上使用仅 3 条边的网格 1x 方块更大,结果是一个数组,然后在检查每个方块的 12 条边时进行交叉引用。使用 GPU 比 CPU 快 100 倍,因此从性能上来说,CPU 在这些天已经落后了。 - bandybabboon
3个回答

2
通过按每个轴向对齐的平面依次计算立方体来简化边缘计算是一个简单的方法。如果您保留了所有带有其边缘的立方体,那么仅需计算每条边一次,并通过索引找到相邻的边将变得容易。然而,由于空间要求,通常不想同时在内存中保存所有立方体。
解决方法是逐个计算立方体平面。即从一侧开始并向相反侧进展的轴向截面。然后,您只需要同时保留最多两个完整平面的立方体。当您通过每个平面移动时,您可以引用先前平面中共享的边缘和当前平面中先前计算的立方体。当您移动到下一个平面时,可以取消分配您将不再需要的平面。
编辑:本文讨论了我所建议的内容:http://alphanew.net/index.php?section=articles&site=marchoptim&lang=eng

1
有趣的是,当我实现自己的MC时,我想出了类似的解决方案。
当你开始使用MC时,你将它们视为不同的立方体,但如果你想要高性能,你需要将整个网格作为一个整体创建,并且在这里创建顶点索引等并不容易。当您想要添加平滑的每顶点法线时,情况变得更加有趣 :)。
为了解决这个问题,我创建了一个简单的索引缓存机制来存储每个边的顶点索引。 然后,对于每个计算的边,我都有立方体位置x、y、z和边索引,我按如下方式操作:
For each axis:
    if the edge is on '+' side of axis:
        replace edge index with its '-' side sibling
        increment cube position along axis

这个简单的操作让我得到了正确的立方体位置和边缘索引0、1、2。然后,我使用简单的位旋转从x、y、z、edgeIndex值计算出总缓存索引。
当我有缓存索引时,我检查它是否大于-1。如果是,那么这条边上已经计算出了一个顶点,我可以重复使用它。如果它是-1,则需要创建一个新的顶点并将其索引存储在缓存中。这样,您只需计算每个顶点一次,并且甚至可以添加共享于包含您的顶点的每个三角形的法线值。

谢谢!我花了一段时间来处理这个问题,并制作了一个每个立方体有3个边的索引,为外侧添加了一行,但出于某种原因速度并没有提升太多。未来的计算着色器MC将比处理器快100倍。 - bandybabboon
仅仅共享顶点并不能带来太多的性能提升,但如果你想计算每个顶点的法线,这真的非常有用,我就是这么做的。我仍在解决一些模糊情况,但完成后我会公开发布。 - kolenda
如果你感兴趣的话,nVidia的GPU Gems有一些关于使用GPU生成复杂程序地形的迷人内容,包括如何实现碰撞检测。 - Basic
我对每个顶点法线如何更快感到困惑?因为所有顶点都以数组的形式到达,然后法线是由同一三角形的顶点制成的,只是数组索引。 - bandybabboon
如果您需要一个慢而复杂的选项,可以使用超级精确的等值面力场法线,但是它会在快速变化的网格区域处感到困惑。 - bandybabboon
显示剩余2条评论

1

是的,我认为我做得与kolenda类似。我有一个包含5个整数的结构体:(cube)索引和4个顶点索引(A、B、C、D)。

对于最内部的循环(x),我只有lastXCache和nextXCache。在指向-x方向的四条边上,我会问lastXCache.A != -1,如果是,就分配先前计算得出的值等等。 在+x方向上,我将计算出的顶点存储在nextXCache中。当立方体完成时:lastXCache = nextXCache; 对于y和z方向,它需要是列表(unity术语用于可变数组),下一个y是下一行(因此是sizex),下一个z是下一个平面(因此是sizex * sizey)

唯一的缺点是这种方式必须串行地运行立方体之后的立方体。但是,您可以并行计算不同的块。

我想到的另一种更并行的方法需要两次传递:1.每个立方体计算3个边,当1完成时-> 2.绘制三角形。

不太清楚哪种更好,但实际起作用的方式似乎足够快。使用Unity Jobs效果更佳。为每个块/网格创建一个IJob。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接