（计算机应用技术专业论文）基于体素的快速表面重构.pdf

摘要 摘要 科学计算可视化，是计算机图形学的一个重要研究方向，是图形学的新领域。其中面绘 制和体绘制是实现三维曲面重构两种重要手段，面绘制算法主要是按照给定的闽值从体数据 中提取等值面，然后利用曲面绘制方法绘制此等值面，能体现物体的表面信息，如果要体现 内部大量有用的信息，就要使用体绘制算法，但其绘制速度较慢。本文研究面绘制中的移动 立方体算法。 移动立方体算法是面绘制中一个经典算法，但原始的移动立方体算法中存在着二义性、 生成的三角面片多、执行速度慢等不足之处，国内外对这些方面已有了很多深入的研究。 结合已有的研究，对这三个方面进一步研究，本文提出的基于体素生长的移动体素算法 可以对原算法进行改进，借用体素的生长只处理与等值面相交的那些立方体，并将这些体素 以栈的数据结构形式进行保存，加快绘制速度；在三角面片形成处理中，使用移动体素的方 法生成三角面片，消除了二义性。 八叉树是一种有效的表示三维物体的方法，本文在八叉树生成的基础上，提出的基于空 间分割的表面重构算法，将绘制空间分别按x 轴、y 轴和z 轴进行分割，生成的树的节点个 数小于等于八个，与八叉树方法相比，减少了所生成叶结点数量，再通过移动立方体算法生 成三角面片，三角面片通过平滑处理，提高图形显示质量。这种由八叉树改进的空间分割算 法，减少生成的三角面片数量，同时通过三次插值，将所得到的近似曲面进行平滑处理。 关键词：移动立方体、二义性、移动体素、体素生长、空间分割、平滑曲面 江南大学硕士学位论文 a b s t r a o t v i s u a l i z a t i o ni sai m p o r t a n ta s p e c ti nc o m p u t e rg r a p h i c s s u r f a c er e n d e r i n ga n d v o l u m er e n d e r i n ga r et w oi m p o r t a n tw a y st os u r f a c er e c o n s t r u c t i o n s u r f a c er e n d e r i n g a l g o r i t h me x t r a c ti s o s u r f a c ef r o mv o l u m ed a t a v o l u m er e n d e r i n ga l g o r i t h mc a ns h o w m a n yi m p o r t a n ti n f o r m a t i o ni n s i d e ，b u ti t sr e n d e r i n gs p e e di ss l o w m a r c h i n gc u b e s a l g o r i t h mi sr e s e a r c h e di nt h i sa r t i c l e 。 m a r c h i n gc u b e si sas u r f a c er e n d e r i n ga l g o r i t h mf o re x t r a c t i n gi s o s u r f a c e sf r o m t h r e e d i m e n s i o n a ld a t af i e l d s b u ti no r i g i n a la l g o r i t h m , t h e r ea r em a n ys h o r t a g e s s u c ha sa m b i g u o u s ，t o om a n yt r i a n g l e s ，e x e c u t i n gt o os l o w l y ，e t c t h i sp a p e rg i v e sa ni s o s u r f a c e se x t r a c t i o na l g o r i t l nw eu s ev o x e l sg r o w i n gt o h a n d l et h ec u b e st h a ti n t e r s e c tt h ei s o s u r f a c e s i ts p e e d su pt h eh a n d l i n gt i m e i n t h ep h a s eo ft h et r i a n g l e sc o m b i n a t i o n ，w eu s em a r c h i n gv o x e l sa l g o r i t h m i t e l i m i n a t e st h ea m b i g u o u s o c t r e ei sa ne f f e c t i v ew a yt od e s c r i b e3 do b j e c t s i nt h i sp a p e r 。as u r f a c e r e c o n s t r u c t i o na l g o r i t h mu s i n gs p a c es e g m e n t a t i o ni sp r e s e n t e d t h i sa l g o r i t h mi s b a s e do no c t r e e t h es p a c ei sd i v i d e da l o n gx ，y ，a n dzr e s p e c t i v e l y t h en o d e so f t h et r e ea r el e s st h a ne i g h t t h en u m b e ro fm e s h e si sl e s st h a no c t r e e t h e nb ym e a n s o fm a r c h i n gc u b ea l g o r i t h m , t r i a n g l e sa r ep r o d u c e d a yt r i l i n e a rm e t h o d , t h e t r i a n g l e sa r ed e a l tw i t hs m o o t h l y t h es u r f a c eo ft h e0 b j e c ti sr e c o n s t r u c t e du s i n g c 卧a n do p e n g l i nt h i sw a y t h eq u a l i t yo ft h ea l g o r i t h mi sg o o d k 唧岫：m a r c h i n gc u b e s ，a m b i g u o u s ，m a r c h i n gv o x e l s 。v o x e i sg r o w i n g ，s p a c e s e g m e n t a t i o n ，s m o o t hs u r f a c e 一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所傲的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：起：哇日期：丸叼年3 月7 日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：垃 第一章绪论 1 1 科学计算可视化简介 第一章绪论 近年来，随着计算机图形学( c o m p 咖g r a p h i c s ) 技术的发展，科学可视化( s c i e n t i f i c v i s u a l i z a t i o n ) 的应用也随之快速地兴起，与传统使用一堆数字的表示方式相比较，科学可视化利用图形、颜色及影像来 呈现三维实体的内容，使人更加印象深刻，并且一目了然。 1 1 1 科学计算可视化的概念 科学计算机可视化i l h 日( 简称可视化) ，是计算机图形学的一个重要研究方向，是图形学的新领域。 “v i s u a l i z a t i o n ”一词，原意是视觉的、形象的，中文译为“可视化”。事实上，将任何抽象的事务、过程 变成图形图像的表示都可以称为可视化。与计算机有关的可视化如界面( w i n d o w s ) ，可视化编程( s u a l c + + ) 等。但作为学科术语，“可视化”一词正式出现于1 9 8 7 年2 月美国国家科学基金会( n a i l o n a ls c i e n c e f o u n d a t i o n ，简称n s f ) 召开的一个专题研讨会上。研讨会后发表的正式报告给出了科学计算可视化的定 义、覆盖的领域以及近期和长期研究的方向。这标志着“科学计算可视化”作为一个学科在国际范围内已 经成熟。 科学计算可视化的基本含义是运用计算机图形学或者一般图形学的原理和方法，将科学与工程计算等 产生的大规模数据转换成图形、图像，以直观的形式表示出来。它涉及计算机图形学、图像处理、计算机 视觉、计算机辅助设计及图形用户界面等多个领域，已成为当前计算机图形学研究的重要方向。 1 1 2 科学计算可视化的意义 在二维的表示法中，我们一般通过条形图、折线图或饼图等来了解数据的分布状况，而对于三维资料 的表示，我们可以借助于三维几何模型的操作( 如旋转、平移、缩放) ，加上颜色的分布，使得资料里不 易观察的信息能够更加完整地表示。如图1 1 所示，此图 形为三次曲面，若我们只有曲面方程，那么我们很难想象 曲面在空间的分布情况，但如果我们通过计算机绘图，则 让我们对此曲面一目了然。 近年来，随着计算机应用的普及和科学技术的迅速发 展，来自超级计算机、卫星遥感、c t 、天气预报以及地震 勘测等领域的数据量越来越大；另一方面，由于计算机技 术的高速发展，使得计算成本不断下降，计算精度和速度 不断提高。这使得对复杂问题求解的数值模拟成为一种更 图1 1曲面z ：x 3 3 x y 2 直接、更有效的方法。因此，科学计算可视化技术已经成 为研究中的必不可少的手段，它是科学工作者洞察数据内 含信息，确定内在关系与规律的有效方法，使科学家用直观形象的方式揭示理解抽象科学数据中包含的客 观规律，从而摆脱直接面对大量无法理解的抽象数据的被动局面。 实现科学计算可视化技术的意义重大，具体来讲有以下几点： ( 1 ) 大大加快数据的处理速度，使目前每日每时都在产生的庞大数据得到有效的利用。 ( 2 ) 实现人与人和人与机之间的图像通讯，而不是目前的文字或数字通讯，从而使人们观察到传统 方法难以观察到的现象和规律。 ( 3 ) 使科学家不仅被动地得到计算结果，而且知道在计算过程中发生了什么现象，并可改变参数， 观察其影响，对计算过程实现引导和控制。 1 江南大学硕士学位论文 ( 4 ) 可提供在计算机辅助下的可视化技术手段，从而为在网络分布环境下的计算机辅助协同设计打 下了基础。 总之，科学计算可视化技术的发展将使科学研究工具和环境进一步现代化，从而使科学研究的面貌发 生根本性的变化，具有极为重要的意义。 1 1 3 科学计算可视化的研究内容 可视化的研究主要分为两大部分，可视化工具的研究和可视化应用的研究。科学计算可视化研究的重 点是有关可视化参考模型的内涵，即可视化过程的组成内容，其中包括： ( 1 ) 数据预处理：可视化的数据来源十分丰富，数据格式也是多种多样的，这一步将各种各样的数 据转换为可视化工具可以处理的标准格式。 ( 2 ) 映射：映射就是运用各种各样的可视化方法对数据进行处理，提取出数据中包含的各种科学规 律、现象等，将这些抽象的、甚至是不可见的规律和现象用一些可见的物体点、线、面等表示出来。 ( 3 ) 绘制：将映射的点、线、面等用各种方法绘制到屏幕上，在绘制中有些物体可能是透明的，有 些物体可能被其他物体遮挡。 ( 4 ) 显示：显示模块除了完成可视信息的显示，还要接受用户的反馈输入信息，其研究的重点是三 维可视化人机交互技术。 1 1 4 科学技术可视化的应用 从可视化技术的诞生之日起，便受到了各行各业的欢迎。现在，可视化的应用范围已由最初的科研领 域走到了生产领域，到今天它几乎涉及到了所有能应用计算机的部门。 ( 1 ) 医学：在医学上由核磁共振、c t 扫描等设备产生的人体器官密度场，对于不同的组织，表现出 不同的密度值。通过在多个方向多个剖面来表现病变区域，或者重建为具有不同细节程度的三维真实图像， 使医生对病灶部位的大小、位置，不仅有定性的认识，而且有定量的认识，尤其是对大脑等复杂区域，数 据场可视化所带来的效果尤其明显。借助虚拟现实的手段，医生要以对病变的部位进行确诊，制定出有效 的手术方案，并在手术之前模拟手术。在临床上也可应用在放射诊断、制定放射治疗计划等。 ( 2 ) 生物、分子学：在对蛋白质和d n a 等复杂结构进行研究时，可以利用电镜、光镜等辅助设备对 其剖片进行分析、采样获得剖片信息，利用这些剖片构成的体数据可以对其原形态进行定性和定量分析， 因此可视化是研究分子结构必不可少的工具。 ( 3 ) 航天工业：飞行器高速穿过大气层时周围气流的运动情况和飞行器表面的物理特性的变化，在 现有的流场可视化技术下，可以非常直观地展现出来。尤其是对飞行器的不稳定现象、超音速流的研究， 这是计算流体力学里的新课题，借助可视化技术，许多意想不到的困难都可以迎刃而解。 ( 4 ) 工业无损探伤：在工业无损探伤中，可以用超声波探测，在不破坏部件的情况下，不仅可以清 楚地认识内部结构，而且对产生变异的区域也可以准确地探出。显然，能够及时检查出有可能发生断裂等 具有较大破坏性的隐患是有极大现实意义的。 ( 5 ) 人类学与考古学：在考古过程中找到古人类化石的若干碎片，由此重构出古人类的骨架结构。 传统的方法是按照物理模型，用粘土来拼凑而成。现在，利用基于几何建模的可视化系统，人们可以从化 石碎片的数字化数据完整地恢复三维人体结构，因而向研究人员提供了既可以作基于计算机几何模型的定 量研究，又可以实施物理上可塑的化石重现过程。 ( 6 ) 地质勘探：利用模拟人工地震的方法，可以获得地质岩层信息。通过数据特征的抽取和匹配， 可以确定地下的矿藏资源。用可视化方法对模拟地震数据的解释，可以大大地提高地质勘探的效率和安全 性。 一2 - 第一章绪论 1 2 科学计算可视化现实技术 1 2 1 二维数据场的可视化技术 二维数据场是科学计算可视化处理的最简单的一类数据场，二维数据场是在某一平面上的一些离散数 据，可看成定义在某一平面上的一维标量函数f 2 f ( x ，y ) 。二维数据场可视化的方法主要有颜色映射法、 等值线法、立体图法和层次分割法等。 1 2 1 1 颜色映射法 可视化系统中，常用颜色表示数据场中数据值的大小，即在数据与颜色之间建立一个映射关系，把不 同的数据映射为不同的颜色。在绘制图形时，根据场中的数据确定点或图元的颜色，从而以颜色来反映数 据场中的数据及其变化。可视化系统处理的数据一般为离散网格数据，网格之间的数据采用插值的方法计 算。可视化系统的绘制模块一般不直接插值计算网格问的数据，而是利用计算机硬件提供的功能直接对颜 色的r g b 基色值进行插值计算，这样有助于提高绘制速度。但也由此引起了误差。由于大部分颜色映射 模型都采用非线性的映射，对颜色的线性插值实际上是对数据的非线性插值，从而造成误差，导致完全错 误的颜色。实践中可采用颜色表方式来解决这一问题。由于颜色表索引与数据间是完全线性的映射关系， 因而不会引起插值误差。 1 2 1 2 等值线法 所谓等值线是由所有这样的点( x ，只) 定义，其中f ( x l ，只) = 只( f 为一给定值) ，将这些点按一定 顺序连接组成了函数，( 暑力的值为只的等值线。常见的等值线如等高线、等温线等，是以一定的高度、 温度作为度量的。等值线的抽取算法可分为两类：网格序列法和网格无关法。网格序列法的基本思想是按 网格单元的排列顺序，逐个处理每一个单元，寻找每一单元内相应的等值线段。处理完所有单元后，自然 就生成了该网格中的等值线分布。网格无关法则通过给定等值线的起始点，利用起始点附近的局部几何性 质，计算等值线的下一点；然后利用计算出的新点，重复下一点，直到达到边界区域或回到原始起始点。 网格序列法按网格排列顺序逐个处理单元，这种遍历的方法效率不同。网格无关法则是针对这一情况提出 的一种高效的算法。 1 2 1 3 立体图法 立体图法就是以一个立体图形来显示平面数据场，因为将平砸数据场的数据转换为高度，从整体上可 以看成三维图形。使用立体图方法显示，可以用多种方法拟合数据场，如：三角面片、曲面逼近等，曲面 逼近会产生更好的效果。但由于数据场的密度较大，完全可以使用三角面片模型来显示整个数据场。 1 2 1 4 层次分割法 层次划分法是立体图法的扩展，首先用户定义层范围及各层的颜色。在绘制每个三角面片时，若三角 面片的最大值、最小值都在一个层内，则按该层的颜色绘制；否则将三角面片进一步剖分为m 个多边形， 每个多边形处于一层，并以各层颜色绘制。这样各层之间就有一个明显的层次分割线。在实际应用中可用 于显示等值线、等高线等。 3 一 江南大学硕士学位论文 1 2 2 兰维数据场的可视化技术 三维空间数据场与二维数据场不同，它是对三维空间中的采样，表示了一个三维空间内部的详细信息， 这类数据场最典型的医学c t 采样数据，每个c t 的照片实际上是一个二维数据场，照片的灰度表示了某 一片物体的密度。将这些照片按一定的顺序排列起来，就组成了一个三维数据场。此外用大规模计算机 计算的航天飞机周围的密度分布也是一个三维数据场的例子。 1 2 2 1 抽取表面信息的可视化技术 抽取表面信息的可视化技术主是按照给定的阈值从体数据中提取等值面，然后利用传统的曲面绘制方 法绘制此等值面，主要有二维等值线拼接法、移动立方体法、几何变形曲面法、c u b c r i l l e 等1 3 1 。 ( 1 ) 二维等值线拼接1 4 卜i o j ( c o n t o u rc o n n e c t i n g ) 算法 由于体数据为三维数据，我们可以沿某一方向将体数据分解成一些二维数的集合，在此二维数据所在 面上，利用预先给定的阈值构造出平面上的等值线，然后根据这样一系列平面上的等值线图，再利用一些 几何基本元拼接出等值面。这种轮廓线表示方法简单且数据量小，但是不很直观。除了以轮廓线表示物体 外，还可以由轮廓重建物体的表面来表示。最早的方法是基于多边形技术，主要采用平面轮廓的三角形算 法，用三角片拟合这组表面轮廓的曲面。b u s s o n n a t 提出了另外一种基于表面轮廓的d e l a u n a y 方法，解决 了系列表面轮廓的三维连通性问题。用三角形或多边形的小平面( 或曲面) 在相邻的边界轮廓线间填充开 成物体的表面，所提出的只是分片光滑的表面，l i n 采用从轮廓从发的b 样条插值重建算法，得到了整体 光滑的表面。 ( 2 ) 移动立方体法川( m a r c h i n gc u b e s ) 构造物体的表面也可以采用等值面的方法。等值面可以看成是等值线的三维扩展，最典型的就是 m a r c h i n gc u b e s 方法。二维数据场的基本单元是矩形，在三维空问的基本单元是一个小立方体。如果我们 找出每个小立方体中的等值面，这些等值面也就构成了整个物体的表面。移动立方体算法的考虑的对象是 由8 个顶点构成的立方体元。将体元顶点处的标量值按阈值二元化。当顶点值大于或等于阈值时置l ，否 则置0 。若立方体元某条边的两个顶点发生0 与1 的交换时，则此边与二值图象所形成的等值面有一交点， 由体元各边的交点可构成体元可能拥有的等值面部分，将每个体元内的结果综合在一起，就得到所求的等 值面。m c 算法的提出提供了一种精确地定义体素及其内等值面的生成方法，随后又有很多人在它的基础 上继续研究i s l - 1 17 1 。m c 如今已经成为最流行的三维重建算法之一，在许多商业软件中也有应用。 ( 3 ) 几何变形曲面算法 在网格节点外设置耗散值函数，通过逐步减少耗散值的方法来调节初始时放入体数据中的“种子”曲 面的形状，逐步逼近所要求的等值面。 ( 4 ) c u b e d l l e l l 8 i 算法 c u b e r i l l e ( 立方体法) 是最早的体素级重建方法，由h e r m a n 和l i u 提出的，主要适用于医学图像，无 损探伤等三维图像的等值面抽取。其后被他人多次改进。该方法执行过程是：先进行边界体素的确定，对 于某个设定的数值c 。对每个体素遍历一遍，比较每个体素八个角点值与c 的大小，并以此为依据判定它 是不是边界体素，然后对所有边界体素的六个由多边形表示的面进行显示。此方法显示物体微小细节时效 果不佳，出现严重的走样，显示图像给人一种“块状”感觉，尤其在物体边界处锯齿形走样特别醒目，而 且显示粗糙，不能很好的显示物体的细节。但实现简单，表面抽取及绘制过程快速、简单。 ( 5 ) m a r c h i n g t e t r a h e d r a l 方法【1 9 j m a r c h i n gt e t r a h e d r a l 算法简称m t 算法，它是在m c 算法的基础上发展起来的，该算法首先将立方体 体素剖分成四面体，然后在其中构造等值面，进行四面体剖分后，等值面四面体中的剖分模式减少，算法 实现简单。其次，构造的等值面较m c 算法构造的等值面精度高。而最直接的原因是企图通过在四面体内 构造等值面来避免m c 算法中存在的二义性问题。常见的立方体剖分成四面体的方法有5 个、6 个和2 4 个四面体剖分方法。一般最常用的是5 个四面体剖分法。 ( 6 ) d i v i d i n g c u b e s 方法【2 0 1 4 第一章绪论 在密集数据场处理时，特别是医学图像上，包含等值的单元数很多，每一三角片很小，使每一体素的 投影接近于象索大小，因此往往使显示精度而不是体素大小限制了图像精度。一种更有效的方法是直接显 示图像上显示象素点，这就是d i v i d i n gc u b e s 方法的基本思想。它逐个扫描每个体素，当体素的八个顶点 越过等值面时，将该体素投影到显示图像上。如果投影面积大于一个象素的大小，则该体素被分割成更小 的子体素，使子体素在显示图像上的投影为一象素的大小，每一子体素在图像空间被绘制成一表面点。每 一表面点由对应子体素的值，对象空间中的位置和剃度三部分表示，可使用传统的图形学消影技术，将表 面点绘制到图像空间中。采用绘制表面点而不是绘制体素内等值面片，从而节省了大量的计算时间。 1 2 2 2 直接体绘制技术 在自然环境和计算模型中，许多对象和现象只能用三维数据场表示，对象体不是用几何曲面和曲线表 示的三维实体，而是以体素为基本造型单元。例如人体里面就十分复杂，如果仅仅用几何表示各器官的表 面，不可能完整显示人体的内部信 息。体绘制( v o l u m er e n d e r i n g ) 1 2 1 f 1 2 5 l 的目的就在于提供一种基于体素 的绘制技术，它有别于传统的基于 面的绘制技术，能显示出对象体的 丰富的内部细节。体绘制直接研究 光线穿过三维体数据场时的变化， 得到最终的绘制结果，所以体绘制 也被称为直接体绘制。体绘制与传 统面绘制的区别见图1 2 。从结果 图象质量上讲，体绘制优于面绘 制，但从交互性能和算法效率上 讲，至少在目前的硬件平台上，面 绘制优于体绘制，这是因为面绘制 是采用的传统的图形学绘制算法， 现有的交互算法和图形硬件和图 形加速技术能充分发挥作用。 们几何旋曼工且软悼 图1 2 两种绘制方法的比较 体绘制方法提供二维结果图象的生成方法。根据不同的绘制次序，体绘制方法主要分为两类：以图象 空间为序的体绘制方法和以物体空间为序的体绘制方法。 以图象空间为序的体绘制方法是从屏幕上每一象素点出发，根据视点方向，发射出一条射线，这条射 线穿过三维数据场，沿射线进行等距采样，求出采样点处物体的不透明度和颜色值。可以按由前到后或由 后到前的两种顺序，将一条光线上的采样点的颜色和不透明度进行合成，从而计算出屏幕上该象素点的颜 色值。这种方法是从反方向模拟光线穿过物体的过程。 以物体空间为序的体绘制方法首先根据每个数据点的函数值计算该点的颜色及不透明度，然后根据给 定的视平面和观察方向，将每个数据点投影到图像平面上，并按数据点在空间中的先后遮挡顺序，合成计 算不透明度和颜色，最后得到图像。 体绘制由于直接研究光线通过体数据场与体素的相互关系，无需构造中间面，体索的许多细节信息得 以保留。结果的保真性大为提高。从结果图像的质量上讲，体绘制要优于面绘制，但从交互性能和算法效率 上讲，至少在目前的硬件平台上，面绘制还是要优于体绘制的。下面讨论三种体绘制方法： ( 1 ) 投影法( p r o i e c t i o n ) “” 首先根据视点位置确定每一体素的可见性优先级，然后按优先级由低到高或由高到低的次序将所有体 素投影到二维像平面上，在投影过程中，利用光学中的透明公式计算当前颜色与阻光度，依投影顺序( 即体 素可见性优先级) 的不同，投影法分为从前至后( f r o n t - t o - b a c k ) 算法与从后至前( b a c k - t o - f r o n t ) 算法。一般 一5 - 江南大学硕士学位论文 说来，前一种算法运算速度快，但除需个颜色缓存区外，还需要一个阻光度缓存区；后一种算法仅需一 个颜色缓存区，并在执行过程中产生不同层面的图像，有助医生更好地理解医学图像。 ( 2 ) 光线跟踪法0 l a y - t r a c i n g ) ) “1 该方法是在体数据进行分类后，从象空间的每一体素出发，根据设定的方法反射一条光线。在其穿过 各个切片组成的体域的过程中，等间距地进行二次采样，由每个二次采样点的8 个领域体素用线性插值方 法得到采样点的颜色和阻光度值。依据光照模型求出各采样点的光亮度值。从而得到三维数据图像。直接 体视法所面l 临的问题是运行速度慢，利用空间相关性可提高算法的效率。 ( 3 ) 最大密度投影( m a x i m u mi n t e n s i t yp r o j e c t i o n , m i p ，“w 最大密度投影是一种广泛使用的体绘制技术，传统的m i p 算法使用光线跟踪法( r a y - t r a c i n g ) 跟踪图像 平面上每个象素发出的投影光线与体数据相交的每个体素，逐个比较，找出每条光线上的最大值，将它作为 投影平面上对应点的象素值。临床上在病人血管中注入造影剂后进行c t 或磁共振成像，然后用m i p 算法 显示血管的位置、形状和拓扑结构，也称为血管造影( a n g i o g r a p h y ) 。几乎所有的商用医学图像系统都包 含m i p 绘制模块。由于m i p 的结果缺少深度信息，观察时要对体数据旋转，这意味着每次要计算5 - 2 0 帧 图像。显然，若不优化。血管造影只能在昂贵的大型工作站上实现 1 3 本文研究课题 面绘制是进行三维表面重构的一个重要方法，其中移动立方体算法又是面绘制是一个经典算法，它主 要针对三维规则网格数据提出的，常应用于计算机x 光断层摄影( c t ) 。磁共振( m r ) 、单光子发射计算 机断层摄影( s p e c t ) 、地震测定、电子显微镜、大气压测定等。因此，对于此算法的研究以及如何改进 此算法是计算机图形学中一个非常重要的方向。本文在对移动立方体算法已有的现实技术进行研究，并逐 步延伸，努力做到改进原有算法。 1 3 1 论文范围与课题意义 本文先介绍了表面重构中两种经典算法，即移动立方体算法和光线投射算法，具体对移动立方体算法 进行了较为深入地研究，在该算法中存在的生成的三角面片数量多，存在二义性从而使产生的重构表面产 生空洞，执行效率低下等问题，在阅读和学习了大量有关的参考文献的基础上，提出了基于体素生长的移 动体素技术和空间分割技术，改进已有的算法 从学术意义和应用范围来看，移动立方体算法有着非常重要的应用场合，从医学应用，到地质勘探， 再到气象测定，移动立方体算法都发挥着重要的作用。因此我们就更加有理由相信研究本课题是有必要的。 1 3 2 本文主要工作 本文主要研究工作是建立在前人在对移动立方体实现技术探讨基础上的，本人所做的主要工作如下： ( 1 ) 分析了当前表面重构的主要方法与特征。介绍了可以通过面绘制与体绘制方法实现三维表面重 构，并对当前经典的面绘制方法即移动立方体算法和经典的体绘制算法即光线投射算法进行了深入地研 究。 ( 2 ) 针对移动立方体算法中存在的效率低下问题，从减少产生的三角面片数目和缩短体素遍历时问 两个方面，解决这个问题，并通过平滑处理，产生符合要求的曲面。 ( 3 ) 针对移动立方体算法中存在二义性的问题，通过移动体素算法解决这个问题，并通过实验进行 评估，证明本文研究的有效性与实用性，达到了预期的研究目的。 1 3 3 内容组织 各章节的内容分布如下： - 6 第一章绪论 第一章是绪论，主要介绍了课题的相关背景。从科学计算可视化的概念入手，介绍了科学计算可视化 的研究内容与研究意义，实现科学计算可视化的现实技术，列举了国内外有关科学计算可视化有代表性的 研究成果，以及本文所要探讨的主要问题，即基于体素快速表面重构问题的研究。 第二章主要探讨等值面生成的现实技术，分析了当前三维曲面生成技术的主流技术，从本文最终的研 究目的出发，结合实践，介绍了体数据、移动立方体算法、光线投射算法，以及算法的不足之处。 第三章开始探讨基于体素的移动体素算法，从缩短遍历体素时间和消除二义性两个方面进行阐述。本 章主要研究了移动立方体算法中对空间体数据进行遍历，需要消耗大量的运算时间，从而执行效率不高， 通过研究等值面的空间连续性，提出了基于体素生长的方法，改进了原算法中对所有体素进行遍历的缺点。 同时介绍了移动体素算法，因为等值面的生成有空间顺序性，消除了原算法中的二义性。 第四章结合原始移动立方体算法中生成的三角面片数量太多，绘制速度慢的问题出发，从减少生成的 三角面片数目和产生光滑曲面的方面进行阐述。利用八叉树改进的空间分割方法，使得所生成的三角面片 数目大量地减少，同时由于三角面片数的减少导致有些三角面片的空间显示较大，使图形变粗糙，再利用 三次插值法，对所生成的三角面片进行平滑处理，最终生成较为光滑的曲面。 第五章是结论，同时介绍了今后需要进一步完善的工作。 - 江南大学硕士学位论文 第二章等值面生成技术 科学计算可视化技术处理的对象是科学数据，这些科学数据的来源是多种多样的，数据中包含的科学 规律和现象有很多。这些科学数据都是离散的采样数据，它们有很多属性，主要有：来源、维数、定义域 的维数、组织形式、时间特性及数据量等等。其中数据的时间特性表示数据是否与时间相关，是否表示随 时间变化的物理现象：数据的维数表示标量数据、向量数据及高维的张量数据等；数据定义域的维数分为 一维、二维、三维数据等；数据的组织形式分为有网格数据和无网格散乱数据，有网格数据的组织形式也 不一样，图2 1 给出了一些二维网格的组织形式，这些二维网格的处理由易到难。维数( d i m e n s i o n ) 是一 个数学概念。可以认为是对空间的几何的一种延伸度量。传统经典的几何学对空间维数的定义都是整数 粗略地说，如果一个物体的运动轨迹可以用一个坐标参数描述，它的轨迹就是一维的。例如，火车的运动， 给定了起始点，再给定它到起始点的距离，就可以唯一确定它在轨道上的位置。不难理解，一个蚂蚁在地 球仪上运动时，须同时给定经度和纬度才能唯一确定它的位置。这时它的运动轨迹就是二维的。一般认为， 我们生活在三维空间，是说一般需要三个独立参数才能确定我们的位置。对应于数学中的元素，点是零维 的，线( 包括曲线) 是一维的，曲面是二维的，体是三维的等等。( 关于分数维数的几何，叫做分形几何。) i i i i i l圆圆 ( a ) c a r t e s i a n 0 0 ) l l e l 蛆缸 ( c ) r e c t i l i n e a r s t 眦恤蜘 硒圆 嘶恻( g ) t 州h y t n d 图2 - l 数据场网格分类 三维等值面的抽取为非直接式的体数据成像方法，其主要是对三维实体资料数据做运算而产生一连串 的多边形，并组成多边形网格( p o l y g o nm e s h e s ) ，而且此网格非常近似于我们所希望得到的等值面，然后将 这一连串的多边形显示在屏幕上。 我们以图2 - 2 来说明等值面的抽取过程及定义，图( a ) 为实体对象的三维数据集合，集合中的每一个单 位为立体像素( v o x e l s ) ，是组成此三维数据集合的基本单位。现在，我们想从此资料集合中抽取我们想要 ，、一， 了解的等值面( 如图b 所示) ，首先，我们给定一个等值( i s o - v a l u e ) c ，通过p j ，l f ，一。等式将 数据集合中有与等值面相交的单元格( c e l l s ) 找出来，再由单元格中产生出最接近等值面的多边形( 如图c 所示) 。从而完成整个等值面的抽取过程。 - 8 第二章等值面生成技术 ，伉y ，z j = c 固固一 2 1 体数据 ( a )( b )( c ) 图2 - 2 等值面的抽取 ( a ) 三维体数据；( b ) 等值面；( c ) 利用多边形网格来近似于等值面 实体数据是由许多连续的二维影像重叠而成的三维立体资料，如图2 - 3 所示，例如使用计算机断层扫 描技术将人类的头颅进行分层扫描，可得到多张连续的二维灰阶影像( 图b 、图c ) ，再将这些连续的影像重 叠形成三维的实体数据( 图d ) ，又称为数据集。其中要特别注意的是，这些灰阶影像中像素值( p i x e lv a l u e ) 的高低与真实对象的密度值相关。举例来说，人类头颅中骨胳的密度大于软骨组织的密度，而软骨组织的 密度又大于皮肤的密度，因此在灰阶影像中骨骼所在位置的像素值高于软骨组织所在位置的像素值，相同 地，软骨组织所在位置的像素值高于皮肤所在位置的像素值，如图a 所示，深灰色的部份为骨胳，其密度 较高，像素值较高，浅灰色的部份为内部组织，其密度较低，因此像素值也较低) 。 ( a )( b )( c )( d ) 图2 - 3 三维实体数据 2 1 1 规则体数据在三维空问中的定义 规则体数据( r e g u l a rv o l u m ed a t a ) 是立体的三维数据集 合，立体像素( v o x e l s ) 为其基本单位，它等距地对实体对象 做取样，对x 轴、y 轴、z 轴，每隔a x 、a y 、a z 取一个 样本点，如下图2 4 所示，因此，我们用下面的表达式来表 示立体像素在体数据中的坐标位置。 - 9 z y v o x d 图2 - 4 体数据在三维空问中的定义 江南大学硕士学位论文 x i = x o + x y i = y o + i a y z i 2 z 0 + i a z ( 2 1 ) 此类依顺序捧列且等间距的资料集表示方法，称之为规则体数据集，而且，我们又可以定义函数 f ( x i ，y i ，毛) 来表示体数据中的坐标位置内所存在的立体像素值。 2 1 2 体数据的获取 随着影像技术的快速发展，我们利用各种不同的成像方法获得所需的影像信息( 如：计算机断层扫瞄 c t 、核磁共振影像m r i 、正子断层摄影p e t ) 。对于医学而言，人体内部构造的了解越来越受到重视，一 些重要的信息往往埋藏在医学影像中而无法被肉眼轻易观察到，于是医学影像处理变成一项热门的研究领 域。其中，对于实体数据的处理，我们可以借助于计算机断层扫描取得人体器官各层的三维数据，再通过 计算机图形学的科学可视化技术，制作成我们所需的模型，让医师能够快速且清楚地了解三维资料的内容， 其主要流程如图2 5 所示： 2 2m a r c h i n gc u b e s 算法 ( a )( b )( c )( d ) 图2 - 5 体数据成像流程图 ( a ) 对实体进行x 光断层扫瞄；( b x c ) 取得连续的二维灰阶影像； ( d ) 对此实体资料进行计算，显示出3 d 模型画面 我们先以二维情况的等值线为例进行说明。所谓等值线是由所有这样的点( ，乃) 定义，其中 ，【x ，只) 。，( ，t 为一给定值) ，将这些点按一定顺序连接组成了函数f 【x ，y ) 的值为，的等值线。常见 的等值线如等高线，等温线，是以一定的高度，温度作为度量的。等值线的抽取算法可分为两类，网格序 列法和网格无关法。网格序列法的基本思想是按网格单元的排列顺序，逐个处理每一个单元，寻找每一单 元内相应的等值线段。处理完所有单元后，自然就生成了该网格中的等值线分布。网格无关法则通过给定 等值线的起始点，利用起始点附近的局部几何性质。计算等值线的下一点；然后利用计算出的新点，重复 计算下一点，直至达到边界区域或回到原始起始点。网格序列法按网格排列顺序逐个处理单元，这种遍历 的方法效率不高。网格无关法则是针对这一情况提出的一种高效的算法。下面就举例说明计算等值线的方 法。 假设网格单元都是矩形，其等值线生成算法的主要步骤如下： 一1 0 - 第二章等值面生成技术 1 )逐个计算每一个网格单元与等值线的交点； 2 ) 连接该单元内等值线的交点，生成该单元内的等值线线段： 3 ) 由一系列单元内的等值线线段构成该网格中的等值线： 网格单元与等值线的交点计算主要计算各单元边与等值线的交点，可采用顶点判定，边上插值的方法 计算。设等值线的值为f ，若f ，。( f ，则记顶点为t ，；若， f ，则记顶点为+ ，。若单元的四个顶点 全为+ ，或，则网格单元内无等值线；否则对两个顶点分别为+ 、的单元边插值计算等值线的交点， 并在单元内连线，连线情况见图2 - 6 。 挝料鞲斟 ( c ) 图2 - 6 单元内等值线连接情况 在图2 - 6 ( d ) 的情况下，实际上存在着两种连接方式的二义情况，不可能判断哪种连接情况是正确的。 为了避免这种二义性情况，可采用单元剖分法，算法的基本思想是利用对角线将矩形单元分成四个三角形 单元，求出中心点的函数值，等值线的抽取直接在三角单元中进行。三角单元中至多只包含一条等值线， 从而避免了二义性问题，但处理单元数目增加了四倍。如图2 7 所示。 一圆一函一囟一+ 园一 因固圜因 图2 - 7 剖分法连接情况 下面对三维情况的等值面进行说明。在可视化的研究领域中，m a r c h i n gc u b e s 算法是一个相当重要的 发展，于1 9 8 7 年由l o r e n s c n 与c l i n e 两人所提出，其主要目的是从实体数据中重建出三维等值面，处理的 对象般是以c t 与m r i 等三维实体数据为主。 在介绍m a r c h i n gc u b e s 算法之前，我们先来为体元做定义：体元是由八个立体像素所组成，如图2 - 8 所示，其中四个相邻的立体像素由切面k 提供，而另外四个相邻的立体像素是由切面k + 1 所提供，因此形 成一个立方体。m a r c h i n gc u b e s 算法中c u b e 的意思即为体元。 m a r c h i n gc u b e s 算法的主要概念为，对于一个三维体数据集合，以线性搜寻的行进方式，一个接一个 地处理每一个单元格子，并分析是否等值面有通过它，进而产生出一连串的三角面片来近似于等值面，以 下为m a r c h i n gc u b e s 算法的主要步骤： l 、使用者给定等值； 2 、对体元进行分类； 江南大学硕士学位论文 3 ，三角面片网格的产生 k 以； 8 c k + 图2 8 体元 在m a r c h i n gc u b e s 的算法中，首先使用者给定一个有兴趣的等值，希望能建构其三维等值面，进而观 察实体对象的内部结构。举例来说，对于头颅的三维数据集合， 假如我们对骨头的等值面分布有兴趣，m a r c h i n gc u b e s 算法即 会对此数据集合建构出骨头附近的等值面出来。 给定一个感兴趣的等值( i s o - v a l u e ) ，在三维数据集合中， 有些体元的八个立体像素值完全小于等值，即表示这些单元格 子完全落在等值面的外部；同样地，有些体元的八个立体像素 值完全大于等值，即表示这些单元格子完全落在等值面的内 部。具有以上这两种情况即表示等值面没有通过这些体元，因 此不需要再讨论。另一方面，有些单元格子的八个立体像素值， 其部份小于等值，部份大于等值，即表示等值面有通过这些体 元( 如图2 - 9 所示) 。因此，我们将对这些有等值面通过的体元 图2 - 9 单元格子与等值面相交 做进一步的处理，进而产生三角面片来逼近等值面。 以下列表示法来对体元做分类： r 一 i s o v a l u e m 单位格子完全落在等僵面的内部 、m a x i s o v a l u e单位格子完全落在等值面的铃都 b a f i n 量i s ov a l u es m a x单位格子内肖等值面扶中通过 m a x ：表示单元格子中八个立体像素的最大值 m i l l ：表示单元格子中八个立体像素的最小值 妇d v a l u e ：等值 为了方便说明，如何从有包含等值面的体元中计算出三角形面，我们对体元内的八个立体像素着色， 若立体像素值大于或等于等值，将涂成黑色小圆( 等值面内部) ；若立体像素值小于等值，将涂成白色小圆( 等 值面外部) 。因为体元