（通信与信息系统专业论文）基于多核cpu的并行体绘制算法应用研究.pdf

山东大学硕士学位论文 c p u ： v t k ： c t ： m ： l i d c ： 4 符号说明 c e n t r a lp r o c e s s o ru n i t v i s u a l i z a t i o nt o o l k i t c o m p u t e r i z e dt o m o g r a p h y m a g n e t i cr e s o n a n c ei m a g i n g l u n gi m a g i n gd a t a b a s ec o n s o r t i u m 中央处理器 可视化工具包 计算机断层成像 核磁共振成像 肺部影像数据库联盟 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：三缝孝趁舞 日期：迎望! 竺丝 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：型缴导师签名：硇! 未雄日 期：理墅：丝：丝 山东大学硕士学位论文 中文摘要 体绘制技术是科学计算可视化的一个重要手段，是描绘三维数据体内部结构信 息的有效方法。然而，目前的体绘制算法计算量大、绘制时间长，不能满足实时 交互式分析的要求。因此，如何提高体绘制算法的绘制速度成为可视化技术研究 的一个重要目标。 近几年提出了许多体绘制加速的方法，这些方法可分为三类：以图像质量为 代价换取速度的方法、依赖于特定硬件的加速方法和在大规模并行机上实现的并 行算法。其中，并行处理技术因其灵活性高，性能加速比大等优点成为提高体绘 制速度的主要研究方向。 并行处理技术( p a r a l l e lp r o c e s s i n g ) 主要包括并行结构体系、并行算法和并行 编程语言。并行处理技术通过并行编程语言把并行结构体系和并行算法结合起来 进行研究，其核心思想是通过任务的合理划分和分配，使得多个处理器可以同时 执行一个或多个任务，从而达到系统整体计算能力的大i 晤度提升。其中，在并行体 绘制算法中，任务划分一般有两类：基于物体空间的划分和基于图像空间的划分。 本课题研究主要有两部分，其一是分析v t k 的并行机制并探讨其在多核c p u 环境下的应用；其二是选择对图像空间进行任务划分的策略，在双核微机平台上 实现基于0 1 ) e l 小伊的并行光线投射算法。这种方法提高了算法的运算效率，具有 一定的实际应用价值和一定的扩展适用性。 v r k 不仅具有强大的可视化功能，而且也提供了对于并行处理技术的支持， 其集成的m p i ( 消息传递接口) 和s o c k e t s 功能大大方便了并行可视化程序的开发。 多核技术能够使服务器并行处理任务，为用户带来更强大的计算性能。跟传统的 单核c p u 相比，多核c p u 带来了更强的并行处理能力、更高的计算速度和更低的 时钟频率，并大大减少了散热和功耗。同时，o p e l l m a 作为一种基于共享存储系统 的并行编程工业标准，特别适宜于多核c p u 的并行程序设计。 关键词：多核c p u ；并行计算；体绘制；光线投射；o p e i l i v i p 山东大学硕士学位论文 a b s t r a c t v o l u m er e n d e r i n gi sa l li m p o r t a n t t e c h n i q u eo fv 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 ， a n di tc a nd e s c r i b et h ei n t e r i o rs t l l l c t u r ei n f o r m a t i o no f3 dd a t ao b j e c t b u tv o l u m e r e n d e r i n gi sw i t hl a r g ec o m p u t i n ga n dl o n gr e n d e r i n gt i m e ，a n dr e c e n t l yc a n tm e e tt h e r e q u i r e m e n tf o rr e a l - t i m ei n t e r a c t i v ea n a l y s i s s oh o wt oa c c e l e r a t et h ep r o c e s so f r e n d e r i n gb e c a m ea ni m p o r t a n tg o a lo fv i s u a l i z a t i o nr e a s e a r c h r e n c e n t l ym a n ya c c e l e r a t e dm e t h o d sf o rv o l u m er e n d e r i n gh a v eb e e ns u g g e s t e d ， i n c l u d e da c c e l e r a t i n gt h ep r o c e s sa tt h ec o s to fi m a g eq u a l i t y , d e p e n d i n go ns p e c i c a l h a r d w a r ea n dp a r a l l e lc o m p u t i n go nc o s m i c a lp a r a l l e lm a c h i n e a n dp a r a l l e lp r o c e s s i n g b e c a m et h em a i nr e s e a r c hd i r e c t i o nb e c a u s eo fi t sf l e x i b i l i t ya n dp e r f o r m a n c e so fh i g h a c c e l l e r a t i n gr a t e p a r a l l e lp r o c e s s i n gi n c l u d e sp a r a l l e lc o m p u t e ra r c h i t e c h t u r e ，p a r a l l e la l g o r i t h ma n d p a r a l l e lp r o g r a m m i n gl a n g u a g e p a r a l l e lp r o c e s s i n g c o m b i n e sp a r a l l e l c o m p u t e r a r c h i t e c h t u r ea n dp a r a l l e la l g o r i t h mt o g e t h e rb yp a r a l l e lp r o g r a m m i n gl a n g u a g e t h a ti s t om a k em u l t i - p r o c e e s o rp e r f o r mo n eo rm o r et a s k ss y n c h r o n o u s l yb a s e do nr i g h t p a r t i t i o na n da s s i g n m e n t t h e nt h ec o m p u t i n ga b i l i t yo ft h ew h o l es y s t e mi se n h a n c e d g r e a t l y a l s ot a s kp a r t i t i o no fp a r a l l e lv o l u m er e n d e r i n gh a st w oc l a s s e s - o b j e c tb a s e d a n di m a g eb a s e d t h i sp a p e rh a st w or e s e r c hp a r t s o n ed i s c u s s e dt h ep a r a l l e lm e c h a n i s mo fv t k a n di t sa p p l i c a t i o no nm u l t i - c o r ec p u t h eo t h e rr e a l i z e dt h eo p e n m p - b a s e dp a r a l l e l r a yc a s t i n ga l g o r i t h mb a s e di m a g ep a r t i t i o no nd o u b l e - c o r ec o m p u t e r s e x p e r i m e n t s s h o wt h a t t h i sm e t h o dc a ni m p r o v et h ec o m p u t i n ge f f i c i e n c ya n di sw i t hp r e s s i n g e n g i n e e r i n ga p p l i c a t i o nv a l u ea n de x t e n d i n ga p p l i c a b i l i t y v t ki sn o to n l yw i t hp o w e r f u lv i s u a l i z a t i o nf u n c t i o nb u ta l s os u p p o r tp a r a l l e l p r o c e s s i n g i t sc o m p o s i t i v em p ia n ds o c k e t s c a l la f f o r df a c i l i t i e st ot h ed e v e l o p m e n to f p a r a l l e lv i s u a l i z a t i o np r o g r a m m i n g m u l t i - c o r ec a l l m a k es e r v e r sp a r a l l e la n db r i n g u s e r sp o w e r f u lc o m p u t i n gp e r f o r m a n c e c o m p a r i n gw i mt h es i n g l ec o r e m u l t i c o r e c p ub r i n g su sm o r ep o w e r f u lp a r a l l e lp r o c e s s i n ga b i l i t y , h i g h e rc o m p u t i n gs p e e d ， 2 山东大学硕士学位论文 l o w e rt i m ef r e q u e n c ya n dl o wc o s t m e a n w h i l eo p e n m ps t a n d a r dw h i c hi sa n a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ( a p i ) o np a r a l l e lp r o g r a m m i n gm o d e lo fs h a r e d - m e m o r y i se s p e c i a l l yf i g h tt op a r a l l e lp r o g r a m m i n go nm u l t i c o r ec p u k e y w o r d s ：m u l t i - c o r ec p u ；p a r a l l e lc o m p u t i n g ；v o l u m er e n d e r i n g ；r a yc a s t i n g ； o p e n m p 3 山东大学硕士学位论文 第一章绪论 第一节课题的来源及背景 科学计算可视化( 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 ，简称v i s c ) 是发达国 家2 0 世纪8 0 年代后期提出并发展起来的一个新的研究领域。它指的是运用计算机 图形学和图像处理技术，将科学计算过程中及计算结果的数据转换为图形及图像 在屏幕上显示出来并进行交瓦处理的理论、方法和技术。它不仅包括科学计算数 据的可视化，也包括测量数据的可视化，如用于医疗领域的计算机断层扫描( c t ) 数据( 如图1 1 所示) 及核磁共振( m 砌) 数据的可视化。1 9 8 7 年2 月，美国国家科 学基金会在华盛顿召开了有关科学计算可视化的首次会议，并将这一涉及到多个 学科的领域定名为“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 ” 1 】，简称为“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 _ 维头部c t 切片序列，( 来源于文献 2 1 ) 科学计算可视化的核心问题是三维空间数据场的可视化问题。相对于传统的面 绘制【3 ，4 1 ( s u r f a c er e n d e r i n g ) 方法，体绘制【5 捌( 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 ) 7 8 】算法，如图1 2 所示。这种 山东大学硕士学位论文 算法能产生三维数据场的整体图像，包括每一个细节，并具有图像质量高、便于 并行处理等优点，是近年来得以迅速发展的一种三维数据场可视化方法，是科学 计算可视化研究领域中的一个重要研究方向。 譬 图1 - 2 规则数据场的直接体绘制，( 来源于文献 9 1 ) 目前，体绘制技术的丰要方法有：以物体空间为序的抛雪球方法和以图像空 间为序的光线投射算法。这两种方法都存在计算量大、计算复杂，且牛成图像速 度慢等问题，这无疑成为限制体绘制技术向更深更广领域拓展的瓶颈，也使得并 行处理技术成为提高体绘制算法绘制速度的丰要研究方向【1 0 , 1 1 】。因此，本课题拟解 决的关键问题就是：基于一定的并行处理技术和并行程序设计平台，完成体绘制 算法的并行实现，提高体绘制算法的绘制速度，缩短绘制时间。 多核技术【1 2 】能够使服务器并行处理任务，而在以前，这可能需要使用多个处 理器，多核系统更易于扩充，并且能够在更纤巧的外形中融入更强大的处理性能。 跟传统的单核c p u 相比，多核c p u 带来了更强的并行处理能力、更高的计算速度 和更低的时钟频率，并大大减少了散热和功耗。 本课题首先讨论了基于k ( v i s u a l i z a t i o nt o o l k i t ) u 3 的并行可视化及其在多 核环境下的应用。v t k 是用于二维计算机图形、可视化和图像处理的面向对象的 软件系统，提供全面的面绘制、体绘制和充分的交瓦功能，具有开放源代码和可 移植性等特点。其次，本课题在多核环境下实现了基于o p e n m p 的并行光线投射 算法。o p e n m p 1 4 ，1 5 ，1 6 】是由o p e n m p 标准委员会( o p e n m p a r b ，o p e n m p a r c h i t e c t u r e r e v i e wb o a r d ) 于1 9 9 7 年推出的支持共享存储并行编程的工业标准。o p e n m p 标 准通过定义编译制导、运行库和环境变量规范的方法，为程序员提供了支持f o r t r a n 和c c + + 语言的一组功能强大的高层并行结构，而且支持增量并行。 山东大学硕士学位论文 第二节课题研究内容和论文结构 科学计算可视化的目标就是把由数值计算或实验获得的大量数据转换成人的 视觉可以直接接受的计算机图像。体绘制技术作为科学计算可视化研究领域中的 一个重要研究方向，在一定程度上脱离了传统图形学点、线、面的束缚，由体素 作为基本的单元。它是一种基于光学映射的方法，采用体光照模型直接从三维数 据场中绘制出各类物理量的分布情况。针对体绘制技术计算量大、牛成图像速度 慢等问题，本课题拟基于并行处理技术提高体绘制算法的绘制速度。 并行处理是提高体绘制速度的一种重要方法。并行处理的基本思路就是将一 个任务划分为不同的部分分配给不同的处理器同时处理。并行体绘制算法中的任 务划分方法一般有两类：基于物体空间的划分和基于图像空间的划分【1 7 l 。多核技 术能够使服务器并行处理任务，为用户带来更强大的计算性能。多核处理器通常 由片上网络连接的多个处理核( c o r e ) 和层次化的存储系统组成，越来越多地被 用于网络设备、控制系统、视频游戏平台及多种嵌人式应用，丰要通过提高并行 性和并发性来提高性能【1 8 】，另一方面也通过可编程的处理核来提高灵活性。 本课题研究的问题丰要有两个：一是v t k 的并行机制及其在多核环境下的应 用。二是多核环境下基= j = o p e n m p 的并行光线投射算法实现。具体研究内容如下： 第一章为绪论部分，介绍了课题的来源及相关背景，指出了课题的目的和意 义、课题研究的主要内容、论文的主要结构及论文的创新之处。 第二章介绍了本课题所用的相关理论。首先是体绘制技术的基础理论及规则 数据场体绘制算法加速的一般方法；其次介绍多核及并行计算相关知识。 第三章介绍了v r k 的并行处理机制。首先介绍了v t k 的一般知识及基于v r k 的并行可视化；其次，基于任务并行、流水线并行、数据并行这三种并行处理方 式具体说明了多核环境下v r k 并行机制的应用。 第四章介绍了多核c p u 环境下基于o p e n m p 的并行体绘制算法的具体实现方 法。第五章总结了本课题工作并展望课题前景。 7 山东大学硕士学位论文 第三节课题的创新之处 体绘制技术计算复杂、计算量大，即使对于小规模数据，也难以在普通p c 上 满足用户交互分析，实时绘制的要求。在对可视化的实时性要求越来越高的情况 下，高复杂度的计算成为限制体绘制向更深领域发展的重大障碍。引入并行处理 技术是提高体绘制速度的主要方法。本课题采用了多核程序设计和基于o p e n m p 的并行技术，提高了体绘制速度并取得了满意的结果。o p e n m p 作为一种基于共享 存储系统的并行编程工业标准，特别适宜于多核c p u 的并行程序设计。在多核c p u 上实现并行，能带来更强的并行处理能力、更高的计算速度。 本课题的创新之处在于： 一、将k 的并行机制成功应用于多核环境。 二、在多核c p u 环境下实现基于o p e n m p 的并行光线投射算法，提高了该算 法的体绘制速度。 山东大学硕士学位论文 第二章相关理论 第一节体绘制技术算法基础 1 1 体数据的分类及表示方法 科学计算可视化技术的核心就是三维空间数据场的可视化【l o l 。数据来源不同， 既有来自科学实验的，也有来自生产实践的。其中最常见的是通过各种科学仪器 扫描而得到的，这类数据有三维规则的c t 数据、m r i 数据等。在工程应用当中， 经常采用有限元分析和计算流体动力学的方法产生各种模拟数据，而在气象、地 质勘探等领域则大都通过观测获得数据。这些数据有一维的、二维的、三维的、 四维的以至更高维的，但目前关于三维空间数据场的研究是最活跃的。实现三维 空间数据场可视化的算法与数据类型有极大的关系。 数据类型有两层含义，一是数据本身的类型，二是数据分布及连接关系的类 型。根据数据本身类型来分类，在科学计算可视化中，可以实现三种不同类型数 据的可视化，分别为标量、矢量和张量：( 1 ) 标量，可以用一个不依赖于嫩标系 的数字表征其性质的量，如密度、温度、质量等；( 2 ) 矢量，需要用不依赖于坐 标系的数字及方向表征其性质的量，如位移、速度、加速度等；( 3 ) 张量，将矢 量按以华标变换为基础的定义加以推广得到的量。 可视化的对象一般都是空间上离散的三维数据，根据三维空间上离散数据之 间连接关系的分类，可分为以下几类：( 1 ) 结构化数据，逻辑上组织成三维数组 的空间离散数据；( 2 ) 非结构化数据，不能组织成二维数组的系列空间数据单元； ( 3 ) 结构化和非结构化混合型数据。根据结构化数据中各元素不同的物理分布， 又可分为规则网格和不规则网格结构化数据。其中的规则数据场就是由均匀网格 或网格组成的结构化数据。由c t 扫描仪或m 扫描仪获得的一系列二维医学图像 就属于这一类型的数据，它能较好的反映物体特征，每个网格是结构化数据的一 个元素，称之为体素( v o x e l ) ，结构示意图如2 1 所示。假定数据场的函数值分布 在体素的8 个顶点上，那么，位于顶点( t ，y ，z 。) 处的函数值为厂( 薯，y ，z 。) 。 9 山东大学硕士学位论文 烈 n 2 da r r a i e s 黜 3 da r r a y 图2 1 体数据的表不方法 对于规则数据场，三维数组表示是最常见的表示方法。通常，数据场在x ，y ， z 方向等间距，此时规则数据场表示为形，_ ，圪，i = ( 0 ，l ，n x ) ，j = ( o ，l ，。) ， k = ( 0 ，l ，1 ，n ) ，每一个体素由下标寻址( f ，j ，k ) 。对于医学数据中常见的 1 2 8 1 2 8 1 2 8 * 8 位灰度组成的c t 图像，所需要的基本存储空间为2 m b ，再加上存储 颜色、不透明度等信息，所需的存储空间约为1 0 m b ，对于更大规模的数据场，所 需的存储空间更是惊人。规则数据场的另一种常见的表示方法是八叉树表示，通 常用于加速算法中，仙由于通常规则数据场所需的存储空间巨大，而且八叉树相 对于3 d 数组表示还需要相当多的额外存储空间，因此，怎样对八叉树进行组织是 此类算法重点讨论的问题之一。利用八叉树的线性存储是一种可行的方法，而且 八叉树的线性存储在能够利用八叉树特性的同时可以减少相当大的存储需求【1 9 】。 1 2 体绘制光照模型 体绘制技术是将三维空间的离散数据直接转换为二维图像而不必牛成中间几 何图元。二维空间的离散采样点原本是不具有色彩属性的，只具有灰度值。体绘 制技术要实现的功能是，计算全部数据点对屏幕像素的贡献，也就是每一个屏幕 像素的光强度值i 。由计算机图形学可知，在灰度图像中，i 表示灰度值；在彩色图 像中，对红、绿、蓝这3 个颜色分量会有不同的i 值。因此，需要分别计算这3 种颜 色各自的i 值。为了实现这一功能，需要给出光学模型，用它来描述二维数据场是 如何产牛、反射、阻挡以及散射光线的，从而计算出全部采样点对屏幕像素的贡 献1 2 0 1 。 i o 山东大学硕士学位论文 假定连续分布的三维数据场中充满着小粒了，这些小粒子在空间中的存在， 对穿过空间的光线发生作用，它们对光线的吸收、反射以及他们本身的发光作用 引起了光线在通过三维数据场后的变化。基于这一假设，形成了几种不同的光学 模型【2 1 2 2 1 。 光线的吸收和发射模型是体绘制中的光学模型，是用来描述连续数据场的光 学性质的，包含了光线的吸收和光线的发射两个过程。使用数据场时，先通过插值 将三维离散数据场转换为连续数据场，其中一种简明快捷的方法是让插值点的数 据值与距其最近的网格点上的数据值相等。 一、光线吸收模型 光线吸收模型用于为光线吸收过程建模。假设空间中的小粒子可以完全吸收所 接收的光线，而没有反射和发光功能，就形成光线吸收模型。 为简单起见，假定所有的粒予均为大小相同的球状体，其半径为厂，投影面积 为a = 万r 2 。令p 为单位体积内的粒- 了数。现假设有一个圆柱形薄板，其剖面面积 为e ，厚度为厶，则圆柱形薄板的体积为e 厶( 如图2 2 所示) 。设光线以垂直 于圆柱形薄板的方向射入，当厶很小时，投射到圆柱形薄板上的粒了之间相瓦覆 盖的概率很小。 e 图2 2 光照模犁参考模板 覆盖的总面积近似为： n a = p a e z k s ( 2 一1 ) 那么，投射到该圆柱形薄板上的光线被这些粒了吸收掉的部分占全部光线的份额 山东大学硕士学位论文 为： p a e z s s e = p a z s( 2 2 ) 设射入光线的强度为，被吸收掉的部分为，则： 一zk：血(2-3)t pa 2 。j 当血趋近于零时，粒子之间相互覆盖的概率也趋近于零，于是有： 磊d i = 一p ( s ) a 小) = 一f ( s ) 小) ( 2 - 4 ) 此微分方程的解为： 小) = i oe x p ( 一r f ( r ) 出) ( 2 - 5 ) 其中，厶是光线进入三维数据场时( s = 0 ) 的光线强度。f 是光线强度的衰 减系数，含义是沿光线投射方向的s 处的光线吸收率。令 丁( s ) = e x p f ( r ) 巩) ( 2 - 6 ) 表示光线经过数据场的边缘到达s 这段距离后的光线强度，也叫透明度。令口为不 透明度，则有： 口= l r ( s ) = l e x p ( 一r f ( f ) 衍) ( 2 - 7 ) 在将三维数据场映射为颜色值时，如果将某一数据值的f 定义为零，则表示光 线不被吸收而完全穿过，因而在结果图像中该数据代表的物质将是透明的。与此 相反，如果将某个数据值的f 定义为o o ，则表示光线完全被吸收，在结果图像中该 数据代表的物质将是完全不透明的，而在它后面的物质将被完全遮挡。 二、光线发射模型 一般来说，在二维空间数据场及悬浮状物质的可视化中，三维空间小粒予都具 有吸收、反射或发射光线的功能。f u - 是，在火焰、高温气体等的可视化中，我们 可以认为小粒予是很小的，而且是透明的，但是发出的光线却是很强。这时，可 以认为小粒了仅具有发射光线的功能。 设图2 2 中的小粒了都是透明的发光体。在圆柱形截面的单位投影面积上，小 粒了各向均匀地发射出强度为c 的光线( 己知全部投影面积为p a e 厶) ，故整个 山东大芋坝士字1 立论文 | 圆柱形截面上将发射出光通量为c p a e a s 的光，而单位面积的光通量为c p a s 。 因此当光线通过三维数据场时，描述光线变化的微分方程为： i d = c ( j ) p ( j ) 彳= c ( j ) f ( s ) = g ( s ) ( 2 - 8 ) 式中，g ( s ) 为光源项，目前与反射光无关。式( 2 8 ) 的解为： 小) - - z o + r g ( f 矽( 2 - 9 ) 上式中，厶为初始光强度值，s 为沿光线射入方向的长度参数。 三、光线吸收和发射模型 如果将光线吸收模型与发射模型合并在一起，可以更好地反映出光线在充满粒 子的三维空间中的变化。这时，我们有： 面d = g ( s ) 一f ( s ) 小) ( 2 - 1 0 ) 这一模型可以有效地应用于三维医学图像数据或数值计算数据的可视化中。当这 些数据根据所代表的物理意义进行分类之后，即可以赋予不同的r 值和g 值。 由三维体数据的边缘处( s = o ) 积分到观察点( j = d ) ，则有： ，( 。) = i oo x p ( 一r f ( 力出) + r g ( j ) e x p ( 一r f ( f ) 出) 凼 ( 2 。) = i o r ( d ) + r g ( s 沙( s ) 西 ( s ) = e x p ( 一f d f ( f ) d r ) ( 2 - 1 2 ) 式( 2 1 1 ) 中的第一项代表从背景处射入的光线经过三维体数据的吸收以后到达观 察点的光强。第二项表示在各j 点处的光源对观察点处光强贡献的综合，它是通过 乘以由5 到观察点处的透明度，( s ) 并对s 做积分而得到的。 一般情况下，很难求解出式( 2 1 1 ) 的解析解，其近似的数值解可按如下方法 求解。将。到d 这个区间等分为玎个子区间，每个子区间的长度为缸：里。每个子 区间中应选择一个采样点薯以便得到f ( 玉) ( 这里，( i - 1 ) a x x ，f ( 缸) ) 。为简 单起见，令= 池。于是e x p ( 一r r ( 工) 出) 可近似表示为： 山东大学硕士学位论文 e x p i - e r ( i 缸) 缸l = 兀e x p ( 一f ( f 血) a x ) = 兀 ( 2 1 3 ) 这里，= e x p ( - r ( i 血) 缸) 可以看作是沿视线方向上第f 个区段的透明度。如前 所述，不仅决定于f ，而且也决定于区间长度缸。 与此相似，在式( 2 1 1 ) 中，可令g i = g ( i a x ) 。并且，可将鼍到d 之间的透 明度r ( s ) = e x p ( 丘f ( x ) d x ) 近似地表示为 息。 ，于是， j c d g ( j ) e x p ( 一f f ( r ) 以) 幽可近似地表示为： 厅一 g ，兀0 i = 1 j = i + l 因而可得式( 2 1 1 ) 的近似表达式如下： ( 2 - 1 4 ) 巾) = i o i 矧- t ，+ i = l 蜃爿h + 。t j ( 2 - 1 5 ) = g 。+ 乙( g ，。+ 一。( g 。一：+ 一：( g 。一，+ + 乞( g 。+ 厶) ) ) ) 如果我们假设二维数据场具有发光及光线吸收作用，那么，利用公式( 2 1 5 ) ， 可以得出光线从背景射入并由后往前计算到达观察点的光强度值，也可以利用公 式( 2 1 5 ) 由前往后计算光强度值。 在特定的条件下，式( 2 1 1 ) 可以求出解析解。由式( 2 - 8 ) 我们有 g ( s ) = c ( s ) f ( s ) 。如果假设沿着光线发射的方向，发光强度c 为常数，或者在同 类物质区间，所赋予的颜色值c 为常数，那么就有： r g ( s ) e x p ( 一r r ( r ) 巩卜c ( 1 一唧( 一r f ( r ) 出) ) ( 2 - 1 6 ) 将上式代入式( 2 1 1 ) ，得： ，( d ) = i o t ( d ) + c ( 1 - t ( d ) ) ( 2 1 7 ) 1 一t ( d ) 可表示为不透明度口。式( 2 一1 7 ) 表示出背景光厶与所赋颜色值c 在透明 度t ( d ) 作用下的合成值。 1 4 山东大学硕士学位论文 1 3 体绘制算法分类 目前体绘制方法主要分两类，以物体空间为序的体绘制方法和以图像空间为序 的体绘制方法。 以物体空间为序的体绘制方法首先根据每个数据点的函数值计算该点的颜色 及不透明度，然后根据给定的视平面和观察方向，将每个数据点投影到图像平面 上，并按数据点在空间中的先后遮挡顺序，合成计算不透明度和颜色，最后得到 图像，也称作前向体绘制。 以图像空间为序的体绘制方法是从屏幕上每一像素点出发，根据视点方向，发 射出一条射线，这条射线穿过三维数据场，沿射线进行等距采样，求出采样点处 物体的不透明度和颜色值。可以按由前到后或由后到前的两种顺序，将一条光线 上的采样点的颜色和不透明度进行合成，从而计算出屏幕上该像素点的颜色值。 这种方法是从反方向模拟光线穿过物体的过程，也称作逆向体绘制。 表2 1 主要的体绘制算法 分类物体空间方法图像空间方法 抛雪球法( s p l a t t i n g ) 。 光线投射法( r a y c a s t i n g ) 绘 深度缓存( z - b u f f e r ) 。，自适应采样( a d a p t i v es a m p l i n g 制 从前至后投影( f r o n t - t o b a c k ) 空间跳跃采样s p a c e l e a p i n g ) 方 从后至前投影( b a c k - t o - f r o n t ) 基于模板的光线投射法( t e m p l a t e - 法 。递推计算( i n c r e m e n t a l b a s e dv o l u m ev i e w i n g ) c a l c u l a t i o n ) 光线跟踪法( r a y t r a c i n g ) 光线投射算法【6 ，2 3 】是一种基于图像空间的经典体绘制算法，f l j l e v o y 提出。其 基本原理是根据视觉成像原理，构造出理想化的物理视觉模型，即将每个体素都 看成为能够透射、发射和反射光线的粒子，然后根据光照模型和体素的介质特性 得到它们的颜色和不透明度，并沿着视线观察方向积分，最后在像平面上形成具 有半透明效果的图像。光线投射体绘制算法有利于保留图像的细节，绘制高品质 的图像，特别适用于绘制区域特征模糊、体素特征相关性高的三维图像。图2 3 为 简化的体绘制模型。 山东大学硕士学位论文 图2 - 3 简化的体绘制模型：体数据中的每个体素发出一条光线，并且吸收经过它的光线的一 部分，同时忽略散射光。像素值通过在光线上符个采样点的体素值计算得到。 抛雪球算法是一种基于物体空间的经典体绘制算法，它首先由w e s t o v e r 提出， 其原理【2 4 】是先选择重构核，预计算通用足迹表( f o o t p r i n t ) ，然后将体数据转换到 图像空间，查表找出体素对于像素的贡献值，最后合成图像( 如图2 4 所示) 。抛 雪球算法最大的优点是只有与图像有关的体素才会被映射到像平面，从而可以大 大地减少需要处理和存储的数据量【2 5 1 ，从而提高了绘制速度并且减小了内存消耗。 图2 - 4 抛雪球法， ( 来源于文献【2 6 】) 光线投射算法与抛雪球算法都存在一个问题，就是计算量大、计算时间长。 理论分析和试验测试都表明，丰要的计算量用于三维离散数据场的重新采样上。 每一种体绘制算法都有不同的分割，可利用不透明度得到物体整体层次结构的特 点。t u 是这些算法由于基本原理的不同，牛成的图像质量和绘制速度，以及对配 置的要求都有很大的不同。在实际应用中可根据现有的硬件条件与具体的应用要 求，选择相应的算法来匹配图像质量与绘制速度之间的最佳方案。 1 6 山东大学硕士学位论文 1 4 体绘制加速技术 用体绘制来可视化三维数据是一种高效率且灵活多变的方法，但它的一个关 键弱点阻止了它的广泛应用，即现存的体绘制算法在计算代价上过于昂贵。体绘 制的高额计算代价源自典型数据集的过于庞大。一个几兆字节的数据集是很常见 的事，对如此大的数据集进行交互式的体绘制需要极大的处理器能力和极高的存 储器带宽。人们经常采用的加速体绘制的方法包括：以图像的质量来换取速度， 利用专门的硬件设施，以及利用多处理器的并行方法。为了加快体绘制速度，人 们提出了许多优化方法。下面本文分别从软件的角度和硬件的角度来介绍体绘制 加速的方法。 一、基于软件的体绘制加速方法 1 数据场的组织 由于数据场中各种物质的分布有一定的连续性，因此对数据场进行一定的组织 可以在成像时减少很多计算量。八叉树结构就是常用的一种组织方式，它迭代地 将数据场空间及其了空间进行上下、左右、前后的均匀剖分，形成下一层的8 个子 空间，直至予空间的大小是一个数据样点的尺寸。最底层树结点的函数值就是相 应样点的值，而上层树结点的值是它的予结点值的平均值口7 1 。有时，上层树结点 还保存它相应的数据场予空间数据值的最大值和最小值及其它相关参数【2 8 ，2 9 3 们。这 样，由于较高层次的树结点数目少于原数据场的样点数目，基于它们进行成像操 作时可以提高速度。虽然此时的图像质量要受到影响，但可以方便研究人员对数 据场进行快速的浏览。为使树结点的函数值能更好地反映数据场，可以将l a p l a c i a n 变换、小波变换等与八叉树结合起来【3 i 】。从节省存储空间和空间剖分的自适用方 面考虑，可以用二叉树、四叉树等对八叉树进行改造【3 2 】。 2 光线与数据的求交 体绘制成像的过程中，需要在光线的路径上求取数据样点，这一过程就是光线 与数据单元求交的过程。到目前为止，已经出现了很多快速求交的方法。 k a u f m a n e 等人针对规则数据场提出了一种基于模板( t e m p l a t e ) 的方法【3 3 】。该 方法利用了如下特性：规则场中的数据网格整齐排列，一条光线与这些网格相交 的情形呈周期性出现。因此可以将这种周期性作为一个模板使用，从而大大加快 山东大学硕士学1 立论文 了求交的运算速度。 g a r r i t y 针对非规则场提出了一种利用相邻数据单元的共享面来加速求交的方 法【3 4 1 ，即光线离开一个单元的出点就是进入相邻单元的入点，由此关于一个单元 的求交计算可以只考察它的多面体面片。 f r u h a u f 宅t 对弯曲数据场提出一种方法【3 5 1 ，该方法将数据场变换到规则场，同 时将直线型的光线变换到规则场空间的曲线，以便在规则场中为光线快速求取样 点。 3 插值计算 由于数据场是离散的，因此光线上的采样点往往不能正好位于数据场的网格顶 点上，需要对采样点进行插值计算。当一条光线在规则场的一个数据网格中沿着 其行走路径进行等距采样时，这些样点的数值可以通过依次进行的增量迭加计算 来获得。为此，文献 3 6 提出了一种增量方法来加快插值计算，但关于增量参数的 计算必须在各个数据网格中分别进行。因此，只有当一条光线在每个数据网格中 的采样数比较多时，该增量计算的方法才能发挥积极的作用。 4 排序 体绘制成像过程中，对数据进行排序是非常重要的一个步骤。对规则场而言， 由于网格的规则性，数据之间的前后关系很容易确定，n o v i n s 提出了规则场数据排 序的一个算法【3 7 】，根据成像方向嫩标分量的大小及正负就可以确定数据处理的顺 序，保证每个数据只能在它前面的数据都处理完以后才会被处理。对于非规则场 的数据排序比较网难，因为其数据单元的形状、大小及分布都是不一致的，特别 是凹多面体的形状更增加了排序的复杂度。g i e r t s e n 提出对非规则场进行平行平面 的扫描分割，然后在每个扫描的面上对多边形进行排序，以便将三维空间的排序 操作转换为二维平面上的操作38 1 。s i l v a 等人进一步发展了该方法【3 9 1 ，省去了许多 转换和排序的操作。还有一些其他方法，比如利用数据单元之间的拓扑关系进行 排序m 】，利用二叉树建立数据单元之间的关联并排序【4 1 】等。 二、基于硬件的体绘制加速方法 1 基于硬件的处理 为使可视化技术在实践中得到充分的发挥，实时交瓦的成像操作是非常重要 的。一般而言，硬件的计算速度要快于软件。因此，许多学者致力于研究体绘制 山东大掌硕士学位论文 鼍曼曼曼量詈置| 皇皇皇皇曼鼍詈皇i i i i l oi 量鼍量暑詈置量鼍量 系统的硬件结构。目前，这方面最重要的成果是v o l u m e p r o 系统。它运用光线投射 方法对数据场进行逐个切片方式处理，可以对大小为2 5 6 3 个样点的数据场进行实 时体绘制。 一般计算机上都有纹理映射的硬件，因此有许多关于利用纹理映射硬件来加速 体绘制的工作。许多文献专门讨论了如何用二维或三维纹理来表示数据场。 2 并行体绘制 并行处理是提高计算速度的一种重要方法。并行处理的基本思路就是将一个任 务划分为不同的部分分配给不同的处理器同时处理。并行体绘制算法中的任务划 分方法一般有两类：基于物体空间的划分和基于图像空间的划分。前一种方法中， 每个子进程存储一组二维体数据切片，该方法的优点是存储消耗小，但由于在射 线投射法中，每一条射线的计算可能与所有的切片相关，因此每一条射线的计算 可能需要几个予进程的存储数据，增加了通信的负担，且由于旋转时的视线方法 不断变化，给编程和计算带来了困难，时间开销较大。在后一种划分方法中，每 个予进程对应于一个图像了块，进程间具有很高的独立性。本文后面将详细介绍 基于图像空间划分的并行体绘制算法的具体实现。 第二节规则数据场体绘制算法加速的一般方法 2 1 减少对空体元的采样或投影 因为通常数据场中存在着大量的空体元，这些空体元由于不透明度为0 ，在采 样过程中没有产牛任何作用，因此对数据场进行体绘制后所产牛的最终图像并没 有任何影响，所以如何避免对空体元的盲目采样或者在投影过程跳过空体元是加 速体绘制算法的关键 4 2 1 。因此就有了基于空间枚举的加速光线投射算法【4 3 1 、基于 空间跳跃的体绘制算法【4 4 1 、体元块投影算法【1o 】等避免对空体元进行采样的方法， 从而可以大大加速体绘制的过程。如基于空间枚举的加速光线投射算法的思想就 是对数据场进行分类之后，对数据场的不透明度b u f f e r ，再利用八叉树对二分b u f f e r 进行组织( 此处所谓二分b u f f e r l j j 下一个对所有体元标记是否为空的三维数据，若 为空$ 1 j b u f f e r 中的值为0 ，若不为空贝l j b u f f e r 中的值为1 ) ，从而利用八叉树跳过大的 1 9 山东大学硕士学位论