自动驾驶 – 第 2 页

　Marching Cubes算法是三维离散数据场中提取等值面的经典算法，其主要应用于医学领域的可视化场景，例如CT扫描和MRI扫描的3D重建等。

Marching Cube 首先将空间分成众多的六面体网格，类似将空间分成很多的小块

我们有很多的已知采样点，并且知道这些点在空间中的空间场值，现在我们将空间分为很多个小格子，每个小格子都有8个顶点，我们通过计算8个顶点周围（范围与六面体的大小相关）的采样点，近似计算出8个顶点的空间场值（加权评价等方法）。　

以0等值面为例:如何找到0等值面经过的六面体网格？　

算法主要的思想是在三维离散数据场中通过线性插值来逼近等值面，具体如下：三维离散数据场中每个栅格单元作为一个体素，体素的每个顶点都存在对应的标量值。如果体素顶点上的值大于或等于等值面值，则定义该顶点位于等值面之外，标记为“0”；而如果体素顶点上的值小于等值面值，则定义该顶点位于等值面之内，标记为“1”。由于每个体素单元有8个顶点，那么共存在2^8 = 256种情形，下图是Marching Cubes算法的15种基本情形，其他241种情形可以通过这15种基本情形的旋转、映射等方式实现。

　每个体素单元上顶点和边的索引规则如下图左所示，假如体素下方的顶点3的值小于等值面值，其他顶点上的值都大于等值面值（如下图右所示），那么我们可以生成一个与体素边2，3，11相交的三角面片，而三角面片顶点的具体位置则需要根据等值面值和边顶点3-2，3-0，3-7的值线性插值计算得到。

对于与等值面存在交点的体素边，交点坐标用P表示，P₁、P₂代表边上两个端点的坐标，V₁、V₂代表这两个端点上的值，V代表等值面值，那么交点坐标的计算公式如下：

P = P₁ + (V – V₁)·(P₂ – P₁)/(V₂ – V₁)

　　算法第一步：通过edgeTable表判断等值面和体素单元哪一条边相交

　　体素单元顶点状态的索引号定义规则如下：

cubeindex = 0;
if (V[0] < isolevel) cubeindex |= 1;
if (V[1] < isolevel) cubeindex |= 2;
if (V[2] < isolevel) cubeindex |= 4;
if (V[3] < isolevel) cubeindex |= 8;
if (V[4] < isolevel) cubeindex |= 16;
if (V[5] < isolevel) cubeindex |= 32;
if (V[6] < isolevel) cubeindex |= 64;
if (V[7] < isolevel) cubeindex |= 128;

以上图所示为例，仅顶点3标记为“1”，其他顶点标记为“0”，那么体素单元的顶点状态为0000 1000或者8，通过查找表得到edgeTable[8] = 1000 0000 1100，意味着体素单元的边2，3，11和等值面相交，然后通过线性插值计算各个交点的位置。

算法第二步：通过triTable表生成对应三角面片的组成情况

　　还是以上图所示为例，通过查找表得到triTable[8] = {3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}，意味着该种顶点状态可以生成三角面片(3, 11, 2)，代表三角面片的3个顶点为边3，11，2和等值面相交的交点。

　　经过上述步骤之后，我们可以得到等值面的点面信息。为了进一步完善显示效果，需要调整顶点法向。假设顶点(i, j, k)上的值为f(i, j, k)，采用中心差分方法可以计算该点处的梯度矢量：