浅论可编程图形加速器相关应用技术研究

《浅论可编程图形加速器相关应用技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

上海交通大学硕士学位论文可编程图形加速器相关应用技术研究姓名：冯煌申请学位级别：硕士专业：计算机应用技术指导教师：翁惠玉20080301 上海交通大学硕士毕业论文摘要摘要作为虚拟现实的关键技术，虚拟场景的渲染，一直是虚拟现实研究工作中的一个重点。在三维游戏，虚拟训练系统，三维地理信息系统等应用中，如何使虚拟场景给予用户更为真实的体验，是虚拟现实研究工作者的目标之一。可编程图形加速器（GPU）的迅速发展为更好的虚拟场景渲染效果提供了硬件基础。自1993年以来，GPU的处理能力以每年2.8倍以上的速度飞速发展，当前最先进的民用图形处理器，其数据处理能力已经不亚于甚至在某些方面已经超越了最先进的CPU。不仅是处理能力的提升，GPU还在原有的固定流水线中引入了可编程功能，给予用户在使用GPU进行图形的渲染着色上有更多的自由度，更使GPU拥有了通用处理器的一些特性，给GPU的应用提供了更为广阔的空间。在这样飞速发展的图形处理能力面前，许多在不久前还无法想象的实时图形特效都成为了可能。如何充分利用GPU如此强大的处理能力来实现一些复杂的图形应用，增强虚拟现实场景中的用户体验真实度，成为了虚拟现实研究领域的热点。本文的研究工作主要包括以下内容：首先，本文对实时阴影的渲染算法进行了研究。分析了目前流行的硬阴影生成算法的实现原理，比较各算法的局限性和优越性，并且针对阴影图算法中由于算法本身所带来的偏移量问题，提出了一种改进的自适应偏移量算法。该算法只需设置简单的几个参数，由程序自动分析场景特性取得一个合理的偏移量，这种方法相对于目前存在的 上海交通大学硕士毕业论文摘要解决方案具有不再需要由程序员依据场景手动调整偏移量大小的优点。其次本文研究并实现了一种完全基于GPU的粒子系统。在虚拟场景中，粒子系统能够相当真实得模拟诸如云，雨，气流等不定型物体，有着广泛的应用。但是普通的粒子系统在实时仿真中，粒子总数最多只能达到10000个左右。其中瓶颈在于粒子数据从主处理器到图形硬件的传输和CPU的并行处理能力。利用GPU的多通道并行处理功能，提高处理速度，可以很大程度地增加粒子系统实时仿真应用中的粒子数量，从而可以提高虚拟环境的逼真程度。实验证明基于GPU的粒子系统的实时性能远远高于普通粒子系统。论文的第三部分对在GPU上实现图像滤波进行了研究。图象滤波对于处理器的并行处理能力的要求是相当严苛的，而GPU的某些计算处理能力的特性恰恰满足此类计算的要求。本文讨论了在GPU上两种图象处理工具的实现：频域上的快速傅立叶变换和空间域上的卷积运算，并评估了这两种工具在GPU上的性能表现。关键词：虚拟现实，可编程图形处理器，实时渲染，阴影算法，快速傅立叶变换，卷积，图像滤波 上海交通大学硕士毕业论文ABSTRACTABSTRACTAsakeytechnologyofVR(virtualreality),real-timerendering,isalwaysahotspotinVRresearching.Inapplicationsuchas3Dgame,virtualtrainingsystem,3Dgeometryinformationsystem,VRresearchersareaimingathowtogivetheusermorerealexperience.TheimprovementofGPU’scomputationalabilityhasprovidedagoodhardwarefoundation.From1993,everyhalfyear,therewillbeanewgenerationofGPUdeveloped.ThemostadvancedGPUofnowalreadyobtainedthesimilarcomputationalabilityofthemostadvancedCPUofnow,evenmorepowerful.TherevolutionofGPUismorethancomputationalimprovement,theprogrammablepipelinesubstitutingthefixedfunctionpipelineisthemostimportantrevolution.Itgivesusersmorefreedomwhendoingrendering,alsogivesGPUsomefeatureofgeneralprocessor,whichgivesamuchmorebiggerspaceofGPUapplication.WithsuchafastgrowingGPU,somerealtimerenderingeffectthatcouldnotbeimagednotaverylongtimeagohasbecomepossiblenow.It’snowahotspotinVRgraphicareaabouthowtomakefulluseofsuchacomputationalabilitytoimplementsomecomplexgraphicapplication.Myworkswillbefocusedonthefollowingtopic:First,wehavesomeresearchonalgorithmofrealtimeshadowrendering.Weanalyzedsomecurrentpopularshadowalgorithm,includingthegoodnessandweakness,andinordertosolvethebiasproblemaboutshadowmapsalgorithm,wepresentanoveltyAdaptiveDepthBiasAlgorithm,whichcansetthedepthbiasaccordingthe3Dsceneseasily.Comparedwiththetraditionalalgorithms,ouralgorithmcananalysesthecharacteristicofthe3Dscenesandsetasuitabledepthbias.WealsoimplementedaGPUbasedparticlesystem.Particlesystemhavebeenusedwidelyinrenderingshape-unfixedobjectssuchasrain,cloud,wind.Buttheordinaryparticlesystemscanonlyhandleupto10000articlesinrealtimesimulation,thebottleneckarethetransferofparticledatafromtheCPUtotheGPUforrenderingandtheparallelcomputationalabilityofCPU.UsingthemultiplepassageofGPU,itispossibletoincreaseanumerousofparticlesintherealtimesimulationtoenhancetherealityofthescenes.TheexperimentsprovethattheparticlesystembasedonGPUhasagreatabilityinrealtimesimulationthantheordinaryparticlesystems.Thethirdpartofthispapermakesomeresearchongeneralcomputing 上海交通大学硕士毕业论文ABSTRACTimplementationonGPU.Somescientificcomputingsuchasimagefiltering,requiresapowerfulparallelcomputationalability,whilethesomefeaturesoftheGPU’sabilitycanmeetsucharequest.WegivetheGPUimplementationoftwobasicapproachestoimagefiltering–FastFourierTransform(frequencydomain)andconvolution(spatialdomain),andevaluatethesemethodsintermsoftheperformanceandsuitabilityforGPUimplementation.Keywords:VirtualReality,GPU,real-timerendering,shadowalgorithm,FastFourierTransformation(FFT),convolution,imagefiltering 学位论文原创性声明上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日 学位论文版权使用授权书上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密□，在年解密后适用本授权书。本学位论文属于不保密□。√（请在以上方框内打“√”）学位论文作者签名：冯煌指导教师签名：翁惠玉日期：2009年2月25日日期：2009年2月25日 上海交通大学硕士学位论文第一章绪论第一章绪论1.1虚拟现实技术的发展和关键技术虚拟现实是在计算机图形学、计算机仿真技术、人机接口技术、多媒体技术以及传感技术的基础上发展起来的交叉学科，对该技术的研究始于20世纪60年代，早在1962年第一个具有虚拟现实思想的装置Sensorama就诞生了，它是由MortonHeilig研制的具有多种感官刺激的立体电影设备。但直到90年代初，虚拟现实技术才开始作为一门较完整的体系而受到人们极大的关注，近年来虚拟现实不仅是信息领域科技工作者和产业界的研究、开发和应用的热点，而且也是多种媒体竞相报道的热点。虚拟现实技术潜在的应用范围很广，诸如国防、建筑设计、工业设计、培训、医学领域。例如建筑设计师可以运用虚拟现实技术向客户提供三维虚拟模型，而外科医生还可以在三维虚拟的病人身上试行一种新的外科手术。从本质上来说，虚拟现实就是一种先进的计算机用户接口，它通过给用户同时提供诸如视觉、听觉、触觉等各种直观而又自然的实时感知交互手段，最大限度地方便用户的操作。根据虚拟现实技术所应用的对象不同，其作用可表现为不同的形式，例如将某种概念设计或构思可视化和可操作化，实现逼真的遥控现场效果，达到任意复杂环境下的廉价模拟训练目的等。该技术的主要特征有以下几方面：多感知性(Multi-Sensory)，除了一般计算机技术所具有的视觉感知之外，还有听觉感知、力觉感知、触觉感知、运动感知，甚至包括味觉感知、嗅觉感知等。理想的虚拟现实技术应该具有一切人所具有的感知功能。浸没感(Immersion)，又称临场感，指用户感到作为主角存在于模拟环境中的真实程度。理想的模拟环境应该使用户难以分辨真假，使用户全身心地投入到计算机创建的三维虚拟环境中，该环境中的一切看上去是真的，听上去是真的，动起来是真的，甚至闻起来、尝起来等一切感觉都是真的，如同在现实世界中的感觉一样。交互性(Interactivity)，指用户对模拟环境内物体的可操作程度和从环境得到反馈的自然程度(包括实时性)。例如，用户可以用手去直接抓取模拟环境中虚拟的物体，这时手有握着东西的感觉，并可以感觉物体的重量，视野中被抓的物体也能立刻随着手的移动而移动。构想性(Imagination)，虚拟现实技术应具有广阔的可想像空间，可拓宽人类1 上海交通大学硕士学位论文第一章绪论认知范围，不仅可再现真实存在的环境，也可以随意构想客观不存在的甚至是不可能发生的环境。虚拟现实的特征决定了它是多种技术的综合，包括实时三维计算机图形技术，广角(宽视野)立体显示技术，对观察者头、眼和手的跟踪技术，以及触觉/力觉反馈、立体声、语音输入输出技术等。众所周知，对于一个自然人，外界信息量的百分之七十以上都是来源于视觉，这也就充分决定了实时真实的三维视景生成在虚拟环境平台中的重要性。事实上，利用计算机模型产生图形图像并不是太难的事情。如果有足够准确的模型，又有足够的时间，我们就可以生成不同光照条件下各种物体的精确图像，但是虚拟现实的关键是实时。例如在飞行模拟系统中，图像的刷新相当重要，同时对图像质量的要求也很高，再加上非常复杂的虚拟环境，问题就变得相当困难。可编程图形硬件的发展，为实时三维场景的渲染提供了硬件基础。1.2可编程图形硬件的发展多年来计算机图形处理器(GraphicsProcessorUnit,GPU)以大大超过摩尔定律的速度高速发展，极大地提高了计算机图形处理的速度和图形质量，并促进了计算机图形相关应用领域的发展。目前微型计算机平台的图形处理器已经达到了非常高的性能，2007年，NvidiaGeFeoce8800Ultra图形处理器的理论处理能力已经可以达到576Gigaflops(flops:FLoatingpointOperationsPerSecond)，而Intel最新的双核酷睿2：E6750在2.66G的主频下也只能达到21.28Gigaflops的数据吞吐能力。自从1993年以来，GPU的性能以每年2.8倍的速度增长，这样的增长速度在接下来相当长的一段时间内还将继续维持下去，现在每隔半年，新一代的GPU处理[1]速度便会提升一倍。图形处理器技术的迅速发展带来的并不只是处理速度的提高，还产生了很多全新的图形硬件技术，其中最引人注目的便是从OpenGL1.5规范起，在图形硬件处理管道的顶点处理和象素处理模块中引入了可编程性，并在OpenGL1.x和2.x中将其不断扩充完善，而在最新推出的OpenGL3.0三维图形编程接口中，还在顶点处理之后，象素处理之前的三角形处理模块中引入了可编程性。这些可编程模块的引入，使得用户可以通过程序方式控制图形流水线的执行，极大地扩展了图形处理器的能力和应用范围。图1-1为一个OpenGL2.x编程规范下的最基本的可编程图形硬件的框架，其中阴影模块代表可编程模块。2 上海交通大学硕士学位论文第一章绪论图1-1可编程的图形硬件框架Figure1-1Frameofaprogram-ableGPU从图1-1可以看出，在顶点级的操作上，引入了顶点着色器(vertexshader)处理每个顶点，用户可以通过自己编写的代码实现专门的光照明模型。经过栅格化之后，在象素处理阶段，引入象素着色器(pixelshader)可以实现对每个象素的可编程操作。顶点着色器和象素着色器都是典型的流处理器(streamprocessor)，这种流处理器和传统的向量处理机的主要区别在于，它不具有大容量的快存/存储器可以读写，只是直接在芯片上利用临时寄存器做流数据的操作。对于GPU而言，图形流数据分别是顶点图元以及光栅化后的象素；根据图形处理的特点，GPU流处理的元素为4个单元的向量，可以利用它来表示三维齐次坐标，三维空间齐次向量，颜色等数据。正是这种流处理机的并行结构，实现了指令的并行处理，目前绝大部分的GPU都拥有多条可以并行处理的shader管线，这种体系结构使得其不仅可以用于高效图形绘制，而且可以成为通用并行计算平台。自从1998年以来，GPU的功能迅速更新，平均每一年都有新的一代GPU问世，在现代GPU概念出现以前，只有SiliconGraphics(SGI)等图形工作站上的特殊硬件才就具有硬件的顶点变换和纹理映射功能。第一代图形处理器出现在1998年后期，主要代表为NvidiaTNT2,ATIRage和3DFXVoodoo3,这些处理器主要处理光栅化部分，部分芯片支持多纹理，可以在光栅化过程中完成多幅纹理的融合操作；从1999年后期开始，第二代GPU(NvidiaGeForce256,GeForce2和ATIRadeon7500)可以处理顶点的矩阵变换和进行光照计算，但此时还没有出现真正的可编程功能；第三代GPU(NvidiaGeForce3,GeFroce4,ATIRadeon8500，大约2001年至2002年早期)有了重要的技术变革，此时图形硬件的流水线可以作为流处理器来解释，顶点级出现了可编程性，象素级也出现了有限的可编程性，但在象素级的程序中，访问纹理的方式和格式受到一定的限制，只有定点数可用；第四代GPU(NvidiaGeForceFXseries,ATIRadeon9700/9800)所支持的顶点和象素可编程性更加通用化，依赖纹理更为灵活，可以用索引的方式访问数据，GPU具备了浮点处理的能力，纹理中保存的值不再仅限于[0,1]的定点数范围，可以读[2,3]写一般的浮点数；第五代GPU(NvidiaGeforce66006800,ATIRadeon1600/1800)则功能更为丰富，灵活，顶点级程序可以访问纹理，支持程序的动态分支，象素级程序也开始支持分支操作，如循环，if/else等，支持子函数调用，[4-7]在纹理滤波和融合过程中支持64位的浮点精度，同时支持多个渲染目标。最3 上海交通大学硕士学位论文第一章绪论新的第六代GPU以NvidiaG80series为代表，除了对已有功能的增强（如shader程序的代码长度不再有限制，支持同时访问更多的纹理），还在原有的纹理级和象素级可编程单元外，引入了对几何级处理单元的可编程操作(GeometryShader)用户可以用编程的方式控制几何的变换；同时在硬件实现上一个革命性的变化就是引入了统一渲染架构，流处理器不再分为专门的顶点处理器，象素处理器和几何处理器，而是被设计为通用的处理器，每个流处理器都可以动态得被分配来处理顶点，几何或者象素，分配方式可以根据当前的处理压力进行动态调整，达到最优。目前最新的可编程图形硬件已经具备了下列功能：(1)在顶点级，几何级和象素级提供了灵活的可编程特性。(2)在顶点级，几何级和象素级的运算上都支持IEEE32位浮点运算，可进行高精度的绘制。(3)完全支持4元向量的数据格式（齐次坐标，法向等），方便了图形程序的设计与开发。(4)具有高带宽的内存传输能力(>27.1GB/s)，具备强大的数据吞吐能力。(5)支持绘制到纹理的功能(RendertoTexture)，从而避免将中间绘制拷贝到纹理这个费时的过程。(6)支持依赖性纹理访问功能，以方便数据的索引访问，可以将纹理作为内存来使用。1.3研究课题及意义自从第一块专门用于图形处理的处理器被研制出来之后，人们就开始了对实时三维渲染场景的复杂度、真实感的不断追求。尤其是当虚拟现实技术成为计算机研究领域的一个热点，被不断发展并应用到军事，建筑，航空航天等高技术行业的同时，如何运用当前已有的图形硬件来实现更复杂，更具有真实感的三维场景渲染，成为了所有GPU开发、应用工作者不懈追求的目标。而在一个复杂度高，具有高度的真实感的三维场景中，阴影是其中不可或缺的一环，作为三维场景中的重要因素，可以为场景提供许多重要空间几何信息：首先阴影有助于理解物体间的相互位置关系和大小，利用投射阴影可以决定物体在空间中的位置；其次，阴影有助于理解复杂接收体的几何信息，一个能够实时生成真实感强的阴影的方法对于提高三维虚拟场景的真实感起着举足轻重的作用。本文将对阴影生成算法进行讨论与研究。粒子系统是一个在虚拟现实技术中得到广泛应用的系统，虚拟场景中包含这大量对于自然界不定形物体的模拟，如雨水，喷泉，火焰，烟雾等，这些物体都4 上海交通大学硕士学位论文第一章绪论具有不断运动变化的特征,形状变化没有固定规律,很难用传统的造型方法来表现。粒子系统是迄今为止被认为模拟不规则模糊物体非常有效的一种图形生成算法，它采用一种统一的模式来生成诸如云、烟、火、水等具有不规则形状的自然现象，一个模型精确，复杂度较高的粒子系统，可以非常逼真得模拟自然环境中的云雨，烟雾，给予虚拟现实用户更为真实的体验。然而，粒子系统的复杂度和实时度总是一对难以调和的矛盾，如何提升高复杂度的粒子系统的实时性，是虚拟现实技术中一项十分值得研究的课题。由于GPU拥有比CPU更为强大的并行处理能力，利用GPU来实现粒子系统，必将能够大大提升系统的实时性能，本文将在此方面做出一定的探讨。图像处理也是虚拟现实技术中不可或缺的技术，在虚拟现实应用中，它可以作为虚拟场景渲染的最终环节，将渲染出的场景图像进行各种变换，滤波之后呈现给用户，带给用户各种不同的视觉体验；它也可以作为虚拟场景渲染的中间环节进行对场景纹理图像进行压缩和解压缩的处理，从而提高虚拟现实系统的性能；它还可以作为虚拟场景的源头环节，在对二维图像数据的三维重构中发挥重要作用。然而实时化的图像处理对于处理器的并行处理能力有着极为严苛的要求，即使是最先进的CPU也很难达到，GPU的并行处理能力可以提升系统的实时性，即使是并不要求实时的图像处理，例如三维重构的应用，使用GPU代替CPU进行处理，也可以很好地提升处理性能，节省系统开发时间。1.4本文工作的主要研究工作介绍及章节安排本文以可编程图形硬件技术作为文章主线，介绍了作者的一些研究工作的成果：首先在第一章对可编程图形硬件技术进行了一个综述。介绍可编程硬件相关的软硬件知识和可编程图形流水线的工作原理及架构等基础知识。在第二章本文对实时阴影的渲染算法进行了研究。分析了目前流行的硬阴影生成算法的实现原理，比较各算法的局限性和优越性，并且针对阴影图算法中由于算法本身所带来的偏移量问题，提出了一种改进的自适应偏移量算法。本文第三章研究并实现了一种完全基于图形硬件GPU的粒子系统。实验证明，利用GPU的多通道并行处理功能，提高处理速度，可以很大程度地增加粒子系统实时仿真应用中的粒子数量，从而可以提高虚拟环境的逼真程度，实时性能远远高于普通粒子系统。本文的第四章讨论了在GPU上两种图象处理工具的实现：频域上的快速傅立叶变换和空间域上的卷积运算，并评估了这两种工具在GPU上的性能表现。最后对全文进行了总结。5 上海交通大学硕士学位论文第二章相关技术第二章相关技术2.1可编程图形流水线功能介绍一个符合OpenGL2.x规范的可编程图形流水线的总体框架如图2-1所示，左边用实线表示的流程就是传统的图形流水线的流程；在这种通用的流水线中，首先经过顶点级的光照计算和坐标变换，求出每个顶点的光照颜色值，同时还将顶点坐标从物体坐标系转换到裁剪空间(ClippingSpace)。然后，对每个三角形进行光栅化处理并对三角形顶点的颜色进行双线性差值，得到了三角形中每一个象素的颜色值。接着进行纹理映射，即根据每一个象素的纹理坐标值将纹理图颜色分配到每个象素上。最后进行颜色混合计算(Blending)和雾化效果的计算，得到的结果将会放进帧缓存(Framebuffer)并最终显示到屏幕上。目前的可编程图形硬件中，除了光栅化这一部分的算法实现是固化在硬件上无法由用户控制以外，其余部分都引入了可编程性，也就是图2-1中由虚线表示[8]的部分。顶点着色器(VertexShader)的功能正是为了实现顶点的光照计算和坐标变换。在过去的硬件中，人们只能实现一些固定的光照模型和坐标系转换计算，但是在现在的可编程的图形硬件中，用户可以通过编写代码自由地设计自己所需要的光照模型和坐标系转换公式。在2.1.1节中，将专门对顶点着色器作进一步的介绍。至于象素着色器(PixelShader)，功能相对复杂，同时限制较多。它几乎包括了所有栅格化以后的操作：纹理采样，颜色混合计算(Blending)和雾化效果计算等等，传统图形硬件中每个顶点的纹理坐标值需要人工指定或者根据空间坐标来计算，而在象素着色器中，允许采用多种纹理访问方式；每个象素的绘制信息（例如，象素颜色值、纹理坐标等）均保存在寄存器中，象素着色器通过完成这些寄存器之间的加法，乘法或者点积等运算操作，从而在象素级别上实现光照明模型[9-12]的计算(per-pixellighting)。6 上海交通大学硕士学位论文第二章相关技术图2-1可编程图形流水线的总体框架Figure2-1Frameoftheprogram-ablegraphicspipeline2.1.1顶点着色器下面以2.0版本的顶点着色器为例来分析其架构（如图2-2所示）。其中所有的寄存器长度都为44×字节，即RGBA四个值分别用32位的浮点数（即4个字节）来存储。输入的16个寄存器通常用来保存顶点的绘制信息，包括顶点位置、法向或者颜色值，也可以是由用户自己定义的信息，例如：权重、位移或者速度7 上海交通大学硕士学位论文第二章相关技术等等。至于输出的15个寄存器通常用来保存顶点着色器的运算结果，包括裁剪坐标系下的顶点位置、颜色值，雾化坐标值和纹理坐标等等，同样输出寄存器也可以存放用户自定义的绘制信息，比如：光照方向、视线方向等等，这些信息在三角形光栅化后经双线性差值生成象素级的绘制信息。此外，还有96个只读的常量数据寄存器以及12个可读写寄存器，其中只读的常量寄存器的赋值操作由CPU控制，也就是通过外界函数调用进行赋值，而可读写的寄存器则可在顶点[3,13-15]绘制编程器的计算过程中作为临时寄存器使用。图2-2顶点着色器(2.0)系统框架Figure2-2Systemframeofvertexshader2.0这些寄存器通常有固定的表达方式：输入寄存器为Vn[]，输出寄存器为On[]，常量寄存器为Cn[]，而可读写寄存器则为Rn，这里的n就是具体的寄存器编号。如第十号的输入寄存器就写作V[10]。而且每个寄存器都可以用xyzw后缀名来访问寄存器中的RGBA各个分量，比如说：R1.w表示的就是第1号可读写寄存器的第四个分量－A分量。寄存器为Shader程序的执行提供了变量空间，但程序功能实现最核心的还是指令集。不同版本的着色器对于指令长度的限制是不一样的，早期的顶点着色器只支持128条指令长度内的程序，也就是说，顶点着色器对于程序的复杂度是有限制的，2.0版本的顶点着色器支持的程序指令长度已经达到256条。8 上海交通大学硕士学位论文第二章相关技术顶点着色器的指令集中包含的通用运算指令有:加法(ADD)、乘法(MUL)、先加后乘(MAD)、三维的点积运算(DP3)、四维的点积运算(DP4)、求倒数((RCP)、求平方根的倒数(RSQ)、指数运算(EXP)和对数运算(LOG)，求最大值(MAX)，求最小值(MIN)等;还有寻址指令(ARL)，移动数据指令(MOV)，判断指令:判断是否小于(SLT)，判断是否大于等于(SGE)，以及两个专门为了实现光照计算公式的指令:一个是根据光源距离计算衰减系数(DST)，另一个是实现Phong光照模型公式的计算(LIT)等。具有丰富功能的指令集为顶点处理绘制信息的计算提供了强大[16-19]的支持。有了顶点着色器，就拥有了一个强大的顶点级绘制信息的计算工具。但是，由于颜色计算只是在三角形的顶点上进行，三角形内部各个象素的颜色只能通过插值得到，这样将无法充分表现三角形内部的细节。下面要介绍的象素着色器则可以弥补这点不足，其操作对象是每个象素，可以在象素级别上进行绘制，从而[20-22]充分表现三角形的内部细节。2.1.2象素着色器如图2-1所示，象素着色器的功能主要体现为两个部分:纹理采样和象素级[23-26]运算。其具体结构图如图2-3所示。2.1.2.1纹理采样前面己经提到纹理采样就是通过不同的纹理访问方式，由每个象素的纹理坐标得到纹理颜色值。其中纹理坐标值(,,,)strq和颜色值(,,,)RGBA均可以是iiiiiiii32位的浮点值。如图2-4中虚线所示，通过纹理采样得到的颜色值同样可以再次作为纹理坐标进行采样，这就是前面提到的依赖性纹理访问功能，该功能增加了对于象素处理的灵活性，为把象素处理的中间结果保存在纹理中打下了基础[27-30]。2.1.2.2象素级运算象素着色器提供了象素级上的加法，乘法以及点积等运算功能，丰富的运算功能可支持象素级上的各种绘制运算。目前GPU大都提供了可以并行计算的8条甚至16条象素着色器计算管线，在每一计算管线上都可以对取自多个输入寄存器的数据进行基于指令集的各种运算，象素着色器的指令集和顶点着色器一样提供了丰富的计算功能，此处就不再赘述，可参见具体的开发文档。图2-5以其9 上海交通大学硕士学位论文第二章相关技术中任意一条计算管线为例简单图示其结构。图2-3象素着色器结构图Figure2-3DiagramofPixelShader图2-4纹理采样的功能示意图Figure2-4Functiondiagramoftexturesampling图中计算管线1,2...n的功能和结构是一样的，以管线1为例，首先选择4个输入寄存器，其数据分两组经过输入映射后进行乘法或者点积运算，得到中间结果，中间结果可以直接由输出映射传送到输出寄存器中，也可以作为下一次加法10 上海交通大学硕士学位论文第二章相关技术[33-35]或者乘法运算的输入；最终输出寄存器中的结果值将送入帧缓存中。图2-5象素计算管线结构图Figure2-5Diagramofpixelcomputingpipeline2.2可编程图形流水线的软件开发技术2.2.1编程接口在可编程图形硬件迅猛发展的同时，其相关的软件开发技术也在不断进步。目前GPU的应用途径主要是通过图形API(OpenGL或者Direct3D)扩充新GPU[36]的功能，其扩充功能或由GPU厂家提供，或由API软件开发者提供。利用高级语言不依赖于具体的GPU硬件及计算平台的编程一直是GPU应用的努力目标，朝此目标而在绘制语言(shadinglanguage)和实时绘制语言方面所作的研究一直在进行之中。运用GPU进行通用计算最终需要摆脱图形流水线及其绘制的概念，从流处理机的角度利用高级语言编程，这方面的研究工作在2004年开始有[37]了新的进展。GPU所提供的可编程功能以顶点处理器和像素处理器的操作形式完成，由每个处理器执行用户定义的汇编级的绘制程序(shaderprogram)，对流数据(顶点/11 上海交通大学硕士学位论文第二章相关技术像素)执行绘制程序的操作。对于标准图形界面用户来说，这些GPU的新功能一般通过GPU设计者或用户界面的设计者以扩充函数库的形式提供给用户。OpenGL作为事实上的工业标准已为学术界和工业界所普遍接受，因而绝大部分与图形有关的应用产品一直以OpenGL作为实现界面。对于使用GPU的扩充函数，OpenGL中包括了GPU设计者(如Nvidia)以及OpenGL“架构委员会(ARB)”所扩充的函数。Direct3D作为微软视窗的标准，其图形界面Direct3D亦得到广泛接受和应用，特别是作为游戏软件的实现界面。为适应GPU应用的需求，Direct3D根据GPU新产品功能的扩充与进展及时地定义新的版本以扩充VertexShader和PixelShader的新功能，Direct3D软件接口所提供的功能几乎与GPU提供的功能同步。对于熟悉OpenGL或Direct3D的用户或软件专业用户来说，直接使用其扩充的接口软件应该是比较好的选择，因为这里可以从底层实现更灵活的控制和对GPU编程。2.2.2高级绘制语言以及实时绘制语言使用类似于C的高级语言对GPU直接编程一直是图形界努力追求的目标，也是将来应该达到的目标。在这方面，已取得了一些进展。使用绘制语言及高级语言进行绘制编程可以方便用户书写各种不同功能的绘制程序以及对其绘制程序提供各种控制，从而使GPU硬件的具体功能对于用户而言更具有透明性。绘[38-40]制程序(shader)设计的思想源自于早年Pixar设计的RenderMan绘制软件。此软件多年来广泛应用于好莱坞电影中特技效果的绘制。关于新型标准绘制语言的[41,42]研究工作，近年来具有较大影响的是:OpenGLshadinglanguage，斯坦福大学[43,44]的RTSL(real-timeshadinglanguage)，Microsoft的HLSL(high-levelshading[45][46]language)以及Nvidia的Cg尽管还未形成统一的绘制语言，这些语言的研究和应用为用户提供了直接基于API(OpenGL或Direct3D)编程的较为方便和高层次的工具。2.2.3流处理机编程环境及工具使用绘制语言编程仍然存在着不少缺陷，对使用者来说仍然是一件十分麻烦的工作。首先，用户必须编写控制图形流水线的许多任务，如分配纹理存储、读入绘制程序、构造图形元素等，为此，用户对最新的API以及图形处理器硬件的特点与限制需要有详细的了解。此外，用户仍然需要利用纹理、三角形等图形素元表达他们的算法，这就使得GPU的通用计算编程工作仍然只能由资深的图形开发者进行。如果这一问题不能很好地解决，GPU用于通用计算的前景将会受到很大的限制。因为，熟悉GPU图形编程的人毕竟太少，而这些资深的图形12 上海交通大学硕士学位论文第二章相关技术开发者对通用计算的各个应用领域又比较陌生。为解决这一问题，当前的努力方向主要是将GPU的结构纯粹纳入流处理机的模型而以高级语言编程，使得程序说明、运算操作、模块化定义等一系列运算和控制规范化，使用户在实现高效率利用GPU的同时，不必考虑GPU的具体图形结构。这一研究工作的代表是最近[47]发表于ACMSIGGRAPH2004的斯坦福大学的Brook-for-GPU系统和加拿大[48]Waterloo大学的ShaderAlgebra系统。13 上海交通大学硕士学位论文第三章阴影生成算法第三章阴影生成算法3.1引言3.1.1课题研究意义虚拟现实(VirtualReality,简称VR),是利用计算机发展中的高科技手段构造一个虚拟的环境,使参与者获得与现实一样的感觉,它是一种高级的人机界面。近年来虚拟现实不仅是信息领域科技工作者和产业界的研究、开发和应用的热点，而且也是多种媒体竞相报道的热点。虚拟现实技术潜在的应用范围很广，诸如国防、建筑设计、工业设计、培训、医学领域。例如建筑设计师可以运用虚拟现实技术向客户提供三维虚拟模型，而外科医生还可以在三维虚拟的病人身上试行一种新的外科手术。事实上虚拟现实并不是一项新技术，早在1962年第一个具有虚拟现实思想的装置Sensorama就诞生了，它是由MortonHeilig研制[49]的具有多种感官刺激的立体电影设备。虚拟现实强调人的沉浸感，即沉浸在虚拟的世界之中。这种沉浸感，主要是通过各种虚拟现实技术，对人们的视觉、听觉、触觉、味觉、嗅觉等方面提供感受。虚拟环境(VirtualEnvironment)是虚拟现实技术的表现空间，是将各种技术集成到一起的可视化平台，人们通过虚拟环境来对虚拟世界感知和交互。一个理想[50,51]的虚拟环境应该具备三维、良好的高级人机交互接口、真实感好等特征。众所周知，对于一个自然人，外界信息量的百分之七十以上都是来源于视觉，这也[52,53]就充分决定了实时真实的三维视景生成在虚拟环境平台中的重要性。解决视觉建模中的模型复杂度、绘制的真实感和实时性之间的矛盾，目前仍是计算机图[54]形学和虚拟现实技术所努力的方向。体现真实感的绘制技术中，阴影计算由于其应用的广泛性，被作为一个独立的方法来研究和使用。阴影投射在人们对三维世界的感知方面起着非常重要的作用，它可以为人们提供在三维空间中遮光物[55,56]体的几何形状、大小和位置信息及其被投影物体的位置和几何形状信息。虚拟现实技术通过20多年的研究探索，于80年代末走出实验室，开始进入实用化阶段。目前，世界上少数发达国家在经济、艺术乃至军事等领域，已开始广泛应用这种高新技术，并取得了显著的综合效益。而这一切只有建立真实感强的虚拟系统，才能使其充分发挥其应具有的功效。在人们生活的现实世界中，阴影作为其三维场景中的重要因素，可以为场景提供许多重要空间几何信息：首先阴影有助于理解物体间的相互位置关系和大14 上海交通大学硕士学位论文第三章阴影生成算法小，利用投射阴影可以决定物体在空间中的位置；其次，阴影有助于理解复杂接收体的几何信息，如图3.1所示，在图(a)中无法判断虚拟小人距离地面的多远及接收体的形状，而在(b)中由于加入了阴影，可以清楚的判断接受体的几何性质及小人与地面的距离关系；最后，阴影有助于理解复杂遮挡物的几何形状，如图3.1(c)中显示，可以非常清楚地看出虚拟小人手中拿的是个圆环。(a)(b)(c)图3-1在虚拟场景中阴影提供了丰富的空间几何信息Figure3-1theimportanceaboutshadow可见一个能够实时生成真实感强的阴影的方法对于提高三维虚拟场景的真实感起着举足轻重的作用。3.1.2国内外研究现状国内外在关于如何在实时交互的虚拟场景中生成真实的阴影方面发表了许[55,56]多论文。阴影从最终的显示效果来看，分为硬阴影和软阴影。软阴影的真实感强度比硬阴影要强，这意味着它要考虑更多光源、遮挡体及接受体之间的空间几何特征，实现显然更加困难，尤其在实时应用中。实现三维空间的真实阴影是件非常复杂的过程，现实世界中的光源的复杂性和物体间相互的光照影响，所形[49,55,56]成的阴影明暗程度并不是一个常量，所以大多数的算法设计都是在一定的简化模型下进行的，特别是在实时性要求高的应用中。本课题在研究过程中同样也会作适当的简化。目前，实现阴影的方法非常的多且杂。主要分为图像精确方法和对象精确方法两类，其中图像精确方法是在像素层次上计算阴影的方法，对象精确方法是独[49,56]立于视点来计算阴影信息的。现在有一些算法能够生成与现实非常接近的阴影效果，主要是对现实世界的光照模型进行模拟，如：光线跟踪、辐射度、不连[49,57-59]续网格化等方法。但是正如前所说，现实世界中的光照太复杂，其模拟算法的计算量将相当大，不适合于实时性要求高的三维虚拟场景。虽然也出现了些[49,55,56,59]改良算法，但是计算量仍然不满足需求。[55，56]现有的实时生成阴影的基本算法主要有阴影体算法和阴影图算法。阴影图算法属于图像精确方法，其方法是首先以光源处作为视点来渲染场景，形成15 上海交通大学硕士学位论文第三章阴影生成算法一个阴影图，该图中只保存透视中的深度值，然后从真正的视点处渲染场景，在[60,61]这个过程中对每个可见对象，先将其作深度比较，确定其是否在阴影中。阴影体算法属于对象精确方法，其方法主要是根据光源方向确定遮光物的轮廓边，沿着光源的方向延伸这些边，所形成的面与遮光物一起形成阴影体，物体如果在[62-64]阴影体中，则说明其是避光的，如果不在其中则反之。这两个算法开始都是针对硬阴影的实时生成而产生的，可以通过对其进行相应的改造，从而生成具有一定真实感的软阴影。在保证实时性的同时，生成真实感强的软阴影，一直是个比较难于解决的问题。从现在的软阴影生成算法来看，改进的策略众多，但是还是存在不少问题，有的算法不能形成自阴影，有的算法受到了遮挡体和接收体的类型的限制，有的算法忽略光源的大小和形状，有的只是形成了半影的内半影，或者外半影等等[55,56]。软阴影的生成不在本文的讨论范围内。3.2阴影图(shadowmaps)算法3.2.1基本原理[21]这个算法首先是由Williams(1978)提出来的。如图3-2所示，该算法需要两个空间作坐标转换。算法分为两步。在第一步中,使用光源作为视点并渲染场景到z缓存区(也称深度缓存区)中。注意在这个步骤中对颜色缓存区的内容不感兴趣,只是对每个像素的相对于光源的深度信息感兴趣，可以关掉光照和纹理生成以加速这个过程，只保存z缓冲区，称之为阴影深度缓存区或阴影图。这个阴影图在场景和光源相对位置不变时可以重复使用,由光源所定义的坐标系统称为光空间。在第二步中,从视点渲染对象，但与传统方式唯一不同的是在扫描显示它们的时候，渲染每一个可见对象之前要对它做阴影测试，为了做这一点，首先将像素的坐标(xv,yv,zv)从观察空间转换到光空间坐标(xs,ys,zs)，并比较zs值与存储在阴影深度缓冲区内(xs,ys)位置上的深度值z。如果像素的深度大于所存储的深度,那就意味着从光源处看,有较靠近的对象遮挡了它,因而将它位于阴影中，如图点A所示。如果zs值等于阴影缓冲区中的值,那说明它就是从光源处所能看到的那个点，如图点B所示。16 上海交通大学硕士学位论文第三章阴影生成算法图3-2阴影图算法原理Figure3-2Theoryofshadowmapsalgorithm3.2.2优缺点阴影图算法有许多很好的属性，首先他们很容易被图形硬件实现，因为他们只使用了投影纹理映射及简单的深度比较。另外，算法的效率比较高，因为其通过纹理查找在图像空间计算阴影。最后明显减少了场景中的几何计算，只要场景中的图元被光栅化在深度缓存区中，就可以实现他的阴影渲染。阴影图算法由于算法本身特性使其具有一些局限性。首先算法中假设光源是方向光，如聚光灯。要实现全方向的光源，则需要额外的渲染过程，比如对球形[61]光源要围绕其实现六次渲染，才能实现相应的阴影效果。另外，阴影图算法[65,66]两个比较严重的缺点就是量化误差和走样问题。其中量化误差是指算法在深度比较时所作的点的变换,也就是从观察空间到光空间的变换，由于有限的精度及离散化,z值的比较可能导致在"相等"的时候出现“大于”的情况，即在被照射[67,68]表面上出现随机的亮点，从而会产生不正确的自阴影。走样问题是一种阴影图采样不充分而使形成的硬阴影边界出现锯齿的现象[65,66]，如图3-3(a)所示。具体分析原因，阴影图是在光源视截体中生成的，所以它生成过程实际上是一个从光源对场景逐像素采样的过程，它把场景中的每个采样点作为一个像素保存在图中，当视平面中的像素转换到阴影图进行比较时，肯定会出现转换过去的像素比阴影图的像素要大些或者小些的现象。如果大了，可以平均它所对应的阴影图的像素值来进行比较，确定一个适当的值；如果小些，那么几个在视平面的像素会对应一个在阴影图中的像素，那就造成多个像素获得同样的比较结果，这样就造成了阴影图的采样精度低于视平面的精度而出现的走样问题。根据Nyquist理论，阴影图的精度必须是视平面的两倍才能防止走样17 上海交通大学硕士学位论文第三章阴影生成算法[65]。图3-3显示了一个圆柱体产生的阴影走样问题。三张图显示了使用256*256，512*512，1024*1024不同的精确度阴影图，可以看出走样问题会随着阴影图精确度的提高而减小。但是这个代价是非常高的，尤其是在实时动态场景中，内存空间是非常有限的。(a)(b)(c)图3-3阴影图算法的走样问题Figure3-3Aliasingofshadowmapsalgorithm3.3阴影体算法3.3.1基本原理图3-4阴影体图3-5阴影体的BSP表示Figure3-4ShadowvolumeFigure3-5BSPrepresentshadowvolume[62]阴影体方法首先由Crow提出来的。针对于点光源,阴影体是多边形后面光线所照不到的空间体.它是一个由阴影平面所定义的半无限金字塔,其上表面是多边形本身。给定一个光源L和一个多边形P,多边形P由定点序列[v1，v2，⋯⋯，vn-1，vn]定义,如图3-4所示,阴影平面由三元组(L,vi,vi+1)定义,这里i=1,....,n-1，n，n+1(vn+1=v1)。阴影体定义为一个棱台,它的上下表面分别是P和引用平面(P，L)。当计算位于阴影体内部的平面的时候,很重要的一点是，要让平面方程能正18 上海交通大学硕士学位论文第三章阴影生成算法确地表示平面的"前侧"和"后侧".采用右手定则,即正对平面的前侧看去,其顶点描述为反时针方向的顺序,如图3-5所示.那么对于图中情形,计算阴影平面方程的正确定点顺序是v2Lv1。对应图3-4，此时多边形用顶点描述为v1,v2,v3,v4,这样反时针顺序使得它是面向光源的，并约定阴影平面的"背面"位于阴影体一侧。继Crow之后1986年阴影体算法被Bergeron进行了修改,使其至今仍是[63]阴影计算最流行的方法之一。它基于下列思想，如图3.6所示。假设有一个不位于阴影中的视点,如果从眼睛处向场景中的某个点p画一个矢量v,确定该点是否在阴影中的方法是，看v在到达p之前所相交的前向(front-facing)阴影平面数和背向(back-facing)阴影平面数．如果前向阴影平面数和背向阴影平面数之差等于零,那么该点是光线能照射到的，如图3.6中P所示，否则它在阴影中，如4该图中P、P、P所示．注意，这个差值可能大于1，因为某些区域可能位于123多个多边形的阴影体中，如该图中P所示，其值为2。眼睛位于阴影中是个特2殊的情况，需要修改技术规则以便考虑到这一情形。总的来说，阴影体算法分为两个步骤进行：(1)在对象空间中构造阴影体；(2)通过阴影平面计数确定每个像素阴影。图3-6阴影体算法原理Figure3-6Theoryofshadowvolume阴影平面的产生可以预先处理,因为它是独立于视点的,而且只需要执行一次,然后可以重复使用,只要对象不发生改变.阴影平面包含在场景数据库中,然后被送到图形管道.因为这些平面的多边形表示是必须的,它的边界是由视域或光的影[49]响范围裁减所得。19 上海交通大学硕士学位论文第三章阴影生成算法3.3.2优缺点阴影体算法与阴影图算法相比有两个优势。第一，该算法由于是在对象空间中计算每个像素的阴影渲染，其产生的阴影非常准确，不会因为采样不足而出现走样和量化误差的问题。第二，它不像阴影图算法，该算法不局限在一个方向光[64]源，可以实现全方向光源的阴影渲染。就其缺点来说，阴影体算法不如阴影图算法具有一般性。阴影图算法可以支持任何被渲染到深度图中的图元产生阴影，一个阴影体算法需要对几何模型有相应的描述，以便其确定轮廓边，尤其是表面必须是具有方向的且封闭的几何模型。阴影体最严重的缺点是算法不能很好地应用于阴影渲染复杂的场景。导致这个缺点最主要的问题是，阴影体算法需要非常大的填充率(fill-rate)。这是因为，光栅化后的阴影体多边形覆盖了较大的屏幕空间(视屏)，尤其在阴影区域大或者视点在阴影体中的情况。再者，阴影体多边形在空间中相互叠加，而每个阴影多边形都是潜在更新模版缓存数值的因素。多边形叠加的程度，结合着其屏幕的覆盖率[49,55,56]随着场景阴影复杂度的提高而提高，从而最终导致巨大的填充率。3.4基于阴影图算法偏移量问题的改进3.4.1偏移量问题及自适应偏移量算法阴影图算法的偏移量问题是由算法本身特点决定的。该算法阴影的质量取决于深度缓存的精度。因为在确定一个像素是否处在阴影之中的时候，存在一个深度值比较，其中一个深度值是通过坐标转换计算而来，那么该值的准确性必然会受制于深度缓存的精度和计算机本身的计算精度，像素可能被错误地渲染为阴影或非阴影。如图3-7所示。解决这个问题的基本思想就是给存储在深度缓存里的深度值添加一个很小的偏移量。直接使用一个固定的偏移量或者使用OpenGL中的glpolygonoffset函数都可以给深度缓存添加偏移量，但是偏移多少是个经验值，需要编程人员根据具体场景不断尝试来确定最佳的值。一旦使用了不恰当的偏移量，会产生错误的阴影起始位置从而会产生错误的自阴影，如图3-8所示。20 上海交通大学硕士学位论文第三章阴影生成算法图3-7无偏移量的阴影渲染Figure3-7Theshadoweffectwithoutbias(a)偏移过小(b)偏移过大(c)偏移合适图3-8使用glpolygonoffset函数确定偏移量的问题Figure3-8ThedisadvantageaboutusingglpolygonoffsetAPI[67]如何设置这个偏移量？Wooshadowmaps首先提出了一种由程序自动生成合适偏移量的方法，其思想如图3-9所示，首先获取离光源最近的几何表面深度值及离光源第二近的几何表面深度值，分别称为第一层深度值和第二层深度值，然后计算两者的平均值作为新的深度值存入深度缓存，使用新的深度值来进行阴影测试。其实该方法就是将第一层深度值与第二层深度值的差的二分之一作为偏移量。图3-9Wooshadowmap原理图3-10Wooshadowmap的不足Figure3-9TheoryofWooShadowmapFigure3-10DisadvantageofWooshadowmap21 上海交通大学硕士学位论文第三章阴影生成算法3.4.2自适应偏移量改进算法的思想Wooshadowmap的不足就在于可能会在物体的断层处错误地产生光照效果，如图3-10所示的C点。另外在A点与B点处，因为第一层深度值与第二[68]层深度值非常接近，也会产生走样现象，造成光照区域与阴影区域边界错误。对于C点，其产生错误光照的原因是，在取新的深度值作比较时，计算机可能会使用a点的深度值，也可能会使用b点的深度值，如果使用b点的深度值，那么就会使C点错误地接受光照。本文结合固定偏移量的方法，在wooshadowmaps算法的基础上提出一个新的自适应偏移量算法来解决这些问题。算法首先确定一个常量，在确定新的深度值之前，用wooshadowmaps算法产生的偏移量与其比较，哪一个小就选择它作为偏移量，从而防止产生过大的偏移量。虽然这里也要设置一个常量值，但是不用考虑这个常量过大而造成物体产生错误的自阴影边界。另外一种情况出现走样问题是当第一层深度表面与第二层深度表面过于接近的时候，比如在三维场景中要绘制一个薄片，这样使用wooshadowmaps的方法会产生过小的偏移量，以至于起不到偏移的作用。为了在一定程度上防止这个问题出现，进一步完善算法，可以尽量将新的深度值与第二层深度值接近，使新的深度值与两者距离比为D−1:1，其中D是一个大于2的常数，这样可以在一定程度上保证第一层深度表面(一般情况下是接受光照的表面)不出现走样，而第二层深度表面一般都是背向光源，可以利用Phong光照模型产生阴暗渲染来掩盖这种走样。综上所述，在自适应偏移量算法中采用如下公式3.1确定深度值进行阴影渲染：1ZZ=+min(ZZZ,(−×)(1−))(3.1)newDepth12biasDepthDepth1D(其中Z∈Q且10>>∈Z,DN且D>2)biasZ是指新生成的深度值；Z是第一层深度值；Z是第二层深度值；newdepth1depth2Z和D是设定的两个常量值。常量D的取值，理论上来说可以取任意大，bias但是那样是没必要的，而且影响了算法效率，在后面的实验中，取为8就取得了很好的效果。这种方法对于图3.10中A，B附近的阴影渲染也有一定提高，因为一般来说这些地方也是第一层深度与第二层深度比较接近的地方。3.4.3自适应偏移量改进算法的实现与传统的shadowmaps操作相比较，为了取得新的深度值，需要渲染多次场22 上海交通大学硕士学位论文第三章阴影生成算法景，这样会在一定程度上影响执行效率，通过结合可编程图形硬件，将渲染操作及新的深度值生成由GPU来完成，这样就可以在保证渲染效果的基础上提高实时性。算法实现大致也分为4步：第1步，从光源渲染场景，取得最靠近光源的第1层深度值；第2步，再次从光源渲染场景，取得第2层深度值；第3步，将两层深度值按照前一节所描述的方法进行处理产生新的深度值，写入深度缓冲中；最后，我们从视点渲染场景，使用新的深度值来进行比较生成阴影。[68]目前OpenGL不存在双深度缓存扩展，所以要解决的问题是如何获取第2层深度。第1层深度的获取非常简单，在从光源渲染完场景后直接将深度值从深度缓存中读出，存入深度纹理，该纹理以场景中物体的坐标(x,y,z,w)作为纹理坐标值(s,t,r,q)来存取深度值。在进行第2次渲染场景时，我们将使用到glsl语言来编写vertexshader和fragmentshader，让GPU来完成第2层深度的获取。我们将第1层深度纹理作为uniform参数传入fragmentshader，同时在vertexshader中我们求出每个点在光源坐标系的位置，将该值传递到fragmentshader作为对第4层深度纹理操作的纹理坐标。坐标值(s,t)获得像素点对应第1层深度纹理的深度值，如果该值等于像素坐标的z值(即该像素距离光源的距离)，我们将该像素进行discard处理，也就是放弃对目前操作像素的任何操作，从而相应地不会对缓存进行任何更新。这样在渲染场景后深度缓存中的深度值就是第2层深度值。以下提供了在第2步中fragmentshader具体代码：//No2fragmentshaderUniformsampler2Ddepth1_map;//第1层深度varyingvec4tex_coord;//纹理坐标voidmain(){tex_coord/=tex_coord.q;tex_coord.stp=tex_coord.stp*0.5+0.5;floatdepthvalue=texture2D(depth1_map,tex_coord.xy).z;if(gl_FragCoord.z>=float(depthvalue-0.0000001)&&gl_FragCoord.z<=float(depthvalue+0.0000001)){discard;}//考虑一定偏差进行比较}第3步是为了产生新的深度值。我们将这一部分的处理由GPU来完成。在这次渲染的fragmentshader中结合第1层深度纹理和第2层深度纹理，利用公式(1)计算新的深度值，并将该值输入gl_FragDepth来改变深度缓存中的深度值。取得新的深度值后，在第4步，我们从视点渲染场景。在这一步我们不23 上海交通大学硕士学位论文第三章阴影生成算法仅要考虑如何确定阴影，同时在阴影渲染时考虑反走样的效果，因此我们在相应的fragmentshader中编写了一个PCF_9()的函数，来执行33×Filtering。以下提供了第4步中fragmentshader部分代码：//No4fragmentshder⋯//取得光照及纹理渲染效果其它变量定义uniformsampler2DShadowshadow_map;uniformmat4Tmatrix;//转换矩阵floatpcf_9(vec3s_coord){⋯}//定义PCF3x3的过滤voidmain(){⋯⋯//取得光照及纹理渲染效果的操作floatshadow=1.0;vec4s_coord=Tmatrix*view_location;//转换到光源坐标if(abs(s_coord.s)0.0)//防止反向投影阴影纹理{s_coord/=s_coord.q;s_coord.stp=s_coord.stp*0.5+0.5;shadow=pcf_9(s_coord);}//渲染公式：gl_FragColor.rgb=(ambient+shadow*diffuse)*texture+shadow*specular;}通过使用Opengl的扩展GL_ARB_fragment_shader和GL_ARB_vertex_shader，整个程序在windowsxp(sp2)，CPUAthlon3500+，Nvidiageforce7600，DDR21G平台运行通过，图3-11显示了最终效果，并与wooshadowmaps算法进行了比较。其中Zbias=0.01，D=8。很明显，在相同情况下使用wooshadowmaps算法渲染得L型物体出现了断层，如图3-11(c)所示，渲染的薄片出现了走样的波纹，如图3-11(e)所示，而使用文章中介绍的方法问题得到了很好的改善，如图3-11(d)与(f)所示。24 上海交通大学硕士学位论文第三章阴影生成算法(a)第一层深度纹理(b)第二层深度纹理(c)wooshadowmap渲染L形物体(d)改进算法渲染L形物体(e)wooshadowmap渲染薄板效果(f)改进算法渲染薄板效果图3-11改进算法与wooshadowmap算法比较Figure3-11Thecomparisonbetweenouralgorithmandwooshadowmapalgorithm25 上海交通大学硕士学位论文第三章阴影生成算法3.5结论本章重点介绍了两个经典的硬阴影生成算法，一个是基于图像精确的阴影图算法，另一个是基于对象精确的阴影体算法。并重点分析两个算法优越性和局限性，在实际应用中根据具体的情况对算法进行选择。同时本章还针对阴影图算法偏移量问题的解决提出了一个自适应偏移量算法，其算法不但解决了wooshadowmaps的算法场景断层处的走样问题，而且与目前的解决方法相比它更多地考虑了场景属性来确定合理的偏移量大小，从而减少了人为操作的影响。26 上海交通大学硕士学位论文第四章基于GPU的粒子系统第四章基于GPU的粒子系统4.1引言粒子系统是迄今为止被认为模拟不规则模糊物体非常有效的一种图形生成算法，它采用一种统一的模式来生成诸如云、烟、火、水等具有不规则形状的自[69]然现象，在虚拟场景中对自然环境的渲染起着重要的作用。在粒子系统中，景象被定义为由成千上万个不规则的、随机分布的粒子所组成，而每一个粒子均有一定的生命周期，它们不断改变形状、不断运动，充分地体现了不规则物体的[70,71]性质。在粒子系统中，若想使不规则物体表现的更真实，理所当然的，构成此不规则物体的粒子数量理论上是越多越好，粒子数越多，系统越能符合真实物体的动力学特征，最终系统绘制的效果也会更加的细腻，更具真实感。然而，粒子系统一开始设计出来的时候是基于CPU系统的，人们很快发现，系统随着粒子数量的增加，受到CPU处理能力的限制，系统的实时性迅速下降，在粒子数量达到能够真实有效模拟一个复杂的场景的数量级之前，系统的实时性已经下降到一个令人难以接受的程度。使得虚拟场景的渲染难以达到令人有沉浸感，真实感的效果。GPU硬件技术的发展为高性能粒子系统的实现带来了另一种可能：影响粒[72]子系统实时性能的瓶颈就是CPU的并行处理能力以及CPU与图形硬件GPU的通讯。CPU的架构特点是SISD(SingleInstructionStreamSingleDataStream),这决定了它的并行处理是较弱的，由于粒子系统由许多单个微粒组成，整个系统的运动和变化是依靠每个微粒的独立运动实现的，在系统计算过程中，需要对大量的数据进行并行计算，而在对每个粒子的物理仿真计算过程中，CPU相对较弱的并行处理能力，也大大降低了系统的可实时性能。而GPU的SIMD架构决定了它拥有良好的多通道处理性能，可以很方便地实现大量的并行计算，这为粒[73]子系统在GPU上的应用提供了必要性与可能性。另一方面，在传统的粒子系统系统中，主要的数据运算都是交由CPU来处理，而数据和指令的存储交换则由系统内存完成，系统需要通过CPU向GPU传输每一个粒子的数据来绘制整个粒子系统，即便使用高速的PCIExpress总线，也会给整个传输过程带来很大压力。因此由于传输带宽的限制，使用CPU进行物理仿真后的粒子传输给GPU进行渲染的过程成为整个粒子系统中最耗时的部分，从而大大降低了粒子系统在不定形物体仿真应用中的作用。而在基于GPU的粒子系统中，由于实现了CPU和27 上海交通大学硕士学位论文第四章基于GPU的粒子系统GPU的合理分工，数据和指令存储交换的场所也由系统内存扩展至GPU显存，省去了许多系统内存通过总线和显存交换数据的过程，这使得计算机系统的实时处理能力大幅度提高。由于基于GPU的粒子系统较之于基于CPU的粒子系统有着许多的优势，越来越多的研究人员将目光投放到GPU上。本文探讨了在GPU上实现粒子系统的可行性和技术细节，实验证明，将粒子系统中的大量计算工作交由GPU完成，可以大大提高粒子系统的计算效率，使系统的实时性能大为增强。4.2基于GPU粒子系统的设计基于GPU的粒子系统主要分为无状态和状态保留两大类。无状态粒子系统的特点是随着时间的推移每个粒子属性的变化都可以通过粒子的初始属性与当前时间计算得来，这种粒子系统适用于模拟简单的不规则自然现象，但是对于一些复杂的、与周围环境有相互作用的自然现象就力不能及了。状态保留的粒子系统保存了粒子在前一时刻的各个属性，这样通过运动方程的计算则更适用于对那些复杂、多变的自然现象进行模拟。以下，本文主要描述了状态保留粒子系统的设计与实现。状态保留粒子系统的主要原理是将粒子系统中粒子的位置与速度保存在浮点纹理中，以这些纹理作为图形硬件GPU的输入与输出，所有粒子的物理仿真及渲染过程均通过shader代码在GPU中实现，这样就避免了CPU与GPU的频繁通讯，另一方面利用GPU的多通道并行计算性能则更进一步地提高了系统的实时性。4.2.1系统体系结构图首先我们根据一个粒子在整个系统中的生存周期来总体描述系统的结构。系统主要分为CPU运行阶段和GPU运行阶段两个部分，系统体系结构如图4-1所示。28 上海交通大学硕士学位论文第四章基于GPU的粒子系统一个新粒子产生从空闲索引分配粒子死亡返回空器中取一个索引闲索引分配器填入新填入活粒子堆动粒子从位置纹理写回到顶点数CPU/系统内存栈中堆栈中组中GPU/显示内存从新粒子堆从纹理中读取数据，绘制粒子栈中读取信根据运动方程更新息绘制到相粒子的速度，位置纹应纹理中理更新下一帧，如粒子死亡，将粒子位置移到不可见区域图4-1粒子系统体系图Figure4-1FlowofParticleSystem4.2.2粒子属性的存储众所周知，普通的粒子系统是将粒子的所有属性存储在系统内存中，根据粒子运动方程、粒子当前位置和速度，在绘制每一帧前计算粒子下一时刻的位置，根据新计算出的位置将粒子绘制在帧缓存中。本文所论述的粒子系统将粒子的属性全部都存储在浮点纹理中，在粒子的众多属性中最重要的就是粒子的位置与速度，我们首先介绍粒子位置的存储方式。浮点纹理中每个像素均由R,,,GBA个分量组成，这样，我们便可以将粒子的速度分量x,,yz分别保存在纹理的R,,GB分量中，每一个粒子位置信息占用一个像素，如果我们用256256×大小的纹理，则可以存储65536个粒子的位置信息。这29 上海交通大学硕士学位论文第四章基于GPU的粒子系统样，我们把一个二维纹理看作成一个一维数组，纹理坐标作为粒子数组的索引，就可以很方便地读写每一个粒子的属性。由于在绘制期间这个纹理要同时被当作GPU的输入数据与输出目标，而同一个纹理又不能同时作为输入与输出，所以我们需要同时定义两个相同的浮点纹理形成一组纹理对，用来保存粒子的位置信息，纹理对中一个用于读取信息供shader代码计算，另一个保存计结果。在下一帧的计算时，调换两个纹理。同理，粒子的速度也存储在这样的一组浮点纹理对中。在复杂程度相对不高的粒子系统中，粒子除位置与速度属性的其它属性（包括粒子的生存周期、初始位置、大小、颜色、不透明性等）在粒子初始化后只根据很简单的计算便可得知或根本就不再发生改变，这样，我们便可以用一个单一的浮点纹理来保存这些属性。粒子属性存储方式如图4-2所示。图4-2粒子属性存储方式Figure4-2RestoreoftheParticleattribute4.2.3粒子的生成和消亡粒子可以无限地存活于系统中，也可以根据一定的条件限定粒子的生存时间。无限存活的粒子系统实现起来相对比较简单，而在限定了粒子存活条件的粒子系统中，粒子的生存时间是有限的，当一个粒子超过它的生存时间后就会消亡。由于GPU的能力所限，粒子的生成与消亡不能直接通过GPU实现，而是通过在内存中建立一个索引存储器，用来存储当前活动的粒子索引。粒子生成时，在索引存储器中找到一个空闲值并将粒子属性保存在此索引所指向的粒子结构中，然后利用shader代码将其各属性信息绘制到相应的浮点纹理中。粒子的消亡是在CPU与GPU上同时进行的。当一个粒子消亡时，CPU根据其索引将其从活动的粒子集合中删除，并将其索引放入到索引存储器的空闲位置中30 上海交通大学硕士学位论文第四章基于GPU的粒子系统以备新粒子使用；GPU则将已消亡粒子位置移到不可见的区域，比如无限远处。4.2.4粒子速度与位置更新每经过一个时间单位，粒子的速度与位置都需要更新，但这些更新操作均是通过像素通道由GPU来完成的。这个过程是通过绘制一个帧缓存大小的矩形来更新绘制目标上的所有像素信息，而这个绘制目标就是粒子速度或位置纹理对中的一个。而纹理对中的另一个存储着粒子前一帧的速度或位置信息的纹理则用于GPU的输入。首先更新粒子的速度属性，将存储有粒子速度和位置属性的纹理读入GPU根据运动学方程计算出粒子下一时刻的速度，在这个过程当中，我们可以进行碰撞检测、外力作用等一系列复杂的运动模拟，通过粒子速度的变化。达到这类运动过程的仿真。粒子速度纹理更新步骤：(1)将前一帧的粒子速度与位置属性以纹理方式读入GPU。(2)设定粒子速度更新算法的变量，如重力、粒子质量、碰撞系数、速度衰减因子等。(3)根据前一帧的粒子速度与位置结合运动方程计算出下一帧的粒子速度。(4)将新计算出的结果写入到另一幅保存粒子速度的纹理中。以上步骤均由shader代码在GPU中实现。粒子位置属性信息的更新与速度的更新原理基本相同，利用已更新过的速度信息与原位置信息通过pos+=veltimestep×得到新位置信息，写回到目标纹理中。当然这只是最简单的情况，如果考虑更多受力情况以及碰撞检测，在shader代码中加入相应的算法即可。4.2.5粒子的绘制在目前的OpenGL2.x版本的三维图形编程接口只在vertexshader中支持顶点纹理操作，但由于我们的应用需要将位置、速度等信息输出到缓存中，这又必须在pixelshader中进行。解决的方法是通过OpenGL扩展：NV_pixel_data_range将数据从像素缓存拷贝到顶点缓存中。粒子可以被渲染成点、三角面片或多边形，但是如果一个粒子同时有多个顶点，那么在渲染之前就要手动复制粒子的位置信息。为了避免这样的麻烦，尽可能地只使用点绘制。粒子在转化为顶点信息后，通过普通的渲染过程绘制到帧缓存中即可。31 上海交通大学硕士学位论文第四章基于GPU的粒子系统4.2.6pBuffer的应用与缺陷粒子的速度与位置属性是存储在浮点纹理中，但是浮点纹理的操作必须通过像素缓存pBuffer来实现。pBuffer支持rendertotexture，使应用程序在显示内存中产生复杂的可编程图象，这些图像可以被当作纹理一样操作，甚至可以被写回到系统内存中。wgl_arb_pbuffer扩展可以实现此功能。pBuffer有着强大的功能，使编程更为灵活；但同时存在一些缺陷：(1)GDI没有对Pbuffer做任何的渲染。(2)pbuffer使用的像素格式只能是那样被ICD支持的。通用的格式是无效的。(3)如果没有足够的资源，分配pbuffer会失败。(4)如果显示模式发生改变，pbuffer可能会丢失。在显示模式改变后，可以使用查询来得知pbuffer的状态，如果不可用，就需要重新分配pBuffer。每个pBuffer像普通的帧缓存一样有两个缓存：前缓存与后缓存，这就需要程序员在读写pBuffer之前指定读写操作是基于哪个缓存。4.3实验结果与分析我们实现了上文所论述的粒子系统，并在普通的PC平台上（AMDAthlon643500+，1GB内存，GPU为Nvidia7600GS，256MB显存）对该系统进行了两组实验，图4-3是使用该粒子系统进行的雨景模拟实验效果。图4-3粒子系统对雨景的模拟Figure4-3Particlesystemsimulatestherainyscene32 上海交通大学硕士学位论文第四章基于GPU的粒子系统4.3.1GPU粒子系统与普通粒子系统的对比本试验使用256256×大小的pBuffer存储粒子属性，使用本文所论述的粒子系统与普通粒子系统对雨景进行仿真。实验采用的简化模型在降雨区域上空设定一个成雨立方体，所有的雨滴都在该立方体内随机产生。在不考虑风力影响的情况下，雨滴在下落过程中的受力为：2vFGRm=−=−gkAρv合v其中G，R分别代表雨滴所受到的重力和空气阻力。g是由重力引起的加速度矢量，其值为(0,,0)g，k为常数，ρ为空气密度，A，v分别代表雨滴的横截面积和运动速度矢量，因此，雨滴的加速度为：F合a=m为了简化方程，我们可以把R用常量来表示，即使用速度的衰减因子代替R，这样可以简化方程，进而提高普通的基于CPU粒子系统的实时性能。实验表明，本文论述的粒子系统在绘制过程中，当粒子数在10万以下时，帧数始终保持显示器最高刷新频率75帧每秒左右，其实际处理能力远不止于此；甚至当粒子数超过20万个时，显示帧数仍然超过50帧每秒，依然具有良好的实时性能。而普通的粒子系统在粒子数增加到5万个左右时，系统性能就开始下降，当粒子数超过6万个时已不能达到实时效果。对比实验数据如图4-4所示。图4-4GPU粒子系统与CPU粒子系统性能对比Figure4-4PerformanceofGPU/CPUparticlesystems33 上海交通大学硕士学位论文第四章基于GPU的粒子系统实验表明，基于GPU的粒子系统的实时性能远远高于普通粒子系统，在粒子数增加到26万个左右时，系统还可以保持在55fps左右。4.3.2pBuffer的大小对系统性能的影响在实验过程当中，我们还发现pbuffer的大小对系统的性能影响很大。主要原因是显示内存中的缓存更新问题。当pbuffer大小超过缓存时系统就会因为内存调度问题而降低性能，从而使系统在某一段帧数突变，降低为原来的1/2左右。根据这样的性质，我们固定pbuffer的长度为256，对pbuffer的宽度大小采样，在同一平台上测量出了以下实验数据。实验均是在同一系统平台上并固定了粒子数量的情况下进行的，所以不存在因为硬件问题或粒子数量不同而影响系统性能的情况。实验数据如图4-5所示。图4-5pBuffer大小对系统性能的影响Figure4-5SizeofpBufferaffectssystemperformance由于pbuffer的大小决定了粒子系统中可以同时处理的粒子数量，当粒子系统的粒子数目超出一定数量的范围时，系统的性能瓶颈由粒子的处理速度转为GPU的芯片缓存和显存的数据交换速度，粒子系统的性能也会受到很大的影响。但即使这样，GPU粒子系统的实时性能也远远好于传统的CPU粒子系统，而且相信随着GPU硬件技术的更新，更大的芯片缓存和显存带宽可以逐步缓解这个问题。34 上海交通大学硕士学位论文第四章基于GPU的粒子系统4.4结论本文主要介绍了一种基于当前图形硬件GPU的粒子系统，这种粒子系统最大的特点就是其仿真和绘制过程的计算大部分是由GPU所完成，只有粒子的分配和删除是在CPU中进行。粒子在GPU中的并行处理过程很大程度提高了粒子系统对不定形物体的实时仿真性能。目前GPU的数学计算能力已经越来越强大，灵活，在软件上，GPU编程代码的限制越来越少，理论上CPU可以完成的计算在GPU上都可以完成，但由于GPU毕竟是一种为图形加速专门设计的语言，从实时性考虑，目前现有的应用程序不会在GPU上运行太过复杂的渲染程序，而且精度要求也并非很高，所以，复杂而精确的动力学仿真要想在GPU上完全实现以目前的GPU硬件来看尚未成熟。不过GPU的通用化是一个设计趋势，随着GPU技术的不断更新，现有的缺陷会不断得到弥补，基于GPU的粒子系统就会得到更加广泛的应用。35 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现第五章在GPU上的图像滤波实现5.1引言虚拟场景的渲染会应用到很多图像处理的技术，简单的例如图像模糊、锐化，雾化，复杂例如在最新的三维游戏中得到广泛追捧的高动态范围（HDR）图像的色调映射。这些图像处理的技术都使用了一种或者多种图像滤波器的组合。因此可以说图像滤波器是现代计算机图形学中的关键要素之一。图像滤波中，又分为两种不同的基本方式：在空间域中的滤波和在频域中的滤波。在空间域中的滤波很简单，我们只需要将待滤波的图像和滤波器核进行卷积运算；而在频域的滤波则需要先将图像通过傅立叶变换转换到频域上，然后乘以适当的滤波器，最后，通过傅立叶反变换转换到空间域中。这两种方式在不同的情况下有着各自的缺点和优点，而且在CPU上的实现已经是成熟通用的方法广为人们熟知。然而由于这两种方法都存在计算量巨大的特点，当待处理的图像比较大的时候，CPU的结构特点决定了其的性能往往不能满足图像滤波的实时性要求。图形处理器(GPU)为SIMD架构，决定了它非常适合处理大量数据诸如图像、音频的这类任务。早期的GPU由于是固定管线结构，自由度非常小，人们难以利用其进行3D图形运算之外的工作。自从Microsoft推出DirectX8以后，GPU工作管线中加入了可编程单元，使得人们可以使用GPU进行一些通用的计算，同样，也给使用GPU进行图像滤波处理提供了可能。[74]关于在GPU上实现FFT算法，可能是Moreland和Angel首先进行尝试的，但由于当时条件限制（他们使用的是NV5000系列的GPU），许多工作还无法在[75]GPU上实现；Sumamaweera和Liu在医疗图像处理上做了很有效的尝试，他们使用时间抽取算法实现FFT并把计算量在顶点着色器和象素着色器中做了分摊，但是这种分摊并没有收到很明显的效果，因为老架构的GPU顶点运算单元和象素运算单元存在运算能力的不均衡。本文采用了频率抽取算法在GPU上实现了FFT算法，在实时图像处理方面将FFT和卷积算法就性能和GPU实现的适应性方面进行了比较。简单起见，本文的图像都为灰度图像。36 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现5.2数学原理5.2.1离散傅立叶变换有着N个采样点的一维离散信号x()n的离散傅立叶变换可以表示为：N−1knX()kx=∑()nWN,01≤kN≤−,(5.1)n=02πkn−iknN其中：We=(5.2)N由于我们讨论的数字图像都是二维信号，故需一维傅立叶变换扩展到二维：NN−−111uxvyFuv(,)=2∑∑fxyWW(,)NN,0≤uvN,≤−1(5.3)Nxy==00其中f(,)xy为一NN×的二维离散信号。根据二维离散傅立叶变换的可分离性，二维傅立叶变换可以分解为两步，其中每一步都是一个一维傅立叶变换：首先，对于每一个x值，(,)fxy先沿每一行进行一次一维FT，得到Fxv(,)，然后将其沿每一列在进行一次一维FT，就可得到二维傅立叶变换Fuv(,)：N−1N−11uy1vxFxv(,)=∑fxyW(,)N,Fuv(,)=∑FxvW(,)N(5.4)Ny=0Ny=0图5-18点DIT算法信号流图Figure5-1Decimationinfrequency2-radixbutterflynetworkfor8values37 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现图5-2蝶形单元Figure5-2Detailofone“butter-fly”fromtheDIFnetwork2朴素的离散傅立叶变换的时间复杂度为ON()，而快速傅立叶变换可以将这个复杂度降为ON(log)N。我们采取频率抽取（DIT）基2算法，其模型可以用蝶形网络图5-1，5-2来表示.由图可见，由于DIT算法的输出值和正常顺序有一个码位倒置的关系，所以需要将其做一次转换然后作为最终输出。5.2.2空间域卷积两个大小为NN×的二维离散信号f(,)xy和hxy(,)的卷积可以定义为：NN−−111yxy(,)=−2∑∑fxmynhmn(,−)(,)(5.5)Nmn==00在图像处理领域里面，若一个信号代表输入图像，则另一个为滤波器的核。5.3在GPU上的实现5.3.1FFT在GPU上的实现正如之前所说，2D图像的傅氏变换可以转化为两步一维傅氏变换，而所有的一维傅氏变换又可以转换为logN步的运算，前一步计算的输出就是后一步计2算的输入；结合GPU编程接口的特殊性，我们设计了一个双缓存系统：将初始输入图像传输到其中一个缓存内作为texture输入，而另一个缓存作为Render-Target输出，每一次GPU管线的渲染动作就是一步FFT的运算，渲染一次后将两个缓存的角色对调，上次的输入缓存作为这次的输出缓存，上次的输出缓存作为这次的输入缓存，由于二维FFT需要进行两步，所以共计进行2log×+N2次的渲染（包括两次输出的转置运算），我们就可以得到输入图像238 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现的FFT变换结果。下面我们讨论每一步的FFT计算。由图5.1可以看出，在每一步计算中，输出pixel的值都是由在输入texture上与它位置相同的texel加上另一个不同位置k的texel乘以因子±W得到的。与它位置相同的texel的纹理坐标我们可以从象素N着色器的纹理坐标输入中取得，而另一个texel的纹理坐标，我们可以预先离线k计算求得，而计算因子W可以分解为：Nk22πkkπWi=−cos()sin()(5.6)NNN因为一共只有离散的N个正弦值和余弦值，所以他们也可以很快的预先计算好并通过texture来输入。在DIF的最后的转置计算中，通过预先计算的码位转置的纹理坐标，我们也能够很容易得在一次渲染中将输出次序重排。基于以上讨论，我们设计了这样的一个计算因子texture，其数据的结构如图5-3所示，在前log()N个texture中，每个texel的R通道存放了第二输入的符号信息，G通道存放了第二输入的纹理坐标，而B通道和A通道则存放了相应的正余弦值。值得注意的是由于所有的采样都在相同行（列）中进行，所以第二输入的纹理坐标只需要占用一个通道。在DIF的最后一步，我们并不需要正余弦信息，所以B通道存放了经过码倒置的纹理坐标。NN前logN步DIF的纹理最后码位倒置的纹理2nd2nd2ndSignSinCos一个texel的RGBA通道SignCoordCoordCoord图5-3FFT计算因子纹理的数据结构Figure5-3StructureoftheauxiliarytextureofFFT通过这样的FFT在GPU上实现，我们做到了使用最简的着色器代码，在代码中没有用到跳转和循环等控制流语句，这样即使在较老一些的GPU上也能够运行并获得较高的效率。39 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现5.3.2空间域卷积在GPU上的实现在GPU上实现空间卷积算法原理十分简单，在每个象素上通过其自身的纹理坐标输入获得邻接点的纹理坐标值，采样得到邻接点的象素值，然后和滤波器核进行卷积运算操作。通过一个循环很容易实现。但是随着滤波核的增大，每个象素处理需要执行的指令条数会迅速增多。而SM(shadermode)2.0的asm指令条数限制在了96条以内，这就使滤波核的规模限制在了很小的范围内。到了SM3.0，每个着色器可以使用最多32768条指令，这就给与了我们更多的自由度，允许使用更大的滤波核。在即将到来的SM4.0，着色器指令条数可以没有限制，这将意味着滤波核的大小也可以不受限制。但在当前，尤其是一些较老的GPU上，滤波核还无法做到很大。滤波核的可分离性会严重影响到卷积运算的性能，因为可分离的二维卷积可以分解为两个一维的卷积，这样计算的复杂度就由原来的二次方关系降为线性关系，可以节省很多指令条数。更优化的卷积实现方式是将所有采样点的纹理坐标与滤波核的数据预先计算好放到texture内，在计算卷积时读取。这样Shader代码中就不会出现流控制指令，但是代码长度同样无法得到控制，依然受到软硬件环境的影响。5.4实验结果与比较本文的实验平台环境为AMDAthlon643500+，1GB内存，GPU为Nvidia7600GS，256MB显存，CPU和GPU在2006年都是主流的民用配置。无庸置疑，GPU的SIMD架构决定了它在处理大量数据方面的优势，无论是FFT还是卷积运算，在GPU上的性能表现都大大超出了其在CPU上的版本。图5-4显示在用卷积运算处理256x256和512x512大小的图像时，GPU的处理速度平均是CPU的3倍，若将GPU的处理精度由32bit减少到16bit，其性能还会有大幅度的提高，而CPU的32位架构使得其不会从精度的损失上取得性能的提升。在GPU上对一个256x256的图像做FFT约耗时5.2ms，而在CPU上则大约要用18ms，性能提升的比例约为3.4，在这里FFT的CPU版本是M.Frigo和[76]S.G.Johnson的FFTWlibraries，这是一个高度优化的算法，使用了许多现代CPU的特性。而将经过FFT变换的图像乘以滤波器在CPU上还要花去大约10ms而在GPU上只需要额外的0.1ms，这似乎和总线中的数据传输速度有关，并不完全是CPU性能所致。接下来我们将比较同样在GPU上的FFT和卷积的性能差异。在采用单个高40 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现斯低通滤波器的情况下，我们测试了FFT和卷积在处理256x256，512x512和1024x1024大小的图像时表现出来的性能，图5-5显示了FFT和不同滤波核大小的可分离或不可分离的卷积运算的帧率。从图中我们可以看出随着图像的变大，FFT和卷积运算的性能下降比例是不一样的，这可以用两者的基本运算单元次数2来解释。对一个NN×大小的图像进行可分离卷积滤波的复杂度为OkN(2⋅)，其中k为滤波核的大小：因为对每一个象素我们都要在x，y作标上进行卷积运2算；而FFT的复杂度则为ON(4⋅log())N，因为单次一维FFT需要log()N步22计算，而每个象素都需要经过两个坐标轴和正逆共4次这样的变换。图5-4CPU与GPU的卷积计算比较Figure5-4ComparisonofGPUandCPUimplementationsofconvolution图5-5FFT与卷积的性能比较Figure5-5ComparisonofFFTandconvolution当滤波核较小的时候，使用可分离的卷积滤波会比FFT快很多；如果在某个滤波核上卷积和FFT取得了同样的性能，那么我们可以称之为临界核，基于41 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现上面的复杂度讨论，我们知道临界核的大小会随着图像的增大而随之增加，图5-5中的结果也显示了这一点。22如果卷积滤波核是不可分离的，那么它的计算复杂度将是OkN()⋅，这是相当慢的，同时也会受到pixelshader指令条数限制的严重制约。在SM3.0下，我们可以实现的最大滤波核是99×的（仅允许112次的采样指令）。图5-6多滤波器叠加时FFT和卷积的比较，图象大小为256x256Figure5-6ComparisonofFFTandconvolutionformultiplefilters在现实中很多的应用，象HDR图像的色调映射，会对输入图形叠加多次滤波，所以我们也对卷积和FFT的多重滤波性能表现进行了比较。可以想象，对于卷积滤波，每引入一个滤波器，就需要重复一次卷积操作；而对于FFT，无论引入多少滤波器，我们只需要做一次傅立叶正逆变换，叠加一个滤波器仅仅是多加一次乘法，因此当滤波器数量很多时，FFT有着更好的效率。从图5-6中我们可以看出当滤波器个数变多时，FFT逐渐表现出更好的性能，当仅有一个滤波器时，FFT和33象素的滤波核性能相当，而当滤波器个数变为8个时，FFT的性能可以达到21象素的滤波核的水平。表5.1对卷积滤波和FFT滤波的优缺点进行了比较。表5.1卷积滤波和FFT的优缺点比较FFT卷积+对于任何滤波器性能不受影响-复杂度受滤波核影响，大的或不可分离的滤波核性能较低+基本不受硬件条件限制-滤波核的大小受到软硬件环境限制+可以实现所有频域上的滤波-不是所有滤波器都有合适的滤波核+多个滤波器的叠加并不影响性能-滤波器的叠加会明显的影响性能-傅立叶正反变换非常耗时+滤波核小的情况下性能出色-由于计算步骤过多，对计算精度很敏感，即使是非+对计算精度要求不高，8bit的精度足以满足非高动高动态范围的应用也要有16bit的精度态范围的应用-仅能使用在大小为2的幂的图像，否则需要扩展图+对图像大小没有限制像的大小42 上海交通大学硕士学位论文第五章在GPU上的图像滤波实现5.5结论本文提出了两种基本的图像滤波算法：卷积和FFT在GPU上的实现，在不同方面对其性能表现作出了评价，结果显示无论是卷积还是FFT，在GPU上的性能都远远强于其在CPU上的实现版本。当滤波核较小，滤波器较少的情况下，卷积有着较FFT更优的性能，尤其是若滤波核是可分离的，那么我们可以将所有的采样点纹理坐标预先离线计算好，这样可以大大提升卷积的在线计算性能。而FFT也有着它的优势：当滤波器个数较多，卷积核较大或者卷积核是不可分离的情况下，FFT表现出来的性能更为出色。43 上海交通大学硕士学位论文第六章总结与未来工作第六章总结与未来工作本文在可编程图形处理器在虚拟现实领域中的应用技术方面展开了工作，首先本文研究了两个经典的实时硬阴影算法：阴影图算法及阴影体算法，总结了算法实现的原理及优劣性。并针对阴影图算法偏移量问题提出了一个自适应偏移量算法；其次，本文探讨了在虚拟自然环境渲染中得到广泛应用的粒子系统在GPU上的实现，最后，本文讨论了图像滤波算法在GPU上的实现。在虚拟现实技术的图形渲染技术方面，可编程图形硬件可以说是必不可少的实现工具；目前绝大部分的显卡在硬件结构中已经不再有固定流水线，而只有可编程流水线，其固定流水线的绘制其实是用可编程流水线模拟出来的，因此在进行绘制时使用可编程图形流水线肯定会带来更好的性能表现。另一方面，虚拟渲染和虚拟游戏技术的发展对于GPU技术的发展起着至关重要的作用，许多优秀的图形算法由于游戏的需要而被研究出来并在硬件上得到实现，本文提出的阴影算法就是其中之一。目前许多游戏引擎仅仅支持硬阴影如Doom3、Halo2和NeverwinterNight，由于对于游戏开发者对算法的强壮性及反走样的要求，在这些游戏引擎中都选择阴影体算法来实现阴影，但是正如第二章所讨论的，该算法并不适合于复杂场景。Doom3的开发者JohnCarmack曾经就表示过它的引擎在运行时花费了一半的渲染时间来绘制阴影。而且到目前为止，没有一个游戏引擎采用了一般性软阴影算法，在MaxPayne2和半条命2里面使用的是进行模糊处理了的投影纹理来模拟软阴影效果，但是由于算法不支持自阴影，所以它不属于一个一般性算没法。所以针对实时应用的阴影算法在未来的工作还有许多，首先怎么解决阴影图算法的低采样及非强壮性问题，其次怎么优化阴影体算法使其能应用到大型的复杂的环境中，第三，如何才能寻找到一个有效的，反走样的且强壮的软阴影算法。针对一些非实时性的阴影生成方法，如辐射度法，已经能生成高质量高性能的阴影渲染，可以考虑如何将其扩展，使其能够支持动态场景。总之，就目前来说，实时阴影算法仍然有许多挑战性的问题等待解决。另外对于特殊物体的实时阴影渲染也将是算法研究的重点，比如毛发的阴影，透明物体的阴影，浮云及草丛等物体的阴影。阴影图算法和阴影体算法根本就不适合这些对象，因为其几何构造过于复杂，物体间光反射的影响较大。所以必须针对性地研究这类物体的阴影算法。虽然在这方面有了一定的研究，但是实时性能不理想。除了在虚拟现实技术中的图形渲染方面的应用，由于可编程图形硬件具有并行执行的体系结构，许多在虚拟现实系统中并非图形渲染但对处理器的并行性和实时性要求较高的计算都希望能从传统的CPU转移到GPU上，借助GPU的强44 上海交通大学硕士学位论文第六章总结与未来工作大运算性能来执行，目前已有了大量这方面的研究和应用，如本文的GPU粒子系统和图像滤波算法在GPU上的实现。但是目前的可编程图形硬件还只能提供IEEE单精度的浮点支持，一些精度要求较高的通用计算往往需要IEEE双精度的浮点支持，这是当前限制可编程图形硬件在高性能计算方面得到实质性应用的一个最主要原因；此外现在的可编程图形硬件的显存容量最大也不超过1G，这对于很多计算应用也是不够的。这些都是硬件方面的约束，随着可编程图形硬件的飞速发展，硬件厂商将会提供IEEE双精度的浮点支持，显存容量也会不断增加，这些硬件限制会不断得到解决。在软件上，限制可编程图形硬件在通用计算方面应用的一大障碍就是编程接口，目前的可编程图形硬件编程接口都是面向图形渲染设计的，对于类似于粒子系统或图像滤波这样并非标准的图形渲染应用，必须采用各种转换和变通的方法将其通过标准的图形渲染编程接口在GPU上实现，而这些非图形渲染技术的研究工作者并不一定精通图形渲染的编程接口，这样的接口转换对于他们来说是相当困难的，既精通本专业领域又了解GPU的人是非常少的。而类似Brook这样的流处理机编程环境，使得不熟悉图形流水线的人同样可以充分利用GPU提供的强大计算能力，这样会吸引更多不同领域的研究者关注和利用GPU。目前，这方面的接口还没有一个统一的规范，技术也并不成熟，在这方面的研究也势必大有所为。可以想象，出现基于可编程图形硬件的高性能计算系统只是时间长短的问题。可编程图形硬件在虚拟现实领域将会成为一种普遍的实现工具，同时目前的可编程图形硬件在功能上越来越容易理解和使用，很多世界一流的虚拟现实实验室均己开设了相关课程，并列入学生的培养计划；可编程图形硬件技术也是促进虚拟现实领域学术界和工业界之间沟通的桥梁，学术界的研究者在使用可编程硬件过程中不停地对GPU的功能提出新的要求，从而推动硬件厂商们不断推出功能更加强大的GPU；功能更强大的GPU反过来又会促进更多新的研究成果，这样相辅相成的良性循环一定会推动学术界、工业界，软件、硬件领域的不断进步。45 上海交通大学硕士学位论文参考文献参考文献[1]MacedoniaM.TheGPUenterscomputing’smainstream.IEEEComputer,2003,36(10):106-108.[2]LindholmE,KilgardMJ,MoretonH.Auser-programabevertexengine.In:Proc.OftheSIGGRAPH2001.LosAngeles,2001.149-158.[3]吴恩华，柳有权，基于图形处理器(GPU)的通用计算。计算机辅助设计与图形学学报，2004,16(5):601-612.[4]HopgoodFRA,DuceDa,GallopJr,SutcliffeDC.IntroductiontotheGraphicsKernelSystem(GKS).AcademicPress,1983.[5]EnderleG,KansyK,PfaffG.ComputerGraphicsProgramming:GKS-TheGraphicsStandard.Berlin:Springer-Verlag,1984.[6]HowardTLJ,HewittWT,HubboldRJ,WyrwasKM.APracticalIntroductiontoPHIGSandPHIDSPlus.Addition-Wesley,1991.[7]ClarkJH.Thegeometryengine:AVLSIgermetrysystemforgraphics.In:Proc.OftheSIGGRAPH’82.1982.127-133.[8]OwensJD,DallyWJ,KapasiUJ,RixnerS,MattsonP,MoweryB.Polygonrenderingonastreamarchitecture.In:Proc.OftheEurographics/SIGGRAPHWorkshoponGraphicsHardware,2000.23-32.[9]FuchsH,PoultonJ.Pixel-Planes:AVLSI-orienteddesignforarastergraphicsengine.VLSIDesign,1981,2(3):20*28.[10]EylesJ,AustinJ,FuchsH,GreerT,PoultonJ,Pixel-Plane4:Asummary,advancesincomputergraphicshardwareII.In:EurographicsSeminarsToutorialsandPerspectivesinComputerGraphics.1988.183-208[11]FuchsH,IsraelL,PoultonJ,EylesJ,GreerT,GoldfeatherJ,EllsworthD,MonlnarS,TurkG,TebbsB.Pixel-Plane5:Aheterogeneousmultiprocessorgraphicssystemusingprocessor-enhancedmemories.In:Proc.OftheSIGGRAPH’89.1989.79-88.[12]MolnarS,EylesJ,PoultonJ,GreerT.PixelFlow:High-Speedrenderingusingimagecomposition.In:Proc.OftheSIGGRAPH’92ACMPress,1992.231-240.[13]GovindarajuNK,SucA,YoonSE,ManochaD.SWITCH:ParallelocclusioncullingforinteractivewalkthroughsusingmultipleGPUs.TechnicalReport,TR02-027,UNC-CH,2002.[14]GovindarajuNK,RedonS,LinM,ManochaD.CULLIDE:Interactivecollisiondetectionbetweencomplexmodelsinlargeenvironmentsusinggraphicshardware.In:Proc.OftheEurographics/SIGGRAPHWorkshoponGraphicsHardware.2003.25-32.[15]SudA,OtaduyMA,ManochaD.DiFi:Fast3Ddistancefieldcomputationusinggraphicshardware.In:Proc.OftheEurographics,2004.[16]TomovS,McGuiganM,BennettR,SmithG,SpileticJ.Benchmarkingandimplementationofprobability-basedsimulationsonprogrammablegraphicscards.Computer&Graphics,2005,29(1).46 上海交通大学硕士学位论文参考文献[17]LarsenES,McallisterD.Fastmatrixmultipliesusinggraphicshardware.In:Proc.oftheSupercomputing.2001.55-60.[18]ThompsonCJ,HahnS,OskinM.Usingmoderngraphicsarchitecturesforgeneral-purposecomputing:Aframeworkandanalysis.In:Proc.oftheInt'1Oymp.OnMicroarchitecture.2002.306-317.[19]KrugerJ,WestermannR.LinearalgebraoperatorsforGPUimplementationofnumericalalgorithms.ACMTrans.OnGraphics,2003,22(3):908-916.[20]HallJD,CarrNA,HartJC.CacheandbandwidthawarematrixmultiplicationontheGPU.UIUCDCS-R-2003-2328,Champaign:UniversityofIllinoisatUrbana-Champaign,2003.[21]RumpfM,StrzodkaR.UsinggraphicscardsforquantizedFEMcomputations.In:Proc.oftheVIIP2001.2001.98-107.[22]HarrisMJ,CoombeqScheuermann工LastraA.Physically-Basedvisualsimulationongraphicshardware.In:Proc.oftheGraphicsHardware2002.2002.109-118.[23]LiW,WeiXM,KaufmanA.ImplementinglatticeBoltzmanncomputationongraphicshardware.TheVisualComputer,2003,19(7-8):444-456.[24]BolzJ,FarmerI,GrinspunE,SchrooderP.SparsematrixsolversontheGPU:Conjugategradientsandmultigrid.ACMTrans.onGraphics,2003,22(3):917-924.[25]GoodnightN,WoolleyC,LuebkeD,HumphreysG.Amultigridsolverforboundarybalueproblemsusingprogrammablegraphicshardware.In:Proc.oftheGraphicsHardware2003.2003.102-111.[26]HarrisMJ,BaxterW-VIII,ScheuermannT,LastraA.Simulationofclouddynamicsongraphicshardware.In:Proc.oftheGraphicsHardware2003.2003.92-101.[27]LiW,FanZ,WeiXM,KaufmanA.GPU-Basedflowsimulationwithcomplexboundaries.TechnicalReport,031105,ComputerScienceDepartment,SUNYatStonyBrook,2003.[28]KimT,LinMC.Visualsimulationoficecrystalgrowth.In:Proc.oftheSIGGRAPHIEurographicsSymp.onComputerAnimation.2003.86-97.[29]LefohnAE,KnissJM,HansenCD,WhitakerRT.InteractivedeformationandvisualizationoflevelsetsurfacesusinggraphicsHardware.In:IEEEvisualization.20003.75-82.[30]StamJ.Stablefluids.In:Proc.oftheSIGGRAPH'99.I999.121-128.[33]LiuYQ,WuEH,LiuXH.FluidsimulationsonGPUwithcomplexboundaryconditions.In:ACMWorkshoponGeneral-PurposeComputingonGraphicsProcessors(GP2).2004.[34]GovindarajuNK,LloydB,WangW,LinM,ManochaD.Fastcomputationofdatabaseoperationsusinggraphicsprocessors.In:Proc.oftheSIGMOD.2004.[35]http://lava.cs.virgina.edu/bpred.html[36]WangJQ,WongTT,HengPA,LeungCS.DiscretewavelettransformonGPU.In:ACMWorkshoponGeneral-PurposeComputingonGraphicsProcessors(GP2).2004.47 上海交通大学硕士学位论文参考文献[37]WangJQ.ExploitingtheGPUpowerforintensivegeometricandimagingdatacomputation[MphilThesis].ChineseUniversityofHongKong,2004.[38]HanrahanP,LawsonJ.Alanguageforshadingandlightingcalculations.ComputerGraphics,1990,24(4):289-298.[39]UpstillS.TheRenderManCompanion:AProgrammer'sGuidetoRealisticComputerGraphics.Addison-Wesley,1990.[40]ApodacaAA,GritzL.AdvancedRenderMan:CreatingCGIforMotionPictures.MorganKaufmannPublishers,2000.[41]KessenichJD,BaldwinRR.OpenGL2.0ShadingLanguage.1.051Ed,2003.[42]RostRJ.OpenGLShadingLanguage.Addison-Wesley,2004.[43]ProudfootK,MarkWR,HanrahanP,TzvetkovS.Arealtimeproceduralsystemforprogrammablegraphicshardware.ComputerGraphics,2000.159-170.[44]MarkWR,ProudfootK.CompilingtoaVLIWfragmentpipeline.In:Proc.oftheGraphicsHardware2001.2001.[45]PeeperC,MitchellJL.IntroductiontotheDirectX9High-LevelShaderLanguage.2003.http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnhlsllhtml/shaderx2_introductionto.asp[46]MarkWR,GlanvilleS,AkeleyK,KilgardMJ.Cg:AsystemforprogramminggraphicshardwareinaC-likelanguage.ACMTrans.onGraphics,2003,22(3):896-907.[47]BuckI,FoleyT,HornD,SugermanJ,FatahalianK,HoustonM,HanrahanPBrookforGPUs:Streamcomputingongraphicshardware.ACMTrans.onGraphics,2004,23(3):777-786.[48]McCoolM,ToitSD,PopaT,ChanB,MouleK.Shaderalgebra.ACMTrans.onGraphics,2004,23(3):787-795.[49]MelSlater，AnthonySteed，YiorgosChrysanthou.程成，徐玉田译.计算机图形学与虚拟环境.北京：机械工业出版社，2004,10.[50]石教英．虚拟现实基础及实用算法．北京：科学出版社，2002，4．[51]鲍虎军．虚拟现实技术概论．中国基础科学．2003，03．pp26-32.[52]蒋庆全．国外ＶＲ技术发展综述．飞航导弹．2002，01．pp27-34，61．[53]张茂军．虚拟现实系统．北京：科学出版社．2001,9.[54]DanielCohen-Or,YiorgosL.Chrysanthou,ClaudioT.Silva．ASurveyofVisibilityforWalkthroughApplications．IEEE．July-September2003(Vol.9,No.3).[55]Woo，A．，PoulinPandFourier,A．(1990)ASurveyofshadowalgorithms,IEEECG&A,10(6),pp13-31．[56]Jean-MarcHasenfratz,MarcLapierre,NicolasHolzschuch,F.X.Sillion．AsurveyofReal-TimeSoftShadowsAlgorithms．ComputerGraphicsForum.Volume22,Number4.2003.pp753—774.[57]梅春晖．基于预计算及采样的实时高真实感图像的绘制技术研究．浙江大学博士学位论文．2004，５.[58]Wald，I．，Slusallek，P．andBenthin，C．(2001)InteractiveDistributedRayTracingofHighlyComplexModels．RenderingTechniques2001proceedingsofthe12thEurographicsworkshoponrendering,edsS．J．GortlerandK．Kyszkowski，48 上海交通大学硕士学位论文参考文献London25-27June2001,pp274-285．[59]TimothyJ.Purcell,IanBuck,WilliamR.Mark,andPatHanrahan．RayTracingonProgrammableGraphicsHardware．ACMTransactionsonGraphics．2002，21(3)．pp.703-712.[60]Williams,L.Castingcurvedshadowsoncurvedsurface,ComputerGraphics,12,270-4.1978.[61]CassEveritt,AshuRege,CemCebenoyan.HardwareShadowMapping[R].NvidiaCooperation.2001.[62]FranklinC.Crow.Shadowalgorithmsforcomputergraphics.ComputerGraphics(SIGGRAPH1977),11(3).1977.7.pp242–248.[63]Bergeron.AgeneralversionofCrow’sshadowvolumes.IEEECG&A,6(9).1986.pp17-28.[64]EverittC,KilgardMJ.Practical&RobustStenciledShadowVolumesforHardwareAcceleratedRendering[R].NVIDIACooperation,2002.[65]EricChan.EfficientShadowAlgorithmsonGraphicsHardware[D].MIT.2004,7.[66]PemithRandimaFernando.AdaptiveTechniquesforHardwareShadowGeneration.CornellUniversity.2002.5[67]AWoo,Theshadowdepthmaprevisited.InD.Kirkeditor,GraphicsGemsIII[C].APProfessional,Boston.1992.pp338-342[68]D.Weiskopf,T.Ertl.ShadowMappingBasedonDualdepthLayers[A].TheEurographicsAssociation[C].2003.[69]Reeves,WilliamT.ParticleSystems-TechniqueforModelingaClassofFuzzyObjects[c].In:SIGGRAPHProceedings,1983[70]vanderBurg,John.BuildinganAdvancedParticleSystem[J].GameDeveloerMagazin,2000;(3)[71]McAllister,DavidK.TheDesignofanAPIforParticleSystem[R].TechnicalReort,DepartmentofComputerScience,UniversityofNorthCarolinaatChapelHill,2000[72]LutzLatta.MassiveDevelopmentGmbH,BuildingaMillionParticleSystem.2004[73]LanBuck.DataParallelComputingonGraphicsHardware.StanfordUniversity,2003[74]Moreland,K.,Angel,E.2003.TheFFTonaGPU.ProceedingsoftheACMSIGGRAPH/EUROGRAPHIICSconferenceonGraphicshardwaresession:Simulationandcomputation,112-119[75]Somanaweera,T.,Liu,D.2005.MedicalImageReconstructionwiththeFFT.InProgrammingTechniquesforHigh-PerformanceGraphicsandGeneral-PurposeComputation,Addison-Wesley.[76]Frigo,M.,Johnsom,S.G.2005FFTW.FastFourierTransformlibrary.http://fftw.org49 上海交通大学硕士学位论文致谢致谢本文是在翁惠玉老师的悉心指导和耐心帮助下完成的。她渊博的知识和对专业敏感的洞察力使我受益匪浅，对顺利完成本文起到了极大的帮助，特别是她严谨的治学风范和开拓精神将成为我今后学习和工作的指南。在此，我向她表示我最衷心的感谢！感谢我的父母和家人，感谢他们在我漫长而艰苦的求学之路上能够始终给予无私的帮助，默默的无微不至的关怀。在论文完成过程中，本人还得到了其他老师和许多同学朋友的热心帮助，本人向她们表示深深的谢意。感谢与我一起共同学习的同班同学。与班级同学的交往使我充分地感受到她们对生活的热爱、对学业的孜孜追求，这些都成为我不断努力的动力。与她们的讨论和交流拓宽了我的知识面，同时也为我论文的写作提供了许多有益的启发。最后向在百忙之中评审本文的各位专家老师表示衷心的感谢。冯煌二零零八年三月50 上海交通大学硕士学位论文攻读学位期间发表的学术论文目录攻读学位期间发表的学术论文目录1.第一作者.GPU图像处理的FFT和卷积算法及性能分析.《计算机工程与应用》;200844(2):120-12251