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