（计算机科学与技术专业论文）基于gpu的直接体绘制关键技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 直接体绘制技术是科学计算可视化的重要研究内容，目前在许多科学领域得 到了广泛应用。传统直接体绘制技术存在绘制速度慢、交互性差的缺点，但应用 领域对数据可视化结果的真实感、可视化过程的实时交互性要求却越来越高。 本文在系统地研究与分析直接体绘制的基本原理、典型绘制方法以及相关加 速绘制技术的基础上，针对目前直接体绘制技术存在的问题，结合g p u 的特点， 对基于g p u 的体绘制流水线以及体绘制预处理加速技术、基于g p u 的光线投射 绘制、基于g p u 的混合数据场绘制技术进行了深入研究，并完成了相关算法与原 型系统实现。本文的主要工作和取得的主要研究成果包括： ( 1 ) 提出一种基于g p u 的体数据预处理加速算法。本文对目前g p u 体绘制流水线 结构进行了深入地分析，为消除流水线速度瓶颈，采用自适应数据划分剔除算 法对体数据进行子划分，剔除空白子块后将子数据块定义成子纹理块，然后使 用体纹理打包算法v t p 将子纹理块打包成适合g p u 纹理内存的纹理，再依次 传输至g p u 纹理内存中。实验结果表明加速算法有效地提高了流水线实际吞 吐率，与原始算法相比，加速算法节省了4 0 , - 6 0 的绘制时间。 ( 2 ) 提出一种基于g p u 的单遍光线投射体绘制算法。本文在深入研究经典光线投 射算法以及基于三维纹理切片算法的基础上，针对已有算法存在预先计算梯度 耗时、存储空间需求大的问题，将传统基于c p u 的光线投射算法映射到g p u 上执行，通过片元程序动态计算梯度插值来节省存储空间和提高图像质量。与 传统三维纹理切片体绘制算法相比，本文算法无需回读数据和回写颜色缓冲区 即可在g p u 上的一个通道内完成绘制，达到了实时交互的绘制要求。 ( 3 ) 提出一种基于g p u 的混合数据场绘制方法。本文在研究已有混合数据场绘制 算法的基础上，针对混合数据场求交复杂、绘制效果不理想的问题，结合改进 的混合光照模型，提出了一种等值面快速求交算法。实验结果证明采用混合光 线跟踪算法绘制混合数据场时，新算法比经典光线跟踪求交算法绘制速度快 2 0 。 ( 4 ) 在对上述算法进行分析设计与实现的基础上，本文构建了基于g p u 的光线投 射体绘制系统框架g r v 。实验结果表明，该框架通过采取本文提出的基于g p u 的体数据预处理加速算法、单遍光线投射体绘制算法以及混合光线跟踪绘制算 法，充分发挥了g p u 性能、有效减少了c p u 负担并显著提高了场景绘制速度， 是一个简单、快速、易于实现和扩展的直接体绘制实时交互绘制框架。 关键词：直接体绘制，光线投射，混合绘制，实时交互，g p u 第i 页 国防科学技术大学研究生院学位论文 a b s t r a c t d i r e c tv o l u m er e n d e r i n gi sa ni m p o r t a n tr e s e a r c hc o n t e n to fv i s u a l i z a t i o ni n s c i e n t i f i cc o m p u t i n g ，i th a sb e e nw i d e l ya p p l i e di nm a n ys c i e n t i f i cf i l e da tp r e s e n t t r a d i t i o n a lv o l u m er e n d e r i n gl i m i t e dt oi t sl o wr e n d e r i n gs p e e d ，p o o ri n t e r a c t i v e s h o r t c o m i n g s ，h o w e v e r ，t h ed e m a n df o rt h er e a l i s t i ca n di n t e r a c t i v eo fv i s u a l i z a t i o ni s g r o w i n gf a s tt ot h ea p p l i c a t i o na r e a s b a s e do nt h es y s t e m a t i cr e s e a r c ho fb a s i cp r i n c i p l e ，c l a s s i c a lr e n d e r i n gm e t h o d s a n ds o m ea c c e l e r a t et e c h n o l o g yo fd i r e c tv o l u m er e n d e r i n g ，a i m e da tt h el i m i t a t i o no f d i r e c tv o l u m er e n d e r i n g ，w eh a v er e s e a r c h e dt h ev o l u m er e n d e r i n gp i p e l i n ea n d p r e p r o c e s sa c c e l e r a t et e c h n o l o g y ，r a yc a s t i n ga n dh y b r i dv o l u m er e n d e r i n gb a s e do n g p u t h ec o n t r i b u t i o n sa n dr e l e v a n tw o r ki nt h i sp a p e ra r ea sf o l l o w s ： f i r s t l y ，a na c c e l e r a t e dp r e p r o c e s sa l g o r i t h mb a s e do ng p u i sp r e s e n t e d w eh a v e a n a l y z e dt h ev o l u m er e n d e r i n gp i p e l i n eb a s e do ng p u ，t os o l v et h eb o t t l e n e c ko ft h e s p e e do fp i p e l i n e ，t h en e wa l g o r i t h mf i r s tp a r t i t i o nt h ev o l u m ed a t aa d a p t i v e l ya n d e l i m i n a t et h ee m p t yr e g i o no fs u b d a t a ，t h e nc o n v e xt h es u bd a t at os u b t e x t u r e s ，f i n a l l y ， i tu s et h ea l g o r i t h mc a l l e dv t pt op a c k i n gt h es u b t e x t u r e st ov o l u m et e x t u r e s ，w h i c h f i t st h et e x t u r em e m o r yo fg p u t h er e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di m p r o v e s t h ep i p e l i n ea n da c c e l e r a t e st h er e n d e r i n gs p e e d s e c o n d l y ，as i n g l ep a s sr a yc a s t i n go fv o l u m er e n d e r i n gb a s e do ng p u i sp r e s e n t e d w eh a v ea n a l y z e dc l a s s i c a lr a yc a s t i n ga n dt e x t u r em a p p i n go fv o l u m er e n d e r i n g ，t o s o l v et h ep r o b l e m so fl a r g em e m o r yr e q u i r e m e n ta n dt i m ec o s t i n go fp r e - c o m p u t e g r a d i e n t ，w em a pt h er a yc a s t i n gb a s e do nc p ui n t og p u ，c o m p u t et h eg r a d i e n tu s e f r a g m e n ts h a d e ro nt h ef l y c o m p a r e dt ot h et r a d i t i o n a lo n e s ，t h ep r o p o s e ds i n g l ep a s s a l g o r i t h md ot h er e n d e r i n gi no n ep a s sw i t h o u tr e r e a dd a t ao rr e w r i t et h ec o l o rb u f l f e r ， a n dt h ep r o p o s e da l g o r i t h mc a nm e e tt h er e q u i r e m e n t so ft h ei n t e r a c t i v er e n d e r i n g t h i r d l y ，ah y b r i dv o l u m er e n d e r i n gb a s e do ng p ui sp r o p o s e d b a s e do nt h e r e s e a r c ho ft h ee x i s t e dh y b r i da l g o r i t h m s ，t os o l v et h ec o m p l e xo fi n t e r s e c t i o n sb e t w e e n r a ya n dh y b r i dd a t aa n dp o o rr e n d e r i n ge f f e c t s ，w ep r e s e n tan e wf i r s ti n t e r s e c t i o n a l g o r i t h mb e t w e e nr a ya n di s o s u r f a c e t h er e s u l t ss h o wt h a tw h e nr e n d e r i n gh y b r i dd a t a ， t h es p e e do ft h ep r o p o s e da l g o r i t h mi sf a s t e rt h a nt h eo l do n e s f i n a l l y ，w eh a v ed e v e l o p e daf r a m e w o r kn a m e dg r vb a s e do na n a l y s e sa n d i m p l e m e n t a t i o no fa l g o r i t h m sa b o v e t h er e s u l t s d e m o n s t r a t et h a tt h ef r a m e w o r k d e v e l o p sg p up e r f o r m a n c e ，r e d u c e sc p u o v e r h e a da n di m p r o v e st h er e n d e r i n gf r a m e r a t es i g n i f i c a n t l y i ti sas i m p l e ，f a s ta n df l e x i b l ef r a m e w o r kf o rr e a l - t i m ea n di n t e r a c t i v e o fd i r e c tv o l u m er e n d e r i n g k e yw o r d s ：d i r e c tv o l u m er e n d e r i n g ，r a yc a s t i n g ，h y b r i dr e n d e r i n g ，r e a l t i m ei n t e r a c t i o n g p u 第i i 页 国防科学技术大学研究生院学位论文 表目录 表2 1 光线投射算法伪码13 表2 2 足迹表算法伪码。1 4 表3 1 体数据预处理链表数据结构2 1 表3 2 剔除空白体元伪码2 1 表3 - 3 剔除空白体元后信息保存的伪码2 2 表3 4 两种体绘制算法的数据预处理时间与性能百分比2 5 表4 1 动态计算梯度插值的g l s l 程序2 9 表4 2 光线遍历和插值伪码3l 表4 3 三种方法在数据集上的绘制速度3 2 表5 1 查找等值面区域伪码。3 7 表5 2 求解导数方程伪码3 8 表5 3 迭代求解光线与等值面交点伪码3 9 表6 1 体数据抽象基类结构4 7 表6 2 体数据子划分类结构4 8 表6 3 体纹理打包类结构4 8 表6 4 着色器管理基类结构4 9 表6 5 体绘制抽象基类结构5 0 表6 6 四元数类结构5 0 表6 7 鼠标交互类结构51 第1 v 页 国防科学技术大学研究生院学位论文 图目录 图1 1 图形渲染流水线4 图2 1 不同类型的网格10 图2 2 体绘制基本流程图1 1 图3 1g p u 绘制流水线结构及瓶颈分析l8 图3 2g p u 体绘制流水线优化方案1 9 图3 3 体数据分块示意图2 0 图3 4 边界处插值的示意图2 2 图3 5 体纹理打包示意图2 3 图3 6 采用本文算法的体绘制效果图2 5 图4 1 三维纹理切片体绘制示意图2 7 图4 2 光线投射算法示意图2 8 图4 3 单遍光线投射算法示意图3 0 图4 4 三种算法分别绘制的人体脚效果图3 2 图4 5 三种算法分别绘制的人体头部效果图3 2 图5 1 三维空间体元示意图3 7 图5 2 采用不同着色方式的绘制效果图4 1 图5 3 混合场景绘制图41 图6 1 主程序框架4 4 图6 2 光线投射体绘制总体流程图4 4 图6 3 光线投射体绘制类图4 6 图6 4 数据管理模块流程图4 6 图6 5 数据采样与绘制模块流程图4 9 图6 6 脚裸和头部绘制效果图51 图6 7 放大的机器引擎和倾斜的盆景树绘制效果图5 2 图6 8 混合数据场绘制效果图5 2 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：基王鱼型鲍直接佳绘剑差筵垫盔盈窒 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文作者签名： 作者指导教师签名： 7 习 一砷刎 二 国防科学技术大学研究生院学位论文 第一章绪论 1 1 课题研究背景和意义 1 1 1 科学计算可视化 科学计算可视化t q ( 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 ) 是运用计算机图形学 和图像处理技术，将科学计算的输出数据和一些其它领域通过观察测试生成的数 据转换为图形和图像，最终在屏幕上显示出来并进行交互处理的理论、方法和技 术。科学计算可视化的概念是2 0 世纪8 0 年代末被提出来的，在这二十多年里， 随着计算机图形学和图像处理技术的不断发展，科学计算可视化由幼稚走向成熟， 可视化算法研究和系统设计方面都有很大的提高，并已广泛应用到许多科学研究 领域。 科学数据的可视化是一个复杂的过程，从最开始与图形无关的科学数据到最 终由象素点表示的图形，需要经过一系列的处理过程，主要包括数据的生成、预 处理、映射、绘制和显示等过程。 与传统的计算机图形绘制技术不同的是，科学计算可视化技术侧重的是数据 绘制的准确性和易理解性。目前应用领域对科学计算可视化的要求，不仅要显示 出数据的结构和关系，还要求能够对数据集进行动态显示，并允许用户实时交互。 1 1 2 体可视化技术 科学计算可视化技术的核心是三维空间数据场的可视化，也就是三维体数据 的可视化问题。在体可视化的研究的过程中，逐渐形成了两类不同的体可视化方 法：面绘制和体绘制1 2 】。 ( 1 ) 面绘制 面绘制技术( s u r f a c er e n d e r i n g ) 是指体表面的重建。首先由三维数据场构造出 中间几何图元( 如曲面、平面等) ，然后再由传统的计算机图形学技术实现画面的绘 制。最常见的中间几何图元就是平面片，如从体数据中抽取等值面时，可以抽取 一个等值面( i s o s u r f a c e ) ，也可以抽取多个等值面，如著名的m a r c h i n gc u b e s ( m c ) 方法【3 1 。这时，可以将中间几何图元的生成过程看作是将原始体数据中的部分属性 映射成平面或曲面。 面绘制能有效地绘制体数据的表面，而且可以利用现有的图形硬件实现绘制 功能，使图像生成和变换的速度加快。但面绘制技术不能有效地反映整个原始数 据场的全貌和细节，缺乏内部信息的表达。 第l 页 国防科学技术大学研究生院学位论文 ( 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 ) 。从科学计算可视化流程来看，可以理解 为将可视化映射这一步省略掉了，而是直接对预处理后的体数据进行绘制，进而 生成二维图像。这种技术能有效地反映整个原始数据场的信息，包括内部细节， 并且图像质量高。由于要绘制的体数据一般都比较大，利用体绘制方法在传统图 形硬件上绘制时存在计算量大、实时、交互性差等问题。如何进行实时、交互式 的体绘制，一直是该领域的研究热点。 体可视化技术的应用领域十分广泛，主要包括医学、气象学和地质勘探等领 域。在医学领域，由核磁共振、c t 扫描等设备产生的人体器官密度场，对于不同 的组织，表现出不同的密度值。通过在多个方面多个剖面来表现病变区域，使医 生对病灶部位的大小、位置，不仅有定性的认识，而且有定量的认识，尤其是对 大脑等复杂区域，体可视化所带来的效果尤其明显。借助虚拟现实的手段，医生 可以对病变的部位进行确诊，制定出有效的手术方案，并在手术之前模拟手术。 在临床上也可以应用在放射诊断、制定放射治疗计划等领域中；在气象领域，体 可视化技术可以将大量的天文气象数据转换为直观的图像，使预报人员能对未来 的天气做出准确地分析和预测；在地质勘探领域，利用模拟人工地震的方法，可 以获得地震岩层信息，通过数据特征的抽取和匹配，可以确定地下的矿藏资源。 由于地震数据的数据量及其庞大，而且分布高度不均匀，因而根本无法从纸面数 据做出分析，利用体绘制方法对模拟地震数据进行解释，可以得到矿藏是否存在、 矿藏位置及储量大小等重要信息，大大地提高了质勘探的效率和安全性，具有重 大的经济效益及社会效益。 1 1 3 可编程图形硬件 传统3 d 图形的基本工作都是由c p u 完成，显卡只是起着帧缓存( f r a m e b u f f e r ) 的作用。1 9 9 9 年，n v i d i a 公司推出了具有划时代意义的显示芯片g e f o r c e 2 5 6 引， 它是全球第一款可编程图形处理器( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) 、第一款集成了 硬件多边形变换和光照( t r a n s f o r m a t i o na n dl i g h t i n g ，t & l ) 等3 d 加速功能的图形 处理器，也就是说它能够承担部分原来由c p u 完成的工作。自此3 d 图形芯片踏 上了一日千里的飞速发展时期，n v i d i a 、a t i 等厂商不断改进生产工艺，推出新 产品，显卡性能( 核心频率、显存大小、显存位宽、显存频率) 得到了大幅提升。 目前，越来越多的计算机图形、科学研究开始采用g p u 来提高算法和系统效 率，这些应用研究主要是利用g p u 来做加速处理，而加速的动力来自g p u 所具 第2 页 国防科学技术人学研究生院。孑：何论文 有的以下主要优势p j ： ( 1 ) 可编程流水线 传统的图形硬件的设计目标是尽可能快速执行相同的硬编译计算指令集，不 同的计算步骤可以跳过，参数可以调整，但顶点级和片元级的计算却是固定不变 的，即- # j 的渲染流水线是一种功能固定的流水线，如图1 1 ( 左) 所示。而现在的 图形硬件发展趋势是朝着设计通用目的的图形处理器发展，就像c p u 一样，g p u 也可以用特定的编程语言在顶点级和片元级进行编程，执行你可以想象得到的任 何计算【6 】，如图1 1 ( 右) 所示。这种可编程的图形流水线使得3 d 图形渲染方式更加 灵活，不受任何限制，为开发者提供了无限发挥的空间。 ( 2 ) 一定的并行性 g p u 的并行功能主要是通过多个渲染管道和r g b a 四个颜色通道同时计算来 体现的。此外，在一个时钟周期内可以同时获取两个甚至更多副纹理。顶点程序 的多个渲染管道意味着一个时钟周期可以并行处理多个顶点，而对于片元级程序 同样如此。相对并行机而言，g p u 提供的并行性虽然较弱，但它在十分廉价的基 础上为很多应用提供了一个很好的并行方案。 ( 3 ) 高密集的运算 g p u 在顶点级和片元级运算上都提供了i e e e 3 2 位浮点运算，而且由于g p u 内部的内存接口位宽大于c p u 上的位宽，如g e f o r c ef x 的内存位宽达到2 5 6 位， 显然高于c p u 上的3 2 位的位宽，这样整个计算的带宽大大提高。g p u 相对与c p u 来说，更适合传输大块的数据，虽然c p u 上有c a c h e 来加速整个计算过程，但这 种c a c h e 一般只有6 4 k b ，而现在的显存大多在6 4 m 以上，其计算速度由此可见 一斑。 ( 4 ) 通用计算能力 当前g p u 的计算能力已经大大超过了c p u 。以n v i d i a 公司的g e f o r c e 6 8 0 0 为例，其计算能力可达到1 2 0 g f l o p s ( g i g af l o a t i n gp o i n to p e r a t i o n s ) ，相当于六个 5 g h z 的p e n t i u m 4 处理器。这是因为g p u 具有多个顶点处理器和片元处理器 ( g e f o r c e 6 8 0 0 有6 个顶点处理器，1 6 个片元处理器) ，能够更好地挖掘浮点计算的 并行性，另外，g p u 显存带宽更大r 7 1 。我们可以通过可编程的图形流水线，将原 来在c p u 上执行的计算移植到顶点或片元处理阶段，充分利用g p u 的通用计算 能力，减少c p u 负担，避免c p u 成为图形渲染性能的瓶颈。 ( 5 ) 减少c p u 与g p u 之间的数据通信 这个特点尤其体现在图形生成的时候，不再需要在c p u 和g p u 之间进行多 次数据交换，因为g p u 提供了多遍绘铝l l ( m u l t i - p a s sr e n d e r i n g ) 以及绘制到纹理 ( r e n d e rt ot e x t u r e ) 的功能，从而可以让c p u 解放出来做其它事情。 第3 页 国防科学技术人学研究生1 1 7 哐- r 。- 位论文 目i 口，g p u 在j l f i j 造型、图像处理、科学汁算可视化等领域都有广泛地应用。 本文针对直接体绘制存在计算量大、实时、交互性差等问题，利用g p u 的上述优 势对体绘制的相关加速技术进行研究，具有良好的应用价值。 礁点她理防啦j ；斯处翅阶娌：点点处王；! 1 分心 ”娃i 处理阶段 ；i ； ”； t t ， i转换 纹理 i l 土土i i l i 光照颜色求和 l 土土。i i i 纹理坐标 雾 生成转换 土, l , il , l 土 土上i 抗锯齿 i裁剪 儿儿王j r i i ii 基于片断 i 光栅化的操作 图1 i 图形渲染流水线( 左图为固定功能流水线、右图为可编程流水线) 1 2 国内外研究现状 实时、交互式可视化一直是国内外在科学计算可视化方面研究的热点问题。 本节主要介绍国内外在体绘制加速技术方面的一些研究现状，包括软件算法加速 体绘制技术、采用专用硬件加速体绘制技术以及使用g p u 辅助加速体绘制技术的 研究现状。 1 2 1 软件算法加速体绘制技术 在基于软件的体绘制加速算法的研究方面，国内外使用得比较多的是主要有 两类【8 】，一类是根据图像空间的相关性尽量减少投射光线的数目，做到自适应光线 采样，从而减少采样次数达到加速的目的；另一类就是对空间数据结构进行优化， 尽量减少不必要的数据采样点，从而达到加速绘制的目的。 ( 1 ) 减少投射光线的数目 在体绘制所产生的最终结果图像中，相邻的像素之间存在相关性，甚至没有 什么变化，因此并不需要图像空间所有的像素都投射出光线，可以将结果图像分 第4 页 国防科学技术人学研究生院学位论文 成多个颜色变化不大的区域，将这些区域的颜色值以一束光线投射后得到的颜色 值来代替就可以了。 l e v o y 9 】首先提出根据结果图像的质量和计算复杂性来减少光线投射的数目。 他首先将图像空间分成规整网格，并设定好之间的相关阀值，接着从某个小网格 的四个角分别投射光线，如果计算出来的像素的差值小于该阀值，则该区域的像 素的颜色值就等于浚区域投射出光线的像素插值，否则必须对该区域细化后继续 投射光线，再计算相应的像素颜色。 c h e n g 等【i o 】使用了不透明度截止的加速技术，其主要原理是：在应用由前向 后( f t b ) 融合算法的体绘制中，当累计的不透明度达到_ 个预先设定的阀值时，光 线可以达到的任何其他体素将不做处理，从而达到加速采样的目的。j u n g 等】扩 展了八叉树结构，结合提前不透明度截止技术，使用光线投射算法在医学图像绘 制中可以提高1 “2 2 倍的绘制速度。 ( 2 ) 减少体数据采样点数目 这类技术的基本出发点源于对体绘制计算复杂度的分析，由于一般体绘制的 算法复杂度为o ( n 3 ) ，而一般体数据中透明的体素约占整个体数据的7 0 9 5 嘣1 2 】， 所以通过分析体数据的存储结构，跳过空白体素( s p a c el e a p i n g ) 【】，可以达到加速 的目的。 l e v o y t l 4 】使用金字塔数据结构将体数据分层表示，每个体素对应这个塔的一个 节点，预先将每个空体素指定一个它所在层次的值，当光线遍历遇到这个空体素 时，可以根据它的层次值向前跳到下一个非空的体素。但这种算法较为复杂，缺 乏浮点运算支持时会导致绘制结果失真。 a g a t e l l 5 使用八叉树分层存储结构，并充分考虑了用硬件实现的可能性。但在 计算过程中需要使用乘法和浮点运算，速度虽有提高，但还是不能令人满意。 g l a s s n 一场】将体数据存储成八叉树的形式而不是网格形状结构，利用快速的八 叉树遍历方法，绘制速度比利用网格结构提高很多。w i h e l m s 1 。7 】简化了八叉树的结 构，提出了根据需要对体数据进行分叉表示，进一步加快了处理速度。 s u n g u p 1 8 】基于空间跳跃思想提出了一种更快的跳跃方法，在预处理阶段对体 数据进行了游程编码压缩，然后快速遍历体空间找出非空体素对应的像素，并只从 这些像素投射出光线，找到投射光线遇到的第一个非空体素和最后一个非空体素， 对在此之间的非空体素按其对像素的贡献进行组合，计算得到对应的像素值。 文献【1 9 2 0 川利用小波多分辨率的特性压缩体数据，将体数据表示成多层结构， 按照需要显示多分辨率的图像。同时，文献【侈】还提出了基于有限元的自适应网格 优化方法。 基于软件加速的体绘制算法在体绘制中应用得十分广泛。但绘制的体数据往 第5 页 国防科学技术人学研究，j 二院学何论文 往比较庞大，只依靠软件加速绘制尤其是绘制具有整体光照效果的图像时，算法 性能还是有限的。因此人们将目光转向图形硬件，希望借助硬件提供的相关功能 加速体绘制。 1 2 2 专用硬件加速体绘制技术 采用软件算法优化的体绘制技术往往不能利用传统的图形硬件进行加速绘 制，绘制速度不够理想，为此国内外展丌了对专用体绘制硬件体系结构的研究。 c u b e - 3 2 2 】、c u b e 4 【2 3 】系统是一个比较成功的并行体绘制体系结构设计，它能 在3 0 帧每秒速率下实现5 1 2 级大小数据场的实时绘制。c u b e - 5 2 4 j 是基于c u b e 4 在图形芯片上进行变换( w a r p ) ，然后进行绘制，只是错切( s h e a r ) 的过程在硬件上实 现，光照模型也只限使用p h o n g 模型，因此绘制效果的真实感不是很强，适合中 等规模数据的交互体绘制。 k n i t t e 等【2 5 j 提出将体数据内存( v o l u m em e m o r y ) 组织成八个可同时访问的内存 模块，以支持三线性插值计算中对八个相邻体素的同时存取。系统的基本结构是 一个包括体数据内存和四个处理单元的流水线结构，第一个处理单元完成光线投 射；第二个处理单元完成数据的三线性插值和向量的计算；第三个处理单元采用 p h o n g 光照模型计算采样点的光照强度；第四个处理单元完成图像的合成。 v o l u m e p r o 2 6 】可以说是目前最成功的体绘制加速硬件系统，它能做到实时绘制 2 5 6 级的体数据。但由于其核心绘制流水线体系结构是基于c u b e 4 扩展的，用于 支持s h e a r - w a r p 算法的特殊存储子系统的设计使它还不能做到透视投影绘制。 v i z a r d 2 7 系列能够进行高质量地透视投影绘制，实时绘制的速度介于c u b e 5 与v o l u m e p r o 之间，它基于图像空间序提供了完整的光线追踪算法的一种硬件实 现方案，这种实现方案具有很大的灵活性，但绘制前需要对体数据进行几分钟到 几十分钟的预处理，导致了实时绘制性能的下降。 m a n n h e i m 大学的v i r i m 2 8 】支持灵活的体绘制优化算法，且支持阴影的计算， 绘制的结果真实感强。但v i r i m 是绘制算法只是在硬件进行直接固定的映射，并 没有支持空间跳跃和自适应光线终止等优化算法，整个系统显得比较庞大。 国内方面，国防科学技术大学在v i r i m 的基础上提出了一种新的体绘制加速 硬件结构v g e 2 9 】，该结构提供了对如空间跳跃、自适应光线终止等体绘制算法的 有效支持，通过引入启发式优化措施，使体数据预处理时间减少到了小于3 0 秒， 在绘制规模为2 5 6 级的体数据时可以达到7 0 h z 的帧频。该系统同时还支持平行投 影和透视投影绘制。另外，国内的清华大学、上海交通大学、中科院等单位也对 专用体绘制硬件进行了研究。 虽然目前的这些专用体绘制硬件系统能够达到大规模数据场实时体绘制的要 第6 页 国防科学技术人学研究生院学1 c 7 ：论文 求，且算法流水线根据硬件结构经过了最优处理，实时绘制性能高，但算法的流 程固定不变，其灵活性相对比较差，其次对硬件配置要求很高，价格昂贵。 1 2 3g p u 辅助加速体绘制技术 与昂贵的专用体绘制硬件不同，通用图形硬件( g p u ) 由于性价比高，目自订在普 通p c 机上得到了广泛地应用。许多实时图形的绘制、通用科学计算等丌始从工作 站转向普通p c 机进行研究。现阶段基于g p u 加速体绘制技术是国内外在科学计 算可视化研究上的热点。g p u 辅助加速的体绘制技术主要是利用g p u 的相关特性 加速完成体绘制中求交、重采样插值、颜色合成等原来只能由c p u 才能完成的操 作，从而加快体绘制速度。 c u l l i p 掣驯首先将体数据沿投影轴进行切片并依次装入g p u 纹理内存，在体 数据内定义代理几何体元( p r o x yg e o m e t r y ) 进行重采样、颜色合成等操作。类似算 法还有【3 t l 。由于体数据往往大于纹理内存，需要将体数据分解成小于或等于纹理 内存的切片装入纹理内存，这种频繁的i o 操作导致体绘制性能严重下降。m e i l 3 n e r 等【3 2 】采取压缩纹理的方式以提高速度，但导致了绘制结果失真。 k r u g e r 等【3 3 】在g p u 上进行光线投射绘制时，将与光线相交的体元从纹理表中 取出，计算并更新其透明度和颜色值，在g p u 片元级沿光线方向采用步进法完成 采样进行最终绘制。其次，该方法将提前光线终止和空间跳跃等加速体绘制技术 整合到光线投射中加快g p u 体绘制。类似的方法还有r o e t t g e r 等【3 4 】。但这些算法 在提出时，g p u 。上片元着色器还未提供分支控制和动态循环的功能，因此在绘制 时需采用多遍渲染( m u l t i p a s sr e n d e r i n g ) 的方式，严重影响了绘制性能。 s t e g m a i e 等【3 5 】利用n v i d i ag e f o r c e 6 系列显卡提供的n vf r a g m e n tl a r o g r a m 2 o p e n g l 扩展具有的动态分支功能，采用一组嵌套的r e p 循环指令( 6 5 0 2 5 次迭代) 执行对体数据进行采样操作，利用g p u 做到了对体数据的单遍( s i n g l ep a s s ) 绘制， 速度大大提高。k l e i n 掣3 6 】对s t e g m a i e r 掣3 5 】的方法进行扩展，利用帧与帧之间的 致性( f r a m e t o f r a m ec o h e r e n c e ) 加速空间跳跃，在绘制等值面和半透明体数据 时有较高的性价比。 陈为等【37 j 使用视点相关的层次采样( v d l s ) 将面向多边形绘制的图形引擎转 化为体光线投射算法引擎，在透视投影方式下每秒能处理1 5 亿个插值、后分类 与着色的光线采样点，提供了基于g p u 的一种新的体光线投射绘制方法。 充分利用g p u 提供的顶点级和片元级的可编程性，可提高中小规模体数据的 绘制速度。但由于g p u 的纹理内存有限，且主存到显存的传送带宽也容易形成绘 制瓶颈，不适合那些大规模数据的交互式实时可视化。限于g p u 本身的结构，目 前利用g p u 还只能做到实时光线投射体绘制，w o o p 等【3 即研制的可编程光线处理 第7 页 国防科学技术人学研究生院学何论文 j 芯片r p u ( r a yp r o c e s s i n gu n i t ) 可用来实时光线跟踪绘制复杂的动态几何场景，且 达到了理想的交互绘制要求。相信支持真i 卜意义上的光线跟踪体绘制的图形处理 芯片不久也将会出现。 1 3 论文结构 全文共分七章： 第一章为绪论。主要介绍论文的研究背景与意义，阐述了国内外在直接体 绘制加速技术方面的研究现状。最后对论文工作与研究成果进行了总结。 第二章为直接体绘制的相关关键技术研究。主要从体绘制的基本原理、典 型的体绘制方法以及混合数据场的绘制技术这三个方面进行了阐述与分 析。 第三章对基于g p u 的体绘制流水线以及预处理加速算法进行研究。首先 分析了g p u 体绘制流水线瓶颈，并给出了一种基于g p u 的体绘制流水线 优化设计方案。为加快体绘制预处理速度，突破c p u 与g p u 之间的传输 瓶颈，提出了自适应体数据分块算法以及体纹理打包算法。 第四章对基于g p u 的光线投射算法进行研究。传统的基于g p u 的光线投 射算法都是多遍( m u l t i p a s s ) 绘制的，影响了绘制效率。针对这个问题，提 出了一种基于g p u 的单遍( s i n g l e p a s s ) 光线投射算法，将传统基于c p u 的光线投射体绘制算法映射到g p u 执行，采取动态计算梯度的方法减小 了纹理容量需求，提高了绘制质量。 第五章对混合数据场的绘制技术进行研究。首先分析了经典的光线跟踪光 照模型，并给出了改进的混合绘制光照模型。其次，针对光线与体数据等 值面求交速度慢的问题，提出了一种等值面快速求交算法，结合改进的混 合绘制光照模型，提出了基于g p u 的混合数据场绘制算法。 第六章构建了基于g p u 的光线投射绘制系统框架g r v 。详细介绍了以本 文提出的优化的体绘制流水线结构以及预处理加速算法、单遍光线投射算 法以及混合光线跟踪算法为基础，构建并实现的光线投射绘制框架的开发 环境、总体设计思路、重要数据结构以及实现细节。 第七章为结束语。总结了论文主要工作，并对未来工作进行了展望。 1 4 论文研究成果 本文完成的主要工作和取得的主要研究成果包括： 重点研究了基于g p u 的体绘制流水线，提出一种自适应数据分块剔除算 第8 页 国防科学技术人学研究生院学位论文 法和体纹理打包算法。该算法在体绘制预处理阶段能很好地对体数据进行 自适应分块，并对定义成子纹理的体数据进行打包传输到g p u 纹理内存 中，突破了c p u 与g p u 之间的传输瓶颈，提高了绘制性能。 提出一种基于g p u 的单遍光线投射算法。算法采用动态计算梯度插值的 方法来节省存储空间和提高图像质量，利用g p u 提供的动态循环和分支 的特性，在绘制时无需回读数据和回写颜色缓冲区，体绘制操作在g p u 的一个通道内完成，提高了图像绘制的质量。 提出一种等值面快速求交算法。该算法有效解决了绘制混合数据场时光线 与等值面求交慢的问题。并在该算法基础上设计了一种基于g p u 的混合 光线跟踪算法，有效地绘制了混合数据场分离的场景。 综合上述算法实现了基于g p u 的光线投射绘制系统框架g r v ，并给出了 实验结果。 第9 页 国防科学技术人学研究生院学何论文 第二章直接体绘制相关关键技术 为了后面章节的完整性，我们在本章简要介绍一些直接体绘制的相关关键技 术，其中包括：体绘制基本原理、典型的体绘制方法和混合数据场绘制技术。 2 1 1 体数据主要特征 2 1 体绘制基本原理 三维空间数据可视化的对象既包括计算机的科学计算数据，也包括测量所得的 测量数据。无论计算数据还是测量数据，往往都是离散的，因此可视化的对象一 般是指空间离散的三维数据。 根据体数据中数据样点分布的空间几何特征，体数据一般分为：( 1 ) 结构化数 据，如图2 1 中a 、b 、c 、d 所示；(