python等值⾯_三维等值⾯提取算法（DualContouring）
上⼀篇介绍了Marching Cubes算法，Marching Cubes算法是三维重建算法中的经典算法，算法主要思想是检测与等值⾯相交的体素单元并计算交点的坐标，然后对不同的相交情况利⽤查表在体素单元内构建相应的⽹格拓扑关系。Marching Cubes算法简单，但是存在⼀些缺陷：1.模型⼆义性问题；2.模型特征问题。
对于⼆义性问题，以2D情形为例，存在⼀个单元中同⼀顶点状态⽽不同的连接⽅式(如下图所⽰)。
图：2D中Marching Cubes算法的⼆义性问题
那么对于上图中两种连接⽅式的不同选择，可能会导致在同⼀张图像上完全不同的结果(如下图所⽰)，⼆义性在3D中的直接后果是产⽣“孔洞”。如果在⼀个单元中，⼀条对⾓线的两端点值⼤于等值⾯阈值，另⼀条对⾓线的两端点值⼩于等值⾯阈值，那么通常会发⽣这种⼆义性问题。
图：⼆义性问题的不同结果
对于特征问题，由于Marching Cubes算法只计算体素单元的交点坐标信息，并根据这些交点连接的三⾓⾯⽚来构建体素单元内的⼏何模型，这样假如体素单元内存在⼏何模型的特征信息(棱边、棱⾓)，但是Marching Cubes算法最终构建出的⼏何模型会缺少这些特征信息(如下图所⽰)。
图：左上-交点坐标和法向；右上-Marching Cubes算法；左下-Extended Marching Cubes算法；右下-Dual Contouring算法
Dual Contouring算法[Ju et al. 2002]也是经典的等值⾯提取算法，相⽐Marching Cubes算法，Dual Contouring算法利⽤Hermite数据(交点的位置和法向)进⾏等值⾯构建，它克服了Marching Cubes算法所出现的缺陷。具体算法分两步：
第⼀步：利⽤⼆次误差函数⽣成顶点坐标
对于每个与等值⾯相交的体素单元，通过最⼩化⼆次误差函数来⽣成⼀个顶点坐标：
其中pi为交点的位置，ni为交点的法向。
误差函数可以写成矩阵形式：
其中矩阵A的⾏向量为交点的法向ni，向量b的每个元素为ni·pi。
极值点可以通过求解正则⽅程得到：
但是⽂章指出这种⽅式会存在数值不稳定，并提出⼀种解决⽅法。基于QR矩阵分解计算正交矩阵Q，使得Q与[A b]相乘为如下上三⾓矩阵形式：
其中A'为3*3的上三⾓矩阵，b'为长度为3的向量，r为标量。
那么误差函数可以变化为：
然后再根据上式计算极值点。
第⼆步：⽣成⽹格⾯⽚
对于每⼀条等值⾯相交的体素边，那么包含该体素边的4个相邻体素单元内必然都存在顶点，将这4个顶点连接⽣成1个四边形⾯⽚。
⽂章[Schaefer et al. 2002]详细介绍了Dual Contouring算法的实现细节，通过总结该⽂可以得到Dual Contouring算法过程如下：
对于每个与等值⾯相交的体素单元：
1. 创建1个4*4的零矩阵⽤于存放QR矩阵分解的结果；
2. 对于体素单元的每条相交边，计算交点的位置pi和对应的法向ni；
3. 将向量[ ni.x, ni.y, ni.z, dot(pi,ni) ]添加到4*4的零矩阵底部；
4. 通过QR矩阵分解得到3*3的上三⾓矩阵A'和向量b'；
5. 求解线性⽅程组A'TA'x = (A'Tb' - A'Tb'c) , 其中c是体素单元中所有交点的质⼼位置；
6. 将计算得到的偏移量x加上质⼼位置c即为体素单元中的顶点坐标；
7. 如果计算得到的顶点坐标位于体素单元之外，那么顶点坐标⽤质⼼位置c来代替；
8. 对于每⼀条相交的体素边，将其周围4个体素单元内的顶点连接⽣成1个四边形⾯⽚。python怎么读取桌面上的文件
图：左- Marching Cubes算法；右-Dual Contouring算法
图：左- Marching Cubes算法；右-Dual Contouring算法
图：box与sphere相交模拟
相关：
参考⽂献：
[1] Tao Ju, Frank Losasso, Scott Schaefer, and Joe Warren. 2002. Dual contouring of hermite data. ACM Trans. Graph. 21, 3 (July 2002), 339-346.
[2] Scott Schaefer and Joe Warren. Dual contouring: The secret sauce. Technical Report 02-408, Department of Computer Science, Rice University, 2002.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。