维空间规则数据场的等值面构造.ppt
三维空间规则数据场的等值面构造,将三维数据场中具有某种共同属性的采样点按其空间位置连接起来，构成一张连续表面，然后对抽取出的表面进行绘制等值面算法等值面：在一给定三维数据场中，采样值均为某一给定值的所有空间点的集合三维标量场可视化中最常用Marching Cubes方法Marching Tetrahedra方法,面绘制算法,目的：从一系列二维切片数据中得到物体的三维表示输入：由N张二维的切片生成数据。为得到比较好的显示效果，N应该越大越好其中每张切片可以看成是一幅二维图像，包含了宽高个灰度值输出：物体形状的三维表示，一般采用三角网格的形式来表达,面绘制算法,面绘制算法,特点：不能反映整个原始数据场的全貌及细节可以对感兴趣区域的等值面产生清晰的图像可以利用现有的图形硬件实现加速绘制,Marching Cubes算法,由W.E.Lorenson和H.E.Cline在1987年提出，在美国已申请专利方法原理简单，易于实现，目前已经得到了较为广泛的应用，被认为是至今为止最流行的面显示算法之一Marching Cubes方法的本质是从一个三维的数据场中抽取一个等值面，也被成为“等值面提取”（Isosurface Extraction），常被简称为MC方法,Marching Cubes算法,过程简述：每次读入两张切片，形成一层（Layer）；两张切片上下相对应的四个点构成一个立方体（Cube），也叫Cell、Voxel等；从左到右，从上到下顺序处理一层中的立方体（抽取每个立方体中的等值面），然后从下向上顺序处理（n-1）层，算法结束。故名Marching Cubes,Marching Cubes算法,数据集适用于三维规则标量场每一立方体单元称为一个体素（Voxel或Cell），数据场的数据值分布在体素的8个顶点上典型代表：CT数据、MRI数据,Marching Cubes算法,思想：基于“分治（divide-and-conquer）”思想将整个数据场的等值面抽取分解到每一个体素中去完成,体素模型,Marching Cubes算法,Marching Cubes算法,算法概述读入三维规则标量场对于每一体素依据所需抽取的等值面的属性值（阈值），确定其8个顶点的状态如果一个顶点的灰度值大于阈值，则标记为Marked Vertex，小于阈值的顶点不标记Unmarked Vertex对于体素的每一条边，依据顶点状态，判别它是否与等值面有交点。若交点存在，则求出交点在求出了当前体素的所有边与等值面的交点后，依据一定的准则将这些交点连接成三角形，作为等值面位于该体素内部分的近似表示，并进行真实感绘制当处理完所有体素后，即完成了整个数据场的等值面抽取与绘制,Marching Cubes算法,确定体素顶点状态设所需抽取的等值面的属性值为C0若某顶点V所存贮的数据值大于（或等于）C0，则认为V在等值面外侧（或位于其上），并记其状态值为1反之，若V所存贮的数据值小于C0，则认为V在等值面内侧，并记其状态值为0,Marching Cubes算法,确定体素顶点状态Example：5个顶点均位于外侧，记为10111100用一个字节的空间构造一个体元状态表,Case=v8|v7|v6|v5|v4|v3|v2|v1,v1 v2,v5 v6,v4 v3,v8 v7,Marching Cubes算法,判别体素的边与等值面是否有交对于某一条边E（其顶点为V1和V2），若V1和V2的状态值相同，则边E位于等值面的外侧（或内侧），边E不与等值面相交；反之，若V1和V2的状态值不同，边E必定与等值面相交若边E与等值面有交点，可通过线性插值计算出交点,Marching Cubes算法,三线性插值,沿Z方向插值P0、P1、P2、P3沿Y方向插值P4、P5沿X方向插值P6,1三线性插值结果 2等值面定义,等值面是三次曲面,Marching Cubes算法,Marching Cubes算法,将体素各边与等值面的交点连接成三角形取决于体素每一顶点的状态值分布情况存在着28种不同情况每一体素有8个顶点每一顶点有两种状态值基于体素顶点状态翻转对称性和旋转对称性，将上述256种组合情形减少到15种翻转对称性：如果体素各顶点的状态值0和1互换，所含等值面的拓扑结构（即交点连接关系）不变旋转对称性：体素旋转后，所含等值面的拓扑结构不变根据这15种基本立方体，构造查询表（Look-up Table），长度为256，记录所有情况下的等值面连接方式比较8个顶点与阈值之间的大小关系，得出一个0-255之间的索引值，直接查表得到等值点的连接方式信息，从而形成等值面,Marching Cubes算法,15种等值面连接模式,0 1 2 3 4,5 6 7 8 9,10 11 12 13 14,Marching Cubes算法,15种等值面连接模式：示例,2 9,Marching Cubes算法,法向计算用真实感图形学将等值面显示出来，除了需要每个等值点坐标外，还必须知道每个等值点的法向量在计算立方体某条边上的等值点坐标与法向量时，主要有两种方法：线性插值 中点选择,Marching Cubes算法,法向计算线性插值 其中，P代表等值点坐标，P1P2代表两个端点的坐标，V1，V2代表两个端点的灰度值，isovalue代表阈值，N代表等值点法向量，N1，N2代表两个端点的法向量,Marching Cubes算法,法向计算中点选择 其中，P代表等值点坐标，P1，P2代表两个端点的坐标，N代表等值点法向量，N1，N2代表两个端点的法向量,Marching Cubes算法,法向计算中点选择法的优点：（1）引起的误差低于1/2立方体边长，在解析度越来越高的情况下，所重建出来的图像与线性插值得到的图像没有明显的视觉差异；（2）如果先放大10倍再进行运算，就可以完全采用整数运算，避免浮点运算；（3）可以使得局部表面更平坦，有利于后续的化简过程,Marching Cubes算法,流程：1、将三维离散规则数据场分层读入内存;2、扫描两层数据，逐个构造体素，每个体素中的8个角点取自相邻的两层;3、将体素每个角点的函数值与给定的等值面值c做比较，根据比较结果，构造该体素的状态表;4、根据状态表，得出将与等值面有交点的边界体素;5、通过线性插值方法计算出体素棱边与等值面的交点;6、利用中心差分等方法，求出体素各角点处的法向量，再通过线性插值方法，求出三角面片各顶点处的法向;7、根据各三角面片上各顶点的坐标及法向量绘制等值面图像。,Marching Cubes算法,存在问题二义性改进方法之一：增加连接模式，使其能与相邻体素的状态相匹配以消除“空洞”,256256109MRI表皮重建,（b）12812893CT颅骨重建,（c）12812893CT表皮重建,三角面片：696889顶点：347322,三角面片：187559顶点：94015,三角面片：137799顶点：69331,Marching Cubes算法,Marching Cubes算法,存在问题二义性改进方法之三：将六面体体素分解为四面体单元，并将等值面抽取限制在四面体单元中进行,Marching Cubes算法,存在问题效率低顺序检测每个立方体，属于使用蛮力的方法在抽取一个等值面过程中，超过90%的时间花在了对空立方体的检测上没有一个好的数据缓冲方法，可以对相邻立方体之间所共享的信息重复利用,Marching Cubes算法,存在问题效率低八叉树加速算法本质是利用八叉树的分层结构来实现对空立方体的快速过滤建立一个八叉树，每个节点记录了输入数据中对应范围的最大、最小灰度值在抽取等值面的过程中，快速找到非空的立方体,Marching Cubes算法,存在问题效率低八叉树加速算法,Marching Cubes算法,存在问题效率低八叉树加速算法,Marching Cubes算法,存在问题效率低Surface Tracking算法原始的Marching Cubes算法在寻找等值面时，没有利用邻居立方体元的信息实际上，找到一个非空立方体元后，它的邻居非空立方体元也同时能够得到，利用这些信息可以大大提高等值面的生成速度,Marching Cubes算法,存在问题效率低并行计算Marching Cubes算法对单个立方体元的处理过程是相当独立的，可以很容易地改造为并行算法将原始体数据集划分为几个互不相交的子集，分发给几台联网的计算机，按照一定的通信协议开始并行计算，提高等值面的生成速度,Marching Cubes算法,存在问题输出三角网格数据量巨大一个立方体元最多可以有4个三角面片以一个中等规模数据集为例：数据规模：512Pixel512Pixel58Layer 立方体元：51151157=14883897 三角面片：300万（假设1/10的立方体内含有等值面，每个立方体元含有2个面片）一般有两种解决办法：LOD（Level of detail）方法 网格简化,Marching Cubes算法,存在问题输出三角网格数据量巨大LOD（Level of detail）方法,Marching Cubes算法,存在问题输出三角网格数据量巨大LOD（Level of detail）方法,演示视频,Marching Cubes算法,存在问题输出三角网格数据量巨大网格简化,Marching Cubes算法,存在问题输出三角网格数据量巨大网格简化,Marching Cubes算法,存在问题输出三角网格数据量巨大网格简化,基于分割的Marching Cubes算法,医学图像具有灰度值上的模糊性 在同一组织中密度值会出现大幅度变化同一个物体中密度值也不均匀医学图像具有几何上的模糊性 在一个边界上的大体素中常常同时包含边界和组织两种物质图像中物体的边缘、拐角及区域间的关系都能以精确加以描述,基于分割的Marching Cubes算法,将分割结果作为MC的输入可以根据图像特征选择最恰当的分割方法利用分割结果构造等值面,基于分割的Marching Cubes算法,基于分割的Marching Cubes算法,Marching Tetrahedra算法,立方体的四面体剖分,四面体中的等值面,MT算法的基本原理：首先将立方体元剖分为四面体，然后在其中构造等值面,在MC方法基础上发展起来,Marching Tetrahedra算法,提出该方法的原因：四面体是最简单的多面体，其他类型的多面体都能剖分为四面体将立方体剖分为四面体后，在四面体中构造的等值面的精度显然高于在立方体中构造的等值面企图通过在四面体内部构造等值面来避免MC算法中存在的二义性问题,立方体剖分为四面体的不同方式,Marching Tetrahedra算法,对于一个立方体来说，存在两种不同的四面体剖分方式，不同的剖分方式将导致不同等值面的生成即：等值面的构造依赖于剖分方式,相邻立方体公共面上的剖分一致性,Marching Tetrahedra算法,为了在相邻体元的公共面上不出现裂缝，必须保证在这个面上的剖分一致性即：四面体剖分方式在一系列体元中是交替变换的整个数据场内等值面的构造是与最初一个体元的剖分方式有关的,(a)128128113CT颅骨重建,（b）104185220CT脚骨骼重建,(c)128128113CT表皮重建,三角面片：423998顶点：211905,三角面片：365858顶点：183056,三角面片：331290顶点：165808,Marching Tetrahedra算法,
