科学计算可视化-第二讲-规则数据场及.ppt

科学计算可视化 Visualization in Scientific Computing (ViSC) 第二讲 三维规则标量数据场及 基于面片提取的绘制算法 李吉刚 计算机学院 虚拟现实技术国家重点实验室 软件开发环境国家重点实验室,内容回顾,第一讲 绪论 可视化及数据可视化 科学计算可视化 产生背景及概念 技术分类 处理过程 主要应用领域,按照数据场的分布空间 （二维、三维、四维、） 按照连接类型 （规则、不规则、） 按照数据类型 （标量、矢量、张量）,本讲主要内容,三维规则标量数据场及绘制算法分类 典型的基于面片提取的绘制算法,三维规则标量数据场及绘制算法分类,描述：定义在3维空间正交网格上的数据场，其空间结构为： Grid = ( ) | Dx,Dy,Dz0 且为常数； =i*Dx ,i=0,1,2,Maxx; =j*Dy ,j=0,1,2,Maxy; =k*Dz ,k=0,1,2,Maxz; 数据场的标量数据定义在每个网格节点( )上。 在这种方式下，每个节点的坐标值和相邻节点可以便利的推算出来,三维规则标量数据场 1 场的描述,体元(CELL) ：如下式所示的八个点构成了一个数据场中的体元 CELL= (i,j,k) , (i+Dx,j,k) ,(i,j+Dy,k), (i+Dx,j+Dy,k),(i,j,k+Dz) , (i+Dx,j,k+Dz) ,(i,j+Dy,k+Dz), (i+Dx,j+Dy,k+Dz) 定义该体元标号为(i,j,k)。,三维规则标量数据场 2 体元,体素(Voxel) ：正交网格中的网格点。其主要属性为该点在三维空间的坐标值、数据场的场值等信息。,三维规则标量数据场 3 体素,三维规则标量数据场 4 图示,数据常见的获取方法：CT，MRI，计算获取等， 例如：常见的CT图片，每一幅图构成了一层，全部图构成三维规则标量场。实际上，如何获取这类数据、数据如何进行预处理、几何映射等本身也是数据场研究的一些重要内容。,CT是用X线束对人体某部一定厚度的层面进行扫描，由探测器接收透过该层面的X线，转变为可见光后，由光电转换变为电信号，再经模拟/数字转换器（analog/digital converter）转为数字，输入计算机处理。图像形成的处理有如对选定层面分成若干个体积相同的长方体，称之为体素（voxel）。扫描所得信息经计算而获得每个体素的X线衰减系数或吸收系数，再排列成矩阵，即数字矩阵（digital matrix），数字矩阵可存贮于磁盘或光盘中。经数字/模拟转换器（digital/analog converter）把数字矩阵中的每个数字转为由黑到白不等灰度的小方块，即象素（pixel），并按矩阵排列，即构成CT图像。所以，CT图像是重建图像。每个体素的X线吸收系数可以通过不同的数学方法算出。,为了显示整个器官，需要多个连续的层面图像。通过CT设备上图像的重建程序的使用，还可重建冠状面和矢状面的层面图像，可以多角度查看器官和病变的关系。,三维规则标量数据场 5 数据结构,外存组织方式：数据文件 文件头可存储场的大小信息，各个方向单位距离信息 文件内容按照顺序图层的方式组织 内存组织方式：三维数组 Double RegularFieldMaxXMaxY MaxZ 其中，数组标号为各个场顶点的空间位置索引值，数组内容为场数据值。 例如：假设整个数据场初始点坐标为（x,y,z），则数据标号为（i，j，k）的顶点坐标为（x+i*Dx, y+i*Dy, z+i*Dz ） 按照体元定义中取出的8个顶点就构成了体元。 根据对数据结构的掌握，可采用指针、指针数组、指针的指针等方式描述三维数组。,常见的绘制方法,常见的绘制方法,基于等值面面片提取的方法 在物体空间的每个体元中提取等值面片，随后按照计算机图形学中绘制面片物体的方法进行绘制。其最大的特点是可以充分利用现有计算机对三维图形的支持。（OpenGL、显卡加速等） 体绘制方法 直接基于体数据进行绘制，其最大的特点是可以体现数据场中的整体数据分布，而且绘制效率高。 从图像空间出发的方法（像序） 从物体空间出发的方法（物序） PS:轮廓线提取及绘制算法Michael Burns ACM/SIGGRAPH2005,常见的绘制方法,小结,Questions? Exercise 2.1： 将三维空间的单位球构造为体数据，并保存在文件中。,关于作业Exercise 2.1：,规则网格,球的生成方式和建模方法？ 体数据网格大小的设置？ 体数据表示方法的精确度？,关于作业Exercise 2.1：,三维规则标量数据场基于等值面片提取的绘制算法,主要内容,预备知识 Cuberille算法 Marching Cube算法 基本算法 存在的问题和改进工作 Marching Tetrahedral算法,等值面概念,等值面：空间中的一个曲面，在该曲面上的函数值F(x,y,z)恒等于某个给定值U，即 F(x,y,z) = U。 基于等值面方法的特点：不能反映整个原始数据场的全貌和细节，但可以对感兴趣的等值面产生清晰的图像。,预备知识1 计算机图形学中物体的表示方法,线框表示：结构简单，用顶点和邻边表示形体 曲面表示：在上述基础上，增加面，从而可以满足对面的操作 参数曲面 三角形表示 实体表示 点模型表示 基本几何元素包括：点、边、面、体。 表示方法的关键在于提供一致的方法描述物体及其结构，同时便于进行各种后续的操作，如对物体改变、绘制等,预备知识2 计算机图形学中基于三角形面片绘制需要的主要参数,三个顶点的空间坐标 用途：空间变换，投影 三个顶点的法向量（或面片的整个法向量） 用途：光照计算 三个顶点的纹理坐标或颜色 用途：显示颜色信息,基于面片进行绘制，关键是要求得各个三角形、面片的法向量、三角形间的连接关系等,预备知识2 计算机图形学中基于三角形面片绘制需要的主要参数,预备知识3 二维规则网格中的网格扫描法提取等值线问题,问题：已知四个顶点的值分别为F00，F01，F10，F11，要在该单元内生成值为Ft的等值线,1.计算该单元各边与等值线的交点 1) 将网格点分为“in”“out”两个状态 IF Fij = Ft THEN （xi，yj）标记为“in”，记为“-” ELSE （xi，yj）标记为“out” ，记为“+” 2) 计算交点（数据场沿边作线形变化） IF 四个顶点均为“+” or “-” THEN 无交点 ELSE 对两个顶点为“+” 和“-”的单元边，用下面的线形插值公式： 设(x0,y0)为“-”，(x0,y1)为“+”，则交点为： Xt = X0; Yt=（y0*(F01-Ft) +y1*（Ft-F00）/（F01-F00）;,预备知识3 二维规则网格中的网格扫描法提取等值线 算法,2.连接交点，生成等值线线段 1)四个顶点有一个+或-，可求得两个交点，有一条等值线：,预备知识3 二维规则网格中的网格扫描法提取等值线 算法,2.连接交点，生成等值线线段(续) 2)有两个+或两个-，且平行分布，可求得两个交点，有一条等值线段,预备知识3 二维规则网格中的网格扫描法提取等值线 算法,2.连接交点，生成等值线线段(续) 3)有两个+或两个-，但交叉分布，可求得四个交点，有两条等值线段,预备知识3 二维规则网格中的网格扫描法提取等值线 算法,3.解决二义性问题 二义性是指2中情况3)出现时如何连接的问题 方法：采用双曲线渐近线交点函数值判断的方法求解。 由于在单元中采用线形插值(双线性插值）， 为双曲抛物面，等值线段为双曲线。,预备知识3 二维规则网格中的网格扫描法提取等值线 算法,通过计算两条渐近线交点处的值，如为“+”采用第一种，否则采用第二种。为简化，有时采用单元对角线交点代替渐近线交点计算。,如何计算渐近线交点（1）,二次曲线,二次曲线的中心,渐近线交点,如何计算渐近线交点（2）,单元剖分法 用对角线将矩形单元分成4个三角形,预备知识3 二维规则网格中的网格提取等值线的其他方法,网格无关（grid free）法,网格序列法是一种按网格单元排列的次序逐个单元处理的方法。实际上应用中，某个值的等值线所穿过的单元数往往只占整个网格单元数的较小部分（10%以下）。因此效率不高，特别是在大型密集网格分布的情况下。由此提出网格无关（grid free）法。 网格无关步进法、适应法、递归法 -给定起始点或先求出起始点，利用改点附近的局部几何性质计算等值线的下一点，如此继续，直至区域边界或回到起始点。,步进法,适应法,算