Marching Cubes算法

Marching Cubes（行进立方体）是一种简单的迭代算法，用于为 3D 函数创建三角形表面（在我们的例子中，3D 函数是按点定义的，称为体素）。

它通过在已划分为立方体的整个 3D 区域上Marching（行进）来工作。立方体的顶点是体素。该算法计算三角形表面是否穿过该立方体。对于高层次的直觉来说，如果立方体的角（体素：Voxel）都为 1。这意味着立方体将完全位于表面内。同样，如果体素全为 0，则表示立方体位于表面之外。在这两种情况下，都没有三角形表面穿过立方体。该算法的主要目的是在某些体素为 1 其他体素为 0（在立方体内部）的情况下计算三角形表面（其交点、法线）。由于立方体中有 8 个体素，其值可以为 0 或 1，因此我们有 2⁸ = 256 个立方体配置。

该算法的巧妙之处在于它通过以下方式处理 256 个配置的计算：

将案例数减少到 15 个（考虑到旋转和镜像对称引起的冗余）
使用一个聪明的索引表（查找表）来加速整个过程。

1、算法原理解读

考虑问题的二维变体。我们需要把它分成多边形。我们将整个区域划分为正方形（在Marching Cubes中，我们将区域划分为立方体）。

请注意，这里的蓝色区域是所需的形状，输入将是体素化表示。在 2D 中，体素对应于红点。

现在我们可以看到正方形配置。对于所有顶点都是红色的正方形，不应有边界穿过它。具有所有蓝色顶点的立方体也是如此。对于其他情况，行进立方体算法将计算边界应如何穿过正方形。

由于有 4 个顶点，我们有 16 个案例。

利用上面的图我们标记交点：

粉红色的点是算法计算出的边界与边缘的交点。最后给出这些网格渲染系统可以创建如图所示的网格表示：

虽然这种表示方法不错，但网格边界仍然不太准确。精度可以通过两种方式提高

减少正方形的面积。
更好的插值策略。

减少正方形的面积（增加正方形的数量）将导致计算成本增加。

插值策略：在上面的示例中，在确定立方体的配置后，我们只是将边的中点标记为交点。更好的策略（如原始算法中给出的那样）是通过线性函数标记交点（真正的算法只使用质点平均）。此修改获得的输出是：

2、实际算法

下图显示了边和顶点的命名法：

假设只有顶点 3（或顶点 3 处的体素）为 1，则通过立方体的三角形网格将切割边 3、2、11。注意，当只有顶点 3 为 0 其余为 1 时，应获得相同的表面。（这减少了立方体配置的数量从 256 到 128）。

该算法的作者通过翻转 8 位立方体索引的位来编码信息（哪些顶点在所需体积之内或之外）。

int cubeindex = 0
if (vertex 0 is 1) cubeindex | = 1
if (vertex 1 is 1) cubeindex | = 2
if (vertex 2 is 1) cubeindex | = 4
if (vertex 3 is 1) cubeindex | = 8
if (vertex 4 is 1) cubeindex | = 16
if (vertex 5 is 1) cubeindex | = 32
if (vertex 6 is 1) cubeindex | = 64
if (vertex 7 is 1) cubeindex | = 128

其中 cubeindex |= 2^i 表示 cubeindex 的第 i 位设置为 1

构造另一个哈希表，给出要切割的边（与上面显示的编码类型相同。这次如果要切割相应编号的边，则数字的每个位都是 1）。 hastable（输入）的索引是生成的 cubeindex。

所以在体积内只有 3 个的示例中（体素值为 1，其余为 0），

多维数据集索引将返回 00001000 = 8
边哈希表将返回 edgeTable[8] = 100000001100

如果 P1 和 P2 是切割边的顶点（顶点的坐标位置）并且 V1 和 V2 是每个顶点的标量值（在我们的例子中为 0 或 1），则交点 P 由下式给出：

P = P1 + (0.5 — V1) (P2 — P1) / (V2 — V1)

使用这些点即可以获得网格。

原文链接：Voxel to Mesh Conversion: Marching Cube Algorithm

BimAnt翻译整理，转载请标明出处