（计算机应用技术专业论文）基于物序体绘制的算法和应用研究.pdf

摘要 体视化( v o l u m e v i s u a l i z a t i o n ) 尤其是其中的体绘制( v o l u m er e n d e r i n g ) 是 三维数据场可视化领域最重要、近年来发展最迅速的一项技术。在医学三维重建、 计算流体力学、有限元后处理、地震地质等众多领域得到了广泛应用。体空问扫 描( 物序) 的体绘制技术具有遍历方法简单、可以充分利用各种加速算法、良好 的可并行性和适合硬件实现等一系列优点，但原有算法同时面临计算不准确、容 易产生各种走样等诸多问题，所以本文主要针对基于体空间扫描的体绘制技术进 行了深入探讨和研究。 首先，通过深入研究基于体空剐扫描的体绘制s p l a t t i n g 方法的基本原理， 指出了这种方法存在的诸多问题：由于要提前把重构核积分成二维的足迹表，会 产生积分、重叠和p o p p i n g 等问题，所以它并不能生成很精确的图像：在此基础 上本文提出了一种基于新型遍历方式的改进s p l a t t i n g 算法。该算法通过定义平 行于视平面的v i e w b u f f e r ，及采用平行于v i e w b u f f e r 的体素遍历方法，并且根 据预先计算好的三维查找表等技术来改善经典s p l a t t i n g 算法。该算法不仅能很 好地消除体旋转过程中的p o p p i n g 现象，而且能够得到更高质量和更精细的绘制 结果。 其次，在总结各种体绘制方法优点的基础上，尤其是s p l a t t i n g 方法的精髓， 论文提出了一种基于体空阳j 扫描的新型体绘制方法。浚方法通过构造两重重构查 找表束进行三维重构，并采用高效的层遍历策略来完成绘制。该方法使绘制时的 重采样操作更符合采样理论，使得该方法能够更好地逼近理想绘制方法。并且由 于该方法是一种基于物序的体绘制方法，所以既具有s p l a t t i n g 方法中的诸多优 点，又能够达到r a y c a s t i n g 方法的绘制质量。同时出于该方法具有良好可并行 性。为今后本课题组的加速体绘制体系结构设计提供了有效的理论方法。 最后，对课题组研制丌发的三维医学重构系统v 0 1 g r 印h 作了简单的介 绍。 关键词：体视化，体绘制，体素，s p l a t t i n g ，重构，查找表 a bs t r a c t v o l u m ev i s u a l i z a t i o n e s p e c i a l l y v o l u m e r e n d e r i n g h a sb e e nt h em o s t i m p o r t a n ta n dr a p i dd e v e l o p e dt e c h n i q u e si n t h ev i s u a l i z a t i o no ft h r e e d i m e n s i o n a l d a t as e t sr e c e n t y e a r s i t h a sb e e n w i d e l y u s e di nt h r e e d i m e n s i o n a lm e d i c a l r e c o n s t r u c t i o n ，c o m p u t a t i o n a ld y n a m i cf l u i d ，p o s t p r o c e s s i n g o ff i n i t ee l e m e n t c o m p u t a t i o n ，s e i s m i c a n d g e o l o g i c a la p p l i c a t i o n s b e c a u s eo b j e c t o r d e r v o l u m e r e n d e r i n gm e t h o d sh a v et h ea d v a n t a g e si n c l u d i n gs i m p l ev o x e lt r a v e r s e ，e a s yu s eo f a l lk i n d so f s p e e d u pt e c h n i q u e s ，h i g hp a r a l l e la b i l i t y ，a n de a s y h a r d w a r e i m p l e m e n t a t i o n ，a tt h es a m et i m et h e s ea l g o r i t h m sh a v et h ed i s a d v a n t a g e ss u c ha s c o m p u t a t i o ni n a c c u r a c ya n da l i a s i n g s ，o b j e c t o r d e rv o l u m er e n d e r i n gi sd i s c u s s e di n t h i sp a p e r f i r s t ，b ys t u d y i n gt h ef u n d a m e n t a lp r i n c i p l eo fo b j e c t o r d e rv o l u m er e n d e r i n g e s p e c i a l l y t h e s p l a t t i n ga l g o r i t h m ，w e f i n dt h em a i nr e a s o n so ft h et r a d i t i o n a l s p l a t t i n gi n a c c u r a c ya n da l i a s i n g s ：t h et r a d i t i o n a ls p l a t t i n ga l g o r i t h mp r e - i n t e g r a t e s t h er e c o n s t r u c t i o nk e r n e li n t ot w od i m e n s i o n a l f o o t p r i n t st a b l e ，w h i c h r e s u l t si n i n e v i t a b l ei n t e g r a t i o np r o b l e m ，o v e r l a yp r o b l e m ，s oi ti sd i f f i c u l tt op r o d u c ea c c u r a t e r e n d e r i n g r e s u l t s a sa n i m p r o v e m e n t ，s h e e t - b u f f e r m e t h o do v e r c o m e st h e o v e r l a p p i n gp r o b l e m ，a tt h es a m et i m ei n t r o d u c e sp o p p i n ga r t i f a c t si n t os p l a t t i n g i n t h i sp a p e r , w ep r e s e n tan e wk i n dm e t h o dw h i c hi sb a s e do nv i e w b u f f e rr a t h e rt h a n s h e e t b u f f e r b yu s i n g av o x e lt r a v e r s a lo r d e rw h i c hi sp a r a l l e lt ot h ev i e w b u f f e r ，a n d a p r e i n t e g r a t e dt h r e ed i m e n s i o n a ll o o k u pt a b l e ，w es o l v e t h e p r o b l e m so fc l a s s i c s p l a t t i n ga l g o r i t h me f f i c i e n t l y t h em e t h o dw ep r o p o s e d c a nn o to n l ys o l v et h e p o p p i n gp r o b l e m i nt h er o t a t i o n p r o c e s s ，b u t a l s oo b t a i n h i g hq u a l i t y r e f i n e d r e n d e r i n g s e c o n d ，b a s e do nt h ea n a l y z i n gt h ea d v a n t a g e so fa l lv o l u m e r e n d e r i n gm e t h o d s ， e s p e c i a l l yt h ee s s e n c eo fs p l a t t i n ga l g o r i t h m ，an e wo b j e c t o r d e rv o l u m er e n d e r i n g a l g o r i t h mi sp r o p o s e d i nt h i sp a p e r f i r s t l y , t h en e w a l g o r i t h m c o n s t r u c t sa ne f f i c i e n t d a t a s t r u c t u r e ，n a m e l y ，at w o s t e pl o o k u p t a b l e ，w h i c h i su s e df o rt h e t h r e e d i m e n s i o n a l r e c o n s t r u c t i o n s e c o n d l y , an o v e ls l i c e - o r d e rt r a v e r s a ls t r a t e g y i s a d o p t e df o rt h ep r o j e c t i o n t h er e s a m p l eo p e r a t i o ni nt h ep r o p o s e dm e t h o di sm u c h c o i n c i d e n t a lt ot h es a m p l et h e o r y ，w h i c hm a k e st h em e t h o dm u c hc l o s e rt ot h ei d e a l r e n d r i n gm e t h o d b e c a u s et h en e wm e t h o di s a no b j e c t - o r d e rv o l u m er e n d e r i n g ，i t i n h e r i t e st h e a d v a n t a g e s o ft h e s p l a t t i n gm e t h o d ，i na d d i t i o n ，i t c a n p r o d u c e r a y 。c a s t i n gl i k er e n d e r i n gq u a l i t y a tt h es a m et i m e ，t h ep r o p o s e dm e t h o dh a sh i g h p a r a l l e la b i l i t y t h i sp r o v i d e su saf i r mb a s i sf o ro u rf u t u r eh a r d w a r e a c c e l e r a t e d v o l u m e r e n d e r i n ga r c h i t e c t u r er e s e a r c h a tl a s t ，at h r e e d i m e n s i o n a lm e d i c a lr e c o n s t r u c t i o ns y s t e m v o l g r a p h ，w h i c hi s d e v e l o p e db y o u rr e s e a r c ht e a m ，i sd i c u s s e d k e y w o r d s ： v o l u m ev i s u a l i z a t i o n ， v o l u m e r e n d e r i n g ， v o x e l ， s p l a t t i n g r e c o n s t r u c t i o n ，l o o k u pt a b l e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞壅盘生或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名；劢i 篙刚签字r 期：硼年吕月2 p 同 学位论文版权使用授权书 本学位论文作者完全了解基壅盘茔有关保留、使用学位论文的规定。 特授权鑫壅盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字f 1 期：知田年 导师签名 矧椭， 签字同期：扣；年月二，同 k 潭人学 i ! j 11 学位论艾 第一幸绪论 第一章绪论 作为计算机图形学一个新分支和热点研究方向，同时也是计算机可视化技术 的一项核心技术，直接体绘制技术( d i r e c tv o l u m er e n d e r i n g ) 将来自如计算机断层 扫描( c o m p u t e dt o m o g r a p h y ，c t ) 、核磁共振( m a g n e t i c r e s o n a n c ei m a g i n g ，m r i ) 、 计算流体力学( c o m p u t a t i o n a lf l u i dd y n a m i c s ，c f d ) 等的三维体数据有效地绘制出 来，在医学、地质科学、计算流体力学等领域得到广泛重视和应用。 传统的图形学技术需要先建立几何模型并生成三角面片，再进行绘制。它只 能表达体数据的轮廓，不能有效深入的表达数掘场的内部，因此造成整体信息的 丢失太多。而体绘制技术是将三维空间的离散体数据直接转换为二维的图像， 并不需要生成中问的几何图元。它的绘制结果可以使人们从图像中感受到完整的 体数据信息，给人更直观，更方便的视觉表达效果。 其中基于物体空阳j 扫描的s p l a t f i n g 方法是目前国际上最流行的一种体绘制 技术。本文通过研究s p l a t t i n g 方法的原理，具体分析其绘制流程，针对该方法 所存在的积分、p o p p i n g 及采样等问题，从不同的角度提出改进方案，并在具体 的可视化应用平台上加以实现。在吸收传统s p l a t t i n g 方法精髓的基础上，提出 了一种新型的物序体绘制方法，该方法不仅更好地符合采样理论、又能够产生高 质量图像，且适合并行加速。 1 1 研究背量及意义 2 0 世纪8 0 年代后期，随着计算机软硬件技术的不断发展、科学和工程计算 规模和复杂度不断增加以及各科学领域新型实验手段的不断丰富，海量数据集与 无法有效解释和应用这些数据之间的矛盾同益尖锐。科学计算可视化1 1 ( v i s u a l i z a t i o ni ns c i e n t i f i cc o m p u t i n g ) 就是在这种背景下提出并发展起来的一 个全新研究领域，它主要是指运用计算机图形学和图像处理技术，将科学计算、 工程计算以及实验和测量的数据转换为图形和图像在屏幕上显示出来，并进行交 互处理的理论、方法和技术。是一个涉及计算机图形学、图像处理、计算机辅助 设计、计算机视觉和人机交互技术等多个领域的交叉学科，同时也是一个当莳十 分活跃的热点研究领域。 可视化既是种计算方法将数据映射成图像，又是一种交互工具以 可视形式探索数据和计算的本质。其应用领域十分广泛，其技术几乎可应用到所 丕塑叁兰丝! 兰垡堡兰釜二i ! i 堕 有的自然科学和工程技术领域如医学、分子建模、气象预报、石油、地震、计算 流体力学、有限元分析等 2 1 1 3 1 。其作用主要体现在以下几个方面： 为各个应用领域提供分析工具和手段。通过可视化软件和技术使得各领 域的科学家可以分析和显示大体积的多维时变数据，从而快速有效地提 取有意义的特征和结果。增加获取新知识、发现新规律的可能性。可视 化强有力地支持了那些将视觉涮察力作为问题求解能力的应用领域。 科学计算结果的后处理为提高科学计算质量和效率提供强有力的支持。 为模拟计算和数据分析提供视觉交互手段。在驾驭式计算过程中，用户 可直接控制仿真过程，通过参数调整方式对仿真计算进行干预。 国际上美国、西欧和同本各著名大学如s t a n f o r d 、m 1 1 r 、u n i v e r s i t yc a l i f o r n i a ， d a v i s 、研究所、超级计算机中心如美国洛斯阿拉莫斯国家实验室( l o sa l a m o s n a t i o n a ll a b ) 、罗伦兹利弗莫国家实验室( l a w r e n c el i v e r m o r en a t i o n a ll a b ) 、 美国宇航局a m e s 研究中心、海军实验室、n s f 的国家超级计算中心( n c s a ) 以及各大公司如g e 、i b m 、s g i 等都在进行科学计算可视化理论和方法研究， 并在重要的国际计算机会议上发表文章。国外的可视化专家先后提出了一系列可 视化算法，极大促进了可视化技术的发展。自1 9 9 1 年，i e e e 每年召丌一次可视 化会议。1 9 9 5 年，m e e 新增了一个刊物( ( i e e e t r a n s a c t i o n o n v i s u a l i z a t i o n a n d c o m p u t e rg r a p h i c s ) ) 。与此同时，用于科学计算可视化的软件和硬件系统也在加 紧研制，一些软件产品开始在国际市场销售如a v s 、i b m 的o p e n d x 。相对于 国外，国内可视化的研究工作开展地相对较晚，并且也主要集中于可视化基本算 法研究，也尚未推出真征意义上的可视化产品。 可视化是一个热点密集型研究课题，目前尚有很多问题没有解决。在这些问 题中，即使是一些小的突破也会对各科学领域产生深远影响，所以，科学计算可 视化是一个能够出刨新性研究成果、产生直接经济效益以及发表高水平论文的研 究领域。所以，我选择科学计算可视化算法理论及其应用系统研究作为硕士论文 的课题，旨在通过对已有可视化算法理论进行改进，提出自己新的更高性能的可 视化算法，并将这些算法集成到具体的应用系统中去，为其他学科的科学家提供 更好的可视化软件和研究工具，促进科学技术发展。 1 2 体视化 本文主要研究的是科学可视化的一个重要分支体视化【4 】【5 6 】( v o l u m e v i s u a l i z a t i o n ) ，它研究体数掘的可视化问题。 计算机图形学一般采用几何模型，即点、线( 直线或曲线) 和面( 平面或曲 丕竺叁兰竺! 兰竺丝兰生二垦! ! 鱼 面) 等图形基元来描述形体。它主要有边界表示法，构造实体几何和空间分解三 种表示模型f 7 】。几何模型是表示有形而且规则的形体的理想模型，因此常用于 机械、建筑设计上。但是它无法描述好烟云、肌肉等无形对象。几何模型只是描 述了形体的表面，却无法刻画形体内部复杂的细微的结构。从这个角度上讲，它 们只是表示形体的外壳，而不能表示“有皮有肉”的实际物体。 与传统的计算机图形学描述物体的方式不同，体数据是对有限空间的一组离 散采样，每个采样点上的采样值可以是一种或多种，代表在该点上的一个或多个 物理特性，例如用检测仪器对温度场、速度场进行采样，其结果都是以有限个采 样来描述场空间。因此体数据是真f 的三维实体，它含有物体内部信息。 体视化是科学可视化的一个重要组成部分，它是在吸收图像处理、计算机视 觉和计算机图形学等学科有关知识的基础上发展起来的【4 】【8 】，图像处理【9 】主要 研究的从图像到图像的变换，其中图像滤波和变换方法被借用过来，用于滤除体 数据中的噪声和校准成像过程带来的畸变。体数据是对某物理属性的空间采样， 而不同的物质一般具有不同的物理属性，因此利用图像分割技术可以基于采样值 把不同物质分开。计算机视觉 1 0 1 的任务是对图像进行解释，即给每个图像元素 一个符号描述，其中分割或分类可用于区分体数据中不同种类的物质。体数据分 类是体绘制中的一个关键步骤，它的j 下确性和准确性直接关系到对体数据所含对 象的分析和显示。计算机图形学研究物体的描述方法以及从几何描述生成显示图 像的方法。体视化继承了计算机图形学的一些显示技术，如可见性算法和光照模 型等。 体视化在吸收图形学有关知识的同时，又孕育着计算机图形学的场革命 【1 1 】。传统计算机图形学以面和边等基元来描述物体，不含有任何内部信息；而 三维体视化则是以三维基元( 体素) 来描述整个物体的，它包含物体内部的全部 信息。正如7 0 年代光栅图形取代矢量图形而更有效的实现二维物体一样，现在 的体视化正在逐步替代传统图形学来更好地显示三维物体f 不仅是物体表面，还 有物体的内部) 。从硬件上柬看，设计和制造存储体数掘的大容量存储器已经不 是一件困难的事情，用于体数据操作显示的体视化专用并行处理硬件目的国际上 也在设计和测试中，预计不久就会有大批的体视化硬件问世。 目f i i f ，关于体视化的研究可谓是如火如荼，它的应用遍及医学、物理学、化 学、地质学、显微摄影学、工业检测、航空航天和科学计算诸多领域 1 2 1 。本文 中主要讨论三维体视化的原理、方法和应用，并主要以医学领域中的应用为背景， 这不仅因为三维医学图像是可视化的重要研究对象，同时也因为它非常具有代表 性。 图1 - 1 描述了三维体视化的总体框架【4 】，从图中可以看到三维体视化的第一 天津人学埘1 学位论文 第一章绪论 个步骤是图像获取。通过图像获耿设备( c t ，磁共振或超声扫描) 对真实物体进行 扫描而得到一组二维的断层图像，也可以是对计算模型的离散采样以构成二维断 层图像。一般来说，这些断层图像都是含有噪声，需要进行滤波以提高信噪比。 当这组二维断层图像间的恻距相当于图像内像素之问的问距很大时，或者断层图 像之间的距离不均匀时，就需要在断层图像之1 白j 构造新的二维图像，这个过程叫 做图像插值 1 3 ( i m a g ei n t e r p o l a t i o n ) 。经过图像插值，就得到了一个各向同性的 三维体数据。为了进步提高信噪比，有时候还需要进行一次三维滤波。三维体 数据也可以通过对几何模型进行体素化柬获得。 真丈物体 图1 i 二维体视化的总体框架 体视化并不是把产生显示图像作为最终的目标。人主动的参与可视化过程， 根据需要对体数据所蕴含的不同对象进行选择，并施加诸如平移、放缩，旋转等 天津人学 1 j 学位论立 第一章绪论 操作，目的是使人能够很好地理解和掌握对象的结构。对体数据进行操作实质上 是对其进行相应变换。所以，有些文献【1 1 】【1 4 】形容人参与体视化过程的行为是 “在体数据中漫游和勘探”。 体数据的分类 1 5 1 ( c l a s s i f i c a t i o n ) 是一个关键步骤，它的任务是赋予每个体素 一个标号以表明它所属的类别。这罩有必要提一下分类( c l a s s i f i c a t i o n ) 和分割 9 ( s e g m e n t a t i o n ) 的一点点区别，因为大多数的文献中把这两个概念等同。分割 的任务是把图像分成不同的区域，每个区域代表相对均匀的同一类物质，但分割 的任务不包括确定属性。所以分类比分割多了一个解释( i n t e r p r e t a t i o n ) 的过程。 但是，如果把分割得到的每一个独立的区域都给一个唯一的标号，尽管这种标号 不含任何物理意义，我们也可以认为得到一个属性图像，在这种意义上，分类和 分割是一致的。 前面所描述的体数据的滤波、插值、分割或分类构成了体视化的预处理过程， 它是后续体绘制的过程中的一个必要的数据整理和准备工作。实现体数据的可视 化一般有两个途径【5 ，一个是进行物体三维建模，然后用传统的计算机图形学 的显示方法对重构出的物体表面进行显示。另一条途径是直接对体数据进行显 示，所以也叫做直接体绘制( d i r e c tv o l u m er e n d e r i n g ) ，简称体绘制( v o l u m e r e n d e r i n g ) 。直接体绘制完全不同于传统的计算机图形学的思想，它不需要构造 任何中间表示就能够完成显示，所以它是体视化中最具特色的一项技术。 本文讨论的重点就是体视化框架罩的最后一步绘制，尤其是直接体绘 制。它是体视化罩面发展最快，最为关键的一项技术。 1 3 本文的研究工作和创新 体视化是近十年刚刚发展的一项研究领域，本文针对其中的关键技术体 绘制进行了理论研究和实践。其中近两年最受瞩目的直接体绘制是本文中的研究 重点。作者的研究工作和创新如下： 分析比较目前最流行的几种体绘制算法并实践，从而探索更适合本课题 组的研究方向。 深入研究基于物序的直接体绘制s p l a t t i n g 方法的原理，指出其算法中目 前存在的诸多问题。 针对s p l a t t i n g 方法的问题，提出基于一种新的遍历方式的改进方法。 提出一种基于物体空问扫描的新型体绘制方法。 为了达到合理并快速地对体数据进行重采样，构造一种方便快速的两重 重构查找表。 探讨新型体绘制里的并行可行性，为今后本课题组的硬件加速提供理论 天津人学坝i 。学位论义第一辛绪论 方法。 构造适合于物序体绘制的优化体素数据结构。 跟课题组成员共同丌发体视化的应用系统v o l g r a p h 。 1 4 论文组织结构 论文的组织结构和章节安排如下： 第一章绪论，介绍本文的选题背景、研究工作的基础、创新之处和主要研究 工作。 第二章详细讲述体绘制中的相应概念和原理，简单分析并比较了目前流行的 几种体绘制的优缺点。这些工作对作者以后的研究有着很大的启发。 第三章讨论了s p l a t t i n g 方法的原理，并指出该方法中存在的致命问题。针 对这些问题，作者提出了一种改进方法。 第四章在吸收s p l a t t i n g 方法精髓的基础上，提出了一种基于物序的新型体 绘制方法，该方法更符合重采样理论，并适合于并行计算。 第五章简单介绍了我们丌发的一个体视化应用系统v 0 l g r 印h 。 第六章对作者研究生期问的工作进行了总结，并对将来的研究作了些展 挈。 圣笙苎兰些! 兰竺堡兰 塑二主堡丝型竺苎塑垄堡! ! 竺 2 1 体数据 第二章体绘制的基本概念和原理 体数据的来源既包括科学计算的结果，如：有限元的计算和流体物理的计算； 也包括测量仪器的测量数据，如：地震勘测数据、气象监测数据、人体的c t 或 m r i 扫描数据等。由于很难得到连续的计算和测量数据，这些数据通常是离散 的三维数据，一般被称为体数据。 一般情况下，体数据在逻辑上被组织成一个三维的数组空间如图2 1 所示， 每个元素叫做体素4 】( v o x e l ) ，每个体素都可以有它自己所在的层号、行号和列 号。本文中考虑的体数据主要是均匀地分布在三维网格点上，即x ，y ，z 三个方向 上，网格点之间的距离均相等。在这类数据中，无需给出各个体素的空间位置， 只要给出三维网格某一角点的空间位置和某一体素的序号，即可根据网格间距对 应的距离求出该点的空间位置。通常，每个体素是8 1 6 位，存储相对应的密度 值或灰度值。体数据的存储一般都比较庞大，例如对于8 0 个分辨率为5 1 2 x 5 1 2 的 c t 断层图像，需要2 0 m - - 4 0 m 字节的内存。本文之所以只考虑规则均匀的体数 据结构，是因为非规则体数据最后都可以转化成规则体数据结构。 体 行 幽2 - 1 体数据 丕翌叁堂些! 兰些丝兰 笙兰至上竺堂苎堡塑垄堑! 堕竺 2 2 体数据的传递函数 图2 - 2 是体视化流程图，其中映射中传递函数的功能是将一个体数据映射 成相应的光学特性如颜色、不透明度、辐射度以及相关的光学模型参数立n p h o n g 光照模型的k a 、k d 、k s 等。这里，体绘制算法中主要用到的是颜色和不透明度。 幽2 - 2 体视化流稗幽 由于颜色、不透明度等贯穿整个体绘制流程，所以高性能传递函数设计成为体绘 制算法的一个关键步骤。 一般说来，传递函数被定义为体数据场d 笛卡尔积到光学特征t 笛卡尔积的 映射： f ：d l d 2 x d 。_ + l 疋乙( 2 1 ) 其中，n 是原数据集的维数，一般情况下n = l ，此时认为传递函数是一维的， 定义域就是体数据本身。1 6 1 7 1 中n = 2 ，3 或者更大，被称为是多维的传递函数， 这时传递函数的定义域不仅包含体数据，还包括体数据的一阶倒数和二阶倒数， 有时还包括曲面的曲率【1 8 1 、局部形状特征【1 9 1 等等。而通常m = 2 ，主要考虑不 透明度n 和颜色c ( r ，g b ) ，在有些系统中颜色也主要通过所使用的光照模型来计 算，这时m = l ，传递函数主要用来确定不透明度旺，此时的传递函数称为不透明度 传递函数。第二步是通过体绘制算法将体数据经传递函数映射成的光学特性再次 映射成屏幕图像。其中体绘制算法可以使用光线投射算注i ( r a yc a s t i n g ) 2 3 1 、足 迹表法( f o o t p r i n t 或者- s p l a t t i n g ) 算法【3 9 】、错切一变形算法( s h e a r w a r p ) 【2 6 】或者单 元投射法( c e l lp r o j e c t i o n ) 等。 不章的是，实时、交互地设计能够导致良好启示性绘制结果的传递函数是非 常困难的。这主要有四方面原因： 科学计算可视化的最终目的是从数据中获得信息以及对数据的理解，而 很多场合用户未必对数据集本身非常了解，有时甚至是无所知； 同一种结构或者物质可能具有不同的体数据值，而相同数据值又有可能 属于不同结构或者物质。任意体数据的自动分割和分类仍然是科学计算 可视化的难题之一。 灭谭大学颧 学位论文第一章体绘制的蕞奉概念和原理 因为体绘制过程的复杂性，导致体数据值、传递函数映射成的光学特性 以及最终绘制结果之f 白j 并不保持良好的线性关系。传递函数的微小变动 有可能产生绘制图像大的改变。 体绘制过程比较耗时。即使是硬件加速的体绘制算法f 2 0 】目前也只能实 时处理中小规模女n 2 5 6 2 5 6 2 5 6 体数据。这使得对所选传递函数的评 价也变得费时。 为此p a th a n r a h a n 在1 9 9 2 年体视化会议的主题发占中曾将好的传递函数设 计列为体视化研究的十个经典难题之一。探索新型传递函数设计方法也是作者所 在课题组的一个重要研究方向。 2 3 体数据的绘制方法 如何对数据场进行绘制是体视化中的核心技术。目前，大致可以分为两类不 同的可视化绘制算法1 5 1 1 6 1 。 第一类算法首先出三维空间数据场构造出中阊几何图元( 如曲面、平面等) ， 然后再由传统的计算机图形学技术实现画面绘$ i j ( s u f f a c er e n d e r i n 曲。最常见的 中间几何图元就是平面片，当我们需要从三维空间数据场中抽取出等值面时就属 于这种情况。可以抽取出个等值面，也可以抽取出多个等值面。这类方法可以 利用现有的图形硬件实现绘制功能，使图像生成及变换的速度加快并可以产生较 清晰的等值面图像。然而这种基于面绘制的方法构造出的可视化图形不能反映整 个原始数据场的全貌，生成的结果也不够细腻。 在此类技术中，最有影响的面绘制重建方法是l o r e n s e n 和c l i n e 提出来的移 动立方体方法【2 l 】( m a r c h i n gc u b e ) 。在移动立方体算法中，每个体素被分成l 5 种构型，每种构型对应固定的等值面三角片拟合形态。虽然其基本算法存在面 片数过多和二义性( a m b i g u i t y ) 的缺陷，但经过改进后【2 2 ，现已经广泛用于各 种体数据的可视化。 第二类算法与第一类算法完全不同，它并不构造中间几何图元，而是直接由 三维数据场产生屏幕上的二维图像，称之为体绘制( v o l u m er e n d e r i n g ) 算法， 有时候也叫做直接体绘制( d i r e c tv o l u m er e n d e r i n g ) 算法。这种算法能产生三 维数掘场的整体图像，包括每一个细节，并具有图像质量高、能得到深度信息和 便于并行计算等优点。其主要问题是，计算量大，且难于利用传统的图形硬件实 现绘制，因而计算时间较长。然而，这是近年来发展最为迅速的一类三维数据场 可视化算法，也是本论文中详细论述，研究和实现的绘制算法。 灭律人学硕 ：学位论文 第二帝体绘制的皋奉概念和原坶 三维空阳j 连续数据场 有限元分析 t 离散的三维数据场 商接体绘 帧缓存中的二维离散 信号 图形硬十 t 屏幕二维图像 幽2 - 3 直接体绘制概念示意幽 描、采样 我们可以用图2 3 来说明体绘制算法的实质。三维空间分布在离散网格点上 的数据一般是由三维连续的数据场经过断层扫描、有限元分析或随机采样后作插 值运算耿得的。图形设备屏幕上的二维图像则是由存放在帧缓存中的二维离散信 号经图形硬件绘制而成。因而，体绘制算法的作用就是将离散分布的三维数据场， 按照一定的规则转换为图形显示设备帧缓存中的二维离散信号，即生成每个像素 点颜色的r 、g 、b 值。 熟悉采样理论的读者不难理解，要将一个离散分布的三维数据场转换为二维 离散信号，需要进行重新采样( r e s a m p l i n g ) 。而且不仅需要计算每一个数据值 对二维图像的贡献，还需要将全部数据值对二维图像的贡献都合成在一起。因此 尽管有多种不同的体绘制算法，但其实质均为重采样与图像合成。 目酊国际上流行的体绘制算法主要有：光线投射算法2 3 1 1 2 4 2 5 ( r a y - c a s t i n g ) 、错切- 变形算法 2 6 】【2 7 ( s h e a r - w a r p ) 、频域体绘制算法【2 8 】 2 9 】 ( f r e q u e n c yd o m a i n ) 和抛雪球算 法 3 0 1 1 3 1 1 1 3 2 ( s p l a t t i n g ) 。 光线投射( r a y c a s t i n g ) 是一种图像空1 白j 扫描的体绘制的离散方法。从像平 面上每一个像素出发，沿视线方向发出一条射线并进入体素( v o x e l ，数据场中 的数据点) 空1 剐。在这条射线上选去k 个采样点，计算每个采样点在体空间中 天津人学坝f 。学位论文 第二市仲绘制的堆奉社毵念和原理 的位置，然后用插值的方法计算该采样点的不透明度及颜色值，最后对各个采样 点进行图像合成。这种方法的优点是能够产生高质量的图像。但是由于求交等大 量计算，r a y c a s t i n g 是最慢的体绘制方法。 错切变形( s h e a r w a r p ) 算法是将三维离散数据场的投影变换分解为三维数 据场的错切变换和二维图像的变形两步来实现的，从而将三维空间的重采样过程 转换为二维平面的重采样过程，大大减少了计算量。很明显，对二维图像空间的 采样不可能得到完整、正确的三维信息，该方法是以牺牲图像质量和准确性为代 价来加速绘制。 频域体绘制算法( f r e q u e n c yd o m a i n ) 是t o m m a l z b e n d e r 等人根据傅旱叶投 影截面定理提出来的。一般的体绘制方法的结果可以看成是三维数据场沿视线 方向的数值积累，也就是数据场到图像平面的投影。而傅罩叶投影截面定理告 诉我们，可以通过另一条途径来获得这个投影，即在三维数据场相对应的频域场 中，按给定的视线方向经过原点抽取一个截面，再将这个截面做逆傅罩叶变换， 就可以在空域的图像平面中得到所需要的投影。一般的体绘制方法的计算复杂度 是o ( n 3 ) ，而它的计算复杂度不超过o ( n 2 l o g n ) 。但是频域体绘制的绘制结果很 像一张x 光照片，没有深度信息，并且不适合做并行计算。 抛雪球( s p l a t t i n g ) 方法也叫足迹表法( f o o t p r i mm e t h o d ) 是w c s t o v e r 提出来 的一种基于物体空间遍历的体绘制技术。该方法的基本思想是逐层、逐行、逐个 地计算每个数据点( 体素) 对屏幕像素的贡献，并加以合成，生成最后的图像。 由于足迹表可以在预处理中计算，s p l a t t i n g 方法要比r a y c a s t i n g 方法快很多并 且几乎也能能产生像r a y c a s t i n g 那样的高质量图像。另外由于该方法的物空间 遍历特性，它很适合大规模数据并行计算可视化和硬件加速的设计。由于以上的 诸多优点，本文将主要研究和分析s p l a t t i n g 算法。 2 4 光学模型 体绘制技术是将三维空间的离散数掘直接转换为二维图像而不必生成中阳j 几何图元。三维空间的离散采样点原本是不具有色彩属性的，也不具有扶度值， 所以采样点的色彩是在物质分类的基础上人为地赋予的，因而是伪色彩。体绘制 技术要实现这一功能就是，在重采样地基础上，计算全部采样点对屏幕像素的贡 献，也就是每一个像素的光强度值i ( i n t e n s i t y ) 。为了实现这一目的，需要给出 光学模型，用来描述三维数据场是如何产生、反射、阻挡以及散射光线的，并从 而计算出全部采样点对屏幕像素的贡献。 体绘制的光学模型是k a j i y a 2 4 年1 m a x 3 3 1 等人描述的一个积分方程，对于 任意一条光线，计算其光强度值j 。伍。波长为 的光线从，方向投射到像平 天津人学坝 j 学位论j 第一奇体绘制的捧奉概念和原理 面的x 点时，其遵守如下方程： lxr ) = f g ( s ) ( s ) o x p ( 一( r ) 出) 出 汜2 这罩，是光线r 的传播长度。我们可以假定体数据场是由一些密度为u 的 粒子组成，这些粒子接受从四周光源那罩发射过来的光线，根据这些粒子自身的 一些透射、散射等物质特性，然后向观察者即像平面继续传播。c ，( s ) 是波长为 光线在体数据的s 处的光强，由于大量粒子的存在，还要以粒子的密度值f s l 为权值。而e x p 是光线强度的衰减函数，也就是后面将要提到的透明度。 一般情况下，很难求出这个光学模型的积分方程的解析解，所以必须采用一 种近似的数值解。可以采用如下方法： ，。( z ，r ) = c 。( f 厶) ( f 厶) 厶兀e x p ( 一( ，厶) s ) ( 2 3 ) r = d，- 0 这罩把积分方程近似的离散化，l 被分割成若干小段，每段的长度是厶。 很明显，这种近似会使方程的计算又很高的效率。我们作如下定义： t ( i t ) = e x p ( 一( f 血) 厶) ( 2 4 ) 我们用泰勒公式对指数部分近似的展丌，并只采用第- , n 第二项： t ( i a s ) * 卜( f 厶) 厶= 1 - a ( i a s ) ( 2 5 ) 最后，绘制方程可以写成公式( 2 5 、： j ，出一li - i l ( 一r ) = c 。( f 幽) 口( f 厶) 兀( 1 一口( ，厶) ) ( 2 - 6 ) j ；u j = o 这里的口，就是我们经常说的不透明度，即某一光线过某一物质的透过能力。 体绘制过程中的最后一步是图像合成，其目的是沿着某一象素点所发出的射 线。计算该射线上各个采样的颜色值及不透明度值，并按照一定的规则合成，以 形成该象素点的最终颜色值。将屏幕上各象素点的颜色值都计算出来后，就形成 了一幅图像。根据绘制方程，能够很容易地得到体绘制过程中的两种最根本的图 像融合操作，如图2 - 4 所示。 o v e r0 一与一 u n d e r 如- a - 皇，- 一 幽2 4 幽像的融合的揲作 天津大学倾j 学位论文第二审佛绘制的罐车概念年丌原例 当遍历体素是由后向前的时候，要做o v e r 操作p 4 ，其公式如下 其中， c ，口分别是体素a 臼身的黼色值核 i 不透明度，( _ m ，a j 。m 分别是遍历完体素 b 屙的颜色及不透明度，巴