维空间规则数据场的等值面构造.ppt

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