（信号与信息处理专业论文）基于gpu的光线投射算法研究.pdf

摘要 于葡要 科学计算可视化广泛应用于医学、地质勘探、气象学、分子模型构造、计算 流体力学、空间探测和有限元分析等领域。在众多科学计算可视化方法中，光线 投射算法因其重建图像质量高而占据着重要的位置。但是传统的基于c p u 的光线 投射算法绘制速度较慢，限制了它的应用。因此探索如何提高光线投射体绘制的 速度和质量，对于完善可视化理论、拓展体绘制的应用等都有重要的理论和实践 意义。 针对多步光线投射算法的不足，本文首先实现了一种基于g p u 的单步光线投 射算法，绘制包围盒前后面各一次即可得到投射光线的参数，只需一个片段程序 就可以完成光线入射点和方向的生成、光线投射、光线终止( 以及提前终止) 的判断、 颜色和阻光度的积累等。实验结果表明，该算法能大大减小光线投射过程的复杂 性。 为了提高绘制速度，本文提出了一种基于空间跳跃技术的加速算法，利用八 叉树组织体数据，得到体数据的统计信息，绘制时依据当前传递函数跳过对重建 图像无贡献的空体素，从而实现加速。实验结果表明，该算法能有效跳过体数据 内部的空体素，显著提高内部包含大量空体素的体数据的绘制速度。 基于空间跳跃技术的加速算法不能显著提高内部只包含少量空体素的体数据 的绘制速度，而且需要额外生成两个纹理，占用了显存资源。为此，基于体数据 分块的思想，从平衡顶点处理器和片段处理器负载的角度出发，提出了一种基于 紧致包围盒的加速算法。该算法利用八叉树子分体数据，依据当前传递函数生成 紧致包围盒从而排除对重建图像无贡献的空体素。实验结果表明，该算法能显著 提高内部或外围包含空体素的体数据的绘制速度。 在基本算法和加速算法的基础上，本文实现了几种高级算法。其中包括最大 密度投影，离散等值面重建( 多种着色模式) 等，最后基于立方b 样条滤波器实现了 一种等值面曲率重建算法。实验结果表明，基于g p u 的光线投射算法在实现高质 量重建的同时也能达到实时交互的绘制速度。 关键词：g p u 光线投射空间跳跃紧致包围盒立方b 样条 a b s t r a c t a bs t r a c t 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 ) i sw i d e l yu s e di nm e d i c i n e ，g e o l o g i c a l e x p l o r a t i o n ，m e t e o r o l o g y , e ta 1 i nt h es t u d ym e t h o d so fv i s c ，r a y c a s t i n gp l a y sa n i m p o r t a n tr o l eb e c a u s eo ft h eh i g h - q u a l i t yr e c o n s t r u c t i o ni m a g e s h o w e v e r , t h e t r a d i t i o n a lc p u b a s e dr a y - c a s t i n gi st o os l o wf o rw i d eu s e t h e r e f o r e ，r e s e a r c ho nh o w t oi m p r o v et h er e n d e r i n gs p e e da n dq u a l i t yo fr a y - c a s t i n gi ss i g n i f i c a n tt op e r f e c tv i s u a l t h e o r ya n de x p a n di t sa p p l i c a t i o na r e a s a i m i n ga tt h ed i s a d v a n t a g eo ft h em u l t i - p a s sr a y - c a s t i n g ，as i n g l e p a s sr a y - c a s t i n g a l g o r i t h mi si m p l e m e n t e df i r s t l yi nt h i st h e s i s r e n d e r i n gf r o n tf a c ea n db a c kf a c eo n c e c a ng e tt h er a yp a r a m e t e r s o n l yo n ef r a g m e n tp r o g r a mi sn e e d e dt og e n e r a t ee n t r y p o i n ta n dr a yd i r e c t i o n ，i m p l e m e n tr a ym a r c h i n g ，r a yt e r m i n a t i o n ，c o l o ra n do p a c i t y a c c u m u l a t i o n ，e la 1 e x p e r i m e n t a lr e s u l t ss h o wt h ea l g o r i t h mc a l lr e d u c et h ec o m p l e x i t y o fr a yc a s t i n ge f f e c t i v e l y i no r d e rt oi m p r o v et h er e n d e r i n gs p e e d ，a na c c e l e r a t i o na l g o r i t h mi sp r o p o s e d b a s e do ns p a c el e a p i n gt e c h n o l o g yi nt h i st h e s i s o c t r e es t r u c t u r ei su s e dt oo r g a n i z e v o l u m ed a t a a f t e ro b t a i n i n gt h ed a t as t a t i s t i c s ，t h ev o x e l sn o n c o n t r i b u t i n gt of i n a l i m a g ec a nb es k i p p e da c c o r d i n gt ot h ec u r r e n tt r a n s f e rf u n c t i o n ，t h e nt h er e n d e r i n gi s s p e e d e du p e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mc a ne f f e c t i v e l ys k i pt h e i n t e r n a ln o n - c o n t r i b u t i n gv o x e l s ，a n ds i g n i f i c a n t l ys p e e du pt h er e n d e r i n go fv o l u m e d a t aw h i c hc o n t a i n sal a r g en u m b e ro fn o n - c o n t r i b u t i n gv o x e l si n t e m a l t h ea c c e l e r a t i o na l g o r i t h mb a s e do ns p a c el e a p i n gc a n ts p e e du pt h er e n d e r i n go f t h ev o l u m ed a t aw h i c hc o n t a i n so n l yas m a l ln u m b e ro fn o n c o n t r i b u t i n gv o x e l si n t e r n a l ， a n dt w oa d d i t i o n a lt e x t u r e sa r en e e d e d ，w h i c ht a k e su pm e m o r yr e s o u r c e s t h e r e f o r e a n o t h e ra c c e l e r a t i o na l g o r i t h mi sp r o p o s e db a s e do nc o m p a c tb o u n d i n gb o x ，w h i c h d e r i v e sf r o mt h et h i n k i n go fv o l u m ed a t as u b d i v i s i o na n dt h ep o i n to fk e e p i n gl o a d b a l a n c eo fv e r t e xp r o c e s s o ra n df r a g m e n tp r o c e s s o r v o l u m ed a t ai ss u b d i v i d e dw i t h o c t r e es t r u c t u r e ，a n dc o m p a c tb o u n d i n gb o xi sg e n e r a t e da c c o r d i n gt ot h ec u r r e n t t r a n s f e rf u n c t i o n s ot h ev o x e l sn o n c o n t r i b u t i n gt of i n a l i m a g ea r e e x c l u d e d e x p e r i m e n t a lr e s u l t si l l u s t r a t et h ee f f e c t i v e n e s so ft h ea l g o r i t h m o nt h eb a s i so fb a s i ca l g o r i t h ma n da c c e l e r a t i o na l g o r i t h ms e v e r a la d v a n c e d a l g o r i t h m sa r ei m p l e m e n t e d ，w h i c hi n c l u d em a x i m u mi n t e n s i t yp r o j e c t i o n ，d i s c r e t e i s o s u r f a c er e c o n s t r u c t i o na n dc u r v a t u r er e c o n s t r u c t i o nb a s e do nc u b i cb s p l i n ef i l t e r k e y w o r d s ：g p ur a y - - c a s t i n gs p a c el e a p i n gb o u n d i n gb o x c u b i cb - - s p l i n e 西安电子科技大学 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：杀叠! 羔 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名： 导师签名： 日期：j 牛牛 f 日期：丝：! ：生 第一章绪论 第一章绪论弟一早珀 t 匕 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 m i n g ) 是2 0 世纪8 0 年代后期提 出并发展起来的一个新兴研究领域。可视化技术是运用计算机图形学、图像处理、 计算机视觉等方法，将科学、工程学、医学等计算、测量过程中的符号、数字等 信息转换为直观的图形图像并在屏幕上显示出来的理论、技术和方法。 科学计算可视化的应用领域十分广泛，几乎涉及自然科学技术的一切领域。 目前广泛应用的领域有医学、地质勘探、气象学、分子模型构造、计算流体力学、 空间探测和有限元分析等。 当前，科学计算可视化的研究内容和方向主要为：体可视化、流场可视化、 可视化人机交互、科学计算可视化的数学建模、可视化基本原理的研究、复杂对 象形状的建模和复杂数据集基于模型的可视化等。其中3 d 体数据可视化一直是科 学计算可视化研究的核心。本文的研究对象就是规则3 d 标量体数据的可视化。 3 d 体数据可视化方法可分为三类：面绘钝j l j ( s u r f a c 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 ，d v r ) 和混合绘f l ；u ( h y b r i dr e n d e r i n g ) 。 面绘制的基本思想是利用3 d 体数据构造出中间几何图元( 如三角面片) ，然后 再用传统计算机图形学中的明暗模型等技术进行渲染。面绘制的图像不能反映原 始体数据的全貌和细节，但是可以产生较清晰的等值面图像。最著名的是由 l o r e n s o n 和c l i n e 在1 9 8 7 年提出的移动立方体( m a r c h i n gc u b e ，m c ) 算法。 d v r 算法与面绘制算法完全不同。d v r 不构造中间图元，而是直接由3 d 体 数据生成2 d 图像，然后显示在屏幕上，是近年来发展迅速的一种3 d 体数据可视 化方法【2 1 。由于d v r 中没有模型的概念，绘制单元是3 d 体数据中的单个体素， 因此对于没有精确的刚性模型的物体数据、模型结构未知的物体数据、模型结构 非常复杂的物体数据，以及需要观察数据内部信息的应用，d v r 技术具有很大的 优势，在工程测绘、医学影像、气象天文、地质勘探等诸多领域得到广泛的应用。 d v r 能够根据用户需求，选择感兴趣的组织或结构( 如人体骨骼) ，绘制的图像包 含体数据的完整信息，更加直观方便。另外d v r 能生成高质量的图像，也便于并 行处理。但是，d v r 的无模型绘制模式使得确定物体边界非常困难，通常无法获 得层次非常清晰分明的绘制效果；基于体素的绘制导致计算量很大，绘制速度慢， 限制了其在诸多领域的应用。 混合绘制是将面绘制和d v r 结合起来的一种绘制方法。如通过面绘制重建骨 骼，通过体绘制重建肌肉、血管等软组织。 2 基丁g p u 的光线投射算法研究 开展3 d 体数据可视化技术研究，探索如何提高体绘制的速度和质量，对于完 善可视化理论、拓展体绘制的应用领域等都有重要的理论和实践意义。 1 2 研究进展及现状 d v r 算法按照处理数据域的不同可分为变换域方法和空间域方法。前者是将 体数据变换到变换域，然后再进行处理显示；后者是直接对原始的体数据进行处 理显示。 基于变换域的典型算法有频域体绘制法( f r e q u e n c yd o m a i nv o l u m e r e n d e r i n g ) t 3 1 ，基于小波的体绘制法( w a v e l e t b a s e dv o l u m er e n d e r i n g ) t 4 1 。 基于空间域的算法又分为以物空间为序的算法和以像空间为序的算法。以物 空间为序的算法主要有：足迹法( f o o t p r i n t 或s p l a t t i n g ) 5 1 ，剪切一变形法 ( s h e a r - w a r p ) 6 1 ，基于硬件的3 d 纹理映射( 3 dt e x t u r e m a p p i n g ) 7 】。以像空间为序 的方法主要是光线投射( r a y - c a s t i n g ) 法f 1 2 - 1 5 ，这是本文的研究重点。 1 2 1 光线投射算法基础 光线投射算法是一种以图像空间为序的经典d v r 算法，由l e v o y l l 6 】1 1 7 】在1 9 8 8 年提出来的。其基本原理是，成像平面的每个像素沿着视线方向发出一条射线穿 过体数据，沿着这条射线等间距重采样，求出各重采样点的颜色值和阻光度，然 后按照由前向后或由后向前的方式合成射线上各重采样点的颜色值和阻光度，即 得到该像素颜色。原理如图1 1 所示。 成像平 图1 1 光线投射原理图 3 。体数据叫吐j 至亘三至至 叫吨二至至叵 _ 至三三 - 三至 卜叫丑2 。图像 图1 2 光线投射算法流程图 第一章绪论 采用后分类技术的光线投射算法的流程如图1 2 所示。 这罩的3 d 体数据指的是规则的标量体数据( 如c t 数据) 。下面依次介绍图1 2 中的各步。 1 、体数据预处理 在预处理阶段，对即将进入绘制流程的体数据进行简化、剔除、去噪、划分， 设计数据结构，向内存和显存装载数据，以及进行一些在绘制过程中不会动态变 化的辅助参数计算，使得真正进入绘制流水线的数据都是对最终结果有贡献的体 素，使得数据在通过绘制流水线的各个阶段时不会因为辅助参数的变化而受到影 响，使得在绘制过程中所用到的参数都是经过最优化选择后的结果。 预处理阶段并不真正属于绘制流程的一部分，但是通常对绘制性能的提升起 重要作用。很多加速算法都是在预处理阶段完成的，如旨在剔除无效体素的包围 盒( b o u n d i n gb o x ) 、八叉树编码( o c t r e ee n c o d i n g ) 、游程编码( r u nl e n g t he n c o d i n g ) 等技术的计算、构造都在预处理阶段完成。 除了进行性能优化，预处理阶段的一些工作对绘制结果也有着不可低估的影 响，其中最重要的是分害1 ( s e g m e n t a t i o n ) 。 2 、重采样 在体绘制中，我们取得的体数据都是以离散点( 体素) 的形式存在，而绘制的对 象本身却是连续的，将连续的对象通过仪器离散化为体数据的过程，称为采样 ( s a m p l i n g ) 。由于精度的要求，我们很难保证在绘制过程中所要处理的点恰好都是 体数据提供的体素。对于那些原始体数据中未能提供的点值，需要有一种计算方 法通过现有的体素求得体数据中的任意点值。为了达到这个目的，还原连续的体 数据是非常必要的，这个还原的过程称为重构( r e c o n s t r u c t i o n ) ，而在还原的连续体 数据中求得绘制过程中需要的离散点值称为重采样( r e s a m p l i n g ) 。重构只是一个概 念，在实际绘制过程中很难精确地重现连续体数据的原貌，并且也无法采用一种 数据结构把任何精度下的重构结果存储起来，因此重构是由重采样来体现的。重 采样是在确定数据点位置的时候，用插值( i n t e r p o l a t i o n ) 方法通过附近的体素数值近 似的确定该体素的数值。常采用的插值方法是三线性插值( t r i l i n e a ri n t e r p o l a t i o n ) ， 原理如图1 3 ，每个重采样点的值由其周围8 个体素的值决定。 图1 3 三线性插值示意图 4 基t - g p u 的光线投射算法研究 3 、分类 由于用于采集数据的各种仪器不具备人眼和人脑的颜色感受和辨别功能，因 此体数据是不能直接用于绘制的。这些数据或者是与采集对象相关的某种物理特 性，例如密度、亮度、高度等，或者没有具体物理意义，但是仪器容易采集到并 量化的参数。分类是一个映射过程，它将体数据中无法直接用于绘制的值映射成 为人眼可以识别和分析的光学特性，即颜色和阻光度。 分类和分割在体绘制中的作用类似。由于目前没有很好的分割方法，这里用 分类来代替。分类不能够准确反映绘制对象的结构，因为绘制对象的结构无法由 有限个数据特征唯一标示，如最简单的，如果绘制对象的不同结构在经过采集仪 器的离散化后处于不同的数据区间，那么设置不同的阈值，为每个阈值区间分配 一种光学属性即可，可是事实上，绘制对象不同结构对应的数据值都有重叠，因 此更多的数据特性如梯度、散度被用到分类操作中。分类技术不断发展，力求找 到一种方法可以清晰的标志绘制对象的不同结构，这个目标和分割不谋而合；另 一方面，虽然分类技术尚不能非常清晰的区分数据对象结构，但是为具有某些相 同属性的数据分配同样的光学特性，如实反映了数据对象存在的状态，绘制结果 并不会对用户判断造成误导。 分类是通过传递函数( t r a n s f e r f u n c t i o n ) 1 8 】【1 9 1 来完成的，最简单的1 d 传递函数 可表示为： 兄 瓯 b 。 以 = t f ( a t ) 其中砭、皖、最、4 分别代表颜色的红、绿、蓝分量和阻光度，对于数据 对象结构的描述，阻光度起了至关重要的作用，而颜色只是一个强调和美化的因 素，因此在传递函数的设计中阻光度是重点。口可以是标量，也可以是向量，根 据口分量数的不同，传递函数可以分为1 d 传递函数、2 d 传递函数和多维( 3 d 或 以上) 传递函数。1 d 传递函数的口是体素值，2 d 传递函数加入了其他的数据特征， 如梯度。传递函数维数的增加可以更好的标志体数据特征，但同时对存储空间的 要求和计算复杂度也呈指数级增长。 4 、着色 着色主要是模拟光在绘制对象的表面产生反射、折射、衍射等光学现象的过 程，是真实感图形绘制中不可缺少的操作，但在体绘制中并不是必需的。 着色效果与光照模型有关，广泛使用的光照模型是p h o n g 光照模型，其原理 在第五章介绍。 第一章绪论 5 、合成 合成是将多个有前后遮挡重叠关系的重采样点的光学属性沿光线传播的方 向，按照一定的规则作合并处理，最终形成像素的颜色。合成模拟现实世界中人 眼观察事物这一现象，因此每一像素对应的一系列有前后遮挡关系的重采样点是 随着观察方向不同而变化的。常用的图像合成方法有四种：最大密度投影 ( 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 ) 、x 光线投影( x r a yp r o j e c t i o n ) 、等值面重建 ( i s o s u r f a c er e c o n s t r u c t i o n ) 和阻光度融合( a l p h ab l e n d i n g ) 。m i p 和等值面重建将在 第五章介绍。 x 光线投影是将沿视线方向重叠的一系列重采样点的密度进行加总求平均， 作为该视线对应像素的密度值，如图1 4 所示。这种合成方法产生的图像效果类似 于医用的x 光成像。 密度值 采样位置 图1 4 x 光线投影示意图 阻光度融合( 简称融合) 是在体绘制中应用最广泛的合成方法，能产生高质量的 图像。融合将沿视线方向重叠的各个重采样点的光学属性根据绘制方程进行累积。 每个重采样点根据其位置和光学属性的不同，对最后的绘制结果或多或少都有贡 献。如图1 5 所示。 密度值 采样位置 图1 5 阻光度融合示意图 不同的光学模型有不同的绘制方程，常见的光学模型【2 0 1 有：光线吸收模型 ( a b s o r p t i o no n l y ) ，光线发射模型( e m i s s i o no n l y ) ，光线吸收与发射模型( a b s o r p t i o n p l u se m i s s i o n ) ，散射和阴影模蚕f 1 ( s c a t t e r i n ga n ds h a d i n g ) ，多重散射模型( m u l t i p l e 6 基y - g p u 的光线投射算法研究 s c a t t e r i n g ) 。光线吸收与发射模型是最常用的光学模型，根据融合方向的不同，可 以分为从前向后合成( f r o n t t o b a c k ) 矛o 从后向前合成( b a c k t o f r o n t ) 。光线投射算法 更适合采用从前向后合成方式，其公式为： 吒= g ”+ ( 1 一d f 一) c v q ( 1 2 1 o o 耐= p 。+ ( 1 - o i 。) d v 、7 其中：q 和魄为分别是合成之前的颜色值和阻光度，c 口甜和d o w 分别是合成 之后的颜色值和阻光度，c ，和d ，分别是当前重采样点的颜色值和阻光度。 1 2 2g p u v sc p u 早期的光线投射算法是通过软件实现的( 基于c p u 的光线投射) ，绘制速度慢。 随着硬件的发展，越来越多的基于g p u 的光线投射算法出现，其中最有代表性就 是k r u g e r t 2 1 1 和r o e t t g e r t 2 2 1 提出的算法。g p u 是专用的图形处理硬件，内部管线是 专门为图形处理而设计的。现代g p u 一般具备以下特征： 1 、并行架构。内部具有多条处理管线； 2 、独立的处理单元。可编程管线内部一般包括顶点处理器和片段处理器； 3 、高速存储器和存储接口； 4 、支持向量操作； 5 、专用的指令系统。 因此，相对于基于c p u 的光线投射算法，基于g p u 的光线投射算法具有更 多优点： 1 、自动计算投射光线与体数据的交点，而不用通过建立方程求交点，因此更 准确； 2 、硬件完成三线性插值，而不是通过软件实现，因此速度更快； 3 、快速实现浮点类型的颜色和阻光度合成，精度更高： 4 、算法的设计和实现可以做到与投影方式无关，而用c p u 实现时，两种投 影方式下的算法实现差别很大。 与此同时，目前在g p u 上实现光线投射算法，也存在以下不足： 1 、显存容量的限制； 2 、可编程性受处理单元计算能力限制，例如有限次数的循环； 3 、编程语言和模式单一，调试困难； 4 、不同厂商之间的硬件及扩展存在差别，导致算法可移植性差； 虽然在g p u 上实现光线投射算法还有上述限制，但是其优点是显而易见的， 而且随着硬件的发展，以上不足会逐步得到克服。因此本文的算法都是基于g p u 实现的。 第一章绪论 7 目前存在3 d 程序接口有o p e n g l 和d i r e c t x ，d i r e c t x 是m i c r o s o f t 的专有产 品，而o p e n g l 则具有良好的开放性和兼容性，适用于多种平台，其可编程管线 结构如图1 6 所示。因此本文算法都是基于o p e n g l 。 图1 6o p e n g l 可编程管线 1 2 3 光线投射加速算法概述 光线投射算法比较容易理解，采用为每个体素分配颜色和阻光度的方法来合 成图像，因此有利于保留图像的细节，生成高质量的图像。但正是因为需对每个 体素进行操作，从而限制了绘制速度。 基于g p u 的光线投射算法虽然能显著提高绘制速度，但对于较大规模体数据 的绘制还是很难达到实时，因此有必要探索光线投射加速算法，这也是本文的研 究重点之一。 针对基于c p u 的光线投射算法的加速技术主要有空间剖分( s p a c es u b d i v i s i o n ) 技术和光线相关。i 生( r a yc o h e r e n c e ) 技术两种【2 3 1 。 基于空间剖分技术的加速算法：如b s p 、o c t r e e 、k d t r e e 等算法，是从传统的 图形学领域延伸过来的。它们是利用数据空间的相关性，通过对数据空间进行剖 分，将连续的空体素划分到一定的包围盒中，当光线在体数据空间穿行时，碰到 这些包围盒只需进行简单的求交运算，就可以略过整个空体素的包围盒，从而减 少光线投射的步数，达到降低计算时间的目的。与基本的光线投射算法相比，基 于空间剖分技术的光线投射算法需要增加树搜索和包围盒求交运算，当非空体素 在数据空间的分布比较复杂时，空间剖分所产生的包围盒的数量将迅速增加，由 此而导致的预处理时间的增加以及大量的树搜索和包围盒求交运算将极大地降低 算法的效率。 基于光线相关性的加速技术是人们在对光线投射算法的特点进行深入研究的 基础上提出的。它主要是通过挖掘光线在体数据空间穿行过程的一些相关性的特 点，来减少光线投射的数量和穿行的步数，从而实现算法的加速。基于光线相关 甲由 - 基丁g p u 的光线投射算法研究 性的加速算法主要基于以下一种或几种原理【2 4 】：像空间相关性、物空间相关性、 光线间相关性、空间跳跃、序列间相关性。 1 、像空间相关性 基于像空间相关性加速算法的核心思想是，图像平面的像素之间存在着很高 的相关性，两个相邻的像素具有相似的，或者完全相同的颜色和深度。利用这种 相关性，可以采用有间隔的方式投射光线，对于不投射光线的像素采用一定的方 式来插值计算，从而达到算法加速的目的。最有代表性的有自适应重采样算法【2 5 1 。 2 、物空间相关性 基于物空间相关性加速算法的核心思想是，数据空间的体素之间存在着很高 的相关性，可以通过避免或减少在具有相同或者相近的物质区域内进行重采样的 次数来实现算法的加速。具代表性的是自适应调整重采样频率的方法【2 6 1 。 3 、光线间相关性 光线间相关性加速算法的核心思想是，在平行投影条件下，对于所有的光线， 虽然它们的起点不同，但它们具有相同的斜率，当光线在体数据空间穿行时，具 有相同的位移变化。y a g e l 等人充分挖掘了光线间的相关性，提出了基于模板的光 线投射算法【2 7 】。 4 、空间跳跃 当光线在体数据空间穿行时有两种状态，一种状态是在空体素( 透明体素) 中穿 行以搜索非空体素( 阻光体素) ，另一种状态是在非空体素中进行颜色和阻光度的累 积。由于在第一种状态下，空体素对于最终的显示结果没有任何影响，因此尽可 能快地跳过空体素，将显著地加快算法的速度同时对图像的质量不会带来任何影 响。实质上这也是基于空间剖分技术的加速算法的核心思想。p r o x i m i t yc l o u d s 算 法【2 8 】【2 9 1 是空间跳跃技术的一种非常优秀的实现方式。 5 、序列间相关性 当对重建物体进行旋转缩放等交互时，连续生成的图像之间存在着相关性， 利用前一副图像中的有用信息可以有效地加快当前图像的渲染速度。针对这一特 点，人们提出了相应的加速算法，；t r l c o o r d i n a t e b u f f e r ( c - b u f f e r l 方、法【3 0 】。b r a d y 等人 将c b u f f e r 方法进行了深入地推广，并引申到透视投影的成像方式中【3 。c h e n 等人 进一步发掘了序列间的相关性，提出了一种关键帧的方法【3 2 1 。 1 3 论文的研究内容及安排 本文在国家自然科学基金和9 7 3 项目基金的支持下，结合企业合作项目“3 d 医学影像工作站”，主要研究体绘制中的基于g p u 的光线投射算法、加速算法及 其应用。首先实现了一种基于g p u 的单步光线投射算法，减小了光线投射过程的 第一章绪论 9 复杂性。然后基于空间跳跃技术，提出了一种加速算法。着眼于前一种加速算法 的不足又提出了一种基于紧致包围盒的加速算法，最后实现了几种应用。本文的 主要创新点及成果如下： 1 、实现了一种基于g p u 的单步光线投射算法，减小了光线投射过程的复杂 性。 通过绘制包围盒前后面各一次得到投射光线的参数，在一个片段程序中就可 以完成光线入射点和方向的生成、光线投射、光线终止( 以及提前终止) 的判断、 颜色和阻光度的积累等。实验结果表明，该算法能大大减小光线投射过程的复杂 性。 2 、提出了一种基于空间跳跃技术的加速算法，提高了内部包含空体素的体数 据的绘制速度。 利用八叉树组织体数据，得到体数据的统计信息，绘制时依据当前传递函数 跳过对重建图像无贡献的空体素，从而实现加速。实验结果表明，该算法能有效 跳过体数据内部的空体素，显著提高内部包含大量空体素的体数据的绘制速度。 3 、提出了一种基于紧致包围盒的加速算法，提高了内部或外围包含空体素的 体数据的绘制速度。 基于空间跳跃技术的加速算法不能显著提高内部只包含少量空体素的体数据 的绘制速度，而且需要额外生成两个纹理，占用了显存资源。为此，基于体数据 分块的思想，从平衡顶点处理器和片段处理器负载的角度出发，提出了一种基于 紧致包围盒的加速算法。该算法利用八叉树子分体数据，依据当前传递函数生成 紧致包围盒从而排除对重建图像无贡献的空体素。实验结果表明，该算法能显著 提高内部或外围包含空体素的体数据的绘制速度。 4 、基于光线投射基本算法和加速算法实现了几种高级算法。 在光线投射基本算法和加速算法的基础上，实现了最大密度投影，离散等值 面重建( 多种着色模式) ，最后基于立方b 样条滤波器实现了一种等值面曲率重建算 法。结果表明，基于g p u 的光线投射算法在实现高质量重建的同时也能达到实时 交互的绘制速度。 本文的内容安排如下： 第一章主要介绍光线投射体绘制算法的研究背景及研究现状，最后给出了本 文的内容安排； 第二章实现了一种基于g p u 的单步光线投射算法，详细阐述了算法原理； 第三章提出了一种基于空间跳跃技术的加速算法，详细阐述了算法的实现过 程； 第四章在空间跳跃加速算法基础上提出了基于紧致包围盒的加速算法，并与 空间跳跃加速算法进行了比较，表明了其优越性； l o 基于g p u 的光线投射算法研究 第五章在基本算法和加速算法的基础上，实现了几种高级算法； 第六章全面总结本文研究成果以及存在的不足，指出后续研究工作的方向。 第二二章基丁g p u 的光线投射基本算法 第二章基于g p u 的光线投射基本算法 2 1 引言 近年来，随着图形处理器( g p u ) 由固定管线向可编程管线的发展，以及受g p u 的强大的浮点运算能力的驱动，许多基于c p u 实现的光线投射算法被加以改进， 以便能够在g p u 上运行。同时，人们也提出了一些新的基于g p u 的光线投射算 法，其中k r u g e r 2 1 】提出了一种多步( m u l t i p a s s ) 光线投射算法，该算法基于p i x e l s h a d e r2 0a p i 实现，其原理如下： p a s s1 ：渲染包围盒前面到纹理t m p ，生成光线入射点； p a s s2 ：渲染包围盒后面到纹理d i r ，然后启动一个片段程序，计算视口每个 像素投射的光线的方向，并将归一化的方向矢量保存到纹理d i r 的r g b 分量中， 方向矢量的长度保存到a l p h a 分量中； m a i np a s s3 - n ：再次绘制包围盒前面，得到光线入射点，采样纹理d i r 得到 光线方向，从入射点开始沿着该方向以一定的步长采样，并进行颜色和阻光度的 积累，结果保存到纹理r e s 。光线从入射点开始沿着光线方向前进m 步，在这之 间根据纹理d i r 的a l p h a 分量里保存的光线方向矢量的长度判断光线是否穿过体 数据，如果是则将阻光度值1 写入纹理r e s ； i n t e r m e d i a t ep a s s3 n ：再次绘制包围盒前面以启动一个片段程序，比较纹理 r e s 的阻光度值和预设的常量，以判断光线是否终止，如果终止则对深度缓存和 颜色缓存进行相应的设置。 可以看出，多步光线投射算法实现过程复杂。基于统一渲染架构级别的显卡 以及s h a d e rm o d e l4 0a p i ，本章对多步光线投射算法进行了改进，实现了一种单 步( s i n g l e p a s s ) 光线投射算法，渲染包围盒前后面各一次即可得到投射光线的参数 ( 光线方向和入射点) ，而且只需一个片段程序即可实现绘制，大大减小了算法实现 的复杂性。这主要基于统一渲染架构级别的显卡支持更多的循环和分支转移语句， 一个片段程序就可以完成光线入射点和方向的生成、光线投射、光线终止( 以及提 前终止) 的判断、颜色和阻光度的积累等操作。 2 2 单步光线投射算法 改进的单步光线投射算法主要由以下三部分组成： 1 、光线终点的生成：渲染包围盒后面( 沿当前视线方向) 到纹 b a c k ，从而得 到光线终点； 基丁g p u 的光线投射算法研究 2 、光线方向的生成：绘制包围盒前面，得到光线入射点。光线终点与入射点 的华标相减即得视口每个像素投射的光线的方向矢量； 3 、光线投射：从第( 2 ) 步中取得光线的入射点，沿光线方向按设定的步长采样， 并进行颜色和阻光度的积累。 其中( 2 ) 和( 3 ) 在一个片段程序l l 实现。f 面详细讨论以上各部分。 2 2 1 光线终点的生成 在0 1 ) e n g l 中每个多边形都有前后两个面，定义顶点以逆时针方向指定的面 为前面，则另一个面为后面。任何封闭的3 d 物体都可看作由多边形组成的，因此 3 d 物体的前后面由组成该3 d 物体的多边形的面决定。 绘制包围盒的后面，对于规则体数据，包围盒的3 d 大小由下式决定： = s i z e , x s p a c e f( 2 - 1 ) 其中fe y ，z ，s i z e , 为体数据沿i 方向的体素数量，s p a c e i 为该方向体索问 距，再将，归一化到 0 ，1 。 包围盒每个顶点的坐标分量与该顶点的纹理坐标分量以及颜色分量对应相 等。剔除包围盒前面可绘制后而。由于包围盒是凸的，视1 3 上每像素处不会对 应于两个或两个以上的包围盒前面，因此不需要深度测试。通过帧缓冲对象( f r a m e b u f f e ro b j e c t ，f b o ) 将结果渲染到纹理6 d 出，即得到光线的终点。结果如图21 所示。 一0 = ( a ) 包围盒的后面 ( b ) 包围盒的前面光线方向 鞫2 1 包围盒的渲染示例 2 2 2 光线方向的生成 再次绘制该包围龠，这次别除后面，同样不需要深度测试。不将结果渲染到 纹理，而是作为片段程序的输入。在片段程序中取得片段的3 d 纹理坐标，每个分 量乘以缩放园子( 3 d 纹理的坐标在【o ，l 】区问内) 作为该片段的光线入射点： s t a = 1 n t e x c o o 一s c a l e f a c t o r s ； ( 2 - 2 ) 其中s c a l e f a c t o r s i = l ，1 7 4 t e x c o o r d 来自于光栅器的输出，足经过硬件插值 第二章基于g p u 的光线投射基本算法 后的顶点纹理坐标。 将片段的空间坐标( 变换后的顶点坐标经硬件插值而来) 归一化到 0 ，1 ，归一化 公式如下： t e x c x y = ( ( 肼p o s x y i n p o s w ) + 1 ) 2 ( 2 3 ) 其中i n p o s 为光栅器的输出( 片段程序的输入) ，是顶点坐标经过模型视图投影 变换( 没有做投影除法) 后再经硬件插值而得到的。 t e x c 作为2 d 纹理坐标，查找纹理b a c k 得到光线终点，各分量乘以缩放因子 s c a l e f a c t o r s ，进而得到该片段的光线终点坐标。终点与入射点的坐标相减即为该片 段的光线方向加。图2 1 ( b ) 为绘制得到的包围盒的前面，没有渲染到纹理，而直 接用于启动片段程序，生成每一像素的光线方向，如图2 1 ( c ) 所示。 这种生成光线方向的方法与投影方式无关，无论是透视投影还是平行投影， 均可以通过前后两次渲染同一个包围盒得到片段投射的光线的方向和入射点。 2 2 3 光线投射 在片段程序中求得片段的光线方向矢量d r 的长度( 用于判断光线是否终止) ， 并将咖归一化，各分量乘以步长s t e p 就得到采样步长万。由此得到光线方程： ，- ( ，1 ) = s t a r t + n 万( 2 4 ) 其中r ( n 1 是重采样点的坐标，刀为重采样步数。 光线投射过程用一个循环语句就可以实现。光线从入射点开始，每前进一步， 就得到一个重采样点，- ( 门) ，用该重采样点的3 d 位置坐标采样3 d 体数据纹理，得 到该点的密度值。用该密度值查找传递函数纹理就得到该重采样点的颜色值和阻 光度。然后采用式( 1 2 ) 按照由前往后的合成方式对颜色和阻光度进行积累。并计 算下一个重采样点r ( n + 1 1 的坐标，光线矢量的长度也相应地减少s t e p 。 光线终止的条件：光线矢量的长度小于或等于0 。满足该条件时，光线终止。 光线提前终止的标准：阻光度积累到一定值( 如0 9 9 9 ) 。这在某种程度上可以 起到加速的作用。 2 - 3 算法实现 2 3 1 帧缓冲对象( f b o ) 在具体实现算法之前，先简单介绍一下帧缓冲对象( f r a m eb u f f e ro b j e c t ，f b o ) 。 f b o 可以用来实现离屏渲染( o f f - s c r e e nr e n d e r i n g ) ，在这里f b o 用来实现将对象 渲染到纹理。f b o 的使用步骤如下： s t e p l 建立f b