基于渲染光照可见性判断

ResearchandImplementationofRender-basedLightVisibilityDeterminationAlgorithmADissertationSubmittedfortheDegreeofCandidate:ZhouSchoolofComputerScience&EngineeringBeihangUniversity,Beijing,ChinaIntherealworld,theocclusionscanbeseeneverywhere.Theocclusionbetweenlightsandobjectsresultsinshadowswhichcanhelpunderstandingthescene.Inthefieldofcomputergraphics,theocclusiondetectionbetweenlightsandobjectsiscalledlightvisibilitydetermination,whichisimportantfortherealismofimageandbuildingasenseofimmersion.Thevisibilitydeterminationofpointlightisthemostclassicalincomputergraphics,whereastherearerarelyefficientmethodforthelightvisibilitydeterminationforsceneswithcomplexlightsources,includingsceneswitharealightsourceandsceneswithamountsofpointlightsources.Tosolvethisproblem,thispaperfirstlyconvertstheproblemofarealightvisibilitydeterminationtomanycoplanarpointlightsvisibilitydeterminationbysamplingthearealightsource,generatingpixelaccuratesoftshadows.Secondly,thepaperoptimizesontheefficiencyofthearealightvisibilitycomputationonthepremiseofaccuracy.Lastly,thispapereliminatesthecoplanarconstraintsofpointlightstoextendpointlightvisibilitydeterminationmethodtosceneswithmanypointlightsdistributedinspace y,thepaperincludesthreeresearchThepaperproposesapixellevelaccuraightvisibilitydeterminationmethodforarealightsourceforgeneratinghighqualitysoftshadows,whichalsohassomegeneralization.Pixellevelaccuracymeansthevisibilitybetweeneachpixelsampleandeachpointlightonarealightsourceisdeterminedprecisely.Generalizationmeansthemethodisapplicabletoanyscenesmodelledwithtriangles.Foreachpixelsampleoftheoutputimage,thecamerapointingtoarealightsourceisconstructedandthelightvisibilityiscomputedbyrasterizingoccludingtrianglesonthevisibilitybitmaskofthecamera.Thepaperproposesamethodforoptimizingthearealightvisibilitydeterminationmethodforthepurposeofachievinginteractiveframeratesatmoderateoutputimageresolution.Agridstructuremappixelsamplestotrianglesisconstructeddynamicallyusingtherelationsbetweentheminspace,whiakesthemethodsupportfullydynamicscenes,withmovinganddeformingblockersandreceivers,andwithchangingarealightsourceparameters.Thepaperproposesamethodforvisibilitydeterminationofmanypointlightsourcesdistributedinspacearbitrarily.Themethodimprovesonvisibilitydeterminationflowandintroducespre-samplingonthebasisoftraditionalshadowmapmethod,whichreducesmemorycostandpromotestheefficiencyoflightvisibilitydetermination.Noapproximationofthesceneisintroducedandthemethodisbalancedbetweenprecisionandefficiency.:Lightvisibility,Highqualitysoftshadow,Manylights,Interactive目第一章绪 1.1的选题背景及来 1.1.1的选题背景与来 1.2的研究目标及意 1.3的研究内 1.4的组织结 第二章研究现状与相关技 光照可见性判断方法概 精确光照可见性判断方 空间任意分布多点光源光照可见性判断方 可编程图形管线与语 基于CUDA的通用并行计 Optix实时光线引 本章小 第三章面光源像素级精确光照可见性判断方 引 方法基本原理概 基于CUDA的简易光栅器的实 基于CUDA的三角面片的光栅化方 光照可见性的计算及使 实验效果与分 本章小 第四章面光源光照可见性判断方法的效率优 引 方法基本原理概 构建光源视点相 计算二维网格区 组织场景像素采样 组织场景中的三角面 其它加速策 实验效果与分 本章小 第五章空间任意分布多点光源光照可见性判断方 引 方法基本原理概 多点光源光照可见性判断方法流 场景预采样的引 实验效 本章小 结论与展 研究内容总 未来工作展 参考文 攻读期间取得的学术成 致 图图 组织思路示意 图 可编程图形渲染流水 图 线程层次模 图 方法原理示意 图 像素采样点斜相机三维示意 图 空间变 图 形象化图形流水 图 多边形与扫描线示意 图 扫描线4的活动边 图 光栅化过程若干阶 图 光栅化生成位图掩码 图 阴影图示 图 改进后的场景阴影绘制流 图 光照信息打包.................................................................................................图 ........................................................................................................................33图 蜘 图 教 图 牛 图 本章方法（左）与光线方法（右）的绘制效果对比 图 本章方法（每组左图）与光线方法（每组右图）的绘制效果对比 图 面光源可见性判断方法效率瓶颈示意 图 直接.................................................................................................................图 网格.................................................................................................................图 像素ID（左）与三角面片ID（右）在网格中的分布密 图 光源视点相机的二维示意 图 线程间负载均 图 块内规约计算过 图 场景包围盒及网格细 图 阴影体构建示意 图 阴影体示意 图 阴影体缩小方法示意 图 背向像素剔 图 棋盘动态场景软阴影绘制效 图 花园动态场景软阴影绘制效 图 变形物体软阴影绘制效 图 改变场景中面光源位置与朝向时的阴影绘制效 图 逐渐增大面光源尺寸时的阴影绘制效 图 面光源至点光源时的阴影绘制效 图 不同面光源可见性采样率下的绘制效果对 图 帧率随面光源采样率增加时的变化趋势（与光线方法对比 图 不同面光源尺寸的绘制效 图 相同性能下本文方法（左）与光线方法（右）的绘制效果对 图 像素采样点在网格中的分布情况可视化结 图 典型多光源场 图 阴影图算法示意 图 多点光源可见性判断方法流程图（左：传统流程，右：改进流程 图 具有16个点光源的简单几何体场景绘制效 图 具有32个点光源的简单几何体场景绘制效 图 具有128个点光源的简单几何体场景绘制效 图 具有256个点光源的简单几何体场景绘制效 图 具有16个点光源的国际象棋场景绘制效 图 具有32个点光源的国际象棋场景绘制效 图 具有128个点光源的国际象棋场景绘制效 图 具有256个点光源的国际象棋场景绘制效 图 不同光源数量下书房场景绘制效 图 场景面片尺寸过小产生的走样现 表表 实验所用的测试模型片面 表 不同输出分辨率的绘制帧 表 不同面光源采样率的绘制帧 表 不同面光源尺寸的绘制帧 表 不同网格分辨率的绘制帧 表 相同质量下本文方法与光线方法的绘制性能对 表 相同性能下本文方法与光线方法的面光源采样率对 表 每个格子中像素采样点与三角面片分布情 表 有效三角面片与潜在三角面片的比例关 表 实验所用的测试模型片面 表 不同点光源数量下的绘制帧 1.1的选题背景及来1.1.1的选题背景与来GPU（GraphicsProcessingUnit，图形处GPU语言来编写在某个渲染阶段执行的算法，极大地增加了算法的灵活度。于此同时，以CUDA(ComputeUnifiedDeviceArchitecture，计算统一设备架构)为代GPU的通用并行计算架构的出现与兴起，更是突破了传统图形学算法中基于计的应用程序都开始利用GPU惊人的计算能力，这充分说明GPU计算已经发展到了引算界正在从GPU的处理方式向均衡分配的GPUCPU协同处理转变。所需的有力”。本的选题源自于国家自然科学基金——面向实时真绘制的非传统相机模型1.2的研究目标及意是高精度的判断会导致效率的下降。本文借助GPU强大的可编程图形流水线以及通用GPU可编综上，的研究目标主要有下述三点1.3的研究内CUDA软件光GPU渲染的基础上引入场景预采样，以降低和计算开销。该方法可用来绘制具有空间任意分1.4的组织结要研究内容；最后介绍了的组织结构。CUDA及OptiX等对本文算法的实现起到支撑作用的一些图1组织思路示意CUDA的软件光栅器的实现方法；其次，介绍如何利用该软件光栅器进行并光照可见性判断方法概缓存就可以实现，缺点是算法复杂度和物体几何复杂度成正比，而且会消耗GPU的填(例如衣服)会在物体褶皱的地方产生过于清晰的阴影而导致严重的失真。目前该算法主种场景和观察情况的反走样方法，其中深阴影贴图算法（DeepShadowMap）[5]、阴影图算法（ShadowMap）[6]以及平行分割阴影贴图算法（Parallel-SplitShadowMap）[7]等都可以极大地减少走样。光源空间阴影贴图[8]（LightSpaceShadowMap）：光源空间投梯形阴影贴图[9]（TrapezoidalShadowMap光线算精确光照可见性判断方有若干优秀的综述类文章对目前的精确光照可见性判断方法进行深入且易于理解的论述与总结。Eismnn[14]nft[15]3D2D的光源投模拟方法中的半影区域通常是经过对硬阴影进行过滤得到的[19,22,23]。比如，Fernando等人[24]以及mmadBagher等人[25]所方法对硬阴影的边缘进行了模阴影图来近似地估计遮挡体。Guennebaud等人[16]使用背向投影到光源成像面的阴影图后，背向投影所生成的软阴影被改进得更精确、快速[26]。Schwarz和Stamminger[27]近似的阴影中存在的缝隙，这将生成更加准确的遮挡体轮廓。Yang等人[28]引入了多张阴影可交互的绘制帧率。本文中所使用的方法虽然不是采用近似的遮挡体估算，但是与类精确算法的范畴。Whitted[30]文中光线算法了采样像素点与光源采样几乎所有三角形边均为轮廓边的情况。Forest等人[33]提出了深度复杂性Eisemann与Decoret[34]提出了一种计算两个矩形面片可见性的方法，可以被应用到体与阴影接受体进行区分，借以消除自阴影现象。Johnson等人[20]使用点光源和遮掩体此方法的难点在于如何稳定并高效地做边缘检测。与本文方法类似，Benthin和Wald[35]Sintorn等人[36]提出了一种无走样的阴影图方法，用于生成精确硬阴影，之后该方Map，无走样阴影图）中。AFSM是一个光源平面中的规则网格，网格中的每个格子都场景中的所有三角面片。然而，AFSM方法中构造的阴影投影体是近似的，将面光源近AFSM中固定数量的采样点（8个AFSM中最多的采样点数为63，那么将需要进行8遍（对63/8进行向上取整）绘制才能产生最终的结果。空间任意分布多点光源光照可见性判断立即辐射度算法（InstantRadiosity）[37]。立即辐射度算法（InstantRadiosity，最早由源位置，法向和能量。第二步基于光源，虚拟光源被当做普通的点光源向场景中Map）和光线算法（RayTracing）应用过来。对于基于阴影图的方法，可以在多点光源光照可见性判断问题的传统方法共有的问题是效率不高，实时应用的需求，因此很多研究提出了很多多点光源可见性判断问题的加速算法。目前绝些点渲染到不完整阴影图中，其间使用拉推（pull-push）操作解决漏光问题。最后，rendering微缓存由8x824x24个像素构成，保存距离每个像素最近的可见节点的深度和索引信BRDF重要性采样。因为点的选取是在预处理阶段，物体的拓扑不可以改变，所以这种]sblit光源切割[41]（Lightcuts：光源切割方法使用基于CPU的光线算法作为它的基点光源的集合。一个像素点到某一个结点的可见性也仅用一根测试光线进行判断，isibility拟面光源（VirtualAreaLight，简称VAL），然后使用一中利用软阴影图来生成软影的快式分布，所以该方法计算的可见性信息是很确的。Sampling可编程图形管线与语GPU的渲染流水线的主要任务是完成3D模型到图像的渲染工作。常用的图形学APIGPU中渲染流水GPU渲染流水线的不同阶段，需要处理的对象分别是顶点（ertex（Primitive（Fragment（Pixel21PI用简单的图元表示物体表面。2、顶点处理。这个阶段的任务主要是通过计算把三维顶（rtexShdr完成。输入的顶点数与输出的顶点数一一对应，各个顶点间的处理相互独立，可以并行完成。3、图元生成。根据应用程序定义的顶点拓扑逻辑，把上一阶段输出的顶点组装起来形、图元处理此段是可的，几（omeryShdr）理是由ixlShdr）完成，主要成图元的填色功能，计算每个片元的颜色及等属性。7、像素操作。本阶段包含裁剪测试、Alpha语言是用于编写VertexShader、GeometryShader以及PixelShader等程序所使用的编程语言目前主流的语言有Cg（CforGraphicsGLSL（OpenGLShadingLanguage、HLSL（HighLevelShadingLanguage。图 基于CUDA的通用并行计CUDANVIDIAGPU作为并行数据计算设备的软硬件体系。该架构通过利用GPU强大的计算能力，可大幅提升性能。现阶段，计算正在从CPU（处理）向CPU+GPU（协同处理）的方向发展。为CUDA，包括图像与处理、分子动力学仿真、计算生物学和化学、天文计算、流体力学模拟、CT图像再现、分析、石油勘测以及光线追踪等，且在很多应用中获得CUDA不需要借助图形学API，并采用比较容易掌握的类C语言进行开发。与以往的GPU相比，支持CUDAGPU在架构上有显著的改进，有两项改进使CUDA架构GPU通用计算。一是采用了统一处理架构，可以更加有效地利用过去分布y（Host（DeviceGPU运行GPU端的CUDA并行计算函数称为内核（Kernel一个完整的CUDA此为依据，进行线程的分配。CUDA的线程模型以线程网格（Grid）的形式进行组织，的线程则可以通过共享内存进行线程同步和通信。内核函数间则可以通过全局器进行数据的交换。线程的层次模型如图3所示。3在进行CUDA的程序设计时，需要充分了解其线程模型与层次结构，以进行GPU上进行单精度CUDA上还不能由内核单独GPU进行计算，因此需要考虑传输与访CUDA是不划算的。对于计算量较小的问题，由于与传输的时间开销可能远远超过计算的开销，所以性能上可能还不行计算前缀和算法（prefix-sum，scan、并行排序算法（radixsort）和并行归约算法序，流打包，建立树型数据结构以及区域求和算法等。CUDPPCUDA的GPU上。Optix实时光线引GPU的大规模并行处理能力非常适用于处理光线追踪。然而由于传统的光线算法高度的不规则性，使得挖掘GPU的原始计算能力成为关键。OptiX光线追踪引擎的问世，解决了上述的并提供了一套完整的基于GPU的光线开发框架，充分利用了当代及未来的图形硬件来实现基于光GPU上高速运行的光线追踪应用程序。与预定义外观、局限于特定数据结构的渲染器不同，OptiX引擎的通用性非常好，可加速各种情形中所OptiX光线追踪引擎利用英伟达CUDAGPU并行运算，并采用BVHK-D树算法的高级加速结构等技术，可在英伟达GPU上大幅提升光线追踪的速度，从而大幅提升应用程序的互动真度。凭借OptiX引擎，从前需要耗费数查真实场景中的光照、反射、折射以及阴影的效果。另外，OptiX引擎是一个灵活的光线追踪平台。OptiX引擎内的灵活度已经延伸至程序定义以及混合型渲染方法，开发可以利用这些方法来确保最精准的渲染结果以及实现真度与速度的平衡。此外，开发还可以通过采用引擎更新来发掘未来GPU的优势，从而保持最前沿的性能水OptiX本身并不是一个光线渲染器，而是一个可拓展的用于构建基于光线的应用的开发框架。OptiX引擎由两个部分组成：1）APIAPI用于定义光光线求交、求交反馈等。由这两个部分提供对光线应用的底层支持。开发者可以在此基础上应用这些底层的API来构建自己的渲染、碰撞、可见性检测等光线应用。OptiX引擎的由一个简单而强大的光线的抽象模型构成。这种开放式的编OptiX中的光线可以负载用户定义的属性变量，如颜色、递归深度、重要性等。开发者OptiXCUDA-C开发的函数完成对这些属性的操作。由于光线算法本身固有的递归性质，OptiX中也允许用户程序递归地产生新光线，并提供递归栈CUDA-C语言编写的程序段。OptiX中包含若干可编程的组件。这些程序可以在特定的地方被GPU调用以实现通用的光线算法。目前有个像素、自定义作业等完成计算任务。ClosestHit程序在光线找到其最近的相交几何体时被调用，主要用于的计算。AnyHit程序在光线找到了一个任意交点时被调用，Sbvh（Split-BVH、Bvh、TriangleKdTree（K-DTree）等。本章小CUDA的一些程序设计原则与常用算法库。对基于CUDA的OptiX光线引擎进行了介绍，第三 面光源像素级精确光照可见性判断方引场景为例，假设使用kxk个点光源对面光源进行模拟，输出图像的分辨率为wxh，场景由N个三角形建模，我们需要判kxk个点光源wxh个像素采样点之间的可见性。一种解决方案是光线，从每一个像素采样点追踪kxk条光线。每条光线需要与N个三角形做算方法，从wxh个像素采样点朝向面光源以kxk的分辨率渲染场景，对场景三角面片进行性。该方法利用了当代可编程GPU的强大的图形处理能力以及通用并行编程的一些方法基本原理概对于由三角形3-DS，一个四边形面光L0L1L2L3，一个给定的视点相机E及其成I0I1I2I3，本章光照可见4所示（该图为二维示意，面光源顶点L2L3，相机成像面顶点I2I3和三角形顶点B2未画出。图 方法原理示意储场景S中空间采样点P的世界空间坐标；点，以L0L1为成像平面；第四步：对采样点P的位图掩码表MP进行归约计算，得出采样点P对面光源的光照可见度（VP=LL0/L1L0，并到阴影纹理贴图Tv中。RenderSfrobtainimageForeachPinConstructcameraPL0L1witheyePandimageplaneForeachtriangleB0B1inRenderB0B1withPL0L1onvisibilitybitmaskEndComputevisibilityVpasthepercentageofunoccludedlightsamplesinStoreVpintovisibilitytextureEnd其中以PL0L1的构建及场景三角B0B1的光栅化为关键点。如图5所示，像5CUDA并行架构实现这一过程，并行地构建斜相机，计算基于CUDA的简易光栅器的实建模变视变投影变除视图变剪裁世界屏幕标准视空物体ransformation建模变视变投影变除视图变剪裁世界屏幕标准视空物体6有物体提供一个参考。3、视空间。在视空间（或眼空间）的坐标系统里，眼睛的标准化的设备坐标转换为使用像素度量x和y的最后的坐标系统。Frustum段和点，才有可能被被光栅化到一幅图像中。4、除法。用w除x，y和z能完成这（Culling7（AET）”8所示如扫4的“活动边表”P1P2P3P4两条边组成，而7的“活动边表”P1P2、P6P1、P5P6P4P5四条边组成。二、相邻的扫描线与,进关系△x=-b/a，是个常量，为直线斜率的倒数。图 △x＝-所交的最高扫描线。图9为扫描线4的活动边表。图 扫描线4的活动边CUDA上实现了一个简易的光栅器，该光栅器并行地这里使用32个无符号整型（unsignedint）数组来光栅器的采样信息（即像素32x321024级光照可见度，即表示最多可以使用1024个点光源来模拟面光源。GPUGPU的程序开发在调试阶段也比8x832x32之间。甚至，本章算法并不需要保存光栅化生成的片断的深度信息，从而该光栅器无需深度缓冲区。因此只需要在GPU上实现一个能够对三角面片进GPUGPU的分支预测能力远远不及CPU；二、简易代码的可性可以大大提高，无需动态的分配PPL0L1，计算模型视点投影变化矩阵。在空间10（a）所示。再以矩形面光源的四条边作为投影矩阵。最后将生成的两个矩阵相乘，得到该相机的完整的模型视点投影变换矩置个数对于位置总数的比率，就可以知道此三角面片遮挡住点光源的比例。考虑到CUDA中的资源有限且为了提高程序的执行效率，掩码表中的每个元素只用一个比特为32以下的无符号整型（unsignedint）数组就可以。变换矩阵对其进行空间变换，变换到采样点斜相机的裁剪空间（CullingSpace）下。再z分量的值（保存该顶点在空间中的深度信息）做一些三角面片的有效性判断：若三角 123123图

将每个顶点的标准化设备坐标放缩到[0，1]范围。从三角面片的三个顶点的x并截取到[01]范围内。最终可能被光栅化的区间将介于[x_Minx_Max]与[y_Miny_Max][0，1]范围内的有效部分（即三角面片3的左半部分）进行按照传统扫描线算法，在y_Miny_Max之间逐行进行扫描。每根扫描线都寄存器变量ix0，ix1，ix2中，若无交点，则返回NO_INTERSECTION（定义为单精度浮点数上限值ix0ix1<=ix2。如果最终ix2的值为NO_INTERSECTION，那么再将ix2赋值为ix1，这样可以保证ix0ix2为交点横坐标中的最大值。在该扫描线上，掩码表中介于ix0与ix2之间区域的比特均需要被置1。当然并不需要对此区域一位一位地进行置1的位运算操作，我们可以将其作为一个整体，地进行“或”位操作进行记录。如图10（e）所示，有三条扫描线在三角面片2的光栅化中起作用。余的片断操作，因此可以在一个CUDA线程中独立运行。这样我们可以在GPU上开大的算法复杂度为O(k2)。而本文的光栅化方法，可以同时对一条扫描线上的采样结果进行直接的计算，算法的复杂性下降到O(k)，在算法执行效率上有所提升。光照可见性的计算及使一遍场景绘制和一次延迟处理。在CUDA的运算中，并不可以直接的图形API中使用的缓冲区对象以及纹理资源，而是以的方式将图形API生成的阴影图纹理与CUDA中的资源句柄进行绑在CUDA函数中，对位图掩码表（图11所示是对一个16x16分辨率的位图掩码的一个可视化）1的元素个数（11中的白色区域面积。置1的元素个数与掩码表中总元素个数（图11总的面积）的比值即为该像11最后，将可见性信息拷贝到与阴影图纹理对应的cudaResource资源中，利用其与阴影线中使用该阴影纹理贴图。一个阴影图的示例如图12所示。

图 阴影图示PhongMRT（多渲染对象，MultipleRenderingTargets）技术与延迟技术，减少一遍场景绘制。Phong光照模型中，一个物体的表面颜色是放射（emissive（ambientsurfaceColoremissiveambientdiffuse 固定的颜色，但是其强弱也受到全局环境光照的影响，可以用公式diffuseKdlightColor

L,项可以specularKslightColorfacingmaxNH,0shininess表示，其中Ks是材质的镜面反射系数，shininess表示物体表面的光泽度，光泽度越大，物体的镜面反射能力超强，HV（指向视点的规范化向量）L的中间向量的规范化向量，facing1如果NL的值大于零，否则取0。延迟是一种对3-D场景进行后期照明的技术。思路是：首先，将3-D场景的几采样点信息阶段。从视点绘制一遍场景Phong光照模型计算每个像的思想则可以减少一遍场景绘制的开销。改进后的算法的流程（图13）如下：场景信息阶段Phong光照需要的一些信息输出到COLOR2颜色通道中。断的空间法线N、规范化的指向光源的向量L、指向视点的规范化向量V。这三者均为矢量，如果每张float4类型的浮点纹理保存一个矢量，那么总共就需要3张浮点纹理分别+13+的float3类型的浮点纹理中（如图14所示。被保存的光照信息分别在lightingInfo的浮点纹理的R、G、B三个分量中，内容包括三个部分：（a）lightingInfoRPhong光照模型漫反射项中标量部分maxNL0facingmaxNH0shininess计算（c）lightingInfoB分量保存菲涅耳（fresnel）分量。观察者的视线方向与被观fresnelr1r1VN)5进行计算。其中，r是与物体材质相关的一个常数，在实验中，取值0.1。R：漫反 G：镜面反 B：菲涅尔因 光照信息纹图 光照信息打diffuseKdspecularKslightingKadiffuse*visibility*colorspecular*lightColor

硬件平台环境为：PC平台 Core(TM)i7-4770K3.50GHzCPU，16G内存NVIDIAGeForceGTX780软件平台及开发环境为：Windows7操作系统，编译环境为VisualStudioSDKVersion3.0.0Beta1，Shader程序使用ShaderModel3.0。 表 龙图 蜘图 教 图 牛与光线方法的效果对视点、相同面光源参数（32x322）的情况下，分别对与蜘蛛场景进行阴影绘制。如图19、图20所示，分别是使用了本文算法的绘制结果（图19左侧图、图20两组图的左侧图与使用了光线的算法（图图 图 本章小CUDA的软件光栅器的实现方面，先对传统的光栅绘制流水线进行CUDA的三角面片光栅化方法，实现了一个可以并行地在GPU上运行的轻量级软件光栅器。合像素采样点的光照可见度，使用延迟与MRT技术，在传统的阴影绘制流程的基 第四 面光源光照可见性判断方法的效率优引的视景体真正进入光栅化21无需对三角面片B10B11B20B2121效地减少算法的开销，并使得光照可见性的判断具有高效性。方法基本原理概2223一种简单的方法是直接，如图22所示。然而如果要直接对其进行实现，将会耗用极大的空间。假设输出的采样的像素数为NP，场景中三角面片总数为NT。极均生成一个三角面片ID的列表，即像素采样点与三角面片进行直接，那么数据规NP*NT*4ByteID可以唯一表示一个三角面片在其三角面片数组空间连续性，相邻的像素到的三角面片ID列表之间存在很大的冗余，所以本章使到二维网格，如图23所示。然后再建立网格与三角面片的关系。这样就可以将采样点与三角面片之间的关系利用网格进行桥接，大幅降低开销。在实践中，本方法可以减少2到3个数量级的空间开销。第一步：构建光源视点相机。从面光源构建相机C，以二维网格G作为成像平面；第二步：计算二维网格区域。使用相机C对像素采样点进行投影，计算投影的二维G，同时计算每个网格中像素采样点的最大深度；第四步：组织场景中的三角面片。对场景S中的每一个三角面片T，首先构建三角TVCVG中所覆盖的所有格子，并将三角面片T赋给这些格子。ConstructcameraCwithgridGasimageForeachpixelsampleProjectPwithCtoobtainEndComputeAABBboundingboxbbofallP’,thendeterminetheareaofForeachFindgridcellgcP’AssignPtoUpdatemaxdepthdofEndForeachtriangleTinConstructshadowvolumeVofProjectVwithCtoobtainAssignTtoallthecellsofGthataretouchedbyEnd到网格空间中，找到该像素点对应的网格ID，再以此网格ID为索引，找到影响此网格的三角面片ID的列表。 图 构建光源视点相CPiLi25所示。相机C的构建采用以下两个步骤：建立场景像素采样点与面光源四个顶点的三维AABB包围盒，如图25中OLmC，由此确定相机的位置。为了保证当面光源缩小成为一个点光源的时候，相机位置与点光源位置重合，使算法自然收敛成为渲染硬阴影的非传统最后，利用该相机的参数计算模型视点变换矩阵MV和模型视点投影变换矩阵MVP。图 计算二维网格区格上的像素采样点而言，可以有效地减少无需被光栅化的三角面片顶点坐标的。在GPU硬件架构中，对于全局器的延迟相对于其在相同时间内可提供的计算能19个单位的时间才1负载1负载955图 线程间负载均955CUDAAABB包围盒并行计算方法的基本原理是应用成规模较小的相同问题，分而治之。在对大量小问题的处理中，可以充分发挥出GPU全局分配及内核函数中的线程分配。在显存中开辟四块全局线性空间，每个空间的大小为输出像素分组中像素点的数目，用于每个分组AABB256。再为每个分组申请一个线程块对该分组进行处理，并为分量。在第一次执行时，这四块共享内存将被其对应的线程初始化为各个像素采样的对数0号地址里。最后，我们再将27G为步骤（2）256并且小于等于1为止：G。先从全局内存中号地址中的该分组的包围盒结果回存入全局空间中。CUDA素个数1,000,000）的场景，对整个场景AABB包围盒的计算可以保证在1.5毫秒内完成。最终构造的包围盒示例如图28中粗白色方框所示。图 组织场景像素采数量，降低GPU开销，减少三角面片光栅化阶段的耗时。将二维AABB包围28中细为了每个网格像素采样点的数目以及最大深度，需要在CUDA的全局内存中分配两块线性空间，一个无符号整型（unsignedint）数组和一个浮点型（float）数为256），那么一个线程块就可以完成16x16分辨率的子像素块的处理。总的线程块数目512x512的场景，总共就需要分配分辨率为（512x512）/（16x16）=32x32的二维线程块，合计1024个线程块。为每个像素采样点分配一个线程，根据线程块ID以及块内线程ID可以唯一到标记为一个特殊常数值INVALID_CELL_ID，表明该像素对应的是一个的网格ID。阵MVP对其做坐标变换。然后，将投影坐标转换到网格坐标空间中，找到该像素点所在网格的网格ID。最后，对该网格对应的像素采样点计数器执行累加操作，并更新该网格中所的最大深度值。这两个操作均需要保证原子性，因为计数器累加操作和深度的更新操作是并行执行的，需要原子性保证结果的正确性，CUDA中提供的原子操作函数可以完成这个目的。了每个网格像素采样点数目的数组用作之后网格利用率和性能评估使用，了网格中像素采样点最大深度的数组留作下一节组织场景三角面片组织场景中的三角面的。该过程使用CUDA进行并行计算，三角面片与网格关系的建立过程简要统计三角面片ID与网格ID对的总数用于分配三角面片ID与网格ID对所需的线性数组的大小。使用求前缀和方法也可以知道每个三角面片的遮挡网格集合性二元组的形式三角面片与网格关系；然后，将后的线性以网格ID为出每个网格ID在该线性空间中第一次出现的地址。这样便可以根据任意给定的网格ID索引到其在全局线性空间中的起始地址，该起始地址与其相邻的下一个网格ID的起始地址之间的元素，即是与该网格所关联的所有三角面片的ID。2929B0，B1，B2变换到光源的视空间中，从光源视空间中的面光源坐标的四个顶点L0，L1，L2，L3产生12个交点，这12个点可以组成四个三角形（可以认为是原三角形经过面光源四个角形的三个顶点在远平面上的小孔成像AABB29右中Q0Q1Q2Q3表示此二维包围盒。如图30红域所示。这个3-D阴影体可以由该四边形棱台的四个侧面，及原三角形图 阴影体示意形ID-网格ID关系对所占用的空间会更大对三角形的光栅化操作也会更耗用计算资图31所示，灰域是将连线延长到相机远平面时得到的阴影体，这个阴影体必然不会漏掉任何被三角面片遮挡的像素采样点，但这个阴影体过于保守，它覆盖了过多的网格。在组织场景像素采样点时已经计算得到每个网格中像素采样点的最大深度，可以先后再次做光源顶点与三角面片顶点连线的延长操作，而这一次只需要延长到z_Max即可，这样得到的3-D阴影体如图31中红域所示。这个阴影体同样是保守的，但是绝大多数情况下要比灰色阴影体的体积小得多，对阴影体投影之后覆盖的网格数也少得多。如图31所示，灰色阴影体覆盖网格G0G1，但是红色阴影体只覆盖了G1。图 ID与网格ID关系对的总数nPairs，也无法确定这些关系对所需要的空间大小因为GPU根据nPairs的大小在GPU全局器中分配两个线性空间，用于保存（三角IDID）二元组。启动内核，再一次为每个三角面片分配一个线程，从上一面片ID，网格ID）于全局线性数组中。基数排序（RadixSort）是一种分布式的整数排序算法，因此也易于在CUDA的多线程编程环境中实现。基数排序又称桶排序（BucketSort或BinSort。其原理是将整数时间复杂度为Onlogrm，其中r为所采取的基数，而m为堆数。cudpp算法库中提供的基数排序算法对关系对（ID，网格ID）以网格ID为关键字进行排序。经过排序之后的二元组数组的特征是，相同网格ID的二元组就将彼此邻近，这样可以快速地找到同一网格下的所有三角形ID。下一步需CUDA的多线程计算能力，并行加速这一其它加速策32中白色像素区域所示。因此，可以在绘制流程中的采样点信息阶段的Cg程序里进行法线判断，若该像素的法线背离光源，则直接将其输出图 背向像素剔由于本文网格加速结构动态构建，因此该方法支持动态场景。图33展示的是在国34展示的是在花园动态场景中捕获的若干帧，在这个场景中，树木是随着风吹图 图 35展示的是在一个变形物体的场景中，当模型的高度逐渐变小时的绘制效果对高度 高度 高度图 36本方法对动态面光源场景的绘制效果如图36、图37及图示。其中包括了动态图36展示的是当面光源的位置、朝向及距离场景中物体的远近发生变化时，从阴影的柔和程度也会随着面光源的靠近而发生变化。图37所示的是当面光源的尺寸逐渐 面光源直径 面光源直径 面光源直径图 图 样率（掩码表分辨率）为16x16、网格分辨率为128x128、面光源尺寸为2。算法性能对于有很多轮廓边缘的场景来说（比如，与输出图像的分辨率最为相关。随着输出39所示。当可见性采辨率上升到8x8的，可以得到较好的效果；当分辨率达到16x16的时候，可以得到较为表 龙(a) (b)(c) (d)图 分辨率均为512x512、网格分辨率为128x128、面光源尺寸为2。当为每个像素采样点光3龙6050403020象花100与光线方法对比，图40给出三个测试场景随面光源采样率增加时绘制效率的6050403020象花100图 率为512x512、网格分辨率为128x128、面光源采样率为16x16。绘制出来的龙模型阴影在不同面光源尺寸下的效果如图41所示。表 12345龙(a)面光源直径 (b)面光源直径(c)面光源直径 (d)面光源直径图 辨率为512x512、面光源采样率为16x16、面光源尺寸为2。越低的网格分辨率导致每个性能下滑。由实验的数据可知，当网格的分辨率为128x128时，整体性能最好。表 龙与光线方法的性能对如表6中提供的数据所示，本文方法对比光线方法在相同绘制质量，即相同面光源采样率的情况下，绘制效率上得到了1025倍的提升。这只是对于静态场景的光致，与此相反，光线算法则需要对第一帧重建其加速结构，因此与本方法相比在性的方法（图42右侧图）在相同性能下的绘制结果对比。通过对比发现，光线方不足导致的走样现象（场景最为显著。表7给出两种方法在相同性能下针对不同表 30.51.701.2929.82.912.5236.23.723.05龙38.74.012.9626.51.070.9575.65.333.5421.41.981.65图 表 32x32=32x32=32x32=龙32x32=16x16=16x16=16x16=从每个像素点所关联的遮挡三角面片数量的角度，本节对网格的性能进行分析。表8中给出每个格子中所关联的最大与平均像素点个数。其中网格的分辨率为CUDA里独立运行的线程对像素点进行处理，并不涉及对场景的多遍绘制，表 龙图 效关联，这些三角面片均需要被光栅化，那么算法的整体效率将最大化。表9中数据显也就是说，不超过33%的三角面片是被送入到光栅器中且真正被光栅化的，而其它的将9龙本章小使用CUDA进行并行加速，对关键实现细节进行了介绍。在CUDA中进行实现，可以有效发挥出图形硬件的并行处理能力。此外加入了一与光线方法在效率上进行了对比，相比光线方法可以达到10到28倍的加速。第五 空间任意分布多点光源光照可见性判断方引44所示。这两44图[38]（ImperfectShadowMapISM、微渲染[39]（Micro-rendering）和隐式可见性[40]（ImplicitVisibility）等；另一类是基于光源近似的方法，把具有相似特性（位置、（ightcut]disibility]trixoolumnSpig）等。无论哪一类方法，都引入了很大的计算误差，不能解决光照可见性的准设计并实现一种在准确度和效率上有均衡表现的空间任意分布多点光源光照可见性判方法基本原理概阴影阴影阴影阴影图 阴影图算法示意阴影图算法基本原理如图45间像素采样点相对所有点光源的光照可见性。本章问题与图45示意不同，每个光本章使用立方体阴影图（CubeShadowMap）解决，从点光源出发朝六个方向构建六张阴影图，六张阴影图无缝缝合在一起记录了360度方向上全部的深度信息。GPU显存容量有限，辨率为512x512，每个像素用一个浮点型（float）深度，那么需要生成128张立方体阴影图，总共就是128x6=768张二维图像，需耗费768x512x512x4=805MB的空间。而且目前GPU对纹理资源有较大的限制，在主流GPU上只能同时挂载几个到十几任意时刻只需要一张立方体阴影图就足够了，减少开销。别是光源视点相机采样和眼睛视点相机采样128渲染至少256遍，而原来只需要至少128遍。针对这个问题，本章方法借助延迟渲染的思想，在每个执行单位内只做一次场景渲染和一次屏幕空间像素点比较操作。多点光源光照可见性判断方法直接从经典阴影图方法迁移过来用于判断多点光源光照可见性的方法流程如图GPU显存上；然后从眼睛视点渲染场景，对每一个会输出到屏幕的采样点，循环地程存在弊端，由于所有的阴影体需要同时在GPU显存，会造成极大的开销开开是否是否结初始化开初始化光源是否结GPU图 SMiGPUSMi判断像素采样点与光源Li之间的可见性，这一步骤完成之后阴影图SMi就不再需要，可以直接释放掉作为一个执行单位，减少同时GPU的阴影图数量。在这个处理流程中，需要GPU帧缓冲的混合模式设置为累加模式，将像素采样点对于每个点光源的可见性累场景预采样的引46中有128个点光源，左边的传统流程只需要对场景渲染128遍得到128张立方体阴影图将采样得到的像素点世界空间三维坐标在一张float3类型的二维纹理中，然后将该从眼睛视点渲染场景，进行预采样。配置一个G-缓冲（G-Buffer，一种用于延迟渲染的渲染缓冲对象G-缓冲有四个绑定点，分别绑定采样点视空间三维坐标GPUMRT（多渲染输出，MultipleRenderingTargets）技术，绑定在GPU的纹理句柄TEXTURE0，把前面得到的立方体阴影图帮顶到纹理句柄dz’dP相对此每个像素对应采样点可以看到的点光源的数目。可见性信息，在纹理tex_visibleLightNumber中。首先把步骤（1）得到的采样点视纹理都绑定到GPU纹理句柄，然后启动GPU，在器中可见性信息，根据可见性实验效实验硬件平台环境为：PC平台，InCore(TM)i7-4770K3.50GHzCPU，16G内存NVIDIAGeForceGTX780实验软件平台及开发环境为：Windows7操作系统，编译环境为VisualStudio2010SP1，OpenGL3.0API，Shader程序使用ShaderModel3.0。光源数量为、、和256时的渲染效果，输出和绘制过程中使用的阴影图

表 图47至图50中给出在简单几何体模型场景中，在不同光源数量的情况下，使用本、、 图 具有16个点光源的简单几何体场景绘制效图 具有32个点光源的简单几何体场景绘制效49128502565154在是国际象棋场景中，光源数量分别为、、和256时，使用本章光照可见性判断方法绘制得到的阴影效果。同样地，每组中右侧是像素采样点得到真实的明暗变化效果，从而得到较为真的渲染结果。图 具有16个点光源的国际象棋场景绘制效52325312854256使用本章方法，对具有不同数量点光源的书房场景进行渲染，得到的效果如图55 (a)16个彩色点光 (b)32个彩色点光(c)128个彩色点光 (d)256个彩色点光图 输出分辨率均为512x512，点光源阴影图的分辨率也均为512x512。11本章小结论与展研究内容总方法扩展到三任意分布的大量点光源可见性判断方法上。基于经典的多边形填充算法中的扫描线算法，本文设计并实现了一个基于行与计算，并且可以动态地进行，支持具有变形物体和动态面光源的场景。在的问题，提出了一种改进流程，降低了GPU显存的消耗，使算法可以支持具有大量未来工作展本32x32，虽然在绘制效果上看，已经可以产生较为理想的效果，然而它对场景中的面56所示，场景面片过小导致产生的面光源采样率56参考文FranklinC.C..Shadowalgorithmsforcomputergraphics[J].ComputerGraphics,V11(2):242-WilliamsL..Castingcurvedshadowsoncurvedsurfaces[J].ComputerGraphics,V12(3):270-HartE.,GosselinD.,IsidoroJ..VertexshadingwithDireet3DandProeeedingsofGameDevelopersConference.SanJose,Califomia,USA:[s.n.],HeidmannT..Realshadows,realtime[J].IrisUniverse,1991,18:23-LokovicT.,VeachE..Deepshadowmaps[C].Proceedingsofthe27thannualconferenceonComputergraphicsandinteractivetechniques.ACMPress/Addison-WesleyPublishingCo.,2000:385-392StammingerM.,DrettakisG..shadowmaps[J].ACMTransactionsonGraphics(TOG),2002,V21(3):557-562ZhangFan,SunHanqiu,XuLeilei,etal.Parallel-splitshadowmapsforlarge-scalevirtualenvironments[C].Proceedingsofthe2006ACMinternationalconferenceonVirtualrealitycontinuumanditsapplications.ACM,2006:311-318WimmerM.,ScherzerD.,PurgathoferW..LightSpaceShadowMaps[C].ProceedingsoftheFifteenthEurographicsconferenceonRenderingTechniques.EurographicsAssociation,2004:143-MartinT.,TanT.S..Anti-aliasingandContinuitywithTrapezoidalShadowRenderingtechniques,2004,2004:DonnellyW.,LauritzenA..Varianceshadowmaps[C].Proceedingsofthe2006symposiumonInteractive3Dgraphicsandgames.ACM,2006:161-165WaldI.,SlusallekP.,BenthinC..InteractiveDistributedRayTracingofHighlyComplexModels[M].SpringerVienna,2001:277-288PurcellT.J.,BuckI.,WilliamR.M.,etal.Raytracingonprogrammablegraphicshardware[J].ACMTransactionsonGraphics(TOG).ACM,2002,V21(3):703-712SenP.,CammaranoM.,HanrahanP..Shadowsilhouettemaps[J].ACMTransactionsonGraphics(TOG).ACM,2003,V22(3):521-526EisemannE.,AssarssonU.,SchwarzM.,etal.CastingShadowsinRealSIGGRAPHAsia2009course,2009:HasenfratzJ.M.,LapierreM.,HolzschuchN.,etal.ASurveyofReal-timeSoftShadowsAlgorithms[J].ComputerGraphicsForum,2003,V22(4):753-774GuennebaudG.,BartheL.,PaulinM..Real-timeSoftShadowMapbyBackprojection[C].Proceedingsofthe17thEurographicsconferenceonRenderingTechniques.EurographicsAssociation,2006:227-234YangB.G.,DongZ.,FengJ.Q.,etal.VarianceSoftShadowMap[J].ComputerGraphicsForum,2010,V29(7):2127-2134ShenL.,GuennebaudG.,YangB.G.,etal.PredictedVirtualSoftShadowMapswithHighQualityFiltering[J].ComputerGraphicsForum,2011,V30(2):493-502MollerT.A.,AssarssonU..ApproximateSoftShadowsonArbitrarySurfacesusingPenumbraWedges[C].Proceedingsofthe13thEurographicsworkshoponRendering.EurographicsAssociation,2002:297-JohnsonG.S.,HuntW.A.,HuxA.,etal.SoftIrregularShadowMap:Fast,High-Quality,andRobustSoftShadows[C].Proceedingsofthe2009symposiumonInteractive3Dgraphicsandgames.ACM,2009:57-66ForestV.,BartheL.,GuennebaudG.,etal.SoftTexturedShadowVolume[J].ComputerGraphicsForum,2009,V28(4):1111-1120BrabecS.,SeidelH.P..SingleSampleSoftShadowsUsingDepthMaps[C].GraphicsInterface.2002,2002:219-228ArvoJ.,HirvikorpiM.,TyystjrviJ..ApproximateSoftShadowswithanImage-SpaceFlood-FillAlgorithm[J].ComputerGraphicsForum,2004,V23(3):271-280FernandoR..Percentage-closersoftshadows[C].ACMSIGGRAPH2005ACM,2005:mmadBagherM.,KautzJ.,HolzschuchN.,etal.Screen-spacePercentage-CloserSoftShadows[C].ACMSIGGRAPH2010Posters.ACM,2010:133GuennebaudG.,BartheL.,PaulinM..High-QualityAdaptiveSoftShadowMapComputerGraphicsForum,2007,V26(3):525- MapEurographics2008AnnextotheConferenceProceedings(ShortPapers).2008:295-YangB.G.,FengJ.Q.,GuennebaudG.,etal.Packet-basedHierarchalSoftShadowMap[J].ComputerGraphicsForum,2009,V28(4):1121-1130SchwarzM.,StammingerM..BitmaskSoftShadows[J].ComputerGraphicsForum,2007,V26(3):515-524WhittedT..AnImprovedIlluminationModelforShadedDisplay[C].ACMSIGGRAPH2005Courses.ACM,2005:4LaineS.,AilaT..HierarchicalPenumbraCasting[J].ComputerGraphicsForum,V24(3):313-LaineS.,AilaT.,AssarssonU.,etal.SoftShadowVolumesforRayTracing[J].ACMTransactionsonGraphics(TOG),2005,V24(3):1156-1165ForestV.,Bart