Marching Cubes

Marching Cubes算法是三维离散数据场中提取等值面的经典算法，其主要应用于医学领域的可视化场景，例如CT扫描和MRI扫描的3D重建等值面，即空间中所有具有某个相同值的点的集合，可以类比为地形图里的等高线。

${ (x,y,z)|f(x,y,z)=c, c\in C }$

算法思想

• 基本假设：沿六面体边的数据场呈连续性变化。如果一条边的两个顶点分别大于或小于等值面的值，则在该条边上有且仅有一点是这条边与等值面的交点。
• 逐个处理数据场中的立方体（体素voxel），分离出与等值面相交的立方体，采用插值计算出等值面与立方体边的交点。根据立方体每一顶点与等值面的相对位置，将等值面与立方体边的交点按一定方式连接生成等值面，作为等值面在该立方体内的一个逼近表示
• 直观地说，就是用许多小正方体去对空间进行切分，然后用小正方体内部的平面来近似表示当前的等值面。小正方体的数量越多，逼近的效果越好，计算需要的资源就越多

部分细节

• 小正方体内部的平面可以小立方体和等值面的相交情况来确定

• 对于每个小正方体来说，每个顶点两种情况（大于或小于）当前等值面的值，8个顶点共256种情况，考虑到旋转对称性，从新分类后可得15种基本模式

实现

1. 将原始数据经过预处理之后，读入指定的数组中
2. 从网格数据体中提取一个单元体，成为当前单元体，同时获取该单元体的所有信息，例如8个顶点的值、坐标位置等
3. 将当前单元体8个顶点的函数值与给定等值面值C进行比较，得到该单元体的状态表（edgeTable、triTable）
4. 根据当前单元体的状态表索引，找出与等值面相交的单元体棱边，并采用线性插值的方法，计算出各个交点的位置坐标
5. 利用中心差分法，求出当前单元体8个顶点的法向量，在采用线性插值的方法，得到三角面片各个顶点的法向
6. 根据各个三角面片顶点的坐标，顶点法向量进行等值面图象的绘制

Reference

Marching Cubes算法理解

【算法】Marching Cubes算法理解