《基于gpu加速光线跟踪体绘制算法的研究李万丰》由会员分享，可在线阅读，更多相关《基于gpu加速光线跟踪体绘制算法的研究李万丰（44页珍藏版）》请在金锄头文库上搜索。
1、长春理工大学硕士学位论文原创性声明作者签名：垄硅巡年三月五日长春理工大学学位论文版权使用授权书作者签名：纽逊年玉月山同导师签名愀村：i 田鬻竺竺竺竺法主要是靠c P U 束实现，而G P u 主要是用于图形处理。：黧：旱强大的并行处理能力和可编砒将G P u 视为蒜主蒜；霸嚣晶加速处理工作。昙氛萎黧翟苎竺竺算法经常删的均匀网格K D _ t r 包围体层次这三个加苎苎构孽! 护u 上进行创建和遍历的细节问题进行了阐述和分析研嘉一。i 竺要竺翌兰竺曼璺形渲染管线技术和流处理开发工具进弃孚菇绍，并且通过：釜妻銎：个流处理模型的设计，来详细具体介绍如何将基于G P U 晶芜磊素嚣磊姜茹算法实现的。一
2、硒1 。一霆霎苎篓套! 粤场景复杂度和不同分辨率等情况下做对比试验。通过对比说明更能体现G P U 的优越性，并且通过对比来实现算法的进一步的改五_。”关键词：光线跟踪体绘制G P U 流处理A B S T R A C TE a r l ys t a g e ，r a yt r a c i n ga l g o r i t h mf o rv o l u m er e n d e r i n gi sm a i n l ya c h i e v e db yt h eC P U ，a n dt h eG P Ui sm a i n l yu s e df o rg r a p h i c sp
3、 r o c e s s i n gI nt h ep a p e r , w ew i l lt a k ea d v a n t a g eo ft h eG P Up a r a l l e lp r o c e s s i n gc a p a b i t i t ya n dp o w e r f u lp r o g r a m m a b l e a n dt a k et h eG P Ua sas t r e a mp r o c e s s o rt oa c c e l e r a t et h ep r o c e s s i n ga l g o r i t h mF
4、 i r s t l y ，w eh a v ee l a b o r a t et h ed e t a i l sa b O U tc r e a t ea n dt r a v e r s eb a s e do nG p Uo ft h et h r e ea c c e l e r a t i o ns t r u c t u r e sl i k eU n i f o r i l lG n d K D t r e e ，B V H w h i c ha l eo f t e nu s e db yr a yt r a c i n ga l g o r i t h mf o rv o
5、 l u m er e n d e r i n g ，t h ep a p e rc o m p a r ea n da n M y z et h et h i n ea c c e l e r a t i o ns t r u c t u r e sS e c o n d l Nw eh a v ead e t a i l e di n t r o d u c ef o rc h og r a p h i c sr e n d e r i n gp i p e l i n eo ft h eG P Ua n dd e v e l o p m e n tt o o l sf o rs t r
6、e a mp r o c e s s i n g ，a n dt h r o u g ht h ed e s i g no f as t r e a mp r o c e s s i n gm o d e l r a yt r a c i n gf o rv o l u m e - r e n d e r i n gb a s e do nG P Uh a sb e e nd e t a i li n t r o d u c e dh o wt om a k el tr e a l i z e d L a s t l y , w eh a v eac o m p a r i s o nt e
7、s t su n d e rd i f f e r e n tc o m p l i c a t e ds c e n ea n dr e s o l u t i o n sB yc o m p a r i s o ns h o w st h a tb e r e tr e f l e c tt h ea d v a n t a g e so fG P U ，a n db yc o m p a r i n gt h ea l g o r i t h mt oa c h i e v ef o r t h e ri m p r o v e m e n t sK 目w o r d s ：r a y
8、t r a c i n gv o l u m e - r e n d e r i n gG P US m P r o c e s s i n g第一章绪论11课题研究背景、内窖和意义l1 1 科学计算可视化科学计算可视化“1 ( V i s u a l iz 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 ) 通过使用计算机图形学原理和图像处理技术，把科学和工程计算产生的大规模数据转化为图形图像在屏幕上显示出来从而促进人们对数据的观察和理解并且能够交互处理的理论、方法、技术。科学计算可视化最早是在1 9 8 7 年被提出来
9、的，现已成为计算机图形学的一个重要研究分支，是图形科学的新领域。科学计算可视化主要的应用领域主要有：医学图像、地理信息、天气预报、矿物质资源勘测、c A 0 、生物、分子信息学等。其实，将任何抽象的事务、过程变成图形图像的衰示都可卧称为可视化。与计算机有关的如可视化界面( W i n d o w s ) ，可视化编程( V i s u a l 甜+ ) 等。从最初的科学和工程计算数据到最终转化为出像素点组成的图形图像这个复杂的过程看，科学计算可视化的过程可分为数据预处理、艘射绘制、显示四个基本步骤。1 1 2 体绘制技术科学计算可视化研究的核心是3 0 体数据可视化。3 D 体数据可视化方法可
10、分为：面绘制( 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 ) ”1 。( J ) 面绘制面绘制算法从三维数据场提取出中间几何元素( 如曲线、曲面等) ，井将数据属性值映射为可视元素，再用计算机图形学技术渲染为可视图形。主要基于曲面造型技术以及面光照模型技术。可视化中绘制的面一般都是等值面。等值面的生成方法很多。概括起来主要有以下三类：基于等值线的生成方法：基于体紊的生成方法；几何变形模型( g e o m e t r i cd e f o r m a b l e
11、m o d e l ) 法。著名的( M a r c h i n gC u b e ，M c ) 算法“1 基本思想是：遥个处理数据场中的体素，采用插值方法计算出等值面与体素边的交点作为吹体素上等值面的采样点，然后对采样点进行三角划分，得到等值面在体紊内的一个逼近表示，所有体素中的等值面构成整个数据场的等值面。基本假设：数据场沿着体索的边呈连续线性变化。出于面绘制的原理只是绘制规定的面，所以面绘制不能反映体数据的内部细节信息。优点是可以快速的产生较清晰的等值面图像，并且用现有的图形硬件设备就可以轻松的实现，也就是说硬件依赖性较弱”1 。( 2 ) 体绘制体绘制与面绘制最明显的区别就是不绘制中恻
12、图元。而是直接由三维体数据生成二维图像，所以叉称直接体绘制。这就是说直接省略了可视化流程过程中的第二个基本步骤映射直接把经过处理过的体数捌进行绘制渲染，进而显示出囤像“。体绘制的主要特点为：第一，以体素为对象，体素包含了对象内部信息；第二放弃丁体是出面构造的约束它直接从三维数据场中绘制出各类物理量的分布；第三，其绘制质量优于传统面绘制；第四交互性能、算法效率有待提高；第五应用领域正在不断拓广。体绘制的基本思想为：首先将三维数据场中的数据进行分类；其次指定转换函数，将数据点的值转换为对应的光学属性，如颜色值( R ，G ，B ) 以及不透明度值( o ) ；然后根据各数据点的梯度值及体光照模型计
13、算出其光照强度，然后根据投影到图像平面上同一像素处各数据点的不透明度将其相应的颜色值叠加到一起，形成最终图像。目前，体绘制已经运用到许多领域。成果显著。在生物领域，可以通过医学辅助器材对蛋白质等复杂结构进行剖片获取信息，这些信息组成了体数据，进而对其进行定性和定量分析；在工业产品检验领域，通过超声波获取产品的内部构造结构，利用体绘制可视化技术实现产品内部结构的显示，有利于分析问题和提高产品质量：在医学中，利用C T 、M R I 等设各来获取各方面多剖割面或者重建三维图像，从而对病变部位有定性和定量的认识，有利于确诊病情并且制定相应的解决方案，可以在手术之前模拟手术；在地质勘探领域，通过数据特
14、征的抽取和匹配，可以确定地下的矿产资源。因为体绘制技术能反映出整个数据场的内部细节，整个需要处理的数据量大，在传统的圈彤处理设备上实现就会出现实时性和交互性差的缺点。如何通过软硬件束改善以上的不足，一直是这个领域的重点。1 1 3G P U 概述G P U 的主要优势有：并行处理能力，通过多个渲染管道和R G B A 四个颜色通道同时计算束实现并行；通用计算能力，最早提出通用G P U 概念的是A M I ) ，G P G P U ( G e n e r a lP u r p o s eG P U 通用计算图形处理单元) 可以处理原本由C P U 完成的处理任务，并且在某些方面可以做得更高效这
15、让H P C ( 高性能计算机) 可更好的在几何造型、数值计算、流体模拟、三维重建、场景绘制、数据库操作等领域发挥作用：可编程流水线，用特定的编程语言编写硬编程计算指令集，实现功能可以随编程内容改变而改变：高密集的运算，著名的图形芯片设计厂商M a t r o x 生产的p a r h e I i a 5 1 2 ( 幻同) 内存位宽达到5 1 2位，显然高于C P U 的3 2 位位宽一般服务器C P U 的缓存的容量通常在3 22 5 6 K B ，而显存则在1 2 8 M 以上“1 ，速度差距是明显的。G P U 在科学研究、高级数学运算，还有医学研究中的疾病逆向工程，医学成像中的超声图
16、像渲染，以及视频和图像处理等领域都会有很好的性能表现。本文就针对G P U的以上优点，对光线跟踪体绘制加遽进行研究，具有重要意义。12 国内外研究现状随着科技的发展，在气象、工业、生命科学等领域实际运用中产生的数掘信息量越来越大，这些庞大的信息量给我们更加准确、丰富的素材的同时也带给我们如何实时、快速、交互式的绘制出我们所需要的圈形这样的难题。本部分主要介绍在软件算法加速、硬件加速以及基于G P U 的体绘制加速技术在国内外的研究现状。1 2l 软件算法加速体绘制算法国内外主要有两种方法米实现软件加速体纶指4 算法，种是优化空间数据结构减少无用的数据采样点；另一种就是减少跟踪光线量。减少体数据
17、采样点数目，在场景中空体素占整个体素的绝大部分如果直接跳过空体素，减少了体数据采样点的数目，就可以达到加速的目的。S u n g u p ”1 主要是基于空间跳跃思想，采取快速遍历体空间找出非空体素对应的像素，然后从找到的非空像素开始投射光线，将光线遇到的第一个非空体素和射出场景的非空体素之间的非空体素按照对此像素的贡献比例来设定权值最后确定像素值。减少参与计算光线数量在体绘制中，有些相邻的光线之间具有很大的相同性，方向和起始点基本一致。这时可转化一束光线就可处理，或采取中自J 插值的方法来生成另外少许的光线柬代替这些光线，或是通过测试，先减少一部分肯定不与场景内体素相交的光线。L e v o
18、 r y ”1 将图像空间划分成规整网格然后将网格的四个顶点分别投射光线，此网格的像素值在小于规定阀值时，就将网格投射光线的像素插值设定为像素值，在网格的像素值大予设定的阀值时先将网格细化后重新投射光线，然后再计算像素颜色。通过软件算法实现加速体绘制已经得到了大量使用。由于体数掘比较庞大，仅仅依靠软件算法无法达到理想的效果所以人们又逐渐关注通过硬件加速实现提高体绘制速度。1 2 2 专用硬件加速体绘制技术在实际应用过程中通过软件实现加速的体绘制往往不能很好的利用传统通用图形硬件实现加速。所以国内外开始转向研究通过专用图形绘制硬件来实现加速。M a n n h e i m 大学的V I R I
19、M ”可以说是硬件加速的最好的体现，它只是在硬件上进行直接固定的映射，整个系统特别庞大。V I R I M 优点是支持阴影的计算，绘制的结果真实感强，缺点是不支持空阳跳跃和自适应光线终止等优化算法。在国内方面专用硬件加速体绘制也取得了很大的进展国防科大在V I R I M 的基础上提出一种体绘制加速硬件结构V G E “。V G E 系统支持平行投影和透视投影绘制并且支持空间跳跃和自适应光线终止等体绘制算法。该系统通过引入启发式优化措施将2 5 6缴的体数据控制在7 0 H z 帧频，并且将体数据处理时间控制在3 0 秒以内。专用硬件加速体绘制技术优点是实时绘制性能高缺点是硬件配置要求高。价格
20、昂贵算法依据硬件灵括性差。1 2 3 基于G P u 的加速体绘制技术G P U 与昂贵的专用体绘制加速硬件不同G P U 具有高性价比，目前已经得到广泛的使用。基于G P U 的加速体绘制技术思想就是利用G P U 的可编程性把先前只有C P U 才能处理的工作比如体绘制中求交、重采样差值、颜色合成等转化成自己完成。K r u g e r “”提出在G P U 上计算和更新从纹理表中取出的与光线相交的体元的透明度和R G B 值并把提前终止光线和空域跳过技术整合到光线投影中来加速体绘制，然后在G P U 片元级沿光线方向采用步进法进行最终绘制。13 本文的主要工作和组织结构本文的主要研究目标
21、是利用国内外观有的相戈研究成果根据光线跟踪体绘制的主要特点并在自口人的基础上对如何利用G P U 的优点进行提高光线跟踪体绘制算法性能进行深入的研究工作。主要研究内容包括：l _ 对比分析了现阶段计算科学可视化过程中使用的真实感绘制算法的优缺点以及国内外采用何种方式来加速绘制算法的。2 对光线跟踪算法的基本原理进行了分析对比了针对光线跟踪算法是如何分别在软件和硬件上实现加速的。3 针对在G P U 上经常使用的三种加速结构，均匀网格，K D t r e e B V H 的加速效果和在G P U 上实现的细节进行了对比分析。4 针对基于G P U 的图形渲染架构和流处理丌发工具，利用G P U
22、的可编程性，详细讲述如何在G P U 上实现光线跟踪流处理模型。5 在不同场景复杂度和不同分辨率的情况下对比分析了使用C P U 和G P U 在各自场景下的各自的优缺点。本文共分为六章，各章组织结构如下：篼一章，简单阐述了光线跟踪的概念以及圜内外对体绘制的研究现状和技术发展的趋势。箱二章，详细介绍了光线跟踪体绘制技术基本原理，并介绍了几种加速光线跟踪算法的技术手段。第三章，详细介绍了光线跟踪体绘制的三个加速结构，均匀网格，K D t r e e 和包围体层次数据结构。第理章，介绍了光线跟踪流处理结构和流处理开发工具。第章，针对基于G P U 加速的光线跟踪体绘制算法的实现细节进行了详细介绍。
23、第六章，使用第五章中的算法，进行了实验测试，根据实验结果进行分析总结。最后是针对基于G P U 加速的光线跟踪体绘制算法的总结和展望。第二章光线跟踪算法概述经过近些年柬不断的发展光线跟踪体绘制技术已经得到了大量运用。本章主要讲述光线跟踪算法基本原理、光线投射和光线跟踪的相关技术。2 1 光线跟踪体绘制技术2 1 _ l 光线跟踪体绘制技术基本原理光线跟踪基本思想是：对辫幕上的每一象素点，从视点投射出一条穿过该象素的光线，该光线穿过体数据空间，在光线上选择一系列采样点，利用插值方法计算出各采样点的光强和不透明度，然后进行合成，从而得到屏幕上泼像素处的颜色值。光线跟踪体绘制算法顾名思义就是通过模拟
24、现实世界中光线传播来实现体绘制的。在完全真空环境中，光源发出的光线将是一条直线向前传播，而在自然界中。光源发出的光线不断向前传播，直到遇到阻碍它传播的物体表面，此时光线可以看做在此路径中传输的光子流光线会遇到反射、折射、吸收和荧光这四个影响因素。物体表面可能会在一个或多个方向反射部分或全部的光线：如果物体是透明的或半透明的，就会将一部分光线按照不同的方向折射到物体内帝| j 同时吸收部分或者全部光谱或者改变光线的颇色。吸收、反射以及折射的光线都束自于入射光线，而不会超出入射光线的强度。反射或者折射的光线可以到达其它的物体表面，同样，吸收、反射、折射的光线重新根据入射光线进行计算。其中一部分光线
25、通过这样的途径传播到我们的眼睛，我们就能够看到最终的渲染图像及场景。光线跟踪在直接光照和划接光照效果中都具有优势“”叫，它是现阶段最具绘制真实性的算法之一。体绘制中的光线投射与光线跟踪类似，都是沿光线的路径进行色彩的积累。光线投射算法是一种以圈像空问为序的经典D v R 算法。其基本原理是，成像平面的每个像素沿着视线方向发出一条射线穿过体数据，沿着这条射线等间距重采样，求出各重采样点的颜色值和阻光度，然后按照由前向后或由后向前的方式合成射线上各重采样点的颜色值和阻光度，即得到该像素颜色。光线的跟踪并不是在第一次碰撞到物体后就结束。在光线每一次碰撞到物体时都育可能产生反射线、折射线、阴影线。当光
26、线遇到透明物体产生折射光线，躁踪折射线可体现出透明物体影像的变形效果。在场景中一直跟踪因碰撞物体产生的反射光线直至遇到下一个物体或者没有碰到物体算法彳终止。在绘制屏幕上某一个像素点时必须把初婚光线和反射光线的颜色叠加到块进行渲染，才能够在镜面位置绘制出其中的影像。算法根据阴影线米判断碰撞点是否对光源可见然后停止对不可见光线的继续跟踪并根据结果束绘制阴影。光线跟踪算法设定在光线经过一定行程投有发生碰撞或者碰撞达到一定的次数后，算法自动终止，然后通过渲染各像素的颜色值来完成绘制。2 1 2 场景表示场景一般是采用三角形、多边形、球形、锥形这些常见的基本几何体图元在三维空州对物体建模来表示。但是无论
27、用哪种几何体图元进行表示它们对于光线跟踪可咀说是透明的并且光线跟踪算法的场景还可以用更加复杂的几何体图元来表示比如说，N U R B S “”曲面和等值面”等这是因为在光线跟踪算法中只要能计算出物体表面与光线的交点，就可以进行绘制。光线跟踪的一个显著优势就是能绘制几乎所有的几何图元。在体绘制过程中，如果直接绘制复杂图元算法的整体运行效率会提高且绘制效果较好。在不苛刻要求绘制效果的绘制时，一股绘制复杂的图元时都是把复杂的图元转化为三角形这些简单的图元来实现的，这样会产生囚转化三角形产生离散失真，但是能简化数据的写入和维持算法的设计和优化工作负担减轻许多，并且相对来说硬件设备要求的低些。一般在G
28、P U 计算中，三角形数据可以非常方便的映射到纹理内存中，并且在医学图像、工程检测等应用场景中，一般很少出现锥形或高次图元。即使存在也很容易转化为三角形几何图元。2 i 3 递归光线跟踪算法流程典型的递归光线跟踪体绘制算法一般包括光线生成、光线遍历、相交测试、渲染和光线衍生五个部分。光线生成是从税点位置通过屏幕像素向屏幕内场景发射出光线。光线跟踪的主要工作就是通过光线和场景中图元的相交测试来找到光线的碰撞点。如果将场景中的每个图元都和这条光线进行相交测试，这就带来另外一个难题就是造成很大的速度影响。在算法实际运用中，一般通过在相交测试前经过场景遍历来降低浪费时问的弊端。在相交测试前，场景被预组
29、织成便于快速找到光线附近物体的空间数据结构。相交测试中，光线通过与可能产生交点的节点中所有图元的相交测试来决定是否遍历其后的场景结构，没有产生交点将继续遍历直到得到有效交点或晟终穿出场景。渲染时将会用到遍历过程中有效的交点信息。光线在交点上可能产生新的反射光线和折射光线。然后，衍生光线产生与否由碰撞点物体表面属性和入射光线类型决定。一旦产生了衍生光线，则将衍生光线再次送回到遍历过程中继续遍历。衍生光线将与初始光线通过设定的权值比例来共同决定所对应屏幕像素的颜色。早期的光线跟踪并不能达到照片真实性，在光线的跟踪过程中不断产生衍生光线，造部分光线导致计算量迅速增加，并且无法通过共享其中一部分光线计
30、算米获取像素实现加速，只能单独处理这些衍J 土光线。理论上是如此。但在实际运用中，光线跟踪主要是模拟现实光照，没有必要实现光线从眼睛到光源的全程跟踪通过权衡绘制速度和图像质量来完成一个综合性能高的光线跟踪运算。如何在既能提高速度又能提高质量是光线跟踪一直在研究的目标。22 光线跟踪的加速技术在光线跟踪过程中需要对大量光线进行帽交测试，通常通过一些加速技术来提高算法的效率，如果不采取加速措施那么算法9 5 的计算时间将会用来进行相交测试。加速光线跟踪一直是研究的重点，本文目标也是进行加速光线跟踪。下面对己存在的光线跟踪加速技术进行简要介绍。2 2 1 硬件加速技术目前，实时光线加速技术是通过专门
31、的图像处理设备柬实现加速的，有些是基于工作站和计算机机群的。S c h m i t t l e r “”等人提出了一个完全硬件体系结构，此硬件体系结构主要是通过重建虚拟内存结构和无组织内存存取结构模式来实现的，前者主要是用于缓存渲染场景的数据后者则为了方便光线跟踪算法的数据读取。它们的缺陷是设备昂贵。在一些较小的应用中G P U 整体性价比是比较高的所咀利用G P U 来加速光线跟踪绘制是研究的重点。G P U 不但具有超强浮点计算能力还有高度的并行性和超长的流水线处理能力。P r t c e l l 的光线跟踪算法把所有的光线跟踪内核都建立在G P U 上，光线跟踪的所有程序都能在G P U
32、 上实现，这种方法会使c P U 会有很多空闲状态，但是避免了C P U 和G P U 之洲的数据交换带来的损失。C a r t 则提出光线跟踪的主要工作都在C P U 上完成除了光线与三角形求交运算放在G P U 上。这种方法的优点是提高了G P U 的使用率。但是C P U和G P U 之间频繁的数据交换给整体性能带来损失。2 22 减少参与计算的光线数量参与计算的光线共有两种一种是初始光线另外一种是衍生光线。直接减少这两种光线可显着提高速度。在场景中体索较少时，顶点跟踪1 通过直接向场景中的物体各个顶点发射光线，不用再像其他的光线跟踪方法需要通过屏幕像素发射光线，可以达到较少初始光线的目
33、的。直接较少初始光线的方法主要是通过中间插值来获取相邻光线颜色的近似颜色来达到减少初始光线的目的。这两种方法缺点是对场景依赖度高t容易造成失真。通过减少衍生光线的数量同样可选到减少跟踪光线的目的。一般在光线跟踪时，通过设定光线的最大反射或折射次数和光线的最远行程等规则来限制衍生光线无限产生。可以通过自适应深度控制束控制一些光强消弱的光线深度，判断是否还具有继续计算衍生光线的价值。在场景中很可能出现这样的一些光线，它们彼此相邻且方向一致，通过把这样的光线整合成一束光线也能达到减少光线数量的目的。2 ，2 3 减少相交测试的计算次数在光线跟踪过程中，有关提升速度问题比较集中在如何减少相交测试上。最
34、经常用到的方法就是采用空间数据结构划分场景。这种方法只关注在光线路径上与光线相交的体素而不考虑其它的体索。这个算法的关键问题是选用合适的场景分割方法来把需要进行场景遍历对象降到最少。层次包围盒( B V H ) 树二叉空恻划分法( B S P ) 树，八叉树均匀网格，自适应网格。K D 树等等“”叫4 1 。下面介绍几种常用的数据结构：( 1 ) B S P 数据结构B S P 是B i n a r yS p a c eP a r t i t i o n i n g ( 二叉空间划分法) 的缩写。这种方法递归地将空间使用超平面划分为凸面体集合。这种子划分引出了借助干称之为B S P 树的树形数
35、据结构的场景表示。二维( 称为四元树，q u a dT r e e ) 和三维( k d 树) B S P 树及其变体是计算机图形学中使用得十分重要的数据结构。最初，整个区域被定义为B S P 树的根。之后，你继续划分区域。一旦把凹形区域划分为两个凸形区域( 在晟好情况下) 或凹多边形，命名这些区域，它们成为其父结点的孩子，父结点实际上代表了整个区域。图2l 是展示B S P 树生成过程的图案。如果你仔细观察的话可以发现G 和F 是两个凸多边形。因此生成过程结束。1图21B S P 树生成过程t 2 ) 层次包围体在层次包围体数据结构中最直接的场景划分方式就是对每个物体都用一个球体或者是方盒进
36、行对物体的包围形成包围体。数据结构中的包围体形成了层此结构高层的包围体包围着低层包围体。首先测试光线是否和包围体相交，如果不相交的话肯定不会跟包围体内的物体相交，也就是不用进行后面的运算，如果光线和包围体相交那么再进行测试是哲光线跟包围体内的物体相交。根介。八入酬22 层次包隔盘上图就是一个层次包围盒的示例。其中a 代表光线， 、B 、C 、D 、E 是五个物体，整体上有一个大包围体包围着以上血个物体，大包围体内又划分有A + B 、C 和0 + E 等三个包嗣体。首先测试到光线已和根包围体相交。然后再分别铡得和叶E 包囤体相交，和M B 、C 这两个包围体不相交，那么这两个包围体就不用再继续
37、进行以后的相交测试了光线肯定不跟这两个包围体内的物体相交。对于光线和D + E 这个包围体相交，就要进行后续的测试是否光线和D 和E 这两个包围体分别相交。依次类推最后得到光线和E 物体相交。很明显层次化包围盒能大大减少相交计算的数目，但是缺点是在光线相交测试中需要考虑每个物体。( 3 ) 一致空问细分一致空间细分结构用轴向对齐的正方体包围场景，然后通过一致分割场景来获得更小的体索。一致空间细分方法在计算光线路径上是根节省时间的。图23 就是说明了这一问题。首先计算出光线穿过那些体索再进行对体素内存储的图元进行铡试是否相交。这种划分方法便于遍历不用考虑空日Jt 的所有物体只是需要考虑路径上的体
38、索即可。、 q 吣幽23 一致空问细分跟踪光线( 4 ) 自适应空间细分自适应空间细分方法是使用自适应的层次细分咀便根据对象的分布对空间进行划分t 而不像一致空间细分方法那样只是使用轴向对齐的正方体固定的分割场景，并没有考虑到场景中实体的分布情况在绝大部分场景都是空体素，大部分体素都集中在场景中某角落时这种细分方法计算效率是比较低的，八叉树“”，B S P 树和K D t r e e 等部属于层次化细分方法“”。在K D t r e e 中，随深度的增加，递归的依次选择三个坐标轴中的一个方向的轴对齐平面分割场景形成两个子节点。目前光线跟踪最优加速结构是使用s A H 构建的K D 树n 1 。
39、23 小结本章主要是针对光线跟踪体绘制算法的_ f I = | 关技术进行了介绍。光线跟踪递归算法是后面将要介绍的光线跟踪流处理结构的思想基础，以及介绍的几种加速策略，在第三章中将会根据实例继续深入研究。第三章加速结构的分析和实现上一章舟绍了光线跟踪的基本概念和一些加速技术简单介绍。本章将重点进行介绍在光线跟踪中使用的加速结构。光线跟踪算法常见的加速结构有均匀网格、K D t r e e和层次包围盒树( B V H ) 。本章将分别从每种加速数据结构在G P U 上的适用性以及在G P U上具体实现来详细分析哪种加速数据结构虽适合在G P U 上实现光线跟踪算法的加速。3 1 均匀网格F u
40、j i m o n o 等人首先提出均匀网格结构，加速结构的主要思想就是把场景细分成均匀3 D 网格体索，每个体素包含一个同它相交的三角形的列表。在光线同网格求交时，首先从光线射入的体素开始按照光线射入的方向顺序访问光线穿过的体素，分别测试每个访问的体索相关的三角形列表找出并返回光线同三角形虽近的交点。本次找到交点是唯一的，因为算法是从光线的起点开始，按照光线射入的方向以距离递增的顺序访问体素检测到交点一定是光线与体素最近的交点。当光线到达网格术端时就意味着光线已射出场景外，此时即可终止体素的访问。3 1 1 均匀两格的创建刨建场景的均匀网格需给定场景的包围体和三角形列表。同时，确定沿三维坐标
41、轴线所需要的网格分解度是十分重要，网格是固定的结构那么网格分解度就成了惟一能在构造阶段进行调节的参数。很显然，比值高的分解度会产生更多的网格和更小的网格尺寸，那么每个体素会产生更少的三角形就会导致每个三角形求交次数的减少和算法需花费更多时问在网格遍历上，在这两者之问找到一个平衡点是比较重要的。W o o 建议使用近似立方体体索的分解方法柬确定一个无给定场景的网格分解度P a h r r 和H u m p h r e y s 提出沿晟长轴使用，坼个栅格进行分解“”，N 是整个场景中三角形的数量。H a v r a n 和S i x t a 的试验显示体素与三角形的比率是2 0 时性能最优。但是在
42、某些场景中，仍需手动调节网格分解度来获得塌优效果。随着网格分解度的确定三角形列表分配到三维数组中。由此可以找到场景中相交的体索，井可添加它的索引。3 1 2 均匀网格在G P u 上的应用首先在G P U 上实现加速的数据结构就是均匀网格结构。均匀网格结构只使用简单的算术运算即可在常量时问内定位和存取每个体素的遍历操作。它就避免了对树遍历的需要和重复的比较耗时的纹理查找工作。同时，通过使用递增的算术运算来实现体素的遍历这就避免了使用堆栈。它是从光线的起始点丌始沿着光线以距离递增的方式顺序访问体素。在整个体素的遍历过程中，在访问的体素中，一发现有交点就可停止这条光线的遍历过程。遍历代码非常适合使
43、用向量编写。均匀网格数据结构的不足之处是会出现光线和三角形要重复进行相交测试，这是因为在场景中存在多个体索包含相同的三角形索| ：j | 。这势必会导致资源的浪费。G P U 的输入数据是由已经构建好的均匀两格通过映射到纹理布局上来形成的。体素网格可以被存储为一个三维纹理或把二维切片转换成单一的二维纹理。下圄3 1 将二维切片集合存储为一个单一的三维纹理。j D j 5 i 噩格圈31 均匀网格在纹理中的表示方法乖l 数据布局均匀网格是比较节省内存和带宽的因为在每个体素仅包含一个单一的指向三角形列表们指针。三角形列表单独存储在浮点数纹理中，每个三角形列表咀一1 做为列表终止的标示。如上图3 1
44、 所示。在像素纹理中的纹理元素可以存储四个三角形指针，这样虽然使代码变得复杂化，但可减少片段程序读取纹理次数。因只需要存储一次三角形，所以只在列表中存储三角形的指针能节约内存它的代价是每个三角形另需一个间接指针。并不是都需要用时问换空间这个方法。在需要引用相同三角形多次时，内存会迅速消耗，此时选择总使用指针来表示大场景。列表1，4 表2州表3，U 表4列表5列表6对齐填充鼎宙；斟列表纹理列表数据分布三角形纹理三角形数据分布圈3 2 三角形列表纹理利三角形数据纹理的数据分布方式角形纹理内存中每个三角形的顶点用一个R G B A 浮点向量值来表示如上所示。图3 2 中三角形之间没有共享顶点数据。如
45、需顶点共享只需添加一个间接指针即可。均匀网格主要也是通过尽量减少访问场景中体素包括空体素和不与检测光线相交的三角形面片测试来实现速度上的提升的。按照光线向量来步进式的访问场景中遇到的三角形片元，在场景中的某个体素发现光线与它相交就可停止该光线的遍历。3 D D D A算法是二维画线程序的三维版本用束实现网格日J 的移动。遍历网格需要经过光线初始化，光线和三角彤相交测试，遍历三个阶段。光线初始化就是需要在场景中对应每条光线找出对应相交的体素，找到包含光线起始点被光线穿过的第一个体素。3 D D D A 算法负责将在场景遍历过程中遇到的第一个空体素或无交点的体煮直接跳过，并移动到下个体素重新丌始光
46、线和三角形求交测试过程。相交测试结果是找到交点就可停止遍历过程并返回交点信息。P u r c e l l 将光线初始化求交测试和遍历三个部分分别由三个相应的处理内核来完成。首先运行光线初始化内核函数对场景中的光线进行初始化操作，然后在遍历程序过程中有I 5 的内核函数有求交测试的需求时，程序转向求交内核函数的运行求交内核函数运行多次才重新调用遍历内榱。在求交器中每个内核调用只执行一次三角形求交而在遍历中只执行一次体素递进。在程序运行过程中由C P U 和G P U 各自发挥各自优势协调配台束完成。G P U 主要是根据闭塞查询结果来改变内棱执行流程，C P U 负责全面协调程序中循环和分支的运
47、行。因为P u r c e l l 的程序设计并不支持分支，所以相交测试内核在执行运算时，大量光线会因需要等待遍历而产生大量的资源浪费。输出流输入流幽33 均匀网格在I ；P UE 遍历的模型随着技术的发展，G e f o r c e 7 3 0 0 在片元程 莘设计上已经突破了以往的设计障碍，此图形处理嚣能实现真正意义上的分支处理功能。在G e f o r c e 7 3 0 0 图形处理器中能够把求交内核和遍历内核统一到一起，组成遍历求交内核，如图3 3 。此时每个内核会执行一个遍历操作或求交操作，那么光线在具体内核调用期间不会处于空闲状态。求交和遍历内核合并后，求交测试在初始化时先为包岔
48、在初始化体素中的光线设置遍历状态然后就能运行求交遍历内棱。所有光线都找到交点或射出场景才结束对求交遍历内核的访问。在遍历求交内核调用过程中，需存储内存中时间片段各个参数状态以便状态恢复之时使阚。需要存储tm a x 值，穿越或肴反复状态，体素索引值，列表索引值。体素索引是对三维向量体素的索引。t m a x 值是决定下步光线6 n 进方向的三维向量。列表索引就是三角形列表的索引值。穿越或反复状态说明内核正在穿越网格状态还是处于对三角形列表求交状态。3 1 3 均匀厢格小结均匀网格加速结构比较简单，在G P U 上【| ；i 比较容易实现。均匀网格主要思想就是先把需要进行遍历的场景网格化，这样场
49、景中的体素就被大而化小，遍历检索时只用检测每个网格小块即可。每个网格由三角形片元组成。然后在场攮中通过算法找出所有的被光线穿过的体素，一旦体素被光线穿过，那么一定说明此体素内部存在三角形片元和光线有交点，后续进行它们之削的测试，测试出具体的三角形片元。均匀冈格结构数据分别由保存网格的纹理，保存三角形列表纹理和保存三角形片元各个顶点R G B值的纹理等纹理集台组成。在均匀网格结构实现时，首先用光线初始化核函数初始化遍历状态，再使用遍历核函数柬遍历穿过光线的体素，然后使用求交核函数找出光线与三角形面片的具体交点这就完成了均匀网格结构的实现。32K D t r e eK D t r e e 同均匀网
50、格一样也是一种空间细分数据结构，K D - t r e e 加速结构是采用二叉树数据结构柬实现将场景表示成层次结构而不同于均匀网格结构中采用网格来细化场景。二叉树数据结构中内部节点表示空I | l J 区域的某个部分，叶子节点表示体素和与之相关的保存在该体素内的三角形引用。3 2 1K 口t r e e 的刨建K Dt r e e 的创建过程是一个自顶向下的递归的过程。K D t r e e 的实现主要就是选用轴对齐的分离平面将包围体分成两个组成部分。K D t r e e 数据结构中的场景中的图元都将重新分配成为包含此图元的更大的包围体中的孩子。如果出现某个图元两个分离平面，那么此图元会被重
51、复引用。程序将不断的把场景中给定的包围体选用给定的分离平面分割，然后体桑中的图片通过递归的方式不断成为包台它的更大包围体的孩子，当数据结构达到了规定的最大深度或一个节点中三角形数量小于给定阀值时才终止算法的继续递归循环过程。经过咀往长时间的实验证明，当数据结构深度达到十六，包古的最小三角形片元等于二，K O t r e e 数据结构性能习能达到最优。H f 一t r图34K D t r e e 创建过程面对给定的场景如何选择合适的放置分离平面位置是K D t r e e 数据结构创建过程中的重点也是比较难实现的部分。针对此问题， | l a c D o n a l d 和B o o t h 给
52、出这样的定论：光线与孩子节点相交概率跟孩子节点和父节点的表面积之比成正比。随着科技的发展和研究的不断深入，l l a i n e s 提出的评价方程“考虑到了某些图元会出现横跨在两个体素中的情况这涉及到三角形被重复分配的问题，这种情况如果不避免务必会造成渲染时的资源浪费。如果在分离原始体素时，出现了一个三角形不完全包含在这个体素中，此时需要沿着体素裁减三角形用产生的新的包围体来替代原来的包围体。3 2 2K D - t r e e 在G P U 上的盛用K Dt r e e 不能直接在G P U 上实现因为G P U 没有堆栈结构，不能进行递归运算。近年来，一些专家使用不同的遍历策略来解决K
53、Dt r e e 的遍历问题。G l a s s n e r 使用指针定位策略沿光线从树的根节点向下移动指针的方式顺序遍历K D t r e e 直到找到包古这个指针的叶子节点。F o l e y 和S u g e r m a n 使用的方法与此相似不同的是，它需要使用一个 t m i n ，t m a x 的问隔柬确定需要处理的体素。K D t r e e 数据结构很容易映射成纹理表示。在回退阶段，每节点需额外两个浮点类型R G B A 向量存储包围体，在重置阶段每节点只需一个像素向量。抉句话说，回退阶段比重置阶段多耗费三倍的存储空间。K D t r e e 数据结构中的节点存储的内容包括：
54、分离轴指分离平面的三个相互垂直的辙也就是三维空间坐标轴。分离位置指分离平面被放真的位置。孩子节点需要存储当前节点指向左孩子的指针和指向右孩子的指针。父亲节点需要存储回退到树的上一个节点的指针。列表指针存储的足包含在这个节点的三角形列表的索引，当叶子节点为空时- 三角形列表索引设为一1 并跳过列表查询过程。节点类型存储的是节点类型，内部节点或叶子节点。矗孩子索引分离值父点索引B o x - m a x - z分离轴未使川I朱使H j山部1 ￥点( 重苴)内部肖点( 同堪叶子节点削35K O t r e e 在G P U 上的表示方法在K D t r e e 数据结构中存储的三角形列表中，叶子节点
55、指向列表的第一个元素，通过存储元素值为1 来中止列表。在K D t r e e 数据结构中三角形列表只是存储指向三角形的索引无存储三角形本身内容。K D t r e e 和均匀栅格在遍历过程很相似，相同点是都在体素中保存三角形的引用，不同点是在体素中前进方式不同。K D t r e e 中同样遍历过程分为光线初始化，光线与三角形求交测试，场景遍历三部分。光线初始化就是找出每条光线同场景中包围体相交位置的参数范围 t m i n ，t m a x 来用于遍历中。幽36K D t r e e 在G P U 上的遍历模型求交测试就是不断的测试节点是否同光线相交。在场景遍历过程中，内部节点可吼向树的上
56、方或下方移动，叶子节点只能在重置阶段向上移动。在遍历过程中根据移动的方向和分离平面的朝向以及同光线相关的分离平面的位置和光线方向的符号和光线当前的t m i n 值和t f I a x 值这些综合信息柬选择下一个节点。K D t r e e 中，遍历前通过一个单独内核完成初始化工作，K D t r e e 中无法一次处理完所有的光线遍历以及光线和三角形求交操作所以G P U 将多次调用遍历和求交内核，直到场景中所有光线都被处理完成。场鼎遍历以及光线和三角形求交每完成一趟需要采用闭塞查询来决定被激活光线数量。被闭塞查询激摄的光线数量的多少来决定何时停止遍历和求交测试。存储遍历状态是为便于下次内核
57、调用时迅速还原。存储的信息包括节点移动方向，列表索引遍历还是求交状态，节点索引t m i n 和t m a x 值。遍历= l 丕是求交状态指内核正运行遍历树还是对三角形进行相交测试状态。系统需要知道三角形相交羽4 试过程中此时F 处理哪个三角形，系统需要保存虽后被处理过的三角形列表索引。节点移动方向就是在遍历过程中需要存储向树上方还是下方移动。节点索引就是节点开始移动时，系统需存储开始移动节点的索引。存储t m i n 和t m a x 能有助于清楚树中选择何分支。3 2 3 一t r e e 小结本部分主要介绍了K D t r e e 加速结构的基本原理，以及在G P U 上的实现遍历和创
58、建过程的细节讲述。K D t r e e 通过记录光线行进的距离来决定遍历树的方向的方法突破了G P U 没有堆栈的障碍，使得在G P I J 上实现遍历成为可能。K D t r e e 在使用G P U 遍历时会被表示成纹理集合在遍历时先调用初始化核函数然后再按需调用合并后的遍历求交核函数。33 包围层次( B v H )本部分主要介绍包围体层次的相关知识。包围体层次与上两节介绍的均匀网格和K D t r e e 数据结构在结构划分上有本质的区别。包围体层次是采用对场景几何体进行划分的层次划分结构，均匀网格和K D t r e e采用的是对空日J 划分的空间细分结构。其实，场景中几何体的包围
59、体就是用一个更简单的几何体来包围住此几何体。在光线与三角形相交测试过程中，如果检测到光线不跟包田体相交，则此光线肯定不与包围体内音| i 的几何体相交”。在包围体层次结构中对包围体的求交测试很明显会比上两节介绍的采用对场景内的体素求交测试要容易的多。对包围体层次结构光线求交时，首先测试光线是否与最大的包圈体是否有交点这个包围体在数据结构中用根节点来表示，根节点下面有许许多多的孩子和孙子节点。如果光线和包围住糕个场景的包围体相交，也就是和根节点相交那么继续沿着这个根节点向下判断根节点的孩子节点是否和光线相交。数据结构中的孩子节点也就是包围范围较小的包围体数据结构中的叶子节点表示三角形片元也就是不
60、再包含有其它更小的元素。在相交测试时，一旦判断光线没有相交层次结构中的内部节点那么就不必再继续判断是否和其它孩子节点相交了直接继续兄弟节点的判断。3 3 I 包围体层次的创建遇过测试光线遍历包围体层次耗时，就可刿断此数据结构的质量。目前，没有一个准确的测量包围体层次的平均遍历时洲的方法束最终判断创建的包围体层次算法是不是最优的。G o d s m i t h 和s a l m o n 提出的表面积启发式评价函数1 主要思想是通过父节点和孩子节点的表面积之比来形式化衷示。评价函数主要是对随机光线和层次结构求交时成本评估。表面积启发式评价函数如图所示：P ( h i t ( c ) ) lh i
61、t ( p ) ) 。c S c S p( 31 )c 和p 分别表示父节点和孩子节点，s c 是节点n 的表面积，h i t ( p ) 是光线击中节点p 的情况。目日U 没有晟优的方法来构造最优的包围体层次结构，先介绍几种常用方法。在实践过程中包围体层次结构应用最多的就是辘对齐包围盒。轴对齐包围盒同光线求交测试速度非常快并且容易实现。包围体层次结构的创建，k a y 和k a j i y a 建议以自上而下递归的方式，创建方式与其恰恰相反的是，G o l d s m i t h 和S a l m o n 提出更加复杂的自底向上来创建包围体层次结构。自底向上的构造方式就是先把分配的第一个三角
62、形做为树的根节点，然后每添加一个场景内的实体就需要进行一次评价函数求值婚加的物体的最终位置确定是依据能使评价函数达到最优数值。最终，此嵌体将做为一个新的叶子节点或替代己存在的节点添加到树中。由于在创建包围体层次结构时，每次扫描场景内的实体都有可能改变树中已存在的节点，所以使用此种方法构建的树中内部节点的孩子数是不固定的。层次包围体结构的质量跟输入的三角形的顺序有关，建议构造层次包围体前打乱三角形顺序。3 3 2 包国体层次在G P U 上的应用遍历的主要问题是孩子节点被遍历的顺序。遍历一个f l V H 的标准方式采取深度优先的递归算法。在包围体层次结构遍历过程中，遇到根节点，进行测试光线是否
63、和包围体相交如果相交，那么继续深度遍历根节点下面的孩子节点如果测试不相交，那么光线将不会跟场景中的任何实体相交。遇到内部节点周上面的处理方法一样，只是如果判定孩子都不相交那么需要转到兄弟节点继续递归遍历。遇到叶子节点测试是否相交实际就是判断三角形片元是否和光线相交。K a y 和K a j i y a 曾建议采取寻找离光线法向原点最近的孩子节点来加速遍历解决包围体层次遍历加速的问题。G P U 上遍历包围体层次结构不仅需要不用堆栈结构就能高效遍历树的遍历方法还需要合适的包围体层次结构的表示方法。包围体层次结构的表示方法能将包围体层次做为纹理传递到片段程序中进行处理。在包围体层次结构中选择树的纹
64、理表示的方法是至关重要的，树结构中存储的是树的遍历。在所有光线遍历树的节点时，采用深度优先的方法从左到右访问树的节点。在包围体层次数据结构中树的遍历和树的表示是息息相关的。一。一。lr - - - - 幽：j 7 包阐体层次的表示和遍历过程在圈中，树结构中的节点采取先深度优先再广度优先的遍历顺序进行编码。图中的虚线箭头表示，相交测试时检测到光线与包围体没有交点时将会按照虚线的方向进行遍历下一个节点。在流内核模式下，这个遍历算法如图所示：区函凹38 包甫体层次在G P U 上的垧历模型G P U 使用闭塞查询决定是否还有片元需要再次执行迭代。算法4 在一次G P U 执行中能完成一个固定次数的迭
65、代。此方法缺点是需要不断的存储遍历状态在一遍渲染完成而没有找到交点时- 在包围体层次结构中很容易实现只需存储下一个需被处理的节点索引以及最近交点相关信息即可。包围体层次数据在纹理中以哪种格式存放数据也是很重要的。在包围体层次中数据节点可咀表示成纹理的二元或三元形式，如图所示。包围盒数据纹理二角形倒39 包嗣伴层次的纹理表示方法节点顺序的输出并被简单的存储在纹理中在包围体层次数据结构中包围体是用内部节点来表示的，三角形片元用叶子节点来表示。3 3 3 包围体层次小结使用包围体层次结构的遍历代码非常简单，这给程序员减轻了负担。本小节介绍了包围体层次数据结构的基本原理，以及数据结构的创建过程，和数据
66、结构的遍历方法，在G P U 实现遍历的细节处理等内容。采用包围体层次数据结构的缺点是必须以固定的顺序来实现遍历。34 小结在本章节中分别介绍了均匀网格，K D t r e e 和包匿体层次三种数据结构的创建过程以厦如何在G P U 上实现遍历，以及对空| 1 j J 划分策略进行了探讨研究。均匀网格和K D t r e e 都属于空间细分结构，包围体层次属于层次划分结构。在均匀网格结构实现时，首先用光线初始化核函数初始化遍历状态，再使用遍历核函数柬遍历出穿过光线的体素然后使用求变核函数找出光线与三角形面片的具体交点。K Ot r e e 在使用G P U 遍历时会被表示成纹理集合，在遍历时先
67、调照初始化核函数，然后再按需调用合并后的遍历求交核函数。遍历一个B v H 的标准方式采取深度优先的递归算法。第四章基于G P U 的光线跟踪流处理前面两个章节主要介绍了体绘制技术和光线跟踪算法并且简要介绍了算法的加速技术。本章主要介绍光线跟踪算法是如何使用G P U 图形处理器的功能来绘制体数据的，并且介绍了G P U 的数据流处理方法。其实，基于G P U 的光线跟踪算法的重点和难点就在于如何把光线跟踪任务转化为流处理的形式。416 P U 流处理结构4 1 1G P U 渲染管线和演染架构要可视化一个3 D 场景到屏幕，场景要转换成2 D 图形，这个处理过程叫渲染。渲染管线是显示芯片内部
68、处理图形信号相互独立的的并行处理单元。显旨的渲染管线是显示核心的重要组成部分。现阶段的显卡都是非统一架构的，也就是分为顶点渲染和像素渲染。那么在显示核心的内部就分为两大区域，一个区域就是顶点渲染单元主要负责描绘图形也就是建立模形。一个就是像素渲染管线主要负责把顶点绘出的图形填色。然后再往纹理贴图单元贴上纹理，一个精美的图形就出来了。传统的渲染管线主要由以F 几个组成部分构成：G P U 前端通过P C I 总线从驱动程序中接收命令和数据：用于顶点处理阶段的着色器作用是顶点渲染，主要任务足从X N A程序读取顶点的原始坐标，然后转化原始坐标为二维屏幕坐标然后交给下一阶段处理处理坐标的同时处理法向
69、，纹理坐标，颜色等信息：图元装配将顶点转换为点、线或者多边形的各种图元；在光栅化阶段G P U 确定每个三角形占有那些屏幕像素，最终这些像素将被发送到像素着色器上做处理的最后操作，光栅操作将处理像素渲染操作后的数据进行深度检测和颜色处理；帧缓存显示用来将整个图像信息绘制显示出来。最初的G P U 渲染管线的渲染方式是固定的，无法改变。随着可编程渲染器的产生，G P U 渲染臂线的这种单一的渲染方式得到了彻底的改观，你可通过定点着色器和像素着色器来自由编写程序以取得理想效果。并且在实际的图形渲染过程中会出现各类渲染器的负载不同因为描述3 D 空间图元数量不同和在图元渲染时往往纹理清晰度也是不同的
70、。在非统一渲染管线中，各级渲染器的数量是不变的，并且各个渲染器的功能是固定的。这就带来了一个隐患，就是一旦渲染器在工作过程中会出现某个负载发生变化，比如础页点着色器负担过太，但是只有某个或某几个渲染器是固定负责这项功能的，造成个别的渲染器工作繁忙其他的渲染器处于闲嚣状态，这样就给整体提高处理能力带来困难。为改变以上的缺陷，在G P U 中集成了顶点渲染器、像素渲染器和几何图元渲染器的统一渲染架构己成为发展的趋势，每个渲染单元的功能不再是特定的，它们可以根据各级处理的负载实时进行调整。统一的渲染架构从整体上统筹把握G P U的计算资源从而使G P U 上的计算更加快捷、方便，以便更好的应用于通用
71、计算啪1 。幽411 统一演染管线一1 ：习土统一渲染圈42 非统一到统一渲染槊构的趋势41 ，2 多任务并行和多数据并行从技术上说，多任务并行就是程序流折断加现场保护，主要是由任务调度器保存任务流程折断点信息，并在某个时间恢复该上下文然后继续该任务流程。多个不同的线程可以同时运行而不用经常数据交换这就是多任务并行计算的特点。多数据并行计算需要满足全部计算数据类型是一致的，还需要计算问无依赖关系。很显然多数据并行可以充分的利用计算资源，可以同时计算大量的数据。”1 。C P U 是比较适合于多任务并行处理，因为C P U 具有高速的缓存、高效的调度能力、多进程同时运行能力、分支预测处理能力。G
72、 P U 相比C P U 更适合多数据的并行处理。G P U 作为图形处理器是专门用来做图形绘制的，绘制任务是多任务并行的，顶点的绘制和像素的绘制是相互独立的。G P U 具有大量的绘制管线，能进行S I M D 运算的流处理器。幽此看来，不是说G P U 适台执行所有计算，G P U 比较适合执行数据量大。高度并行计算密集，数据l 刈依鞭度低的任务。4 2 流计算开发工具B r o o k4 2 1B r o o k 引言H L S L 、C G 、G L S L 等部是可编程渲染器的编程语言。这些编程语言都是针对图形任务设计的，它们涉及到很多底层的图形细节戋【l 议通用汁算任务程序员不容易
73、掌握这些编程语言。N V I D I A 针对自己的平台推出了C U D A 通用计算技术而A T I 则推出了A T IS t r e a m 通用计算技术，它包括C A L 和B r o o k + 。这些通用计算技术隐减了底层的图形细节，碱轻了程序员G 州通用计算设计的负担，并且B r o o k + 是一个基于开源项目B r o o k G P U 的扩展。在基于G P U 的光线跟踪算法研究中B r o o k 一直都受研究人员的关注和研究。B r o o ktJ盏r眦j 雠最初是为流处理机开发的语言，因为它非常适合G P U 的流处理运算，并且具有高级编程能力，涉及底层图形知识较少
74、，所以在G P U 刚丌始支持可编程渲染器时就出现了针对G P L i 的B r o o k G P U 项目。B r o o k O P U 是为G P U 开发的编译器和运行时环境。B r o o k 通过调用O p e nG L 和D i r e c t3 D 柬支持N V I D I A 和A T I 的图形处理器。4 2 2B r o o k 架构B r o o k 架构由编译环境B R C C 和运行时库B B T 构成。编译环境负责将后缀名为b r的源代码转换为c p p 文件。编泽器通过B R T 将B r o o k 原语转化成大型应用中常用的c H语法渲染语言，从而达到方便
75、链接的目的。B R T 类库主要提供通用接1 ：1 1 类库并能支持多个具体硬件系统。B R T 能为原晤提供在各类硬件结构上应用的后端支持是跨平台的软件屡。根据特定的环境和用户请求，在运 亍时选择特定后端如D i r e c t X ，o p e n f J LA B R ，和C + + 等。幽43B r o o k 系统架构B R C C 的运行可以简单分为：输入源文件，扫描转换类型，输出内容。第一个阶段是，编译环境对输入的源文件的解析结果存贮在转换单元内；第二个阶段是编译环境扫描转换单元，把具有B r o o k 特性的部分转换为特定的B R T 类型；第三个阶段是，所有转换单元经过编译
76、环境的遍历扫描后输出各个节点内容。B R T 随后生成c 十十代码供运行时库调用。没有转换的单元内窖直接复制到B R T 中。B R C C 源于一个叫做e l o o i 的丌源项目“”。B B T 为B r o o k 提供跨平台的后端支持。42 3B r o o k 的流处理模型B r o o k 是采用流处理模型”发的，流处理模型综合了数据流和核函数的概念而形成的一种数据处理模型，它是C 语占的扩展。核函数的处理对象是数据流。数据流是一种格式一致的类似数据格式的大型数据集合。流处理模型如下图4 4 所示输入流数据经过核函数的处理转化为输出流。核函数具有并行计算的功能，在一个流上调用核函
77、数就是此流数据都需要进行同样的训算，符合多数掘并行特征。核函数处理的数据越多，密度越高，性能越高。流是核函数的操作对象，流通过调用多个核函数来完成复杂任务。输入流输出流图44 流处理模型流是B r o o k 中新的数据类型流元素是指在流数据类型中可以并行参与运算的单个数据。流元素集合的索引称为流变量。流的声明格式如下所示：f l o a ta ：f i o a tb 3 2 ：f l o a tc ：f l o a td ：流声明格式中“ ”用来指定这些变量为流变量，它在流数掘声明中只能出现一次且必须紧罪变量名出现。目前在B r o o k 中没有定义流的数组和流的流数据格式。流声明方式中第
78、一行声明一个浮点数的流第二行声明一个三行两列浮点类型数组的流。第四行声明的数据流中元素个数必须是4 0 0 的整数倍，高维数目由运行环境根据实际元素个数临时得到。在B r o o k 中，流操作函数s t r e a m W r i z e 和s t r e a m R e a d 主要是用来实现从内存中读取和写入流操作。非核函数调用流变量主要是使用指针传递方式，调用函数对流变量的改变将会整个影响流变量的数掘。语法：s t r e a m R e a d ( 数据流，来源数组，第一维中起始地址偏移量，第一维中数据长度第二维中起始地址偏移量，第二维中数据长度，、示例：f l o a ts ( ：
79、f l o a ta 7 ：f l o a tb 3 5 ：s t r e a m R e a d ( s ，a 0 ，7 ) ：s t r e a m R e a d ( s 。b ，0 3 0 ，5 ) ：s t r e a m R e a d ( s ，a 3 ，2 ) ：s t r e a 衄e a d ( s ，b ，1 2 ，i ，2 ) ：B r o o k 的流操作函数中以s t r e a m R e a d 为倒，介绍的是语法定义规则。s t r e a m R e a d函数声明己经很清楚的说明了流操作函数的用法。第一行操作函数是将数组a 中的数据读入流s 中，第三行是将
80、数组a 中的a 3 和a 4 读入到流s 中。s t r e a m R e a d A l l 和s t r e a m W r i t e A l l 这两个流操作函数主要功能就是读写所有数组元素，其实它就是s t r e a m B e a d 和s t r e a m W r i t e 函数的功能的扩展，如将这两个流操作函数的数据长度设为最大，并把偏移量设为零就能实现s t r e a m R e a d A l l 和s t r e a m W r i t e A l l 流操作函数的功能。流中元素类型可以是用户自定义类型，向量和浮点型。在流变量使用过程中，不能在核函数范围外将流变
81、量初始化为静态变量、单独访问流元素和对漉变量赋值，是因为流结构只是作为数组、核以及流操作的连接中介。核函数是由关键字K e r n e l 标示的B r o o k 中的特殊函数。流数据调用核函数时，将会对流数据中所有元素都进行一次核定义的操作。核函数一般是以并行方式运行的，执行效率较高，主要是困为对流中的各元素操作是相互独立的，彼此互不影响。核函数接受的参数包括：由c 语言数组语法标示的可通过下标随机访问流数据的只读G a t h e r 流和用于存储运算结果的输出流，由只读数据组成的输入流。在核函数中的非流参数都是只滇纳。k e r n e l v o i dS a X p y ( f l
82、 o a ta ，f I o a t 4x f l o a t 4y ( ，o u tf I o a t 4r e s u l t ( 1lr e s u l t = a x + Y ：B r o o k 针对核函数中输入和输出流形状不一致的情况，会把输入流形状转化为输出流这样的操作放在核函数调用数据之前来完成。例如将1 2 维的a b 扩展成2 2 雏的a a b h 。系统为便于对数据流区分处理而采取强制区分输入输出和G a t h e r 流，区分的目的就是高效利用缓存。系统采用固定方式访问输入流元素，只处理没有访问过的流数据但是可能重复使用G a t h e r 流的元素。为保证计算井
83、行性，核函数的操作会受到一定的限制。流处理和向量处理数据是显然不同的。向量运算只能进行算术操作，并且需保持向量寄存器中数据。但是核函数可处理任意类型计算井且只需将运算结果写入存储器即可，这样就节省了内存带宽。规约是以并行方式从数据集中的所有元素获得运算结果的机制。为方便系统选择最合适的底层体系结构的顺序进行运算，要求数据处理操作具有联台性，这样也方便运算的并行执行。流、核和规约都可以通过B r c c 和B R T 方便地映射到G P U 上。B R T 通过多通道的方式实现舰约。舰约操作的时l 白J 复杂度是线性的因为在多通道机制中的每个通道中只产生较少的2 至8 个值，并且在每个通道中，通
84、过规约操作将读取的8 个相邻的流元素运算结果输出。流处理模型首先将流变量初始化为纹理，B r o o k 对存储在纹理内存中的流数据进行调用渲染核函数进行处理，然后通过B r c c 来将核函数内容编译成c G 语句。在运算过程中用静态寄存器来传递非流参数B r o o k 流处理模型在整个运算结束后，将结果绘制到包含输出流的纹理中。43 小结本章介绍了G P U 渲染管线和渲染架构。重点介绍了光线跟踪绘制算法所使用的B r o o k 流处理工具。B r o o k 对存储在纹理内存中的流数据进行调用渲染核函数进行处理B r o o k 流处理模型在整个运算结束后将结果绘制到包含输出流的纹理
85、中。第五章算法实现本章节主要是讲光线跟踪体绘制算法是如何实现的。光线跟踪体绘制主要是由两个功能模块完成，一个是负责整个光线跟踪体绘制算法的整体控制和平街，它主要是由C P U 柬完成；另外一个功能模块主要负责光线跟踪体绘制的计算工作，它主要是由G P U束完成，此功能模块又细分为光线生成、场景遍历、模型求交、渲染和光线衍生四个计算内核束完成的。51C P U 端控制部分C P U 控制部分主要是完成整个光线跟踪体绘制算法的整体控制和计算的平衡。在G P U 控制部分有一个渲染和光线衍生的功能内核，它在衍生光线时会产生反射和折射光线，整个衍生光线过程是一个多路径的复杂计算过程，但是需要由C P
86、U 来控制路径之间的切换。当光线生成或衍生出时生成的光线将按I | 先后顺序压入栈，C P U 无法同时计算这些光线需要C P U 对G P I I 的资源进行统一分配控制。本文研究的侧重点就在于研究光线的遍历和求交。因为光线的遍历和求交运算过程就是需要不断的访问存储空叫和不断的判断光线与三角形的相交问题，所咀这两种操作会直接影响到渎取存储空州大小和速度的限制和整个算法的速度控制的问题。总结以往的光线跟踪体绘制算法，它们采用的遍历加速结构有以场景的几何基元为中心和以场景的空间为中心的组织方式之分。本论文采用以场景的空白】为中心的组织方式构建类B S P 的算法并且采取一组光线并行入栈柬提高整体
87、效率的。5 2G P U 端控制部分5 2 1 场景部分约定由于本文就是想通过模拟一个场景，通过设计一种提高体绘制算法的加速技术来实现加速然后通过实验来验证算法思想的了F 确| 生和可操作性。基于此目的，现对模拟的场景细节做一下约定，因为不同的场景细节将需要不同的遍历算法来实现，比如不同的场景空间结构将影响到使用不同的遍历方法，相交测试算法的选用直接受算法处理的圈元类型影响等等。在本欢设计的光线跟踪流处理模型中，约定采用最基本的三角形几何图元柬对场景中的物体进行建模。之所以采用三角形几何图兀主要是考虑到以下几方面因素：第一，光线跟踪算法可以绘制几乎所有的几何闰元，但是实际应用当中很少会用到复杂
88、的几何圈元米建模并且许多建模工具可以轻易的把复杂的几何图元转化为三角形网格模型，三角形几何图元可以直接在图形处理器上绘制简化了算法的设计和显著提升了速度。第二，在G P U 计算过程中，三角形几何图元可以很容易的映射到纹理内存中方便数据存取。第三，仅采用三角形几何图元米表示场景，这样可以简化光线跟踪流处理模型。本次设计的光线跟踪流处理模型决定采用静态场景和均匀网格加速来实现，原因有二。第一，静态场景不需要实时束捣建，这样可以节省实时构建带来的存储带宽压力和算法速度影响而均匀网格加速结构的遍历易于实现；第二，静态场景的各个部分的特点比较适合映射到光线跟踪流处理模型中而网格结构适合流程控制。5 2
89、 2 光线跟踪核函数和数据流的设计( ：P 【具有高度的并行数据处理能力，超强的晦量数据处理能力G P U 是并行计算定的未来tG P U 的这些特点报显然最适台应用于光线跟踪这样需要高度并行脚1 处理海量数据的场景中。出于光线跟踪算法的并不能直接应用G P U 来处理。需要对算法进行改进，最简单的就是把光线跟踪算法改写为流处型任务，进而把G P U 当做一个流处理嚣来使用。这一部分主要是讨论光线跟踪流处理模型设计 3 l l g 基于流的光线跟踪成为以后许多C , P L I 光线跟踪系统的基础。叫。“把G P U 用做流处理器，首先需要讨论以下几个问题。第一个问题光线跟踪任务和其他一般的流
90、处理任务是不一样的。在光线跟踪任务中的流处理器的核函数不但能读取数据流中的数据，而且能读取场景网格中纹理内存中的数据。之前，通过创建索引流就可以完成访问全局内存的目标，这个索引流包含着内存地址。通过索弓 流获取的数据直接输出到其它核函数中。此数据获取方式存在一个弊端那就是一旦数据需要全局访问内存，但是在编译阶段无法确定其内存地址，此时程序员需要把程序分别设计成更多细化的核函数。目f ；i 为止程序的分割设计核函数工作已可以通过较低层编译系统自动柬完成，这样就可以在程序员设计核函数阶段直接读取全局内存数据，这显然给程序员编写核函数的工作减轻了负担。再者，均匀网格场景数据通过把每个三角形顶点的三维
91、坐标值存储到像素纹理中。网格纹理中存储的是场景中的体素中包含的三角彤在三角形列表中旮匀位簧索 1 三角形列表纹理中存储的是体素中包古的三角形的三个顶点存储在三角形顶点纹理中的地址。均匀网格的场景纹理存储方式见图5 I 所示，首先可阻从网格纹理内存中找到体素为【对应的三角形列袭纹理指针3 ，按照此索引找到三角形顶点纹理索引，然后按照索引找到三角形三个顶点的数据。体索0体紊I体素2 体索3体素4体素5oIN U L LfOl23450网格纹理二角形州表纹理三角形顶点纹理圈5 纹理内存中存储场景弼格虽后一个问题就是，程序员通过把光线跟踪的任务分割成几个内核函数然后通过数据流柬把这些内核函数连接在一起
92、，这样就完成了光线跟踪映射到流处理模型上”“。通过多通道的方法来实现数据流连接核幽数。在图5 2 中，一个输入像素数据流通过核函数的处理输出像索数据流，而此时的输出像素数据流就被拷贝进纹理内存中在光栅化阶段一旦开始生成下一区域的像素时就意味着上一区域的像素光栅化已经结束，此时可以把读取纹理内存的数据输入到下一通道核函数来生成像素信息。但是有的纹理空间根本无法实现数据的存储，只能够重复进行先把数据写入，再到需要数据时把数据重新读取出来。只有所有的像索都被处理过之后，流数据才能拷贝到纹理内存中去然后硬件产生一个中断动作系统就会自动存储当前时削点的各个内存和缓存的内容和设备当前的状态以便中断结束对方
93、便系统的恢复。如果帧缓存和纹理内存在硬件上是同一空间，那么此时的内容复制就只是一个指针变换了，这样就降低了内存读取带来速度上的影响。输入像素数据流渲搬器输出像素数据流酗52 多通道方法实现核的连接通过上面的规定，现可以把光线跟踪流处理模型分为光线生成、场景遍历、模型求交和渲染和光线衍生四个核函数，每一个内核函数相对应6 P U 中路径的计算然后通过数据流柬把这些内核函数连接在一起这样就完成了光线跟踪映射到流处理模型上。在图53 中，图中每个核函数用矩形边框来表示，核函数通过读取纹理内存来获取各个核函数的所需要的输入数据，然后各个核函数也可以相互调用，它们之间的数据流向通过虚线来指向。光线数据需
94、要经过相交测试划断是否和场景中的体素相交，光线数据经过相交测试函数处理过后输出的结果分两种情况，一种情况是如果在相交测试没有产生交点时将会返回遍历的光线，另一种情雠就是如果相交泖j 试产生了交点，那么将会输出需渲染的碰撞点。本部分说的渲染需要生成衍生光线并将它返回继续遍历，还需要汁算像素点的R 6 B 值。第一个核函数就是初始光线生成核函数作用就是生成初始光线的起点和方向。通过给定观察点的位置和方向等参数柬为每个像素生成一条初始光线。生成的初始光线与场景的边界进行相交测试束确定是否能够与场景中的体素相交，如果铡试没有产生交点就| 兑明此光线不会与场景中的体索相交，也就不会再继续后续的操作：如果
95、测试已产生了交点则继续后续的操作。光线体素对碰撞点幽53 光线跟踪的流处理模口本次试验遍历模型中场景遍历采用的是3 D D D A 算法，它是二维画线程序的三维版本，用柬实现网格间的移动。算法将采用按照光线向量来访问场景中的已经细分的网格图元。当每一个遍历步骤完成后核函数将会读取网格中的数据。如果核函数读取网格数据为空，这就意味着在此网格中不含三角膨光线将被遍历核函数输出到核函数内继续做下步的循环测试。另外一种情况就是截包含在网格中核函数将会把他们输出到相交测试中继续后面的操作。在流处理器中的每一条光线都将会被遍历一次，询历核函数被调用一次就意味着光线在网格中行进了一格。这就意味着每次光线梭核
96、函数调用一次，有两种可能要么继续遍历要么继续相交铡4 试。总的来说，在整个相交测试过程中光线同场景体素中所有的三角形进行一次遍历进行判断是否有相交，然后把产生有效碰撞点的光线和三角形数据送到渲染核函数中。模型求交内核函数主要作用就是完成交点的探测及光线与表面基元的求交计算。我们将选择使用M a l l e r 和T r u m b o r e 提出光线乖l 三角形面片的求交算法咖。此算法的主要思想就是通过平移和旋转产生向量( t ，u ，v ) ，其中t 代表光线起点到三角形面片所在的平面距离，( u v ) 代表碰撞点在三角形所在平面的坐标。通过有效性检测就可以判断碰撞点是否藩在三角形图元上
97、，而光线与三角形相交的位置坐标就被标示为碰撞点的信息。之所以选择此光线与三角形面片求变算法是因为它不用先对三角形所在的平面方程进行预处理，只用三角型的顶点坐标位黼就能轻松在图形处理器上实现。此光线与三角形面片求交算法还有个优点就是不用琐处理三角型所在平面方程，仅仅知道三个顶点坐标就能完成任务，无形之中就降低了因为存储三角型网格带来的内存压力。在此算法中的纹理内存中一个纹理代表着三角型的一个顶点。例如6 5 5 3 6 个三角彤需要使用3 个2 5 6 2 5 6 的纹理。在光线与三角形图元相交过程中系统将需要另增用于存储光线参数值的纹理。光线会全部遍历与体素中的三角形图片判断是否相交，相交测试
98、出光线与三角型图元有有效碰撞点，那么将会把此光线送到渲染核函数，如果测试出光线与三角形图元没有有效碰撞点，那么此光线会被送到遍历核函数继续遍历。在纹理存储的过程中如果遇到三角形圈元个数不是纹理的接数倍，那么系统将会自动采用用零填充的方法进行扩充纹理内存。渲染和光线衔生核函数主要工作就是负责将光线与三角形圈元相交和其它因素累加到帧缓存的表面R G B 值。渲染核函数需要处删存储在纹理内存中的各个三角形的顶点法向量值和三角形顶点颜色值。另外，如果光线与场景内三角形图元相交，那么渲染核函数就会生成相应的反射折射或阴影投射光线等衍，土光线，然后这些新生成的衍生光线会继续遍历。如果渲染核函数选择的衍生方
99、法不同，那么就会产生不同的光线跟踪效果，比如只发射隅影射线的阴影蕊和不产生任何衍生光线的光线投射效果等等。在渲染核函数中生成的衍生光线将会被当做遍历的输入流继续循环，当渲染函数经过一定次数的循环后结束并且在衍生光线上加上了权值，为了使它的颜色值贡献和其他光线区别丌来，然后把所有光线的颜色值混合 r 算到第一次碰撞的渲染效果中“”。光线产生器核函数主要用柬产生一束光线流，这束光线流中的每个光线相关连着图像中某一个或几个像素。遍历网格核函数首先作用于光线产生器生成的光线，然后光线逐步遍历网格直到碰到场景中的体录为止。年甘交的光线和体素就会被输出到求交测试内核。首先通过二维K D - t r e e
100、 束存储场景信息。数据结构中每个内部节点表示分离平面，每个节点表示轴向包围盒。其次，求交和遍历前中序线索化K D t r e e 为线索二叉树。然后，当光线同时穿过两个子包围盒时先遍历第一个节点，不用把第二个节点压入堆栈- 如果遍历的节点是叶子节点且测试有交点那么返回成功否则继续遍历后续节点。本算法通过建立线索二叉树柬避免堆栈操作带束的丌销。线索二叉树在初始化时一次完成，算法的平均时间复杂度为0 ( 1 0 9 2 n ) 。在实际应用中，通过限制中间节点的深度来保证二叉树的平衡性。光线跟踪内核实际上就是复杂场景和一个光线树的遍历求交过程，每个像素点的最终像素是由沿着光线树向下迭代求交获得。在
101、G P U 中利用光线栈来管理每次求交生成的子光线。利用循环迭代来替代反射光线的递归调用。光线终止在相交点时将这个相交点像素值写进累加的图像上。如果产生了衍生光线，则需要将衍生光线返回到遍历阶段，继续遍历。53 小结本章完成了光线跟踪算法在G P U 上的映射。完成了一个简单的光线跟踪算法的流处理模型设计。浚模型采用三角形表示场景物体，均匀网格作为加速结构。算法的任务被分为初始光线生成、遍历网格、相交测试、渲染四个核函数。在第六章中将给出试验结果。第六章实验结果与分析实验目的：在不同场景复杂度测试环境下，对基于G P U 加速的光线跟踪体绘制技术和基于C P U 的传统递归方式的光线跟踪体绘制
102、技术的性能进行对比羽0 试。硬件平台：采用A M DA t h 0 1 3 I IP 3 4 022 G I I z 处理器N v i d i aG e l o r c e8 8 9 0 G T S 图形显卡。系统中使用的是由1 2 8 1 2 8 1 2 8 个体素的默认模式的场景加速结构网格精度。采用V i s u a l c + + O p e n G L 和c g 语言柬实现算法程序。6I 实验结果试验使用的场景包含的三角形面片数从7 9 5 8 到6 0 9 6 0 呈复杂度递增。静态场景的加速结构构建都是在预处理阶段完成的。由于本次试验目的是测试G P U加速对场景绘制速度的影响，
103、本次基于G P U 加速的光线跟踪绘制速度的测试试验不包括加速结构构建的时间。以下是基于G P U 加速的光线跟踪体绘制的速度结果。袭l 光线跟踪分别在C P U _ 手H G P U 上实现的加述比较三角形面片数加速方法分辨率79 6 82 35 8 46 09 6 05 1 2 5 1 251 02 7C P U 加速方法1 0 2 4 X1 0 2 41 22 57 35 1 2 5 1 24 5 3 24 3 8 95 8 1 5G P U 加速方法1 0 2 4 1 0 2 41 9 4 6 92 02 1 83 0 1 6 06 2 结果分析通过分析基于G P U 加速的光线跟踪实
104、现的试验数据，现得出以下结论：第一，基于G P U 加速的光线跟踪实现方法与基于C P U 的传统递归调用实现方法相比在场景复杂度较高时，使用具有高性能计算能力的G P U 表现的更突出。第二，如果场景中存在大量的空体素这将导致因遍历空体素耗费大量的资源如果场景复杂度越低，分辨率越商的情况下。凼空体素浪费时闻越明显。当光线遍历空加速结构和有效场景绘制的耗叫达到一定比例时基于( ；P u 加速的光线跟踪甚至不如采用C P U 加速的光线跟踪方法，第三。在分辨率一定时，基于G P U 加速的绘制技术在场景复杂度增加时消耗时间的增加并不明显。主要是因为光线遍历加速结构趣的加速作用。第四，整个系统实现
105、的灵活性和绘制速度欠佳，因为在试验中采用的图形硬件处理器不变持条件分支和循环。第血，如果想使加速性能更优，则应从两方面改进系统性能，一是通过均匀网格技术迸一步优化：二是通过进一步降低空体素的遍历概率。63 小结本文实现了基于G P U 加速和C P U 的光线跟踪体绘制，从两者的试验数据可看出使用G P U 加速具有明显的优势，既能保证算法的质量又有高效的运算速度。C P U 和G P U之间的数据交换限制与负载均衡算法是急切解决的问题。随着G P U 可编程能力增强，C P U 和G P U 之阃的配合和协调处理将更和谐性能也更高。结论光线跟踪体绘制算法在现实生活中被广泛应用于计算机科学可视
106、化领域，对于将复杂抽敦数据转化为形象的真实感图形图像，方便人们理解和交互有重要的贡献。利用G P U 束实现加速，主要是利用G P u 无可比拟的大规模数据并行处理能力和可编程性，使基于G P U 加速的光线跟踪体绘制算法能应用在望加广泛的交互式和实时绘制应用过程中。本文在深入研究了光线跟踪算法和相关加速算法运行的基础上，针对其各自的忧缺点提出了相关的改进观点实现了基于流处理的光线跟踪体绘制算法，并针对不同场景和不同分辨率对采用c P U 和G P U 处理器进行丁对比分析。主要研究工作如下：I 对比分析了现阶段计算科学可视化过程中使用的真实感绘制算法的优缺点，以及国内外采用何种方式来加速绘制
107、算法的。2 对光线跟踪算法的基本原理进行了分析，对比了针对光线跟踪算法是如何分别在软件和硬件上实现加速的。3 针对在G P U 上经常使用的三种加速结构，均匀网格，K D - t r e e ，B V B 的加速效果和在G P U 上实现的细节进行了对比分析。4 针对基于G P U 的图形渲染架构和流处理丌发工具，利用G P U 的可编程性，详细讲述如何在G P U 上实现光线跟踪流处理模型。5 在不同场景复杂度和不同分辨率的情况下，对比分析了使用C P U 和G P U 在各自场景下的各自的优壤点。虽然本文研究已取得了初步成果但由于G P U 的迅猛发展和光线跟踪技术的多样性，以及时间关系，
108、使得基于G P U 加速的光线跟踪体绘制技术的研究工作具有一定的广泛性，今后的研究工作将进一步解决本文中存在的问题和不足之处。主要有以下几方面：1 随着科技的发展，多核C P U 的整体性能在不断的优化，并且6 P u 的并行处理能力和编程能力也在不断的提高，未来这两种处理嚣谁更适合光线跟踪体绘制的运行值得进一步的关注。2 由于本次试验主要是想测试G P U 加速对体绘制的影响，以及对比C P U 来测试。但是都是在静态场景中进行的光线跟踪体绘制，咀后将进一步考虑在动态场景中进行试验比较分析两种处理方式对光线跟踪体绘制的加速效果。致谢本文是在任涛剐教授的悉心指导下完成的。导师渊博的知识。严谨求
109、实的科学态度，踏实进取、勇于开拓的治学精神以及精益求精的工作作风使我终生受益。研究生期间，在学习和生活各方面都得到任老师无微不至的关怀和帮助。至此学位论文完成之际，谨向导师表达我最崇高的敬意和深深的谢意。感谢长春理工大学计算机科学技术学院、医学图像与数字医疗实验室的各位老师和同学多年柬在学习、工作和生活方面给予我的帮助。在我攻读研究生期目】，陈占芳老师，师为礼老师，从各个方面给予了我热情的支持和帮助，为我提出了很多好的建议，让我受益匪浅。在此向他们致以最诚挚的谢意。同时，要感谢尹方超，王佳杰同学，谢谢你们在我的学习和生活上的帮助。感酣我的父母，是他们不辞辛苦的工作为我创造了这么好的学习环境衷心
110、感谢父母对我的养育和教诲之恩。最后，谨向参加论文评审和答辩的各位专家和老师表示感谢! 感谢你们在百忙之中抽出时间评阅我的论文。参考文献。：篙盎毋；。巽亲；品”。”。“”m m ；e n t ，n cC a m - n t n s 。m ”t e r2 店弹圣等= 维教擀蟠可桃化北京：清毕人学j H 版机1 9 6 9码3 芸搿暑1 8 9 8 , 7 。1 2 l l n f e 4 H ) “K 6 3 - W a l r 船e 6 加8 曲b e “g ”肿s o “。n3 。s u r 精c e ( h s t 州i 凸n l g 。n t hc 咖叫t e r们葛军舒毕忠- 鲍旭东基于
111、面绘制的G P U 体绘制加建成用科学学推2 0 0 9 2 7 ( 2 ) ：1 6 7 _ 7 t凸12 芝罢盏2 胡篮村t 陈松彝锋甚十。剐髑慷直接伟绘删算法分析。评价计算机成用研究2 0 0 9 2 6 ( 66 o h nM o n t r y T h eG e F o r c e6 8 0 0I E E 8c 0 叩t e rS o c i e t y 2 0 0 5 ，2 5 ( 2 ) 4 1 57 彭蜓￥- 右救茬傩绘制技术n 医学目f 桃化中的新艘腱中阔留悔钊彤学搬2 0 0 8 1 2 ( 2 ) ：l O 一1 6”3 嚣器品恕黑譬嚣琶怒等酱竺器黜V o 。l u m
112、。eR e 。n d e r i n 。g 鬻端鬻w 一9 L e v o y “V o l u m eR e n d e r i n gb yA R a g t i v eY i s u a lC ”p u t e r1 0 9 0 6 “) ：2 - 7”；：裟j ? 0 ：急：R a 。J n 。h “。 L 。J 。H e s 。s e 。r 。M a 。s s i 。v e ，1 ：。P a r a 1 。l e 。lP ，r o 。c e s 。s o r 。f o 。rR ”w * m 1 1 J 厦放忤- 沈振康等，一种用于安时体绘制系统的自适J 娓骄样算法- U 于学擞2 0
113、 0 23“：芒鬣i 玉慧嚣浆：。A 。c c e l 。r 。a t 。i o 。nT e 。h 。n i q “”“”1 R e n d e r i n g 一一- m 。r13 R e p p l i n g e rM - L o f f l e r T h i e l e nH e ta 1 F l e x i l AeA d a p t a t i o S ev ief o D iti b u t e dn n “r i “1 n ：P 1c c e e d i n g so ft h e9 t hE u r o g r a p h i e sS y m p o s i u mo n
114、P a r a l l e lG l a p h i dV i s l ia t i o nM u n i c h 。G e y 2 0 0 9 8 9 - 3 01 们G l e g o r yJtF r a n c i sMR R o b e r tDC 坤yt ta c i n gs o l u t i o nf o rd i f f u s ei n t e e f l 铫佣I n ：川r 吐抽e e 。d 。i n 。g ? o u f s I “：器：2 c o n f e r 印。删p u ”。G r 印”oI n t e r a c t i v eh h n i qs - S
115、a n 毗e g o ，1 5 jP a b s tH S p r i n g e rJP ，$ c h o l l m e y e r ，L e n h m d tR e ta lR 8 ，c t ig 。ft r l m e d 刚R 8 s ；缸f 虬e sm I n ：P r o c e e d i n g so ft h e2 0 0 6I E E ES y m p o s i u m 。nR a t e , a c t i v eR a yT r a c i n & S a l tL a k et i t y ，Ue a h U S A 、2 0 0 6 1 5 l _ 1 6 0
116、1 6 】G r o BM L o d e w s a iGB e r t r a m 乩e I a lF a s tI m p l i c i K D - T r e e s ：A c c e l e r a t e dI s o s u r f e 托E 时h i n ga n dH a x i m u mR a t e n s i l ；yP r o J e c t i o nf o rL q eS c a l a rF i e l d sI n ：P r o c e e d i n g so fC p u t e rG r a p h dI 眦酊n g 】| 1 r I s b r u
117、 c k A u s t r i a 2 0 0 76 7 7 4i 7 s t e g r & s i m p l e df l e x i b ev o l u m er e n d e r i l n e n d e r i n gf r a = e w o r kf o rg r a p h i c s h ”0 m 、r h 9 “r a y e a s t i n g t c ) P r o c e e d i n g so ft h eI n t e r n a t i o n a l l _ h s h o p V o lm eG la p h i c s 2 0 0 5 ：1
118、 8 7 一1 9 51 6 U l l m a | 1T P r e i d e lT B r a d e r l h lBE f f c i e n ts pL i “T e x t u r e 6s c e n e si nv e n e zT igl nP r o c e e d i r i g so f2 I l r o g r a p l | i c sC o f e r e n c eG r a n a 柏S p a i n ，2 0 0 3 ，1 2 6 一1 3 3【钉故徘杰E 芝成枷# B 等羲于中舟瑚 性光线跟踪计算计算机学撤2 0 0 73 0 ( 8 ) ：2 6 2 2 74 Q
