（计算机科学与技术专业论文）基于gpgpu的快速体绘制算法研究.pdf

基于g p g p u 的快速体绘制算法研究 摘要 作为科学可视化的一个主要领域，体绘制是一种直接由三维数据场产生屏 幕上二维图像的技术。本文以典型体绘制算法为基础，结合图形处理器可编程 性的特性，通过图形处理器通用计算完成体绘制中数据密集型的计算，加速其 成像过程。主要工作和创新点包括以下三个方面：提出一种基于硬件加速的光 线投射算法；在频率域体绘制中引入w i n d o w e d s i n c 函数作为滤波器实现高次 插值；设计并开发出大规模地震数据显示和解释系统。 首先，在对体绘制积分研究的基础上，分析基于图像顺序的体绘制算法的 特点，针对光线投射算法中光线遍历体数据较为耗时的情况，引入基于“厚板 的光线与包围盒求交计算，通过在图形处理器上的并行执行，得到每条光线的 进入点和离开点，最后采用从前往后的颜色累积运算，极大提高绘制速度。同 时，为了避免软件实现三线性插值的问题，引入三维纹理，实现硬件对体数据 的重采样。实验表明，在不影响成像质量的前提下，此算法能获得令人满意的 交互性。 其次，在基于域的体绘制方面，通过对傅立叶投影定理在高维依然成立的 证明，提出基于图形处理器通用计算的频率域体绘制算法。算法结合中央处理 器和图形处理器的多核异构体系，在中央处理器完成简单的文件读取和条件判 断的基础上，利用图形处理器实现傅立叶体绘制的全部流程。并使用 b l a c k m a n w i n d o w 函数作为滤波器在频率域实现高次插值，最终得到具有实时 交互性的图像。此算法在将算法复杂度从d 妒j 降为d f 2 z d g ) 的基础上，获得 近7 倍的加速比。 最后，在以上研究的基础上，设计并实现一个通用的、易于扩展的地震数 据可视化系统。该系统以插件的方式实现对各类地震数据的显示和解释，并在 此基础上解决大规模数据管理、传递函数、数据裁剪、凹凸贴图等实际问题。 经多组数据验证，系统无论在绘制速度或是图像质量上均取得令人满意的效果。 关键词：体绘制：光线投射；傅立叶体绘制；多核异构；g p g p u 硕士学位论文 a b s t r a c t a so n eo ft h em a j o rn e l d so fs c i e n t i 6 cv i s u a l i z a t i o n ，v 6 l u m er e n d e r i n gi st h a t g e n e r a t e st w o - d i m e n s i o n a l i m a g ed i r e c t l yf r o mt h r e e - d i m e n s i o n a ld a t a t h i sp a p e r i sb a s e do n 够p i c a la l g o r i t h mo fv o l u m er e n d e r i n g ，a n di sc o m b i n e dw i t ht h e p r o g r a m m a b i l i t yf e a t u r e so fg p u t h ei m a g i n gp r o c e s si ss p e e du pb yg p g p u t o f i n i s ht h ed a t a - i n t e n s i v ec o m p u t i n go f 、，o l u m er e n d e r i n g t h em a i nc o n t e n ta n d i n n o v a t i v ep o i n t so ft h i sp a p e rc a nb eo u t l i n e da st h ef o l l o 谢n gt h r e ea s p e c t s ： p r e s e n t i n gar a y - t r a c i n ga l g o r i t h mw h i c hi sb a s e do ng p g p u ；i nf r e q u e n c yd o m a i n ， i n t r o d u c i n g w i n d o w e d - s i n cf u n c t i o na saf il t e r t o i n l p le m e n th i g h o r d e r i n t e r p o l a t i o n ；d e s i g n i n ga n dd e v e l o p i n gal a r g e s c a l es e is m i cd a t ad is p l a ya n d i n t e r p r e t a t i o ns y s t e m f i r s t ，b a s e do nt h es t u d yo fv o l u m er e n d e r i n gi n t e g r a l ，t h ei m a g e - b a s e dv o l u m e r e n d e r i n g a l g o r i t h mi sa n a l y z e d s i n c ei nt h er a y t r a c i n g a l g o “t h m ， t h er a y t r a v e r s a ld a t ai sm o r et i m e c o n s u m i n g ，“s l a b ”i si n t r o d u c e dt oc a l c u l a t et h e i n t e r s e c t i o nw i t ht h eb o u n d i n gb o x a f t e rg e t t i n gt h ee n t r yp o i n ta n dt h el e a v i n g p o i n to fe a c hl i g h t ，t h ec o l o rc u m u l a t i v ec a l c u l a t i o ni se x e c u t e d ，w h i c hg r e a t l y i m p r o v i n gt h er e n d e r i n gs p e e d a tt h es a m et i m e ，i no r d e rt oa v o i ds o f t w a r e i m p l e m e n t a t i o no ft r i - l i n e a ri n t e r p o l a t i o n ，t h r e e - d i m e n s i o n a lt e x t u r ei si n t r o d u c e d t 0i m p l e m e n tr e s a m p l eb yh a r d w a r e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h i s a l g o r i t h mc 柚o b t a i ns a t i s f a c t o 巧i n t e r a c t i v i t ) ，w i t h o u ta f f e c t i n gt h eq u a l j t ) ro ft h e i m a g e s e c o n d ，i na s p e c to fd o m a i n - b a s e dv o l u m er e n d e r i n ga l g o “t h m ，an e wf v r a l g o r i t h mi sp r o p o s e dt h r o u g he x p a n d i n gf o u r i e rp r o je c t i o n s l i c et h e o r e mi n t o h i g h - d i m e n s i o na n dm a p p i n gt h ep i p e l i n et o t a l l yo n ( j p u b l a c k m a n - w i n d o w e d f h n c t i o ni su s e da sr e c o n s t r u c t i o nf i l t e rt oi m p l e m e n th i g h e r o r d e ri n t e r p o l a t i o na n d t h er e d u c t i o no fs a m p l e si se x e c u t e do ng p ui n p a r a l l e l ， w h i c hm e e t st h e a r c h i t e c t u r eo fh e t e r o g e n e o u sm u l t i c o r e t h er e n d e r i n gi sa c c e l e r a t e db yaf a c t o r o f7a f t e rr e d u c i n gt h ec o m p l e x i 够o ft h ea l g o r i t h mf r o md mt od 价严，d g m l a s t ，o nt h eb a s i so ft h ea b o v e ，w ed e s i g n 锄dd e v e l o pav i s u a l i z a t i o ns y s t e mo f s e i s m i cd a t aw h i c hi sc o m m o na n da l s oe a s yt oe x t e n d t h ed i s p l a ya n d i n t e r p r e t a t i o no fd i f 先r e n t 锣p eo fs e i s m i cd a t ai si m p l e m e n t e db yp l u g - i n o nt h i s b a s i sw es o l v es o m ep r a c t i c a lp r o b l e m s ，s u c ha sl a r g e s c a l ed a t am a n a g e m e n t ， t r a n s f e rf u n c t i o n ， v 0 1 u m ec “p p i n ga n db u m pm a p p i n g b yav a r i e 够o fd a t a l i i 基于g p g p u 的快速体绘制算法研究 v a l i d a t i o n ，t h er e n d e r i n gs p e e da n dt h ei m a g eq u a h t yo fp l a t f b r ma c h i e v ev e r yg o o d r e s u l t s k e yw o r d s ：、，0 l u m er e n d e r i n g ； r a y - t r a c i n g ； f o u “e r 、，o l u m e r e n d e r i n g ； h e t e r o g e n e o u sm u l t i - c o r e ；( 狰g p u i v 硕士学位论文 插图索引 图2 1g p u 浮点运算能力8 图2 2 图形绘制管线1 0 图2 3c u d a 软件堆栈l l 图3 1 基于c u d a 的光线投射算法1 8 图3 2 空间坐标的建立2 0 图3 3 光线与数据体不相交2 1 图3 4 光线与数据体相交2 2 图3 5 光线投射算法绘制效果2 4 图3 6 三种加速算法的比较2 5 图3 7 图像质量比较2 6 图4 1 傅立叶投影定理2 8 图4 2g p g p u 上的傅立叶体绘制流程3 0 图4 3g p g p u 上求最值操作3 3 图4 4 绘制时间曲线图3 5 图4 5 傅立叶体绘制效果图3 5 图5 1 数据从低分辨率载入3 8 图5 2 正交切面和斜切面3 9 图5 3 感兴趣区域3 9 图5 4 凹凸贴图4 0 图5 5 不同传递函数下的绘制效果4 1 图5 6 红蓝绿颜色索引表4 2 图5 7 数据范围的设定4 2 图5 8 透明度的调节4 3 图5 9 抽象工厂模式4 5 图5 1 0 模块中三部分关系图4 6 图5 1 l 加速体绘制算法在系统中的应用4 7 图5 1 2 单窗口显示切面4 8 图5 1 3 多窗口显示4 8 图5 1 4 平铺窗口4 9 图5 1 5 立体支持4 9 l 基于g p g p u 的快速体绘制算法研究 附表索引 表3 1 光线投射算法结果2 5 表4 1c p u 和g p g p u 进行傅立叶变换3 0 表4 2 傅立叶体绘制实验结果3 4 i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：参垮殳日期：z 洮7 年岁月2 厂日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囱。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 同期：2w 了年堂月矿日 乏 日期： 矽年j ，月歹乡日 硕一 = 学位论文 1 1 研究背景及意义 第1 章绪论 科学可视化是在1 9 8 7 年正式提出并在计算机图形学基础上发展起来的一项 新技术，其思想是用直观的图形输出来代替枯燥的数据输出，借助人类强大的 视觉及形象思维能力，对数据进行本质上的理解。体绘制作为科学计算可视化 的重要分支，运用交互式图形学和图像处理技术从体数据中提取用户需要的信 息，主要研究体数据的表示、操作和绘制。体绘制不仅能显示高质量的图像， 更为重要的是能够比较清晰地显示出物体的内部结构，这是传统的计算机图形 绘制方法所无法做到的【l 2 】。 随着三维体数据的增大，特别是地震数据已经达到数百亿字节，这必将在 体绘制过程中产生巨大的运算量。仅仅依靠软件实现大规模体数据的可视化肯 定无法满足用户实时交互型的需求，所以利用硬件对其进行加速逐渐成为体绘 制技术研究的一个热点。 近几年来，g p u ( g r a p h i cp r o c e s su n i t ，图形处理器) 得到了迅速的发展，已 经从以往的固定流水线操作模式发展成可编程流水线模式，其编程指令经过了 三个版本的更新，逐步发展成为我们可以直接运用的功能强大且成本较低的并 行程序处理器。从系统架构上看，g p u 是针对向量计算进行了优化的高度并行 的数据流处理器，其中包括两种流处理单元：顶点处理流水线是多指令多数据 流的处理单元，像素处理流水线是单指令多数据流的处理单元。这种以数据流 作为处理单元的处理器，在对数据流的处理上可以获取较高的效率【3 】。 利用g p u 的高浮点运算能力和并行执行能力对体绘制算法进行加速，提高 体绘制的成像速度，改善用户交互体验逐渐进入了人们的视野。经硬件加速的 体绘制得到了迅速发展，在医学、石油地质勘探等诸多领域得到了广泛应用。 在医学领域，由核磁共振、计算机断层扫描等设备产生的人体器官密度场，对 于不同的组织，表现出不同的密度值。通过在多个方面多个剖面来表现病变区 域，使医生对病变部位的大小、位置，有定性和定量的认识，尤其是对大脑等 复杂区域，体绘制可视化所带来的效果尤其明显。借助虚拟现实的手段，医生 可以对病变的部位进行确诊，制定出有效的手术方案，并在手术之前模拟手术。 在临床上也可以应用在放射诊断、制定放射治疗计划等。在气象领域，体绘制 可视化技术可以将大量的天文气象数据转换为直观的图像，使预报人员能对未 来的天气做出准确的分析和预侧。在地质勘探领域，利用模拟人工地震的方法， 可以获得地震岩层信息。通过数据特征的抽取和匹配，可以确定地下的矿藏资 基于g p g p u 的快速体绘制算法研究 源。由于地震数据的数据量及其庞大，而且分布高度不均匀，因而根本无法从 纸面数据做出分析。利用加速体绘制方法对模拟地震数据进行解释，可以得到 矿藏是否存在、矿藏位置及储量大小等重要信息，大大地提高地质勘探的效率 和安全性，节约资金，具有重大的经济效益及社会效益【4 1 。 1 2 国内外研究现状 体绘制或者直接体绘制就是从三维体数据中产生二维图像的过程。此类方 法与基于表面的体绘制不同，它直接操作于实际的数据采样点而不产生任何几 何面。由于体绘制技术能够透过物体表面看到其内部信息，在国内外得到了广 泛的研究及发展。主要包括以下几个方面： 1 绘制算法的多样性 进过多年的发展，体绘制已从最初的空间域中，发展到频率域、压缩域以 及小波率在内一些变换域中。并形成了光线投射法、足迹法、剪切曲变法、傅 立叶体绘制等一系列典型绘制算法。 n i n g 和h e s s e l i n k 首次在空间域中使用矢量量化来压缩数据体，然后使用常 规体绘制算法直接绘制量化后的块【5 】。m u r a k i 最先使用小波变换来处理体数据， 并通过三维小波变换从实际体数据中产生1 1 5 张磁共振图片【6 1 。e n t e z a r i 等【7 】 在其论文中阐明了傅立叶体绘制模型，他们将不同的光照引入到傅立叶体绘制 算法中，一种方法是基于“伽玛纠正半球形阴影”此方法适应在固定光源中进 行实时绘制，另一种是“球面调和函数”允许使用不同的光源。c h i u e h 等利用 三维哈特莱变换扩展了静态j p e g 图像的压缩算法，用以压缩数据体的子块， 并且在最终图像合成之前使用频率域体绘制技术来绘制每个子块。通过这种方 法，他们缓解了在频率域绘制过程中出现的缺乏衰减和闭塞的问题，与空间域 中的绘制相比提高了压缩率，加快了绘制速度，与连续频率域技术相比改进了 图像的成像质量【8 1 。w e s t e r m a n n 将体绘制与小波压缩进行了整合【9 1 。g u t h e 和 s t r a s s e r 使用小波变换绘制大规模体数据，并且可以得到理想的帧率。他们首先 使用小波金字塔将体数据进行编码，接着将体数据解码成不同分辨率的小块。 其中，每一小块的分辨率都是基于局部误差和投影面的分辨率大小来设定的， 每一块都利用三维纹理来分别绘制【10 1 。张尤赛、陈福民【1 1 】描述了光线投射法、 足迹法、剪切曲变法、基于硬件的3 d 纹理映射、频域体绘制法和基于小波的 体绘制等典型算法，给出了各类算法的性质评价，展望了体绘制技术研究的发 展前景。 2 针对体绘制加速的研究 体绘制属于一种实时绘制技术，为了满足在实际操作中交互型的需求，就 需要根据体绘制算法的特征，利用软硬件对其进行加速。 2 硕十学位论文 在软件加速方面，通常是利用复杂的数据结构或是根据体数据的特征对算 法进行简化。黄展鹏等【l2 】使用线性八叉树来对物体进行空间剖分，跨越体数据 集中的空体素。并针对光线穿越体数据时的特殊情况，改进线性八叉树邻域查 找的方法，特别是不同尺寸的邻域查找方法，克服了层次八叉树邻域查找的低 效率，同时提出了光线离开平面的简洁判定方法，方便光线下一个采样点的计 算。陈慧、何兴恒则引入了层次细节度技术，建立细节层次模型降低数据量和 复杂度【13 1 。 在硬件加速方面则主要利用硬件在某些方面计算的优势，对相应算法进行 改进，使其满足硬件加速的条件。此种技术不依赖具体的体数据，具有较高的 通用性。自从1 9 9 4 年c a b r a i 等提出了基于3 d 纹理映射硬件的直接体绘制方法 后【1 4 】，该方法就因其具有高绘制效率而引起广泛兴趣，已成为最重要的直接体 绘制方法之一。k r u g e r 等则将传统的多遍纹理合成技术与可编程g p u 绘制相 结合，并集成空域跳过和提前终止光线等加速绘制算法，提出了一个实时而高 质量的g p ur a yc a s t i n g 体绘制算法【1 5 】。s t e g m a i e r 等【1 6 1 在单遍绘制算法的基础 上，提出了一种混合图像物体空间的空域跳过加速算法，极大的提升了绘制速 度。 1 3 本文主要工作 基于上述背景，来源于国际合作项目“地震数据可视化系统 ，本文对体绘 制加速算法做了一定的探索。为了能够较好的反映数据场的整体结构，更好的 显示局部细节，得到质量较高的图像，在光线投射算法上做了相应的研究。同 时为了解决随着数据体增大，绘制效率急剧下降的问题，对频率域中计算复杂 度为d r 2 ，d 删的傅立叶体绘制算法进行了加速。为了在地质勘探领域发挥加 速体绘制算法的作用，最终开发出基于硬件加速的可视化系统。 本文的主要工作体现在以下三个方面： 首先，分别利用三维纹理和一维纹理来存贮三维体数据和传递函数，在g p u 上快速实现光线与体数据包围盒的求交计算。从而降低光线投射算法中遍历每 个体素的时间。在保证最终图像质量的前提下，得到令人满意的加速比。 其次，在对空间域中体绘制算法进行加速的基础上，进一步研究频率域中 的体绘制算法。引入b l a c k m a n w i n d o w 函数在频率域对三维体数据进行高次采 样，避免混叠现象，成功的将算法复杂度由d 帕降为d 酽z d 删。 最后，基于以上研究，开发出跨平台的大规模地震数据显示与解释系统， 并提供多种几何模型来对各种地震数据进行相关的显示。 硕l 学位论文 1 4 本文的结构 全文分五章，结构安排如下： 第一章概述了本文的研究背景、目的及意义，主要工作和组织结构。 第二章详细介绍了体绘制技术的发展，各类算法的优缺点，以及g p u 的特 性。在系统架构上阐述了基于多核异构的算法实现。 第三章在介绍了体绘制积分、帧缓存对象的基础上，从实现的角度，阐述 了一种基于g p u 加速的光线投射算法的实现，详细介绍了在g p u 上实现光线 求交的过程。 第四章对于频率域的体绘制算法进行了讨论，通过引入w i n d o w e d s i n c 函数 以及g p u 上进行卷积运算，完成了基于图形处理器通用计算的傅立叶体绘制算 法。 第五章根据实际需求，开发出大规模地震数据显示与解释系统，并根据实 际地震数据可视化过程中所会遇到的问题进行讨论。 最后是全文的总结和展望。 4 硕士学位论文 第2 章体绘制技术与g p g p u 概述 体绘制方法需遍历三维数据场中的每一体素，因而计算量大，图像生成速 度慢，并且每当外部光照和视角发生变化时，整个绘制过程需要重新开始，难 以满足实际应用中实时绘制和交互显示的需求。为此，人们在以往体绘制方法 的基础上又提出了很多加速方法，但实际应用中所需处理的数据规模通常比较 庞大，单纯依靠改进体绘制软件算法来提高显示速度无法从根本上解决问题。 于是，人们开始求助于硬件，利用高档图形工作站提供的由硬件实现的三维纹 理映射功能来实现体绘制过程中的某些环节，从而大大提高了绘制速度，使得 实时绘制成为可能，但高档图形工作站价格昂贵，不利于广泛推广。近年来， 在游戏和娱乐市场的巨大推动下，计算机图形硬件方面的技术不断进步，性能 不断提高。各大硬件厂商所提供的显示芯片不仅提供灵活的光栅化硬件，而且 还具备可编程能力，能较好地支持多纹理、单像素光照运算、纹理获取等先进 的绘制技术，图形硬件的可编程能力使得用户可以根据自己的要求为硬件定制 较为复杂的渲染程序，产生逼真的复杂的图像效果。以往在图形工作站上实现 的许多体绘制方法经过改进后可以由后期的个人电脑图形硬件来实现，不但可 以获得较高的绘制速度和性能，而且硬件成本也大大降低，应用个人电脑作为 可视化平台已表现出明显的趋势。 2 1 体绘制技术分类 体绘制可以被分为“基于图像顺序”，“基于物体顺序一和“基于域”的几 种技术。基于物体空间顺序的体绘制使用向前映射的模式，体数据被映射到图 像上。基于图像顺序的体绘制则使用向后映射的模式，光线从图像上的每个像 素点投射到体数据中以决定最终的像素值。在基于域的体绘制中，空间域中的 体数据先被转换到其他域中，如频率域、小波域等，然后直接在这个域中产生 投影【17 1 。 基于图像顺序的技术 这种技术共有四种绘制模式：x 射线绘制、最大亮度投影、等值面绘制和 全部绘制【埽】，其中第三种模式是第四种的特例。这四种模式都有两个相同的操 作：l 、光线从图像像素中投射出来，沿着光线的方向对网格中的离散位置进行 采样。2 、采样点通过插值取得。几种模式的不同地方是采样点如何沿着光线的 方向进行融合。在x 射线中，插值得到的采样点仅仅是进行简单的相加，最大 亮度投影只是把最大值的采样点写到像素中。在全部绘制中，插值得到的采样 点要经过进一步的处理来模拟光线穿过物体的情形。 硕。 = 学位论文 基于物体顺序的技术 这种技术是将体数据分解成一些基本元素，然后分别将其投影到屏幕上， 最终组合成图像。由于x 射线绘制和最大亮度投影只需要计算累积和或是最大 操作，所以在这两种绘制模式下基本元素能以任意顺序投影。而在通常的绘制 模式下则需要考虑到深度的影响。在基于物体顺序的投影中，需要将体数据逐 层、逐行、逐个的计算每一个数据点对图像平面的贡献，并加以合成，形成最 终的图像。体数据则可以按照图像平面由近到远的顺序投影，也可以按照由远 到近的顺序进行投影【i 引。 为了确定每一个体素对最终图像的贡献，最有效的方法则是采用预积分的 方式将结果保存在一张查找表中，这张表又被称为足迹表，期间的投影过程则 被称为溅射。这种方法最大的优点是只有与图像有关的体素才会被映射到图像 平面，从而大大地减少需要处理和存储的数据量，从而提高绘制速度并且减少 了内存消耗。足迹表法用经过一个足迹样条的采样均值来代替光线投射法的点 采样，这相当于引入一个低通滤波器对信号进行平滑滤波，一方面有利于克服 图像的失真或混叠，但另一方面有时会使图像的高频分量受到衰减，由于足迹 算法要访问尽可能少的提速以提高绘制速度，所以产生的图像质量不如光线投 射等基于图像顺序的体绘制算法。 基于域的体绘制技术 基于域的体绘制中，空间域中的三维体数据先要被转换到其他域中，如压 缩域，频率域或是小波域，然后根据这个域中的信息直接产生相应的投影面【2 0 1 。 这种方法根据三维体数据的频谱得到三维体数据的投影，将体绘制的计算复杂 葭队o f 耐) 降为o 醑1 0 9 n 基于压缩域的绘制则直接作用于压缩后的标量数据，无需将整个数据体解 压，这样就降低了存贮空间和运算复杂度。基于小波域的绘制技术主要是运 用小波定理【2 。小波的优点就是无论是在空间域还是在频率域都有局部属性， 并且可以通过一些小波系数完美的反映出整个数据体。 目前，基于域的算法继承了体绘制算法的优点且具有运行速度快的优点， 越来越受到人们的高度重视，得到了快速发展，但在以下三个方面还有待提高： ( 1 ) 没有空间域体绘制的光照效果。其采用基于半球形光源模型的方向光照方 法，在此光照模型中，体元的颜色取决于光源颜色，而不是像传统光照模型一 样取决于物质分类结果。( 2 ) 缺乏深度信息或遮挡效果，只把投影图像简单地视 为沿视线方向的线性积分，使得绘图效果呈x 光片效果。( 3 ) 在数据预处理之后， 传递函数就不能再与系统进行交互使用了【2 2 1 。 6 硕士学位论文 2 2g p g p u 加速技术 由于体绘制算法的绘制对象是三维体数据的全部结构细节而不是某一特定 表面信息，绘制复杂度通常比较大，难以满足实时显示和交互的要求，因此必 须与相应的加速算法和策略相结合。现有的体绘制加速技术可以分为两类：软 件加速和硬件加速。其中软件加速对体数据进行删减，或是对体绘制算法流程 进行简化和调整，部分软加速技术是以损失绘制的质量为代价来实现加速的， 部分则是只适用于某些特定情况。然而在保持图像质量的前提下，仅仅依靠软 件加速很难达到实时绘制与交互的要求。相对软件加速，硬件加速不依赖原算 法的实现，充分硬件固有的特性，加速性能很突出。文献【2 3 】在c e l l 处理器上 实现了光线投射的并行算法，文献【2 4 】则在提出了一种半自适应分块的方法对 原始数据进行分块，同时使用图形硬件来进一步加速整个算法的绘制流程。文 献【2 5 】则详细分析了现代g p u 中可编程的单指令多数据工作模式，指出了在像 素着色器中进行提前终止光线加速效果不明显的原因，为基于g p u 体绘制算法 的优化给出了重要的参考，同时也提出了有价值的优化算法。 利用图形硬件所提供的三维纹理功能进行体绘制是当前最有效的体绘制方 法，但是该项技术只是在中、高档图形工作站上才被引用。然而随着图形硬件 的发展，目前主流的计算机显卡已经具有很强的三维纹理加速功能，并且在浮 点运算能力和带宽方面已经远远超出了c p u 。利用g p u 的这种特性不仅可以 加速体绘制算法的绘制过程，而且在一些数据密集型的计算过程中也能大大提 升计算速度，让g p u 进行一些通用计算方面的工作，从而将c p u 从繁忙的运 算过程中解放出来。 g p g p u 全称是g e n e r a lp u r p o s eg r a p h i cp r o c e s su n i t ，即通用计算图形处理 器的意思。g p g p u 着重于利用g p u 的可编程性，让g p u 去实现处理3 d 图形 以外的计算应用。作为一种专用芯片，g p u 必须依靠图形应用程序接口才能够 与应用程序沟通，微软d i r e c t x 与a r b 主导的o p e n g l 是目前流行的两种图形 应用程序接口，简单地说它们就是一套函数的集合，g p u 在硬件层面上支持这 些函数，3 d 程序则在代码编制时调用这些函数，实现相应的功能，这样，程序 开发者不必知晓硬件的细节，就能设计出可以让所g p u 都能运行的图形程序 【2 6 】 o 随着g p u 的发展，用于通用计算的g p g p u 层出不穷。n v i d i a 方面推出 t e s l a 通用计算平台，t c s l a 平台包括硬件部分的g p u 和软件部分c u d a 开发环 境。对开发者而言c u d a 已经提供了非常完整的开发环境，通用程序的开发者 不再需要考虑g p u 硬件的问题，而只要调用c u d a 提供的函数库即可编制出 想要的程序，这些程序所涉及的计算任务都可以为n v i d i a 的g p u 所高效执行。 7 硕i ：学位论文 a m d 方面则提出了基于f i r e s t r e a m 的计算平台，通过基于“c l o s et om e t a l 薄 硬件接口来实现各种通用计算。i n t e l 将在今年推出l a r r a b e e 处理器将设计为高 密集度计算的用途，同时也可以用于图形渲染，换言之，它将通用计算提高到 与图形渲染均等的地位。因为其指令与x 8 6 类似，编制通用计算程序将更为容 易【2 7 】。 相比于c p u ，图形硬件g p u 具有如下特点： 1 高浮点运算能力，高带宽 根据摩尔定律，集成电路上可容纳的晶体管数目约l8 个月便会增加一倍， 性能也将提升一倍。由于人类对视觉真实的需求，远远超过对听觉的需求，在 3 d 游戏和高清视频的助推下，g p u 的性能也不断攀上新的高峰。自从n v i d i a g e f o r c e2 5 6 出现以来，g p u 内部晶体管数目增长速度已经远远突破了摩尔定 律的限制，最新的g t 2 0 0 系列g p u 已经具有1 4 亿个晶体管。得益于g p u 固 有的架构，使其具有高浮点运算能力以及高带宽。 鼍 厶 2 k 口 音 o j 姐蛔 鲫妇妇n 钟m | y 绷潮0 6绷绷 j 缸 绷 图2 1g p u 浮点运算能力 图2 1 【2 8 】是g p u 与c p u 的浮点运算能力的比较，横轴是年份，纵轴代表浮 点运算能力，单位是g f l o p s 即每秒l0 9 次浮点运算。从图中可以看出顶级的 g p u 已经到达每秒9 x1 0 1 1 次浮点运算，而同时代的c p u 的浮点运算能力仅相 当于g p u 的1 3 0 0 。同时g p u 在带宽上也远远超出了c p u ，g 8 0 系列g p u 已 经到达了1 0 0 g b s ，这就保证了强大的吞吐量，不会因为带宽的限制而成为g p u 进行通用计算的瓶颈。 2 高并行执行能力 硕士学位论文 当遭受制造工艺限制，无法通过提升c p u 频率来提高c p u 性能时，多核这 概念就被提了出来用于解决c p u 在处理多任务时的问题。而g p u 是专门为 图形运算所设计的，拥有数百个流处理器，十分适合处理单指令多数据的计算。 而科学计算、数据库分析等高性能计算恰恰是符合单指令多数据，这就使得 g p u 十分利于解决这些通用计算的问题。 由于市场在实时高清三维图形上的需求，g p u 已经发展成一个高度并行， 多线程多核处理器。具体来说，g p u 很适合于解决数据并行( 同一程序在许多 数据元素上并行执行) 的高运算密度( 算术运算与存储器操作的比例) 计算问题。 因为在每个数据元素上执行同一程序，所以对复杂流控制的要求较低；又因为 具有高运算密度的同一程序在大量数据元素上执行，也就可以通过大量的计算 而非大量的数据高速缓存来隐藏访存延迟。数据并行处理将数据元素映射到并 行处理线程。处理大型数据集合( 比如数组) 的许多应用程序可以使用数据并行 编程模型来加速计算。在3 d 渲染中，大量的像素和顶点集合被映射到并行线 程。同样地，图像和媒体处理应用程序，比如渲染图像的后期处理、视频编码 和解码、图像缩放、立体视觉、模式识别，可以将图像块和像素映射到并行处 理线程。事实上，图像渲染和处理以外的许多计算方法也能通过数据并行处理 来加速，其范围涵盖从一般的信号处理或物理模拟，到计算金融学或计算生物 学等的诸多领域【2 9 1 。 3 可编程性 图形绘制管线是实时绘制的核心，它的主要功能就是在给定虚拟照相机， 三维物体，光源，照明模式，以及纹理等诸多条件下，如何生成或者绘制一幅 二维图像。类似于输油管道、工厂的装配线绘制管线也通常包括多个阶段，无 论其中的个别管线速度多快，管线的整体快慢程度是由管线中最慢的那个阶段 决定的。在概念上可以将绘制管线粗略的分成三个阶段：应用程序、几何阶段 以及光栅阶段。同样每个阶段自身也可能是一条管线，也可以包含几个子阶段。 应用程序阶段是由应用程序来驱动，开发者能对其完全控制。几何阶段主要负 责多部分多边形和顶点操作，包括模型与视点变换、光照、投影和裁剪。光栅 阶段则利用前面阶段产生的数据进行图像绘制【3 0 】。 根据其功能可以得到一个简单的绘制管线，如图2 2 。 顶点转换 此过程输入的是单个的顶点信息，包括空间位置、颜色、法线以及纹理坐 标。这个过程所进行的操作有：顶点位置变换；每个顶点的光照计算；产生纹 理坐标和转换。 9 兰! ! ! ! 坚：丝竺些! ：! ! ! 兰坐兰 顶点问的关系 圈22 图形绘制管线 图元组装和光栅化 这个过程的输入是转换后的顶点以及顶点间的关联信息，后者告诉绘制管 线如何进行图元的组装。光栅化则决定片段和图元上像素的位置。片段上包含 一些数据信息用来更新帧缓存上的像素。它不仅包含颜色信息，还包含相应的 法线和纹理坐标，这些将被片j 来计算下一个像素的颜色。它的输出有两部分： 帧缓存中片段的位置和顶点转换后的插值信息。 片段纹理和着色 之前计算的插值后的片段信息和颜色信息作为此过程的输入，展终输出片 段上每个像素的颜色值和深度值。 光栅化操作 图形管线的最后一个步骤主要进行一些测试如：剪裁测试、a l p h a 铷i 试、 模板测试和深度测试。如果这些测试都通过，那么片段信息将用来更新帧缓存 巾的像素信息，只有在这个阶段才能够对帧缓存进行访问操作。 现代的显卡提供了可编程性，分别用顶点着色器和像素着色器替代了固定 功能的顶点转换部分和片段纹理着色部分( 图22 中的深色部分) ，给予开发者极 大的自由度。概括的说顶点着色器提供了一种方法，可以改变与每个多边形顶 点相关的值，包括颜色、法线、纹理坐标，以及位置，为在图形加速器上计算 光照模型提供了更大的灵活性。像素着色器则是在一个绘制通路中是基于每个 像素，每个物体进行的，是对固定功能多重纹理管线的一种扩展。使用一系列 指令对一组常量、插值、纹理值进行操作来生成一个像素的颜色值和透明度值， 学位论! 它提供了一种灵活的方式，可以创建更具有真实感的光照模型和很多其他特殊 效果。 凭借g p u 的超强性能，在运行诸如金融分析、气象预报、数据库分析、人 工智能、多媒体处理、蛋白质折叠在内的高并行计算时拥有比c p u 更卓越的效 率。在这种新趋势下，利用g p u 对体绘制算法进行加速，构架c p u + g p u 的通 用计算平台，在提升绘制性能的基础上也降低了购置成本和能源消耗。 2 3n v i d i ac u d a c u d a ( c o m p u t eu n i n e dd e v i c ea r c h i t e c t u r e ，统一计算设备架构) 是显卡公司 n v l d i a 提出来的一种计算架构，该技术利用其显卡强大的运算能力，从而给 数据密集型的应用提供了完全不受限制的全新的计算能力。它将g p u 视为数据 并行计算设备，在其上进行计算的分配和管理，而无需将其映射到图形应用程 序接口。操作系统的多任务机制负责管理多个并发运行的c u d a 应用程序和图 形应用程序对g p u 的访问。c u d a 软件堆栈由几层组成，如图2 3 所示：硬 件驱动程序，应用编程接口厦其运行时，以及两个更高层的通用数学库c u f f t 和c u b l a s 。在硬件设计上，驱动程序层和运行时层是轻量级的，这样更能够 达到高性能。 。”i = = 【：= 二：二一二二：二，一一一一 f 。u 。一u n n j 围23 c u d a 软件堆栈 为了给编程人员提供尽量低的学习曲线，c u d a 通过标准的c 语言来提供 大量的高性能指令以及简洁的程序开发方式，从而允许开发者创建一个解决办 法，该办法将消耗更少的时问为数据密集型的处理提供足够精确的解答。c u d a 提供了通用的动态随机存储器寻址方式以实现更高的编程灵活性，这就是被称 硕士学位论文 为聚集和散布的存储器操作。从编程角度看，它们就是在动态随机存储器的任 何位置读取和写入数据的能力，与传统的c p u 编程一样。在c u d a 架构中， c p u 被称为宿主，g p u 则被视作一个可以并行执行多个线程的计算设备。能够 有效的共享数据，并且可以同步执行来协调内存访问的多个线程被称为一个线 程块。由于一个线程块中的线程数目有限，具有相同大小和维数的，可以执行 同一段程序的线程块就被称为线程块网格。c u d a 提供了极高读写速度的并行 数据高速缓存或者称其为片上共享内存，线程可以使用它来互相共享数据。应 用程序可以利用它来最小化对动态随机存储器的过取和轮询，从而降低对动态 随机存储器内存带宽的依赖程度f 2 引。 2 4 本章小结 体绘制属于科学可视化的范畴，从其技术特点上来说可以分为许多种类。 本章对各类体绘制技术做了简单的概述，从而明确了研究的对象与任务。接着 对g p g p u 的发展与特点作了一定的研究，从系统架构上阐述了g p g p u 作用于 体绘制的可行性。最后是对本文所采用的通用计算平台n v i d i ac u d a 做了简 单的介绍。 1 2 第3 章基于g p g p u 的光线投射法 光线投射算法是一种基于图像顺序的体绘制算法，它通过模拟实际光线穿 越物体来实现图像的绘制，能够得到极为精细的图像，具有高绘制质量的特点。 此算法从图像空间中的