大规模场景的百分比近邻软阴影绘制算法

袁昱纬，刘传辉，全吉成，，王宏伟，刘 宇

（1.海军航空工程学院电子信息工程系，山东烟台264001；2.空军航空大学航空航天情报系，长春130022）

大规模场景的百分比近邻软阴影绘制算法

袁昱纬1，刘传辉1，全吉成1，2，王宏伟2，刘 宇2

（1.海军航空工程学院电子信息工程系，山东烟台264001；2.空军航空大学航空航天情报系，长春130022）

针对传统软阴影绘制算法在面对大规模三维场景时绘制效率较低的问题，文章基于四叉树加速结构的阴影图构建，研究了邻域节点的搜索方法和遍历顺序的选择方法，提出了一种基于四叉树的百分比近邻软阴影算法。实验结果表明，与传统算法相比，该方法能够有效提高大规模三维场景的软阴影绘制效率，且性能稳定，可以渲染出高质量的软阴影效果。

三维场景；软阴影；百分比近邻滤波；四叉树；邻域搜索

阴影的计算和绘制是虚拟三维场景绘制中不可或缺的重要组成部分[1]。对于仅存在点光源的理想场景而言，采样点仅存在位于阴影中和阴影外2种情况，这种阴影称为硬阴影，不存在柔和的半影区。但是在三维场景的渲染中，为了提高场景的真实感，还需要绘制出面光源或体光源产生的半影效果，这种效果称为软阴影。软阴影虽然更加复杂，但是可以产生柔和的过渡效果，渲染阴影的真实感更强[2]。

常用的阴影绘制算法包括阴影图算法[3-5]、阴影体算法[6-7]、光线跟踪算法[8-9]和光子映射算法[10]等，这些算法并不能直接绘制出高质量的软阴影，一般需要采用与滤波运算结合的方法，不对半影区的范围进行精确计算，仅在符合视觉规律的前提下，采用滤波算法消除锯齿状走样和清晰的边界。基于滤波的软阴影算法主要包括百分比近邻软阴影算法[11]、时刻阴影图[12]，基于层次的滤波预测阴影图[13]、可分离软阴影图[14]，以及基于遮挡区域映射的软阴影[15]等方法，但是当三维场景由大量几何数据构成时，其中几何体包含上万甚至几百万个以上的多边形[16]，即面对大规模三维场景时，由于基于阴影图的算法计算量很大，使这些方法的软阴影计算速度往往无法满足实时性要求。本文针对大规模三维场景，通过为阴影图构建空间加速结构，研究相应的搜索、遍历方法和滤波运算，提出改进的百分比近邻软阴影算法，加快软阴影计算速度，提高大规模三维场景的软阴影绘制效率和质量。

1 百分比近邻软阴影算法及其存在的问题

百分比近邻软阴影（Percentage Closer Soft Shadow，PCSS）算法是基于百分比近邻滤波（Percentage Closer Filtering，PCF）提出的。该算法在传统阴影图算法中采用PCF滤波运算，能根据场景光源和几何体的相对关系产生柔和的半影区域，软阴影质量较高。PCSS算法无须构建多个阴影图，无须对阴影图进行除滤波之外的处理，具有阴影图算法的一般优点[17]，工程实现较简单。

但是当面对大规模三维场景时，PCSS算法就会出现一些不足之处，主要包括：①滤波运算效率较低。因为在大规模三维场景的阴影绘制时，为避免出现走样和锯齿现象，有时需要较大的半影区域，随着半影区的增大，所需的滤波器尺寸增大，滤波的时间开销也随着增加；②受邻域搜索算法效率的限制。大规模三维场景的阴影图分辨率很高，占用的存储空间较大，而滤波运算涉及阴影图中大量采样点的邻域搜索，在庞大的线性存储空间中进行邻域查询的效率通常很低。

针对上述缺陷，本文基于四叉树空间加速结构，提高了滤波运算效率和邻域搜索效率，改进了PCSS软阴影绘制算法，加快了大规模场景的软阴影绘制速度。

2 基于四叉树的阴影图搜索加速结构

大规模三维场景的阴影图的数据量一般很大，包含的采样点很多，在处理与搜索的过程中速度较慢，且加载到内存的时间较长。因此，本文在进行软阴影计算前，基于四叉树结构对三维场景的阴影图建立空间加速结构，形成金字塔状的多分辨率结构，当需要不同分辨率的阴影信息时，可以快速地从加速结构中提取。同时，这种预构建的多分辨率结构可以大幅度减少邻域搜索的计算量。

基于四叉树的阴影图搜索加速结构的构建过程为：将原始的阴影图均匀分块后作为四叉树的叶子节点，分块的大小一般为512×512或256×256个采样点。然后，依次遍历相邻的2×2个分块，对这4个分块拼接后重采样，使其分辨率降低一半，作为四叉树的上一级节点。继续这样操作下去，直至四叉树的根节点，完成基于四叉树的阴影图搜索加速结构的构建。四叉树中的各层分别对应不同分辨率的阴影图，从四叉树的底层到顶层，分辨率越来越低。

3 基于四叉树的PCSS改进算法

3.1 四叉树结构的邻域搜索

在四叉树结构中进行PCF操作时，涉及大量阴影图分块的邻域搜索操作，由于每次PCF滤波操作仅在四叉树中的某一层级进行，且滤波所需的深度值分布在其中心的一个小区域，阴影图分块与其邻域分块在大部分情况下都共用了同一个父节点，每一次邻域搜索不必从根节点开始，只须回溯到2节点分开的父节点，可以有效减少邻域搜索的计算量。如图1所示，当节点1进行PCF滤波计算时，节点2与其共用同一个父节点，仅须回溯一个层级即可。节点3与节点1，虽然不是同一父节点下的兄弟节点，但大部分搜索路径相同，无须重复搜索，仅须要向上回溯2个层级即可。

3.2 邻域节点的遍历顺序选择

在滤波器的滑动和运算过程中，通常需要同时访问若干个节点。根据四叉树的邻域搜索方法，每次相邻节点的访问仅须回溯到其遍历路径分叉的层级，提高节点邻域搜索时的计算效率。

基于上述思想，本文通过选择须要回溯最少层级数的遍历顺序，实现减少在回溯过程中的搜索次数。如图2所示，图中的实线和虚线分别表示从一个节点到另一个节点存在2条可能的路径。

在采用图2中2条路径进行遍历时，须要回溯到的最高层级分别为Li或Lj。

遍历时，可以访问Li1次、Lj2次，或访问Li1次、Lj2次。为了缩短回溯路径的长度，减少回溯操作的次数，在选择遍历顺序时，尽量让更高的层级只回溯到一次，如图2中的虚线路径。对于某些尺寸滤波器，邻域搜索可能存在较多遍历顺序选择，可以采用预先计算的最优搜索顺序表。遍历时，仅须在表中进行简单查找，即可获得当前所需的遍历顺序，减少路径选择时的重复计算和判断。

在搜索的过程中，仅须要存储回溯到的层级的路径，没必要使用一个堆栈来完整存储整个四叉树的节点，减少内存空间。

3.3 PCF滤波器的滤波操作优化

在采用PCSS算法进行软阴影绘制之前，须要选择合适的滤波器尺寸。首先将屏幕空间的像素投影变换到三维场景空间中，计算屏幕中每个像素在三维场景空间中对应区域的大小。滤波器的尺寸应当比该区域略大，以保证足够的半影区域，并防止出现明显的走样现象。

当使用滤波器进行滤波运算时，一般最多同时访问4个节点。当滤波器须要同时访问多个节点时，为了提高滤波计算效率，本文为每个访问到的节点对应的阴影图深度值产生一个模板，以快速清除在滤波范围之外的深度值，如图3所示。

PCF滤波器和访问的节点都将模板与对应的阴影图按位与运算后，可以快速滤波范围内的深度值，统计阴影图中非0的深度值并与采样点的深度值进行比较，按照PCF算法得到位于阴影中的采样点占滤波器总采样点的百分比，获得滤波后采样点的阴影值，即为PCF滤波运算的结果。

忽听一人道：“大哥，既然说到公事，现在公事未完，怎可你先来？还是大哥殿后，我先来。”只见摄魂寅客李双岱抢步上前，迅速来到牌坊下，亮出兵器。让秦铁崖诧异的是，李双岱所使的却不是佩刀。

3.4 基于四叉树的PCSS软阴影改进算法

为了保证绘制软阴影效果，通常采用滤波器进行滤波操作。但是，大规模三维场景的阴影图分辨率很高，如果以同一个分辨率的阴影图来进行滤波操作，那么在距离视点较远的区域就需要一个较大的滤波器内核，以确保阴影具有足够大的半影区，保证软阴影的绘制效果。但是滤波器内核的增大，必然导致滤波器在滤波过程中运算规模的增大。为了避免过大的运算规模，同时保证软阴影质量，本文对基于四叉树的PCSS软阴影绘制算法进一步优化。

本文考虑在四叉树完成构建后，自下而上地处理最低层级至某个层级中每个阴影轮廓上的节点，以该节点为中心，按照PCF滤波器原理，计算该节点的阴影占有率，并存储在节点中，这个阴影占有率的计算过程在四叉树中自下而上地进行，相当于滤波的过程。上述操作在阴影绘制之前完成。

当进行滤波时，只须在四叉树中找到对应节点并获得其中的阴影占有率值，即可停止搜索，该阴影占有率就相当于滤波后的阴影值。如果需要大尺寸滤波器的滤波效果，仅须对这些节点中的阴影占有率值使用小尺寸滤波器进行滤波，不须要在原始分辨率下进行PCF滤波，而是在加速结构的某一级对节点保存的阴影占有率值进行滤波计算，以获得大尺寸滤波器滤波的效果。滤波的加速结构层级越高，获得的半影区范围越大，阴影效果越柔和。

4 实验与分析

本文实验平台的软硬件环境为：CPU Intel Core i7-67003.4GHz，RAM 32GB，NVIDIA GTX 1070，Win⁃dows 7 Ultimate x64操作系统。实验素材为Chalmers大学提供的2个大规模三维场景，Closed Citadel场景和Villa场景，如图4所示。上述2个实验场景分别包含6.14×105和8.89×104个三角形面，以及3.10×106和5.01×104个顶点。实验的对比算法包括不同尺寸滤波器下的本文改进PCSS算法，以及不同层级数量的级联阴影图算法（CSM）[18]。对比实验包括阴影计算效率和软阴影绘制质量2个方面。在实验前已完成了本文提出的基于四叉树的阴影图遍历加速结构的构建，实验时不重新构建，绘制时仅须对加速结构进行搜索和遍历。

4.1 阴影计算效率测试

在阴影计算效率测试中，本文以Closed Citadel场景为例，测试了本文提出的PCSS算法在优化前后的时间开销，包含本文提出的改进PCSS算法在3×3滤波器和7×7滤波器滤波时的情况，以及相应算法在改进前的情况，如图5所示。实验时，视角飞过三维场景上方，记录每种方法在每一帧所需的阴影计算时间。图中横坐标为在场景中连续变化的视角对应的连续的每一帧，纵坐标为时间开销。

图5可以看出，在3×3滤波器下的时间开销平均缩短55.1%，在7×7滤波器下的时间开销平均缩短42.9%，本文改进的PCSS算法的时间开销明显优于改进前，且相对稳定。其原因是当计算距离视点较远的场景区域时，滤波运算在叶子节点层的邻域搜索涉及的节点较多，改进前的算法需要在节点之间反复回溯。而采用改进后的PCSS算法之后，可以在加速结构的较高层级停止搜索，无须每次计算都到达叶子节点层，减少了运算量。

在与其他算法的对比实验中，包含本文提出的改进PCSS算法在3×3滤波器和7×7滤波器滤波时的情况，以及采用4级CSM算法和8级CSM算法的情况，CSM算法在绘制软阴影时，采用3×3的PCF滤波。对于CSM算法，本文对其视域进行分割时，采用文献[16]中均匀分割和对数分割相结合的方法，并应用于各个实验场景中。

实验时，视角飞过三维场景上方，记录每种方法在每一帧所需的阴影计算时间。如图6、7所示，图中横坐标为在场景中连续变化的视角对应的连续的每一帧，纵坐标为时间开销。

此外，从图6、7的统计数据还可以看出，本文算法在使用7×7滤波器时的时间开销与使用3×3滤波器相比，在2个实验场景中分别平均增加19.4%和32.1%。随着滤波器尺寸的增大，运算时间的增长幅度并没有同比例增大。

4.2 软阴影绘制质量测试

为了对比软阴影绘制算法的绘制质量，本文将改进的PCSS算法、改进前的PCSS算法[17]和传统阴影图算法进行了对比，其中，传统阴影图算法按照文献[19]中的传统阴影图算法流程进行了实现。测试以Closed Citadel场景为例，在构建加速结构和阴影图时，边长的分辨率都设定为2 K。PCSS算法采用7×7滤波器。图8为阴影绘制效果的局部放大图。

从图8中可以看出，阴影图算法在某些区域的阴影边缘的绘制质量较低，具有较明显的方块状现象，而PCSS算法在绘制的阴影边缘存在一定范围的柔和的半影区，绘制效果较好，且改进前后的PCSS软阴影绘制效果几何没有差别。

5 结论

本文针对大规模三维场景，提出一种基于四叉树结构的PCSS软阴影算法。通过为三维场景的阴影图构建基于四叉树的加速结构，利用优化的邻域节点搜索方法、遍历顺序选择方法、PCF滤波方法，并进一步改进PCSS算法，能够利用四叉树节点中已经存储的阴影占有率，无须在原始阴影图分辨率下进行滤波操作。同时，可以共用遍历路径中相同的部分，有效减少滤波过程中的计算量，提高软阴影绘制速度，且性能稳定，能够渲染出高质量的软阴影效果。

[1]SUFFER K.光线跟踪算法技术[M].刘天慧，译.北京：清华大学出版社，2011：1-3.SUFFER K.Ray tracing from the ground up[M].LIU TIANHUI，Translated.Beijing：TsinghuaUniversity Press，2011：1-3.（in Chinese）

[2]WOO A，POULIN P.Shadow algorithms data miner[M].Florida：Chemical Rubber Company Press，2012：2-10.

[3]SELGRAD K，DACHSBACHER C，MEYER Q，et al.Filtering multi-layer shadow maps for accurate soft shadows[J].Computer Graphics Forum，2015，34（1）：205-215.

[4]SCANDOLO L，BAUSZAT P，EISEMANN E.Merged multiresolution hierarchies for shadow map compression[J].Computer Graphics Forum，2016，35（7）：383-390.

[5]郭钊，范湘涛，谭剑.基于光源空间透视的平行分割阴影图算法[J].地理与地理信息科学，2016，32（1）：39-43.GUO ZHAO，FAN XIANGTAO，TAN JIAN.Parallel split shadow map algorithm based on light space perspective[J].Geography and Geo-Information Science，2016，32（1）：39-43.（in Chinese）

[6]KOLIVAND H，SUNAR M S.Survey of shadow volume algorithms in computer graphics[J].IETE Technical Review，2013，30（1）：38-46.

[7]GERHARDS J，MORA F，AVENEAU L，et al.Partitioned shadow volumes[J].Computer Graphics Forum，2015，34（2）：549-559.

[8]ZHOU P，MENG X.SIMD friendly ray tracing on GPU[C]//International Conference on Computer-Aided Design and Computer Graphics.Jinan：Cad/Graphics，2011：87-92.

[9]NAH J H，KIM J W，PARK J，et al.HART：A hybrid architecture for ray tracing animated scenes[J].IEEE Transactions on Visualization and Computer Graphics，2015，21（3）：389-401.

[10]孟祥雨.基于光子映射的分布式全局光照计算方法研究[D].济南：山东大学，2016.MENG XIANGYU.Distributed global illumination method based on photon mapping[D].Jinan：Shandong University，2016.（in Chinese）

[11]FERNANDO R.Percentage-closer soft shadows[C]//Acm Siggraph 2005 Sketches.ACM，2005：1-35，38.

[12]PETERS C，KLEIN R.Moment shadow mapping[C]//Proceedings of the 19thSymposium on Interactive 3D Graphics and Games.San Francisco：Association for Computing Machinery，2015：7-14.

[13]ANDERSSON M，HASSELGREN J，MUNKBERG J，et al.Filtered stochastic shadow mapping using a layered approach[J].Computer Graphics Forum，2015，34（8）：119-129.

[14]BUADES J M，GUMBAU J，CHOVER M.Separable soft shadow mapping[J].The Visual Computer，2016，32（2）：1-12.

[15]谢依妨，杨红雨.基于遮挡区间映射的软阴影的研究与实现[J].计算机工程与设计，2015，36（3）：687-692.XIE YIFANG，YANG HONGYU.Research and implementation of soft shadow based on occlusion interval mapping[J].Computer Engineering and Design，2015，36（3）：687-692.（in Chinese）

[16]付杰.大规模场景实时渲染若干技术问题研究[D].西安：西北大学，2009.FU JIE.Study on some technical problems in real-time rendering of large-scale scenes[D].Xi’an：Northwest University，2009.（in Chinese）

[17]晏福兴，王毅刚.改进的百分比靠近软阴影技术的研究与实现[J].计算机工程与应用，2011，47（1）：185-187.YAN FUXING，WANG YIGANG.Research and implement of improved percentage-closer soft shadows[J].Computer Engineering and Applications，2011，47（1）：185-187.（in Chinese）

[18]ZHANG F，SUN H，XU L，et al.Parallel-split shadow maps for large-scale virtual environments[C]//Proceedings of the 2006 ACM International Conference on Virtual Reality Continuum and Its Applications.Hongkong：Association for Computing Machinery，2006：311-318.

[19]刘志旭.基于可视度图的实时软阴影算法研究[D].北京：中国石油大学，2011.LIU ZHIXU.Research on real-time soft shadow algorithm based on visibility map[D].Beijing：China University of Petroleum，2011.（in Chinese）

简讯：

学院“图学与机械课程示范教学与创新教学法”观摩竞赛获佳绩

2017年7月17日至19日，海军航空工程学院飞行器工程系机械基础教研室赵敏、周仙娥、唐伟峰三位教员赴兰州参加第四届全国高等学校教师图学与机械课程示范教学与创新教学法观摩竞赛。该项赛事是由教育部工程图学课程教学指导委员会、军队院校图学与机械基础教学协作联席会、中国图学学会制图技术专业委员会主办，兰州交通大学承办，高等教育出版社赞助的全国性教学比赛。本次比赛共有来自48所地方与部队高校的98名教师参赛。比赛设一等奖（20%）、二等奖（25%）、三等奖（25%）。比赛中，三位教员展现了优异的教学素质和讲台风采，给各位专家和评委留下了深刻的印象，获得了较高的评价。经过激烈角逐，3名教员均取得优异成绩，2人获得一等奖，1人获得二等奖。

学院举办“2017年中国国际飞行器设计挑战赛暨科研类全国航空航天模型公开赛”

2017年5月28日至29日，由国家体育总局航管中心、中国航空运动协会主办，海军航空工程学院承办的“2017年中国国际飞行器设计挑战赛暨科研类全国航空航天模型公开赛”在烟台举行。来自中国民航大学、南京航空航天大学、鲁东大学、解放军信息工程大学、陆军军官学院、武警工程大学等全国17所高校的147名运动员参加比赛。结合本次比赛安排，组委会特别邀请清华大学、北京航空航天大学的知名教授和部队专家开设了3场学术讲座。

“中国国际飞行器设计挑战赛暨科研类全国航空航天模型公开赛”自2004年起已成功举办13届。截止2016年，竞赛共吸引了来自109所院校的2100余名选手参加，赛事规模再创历史新高，已经成为国内水平最高、规模最大、等级最高的科研类航空航天模型赛事，与欧洲ACC竞赛和美国SAE竞赛被并称为世界三大高校科研类航空航天模型赛事。

本届公开赛共设置“电动滑翔机”、“地侦察与打击”、“二对二遥控空战”、“模型火箭运载与返回”4个项目。经过一天的紧张角逐，最终，海军航空工程学院代表队获得“电动滑翔机”、“对地侦察与打击项目”第一名。

Algorithm of Soft Shadow Rendering for Large Scale Scene

YUAN Yuwei1,LIU Chuanhui1,QUAN Jicheng1,2,WANG Hongwei2,LIU Yu2
（1.Department of Electronic and Information Engineering,NAAU,Yantai Shandong 264001,China;2.Department of Aeronautic and Astronautic Intelligence,Aviation University of Air Force,Changchun 130022,China）

In order to overcome the problems of low efficiency of the traditional soft shadow rendering algorithm in the face of large scale 3D scene,in this paper,an acceleration structure based on the quad tree was built for shadow map of 3D scene,the method for searching neighbor node and the method for selecting traversal sequence was studied,and a percent⁃age closer soft shadow algorithm based on quad tree was proposed.The experimental results indicated that,compared with the traditional algorithm,the proposed algorithm could effectively improve the soft shadow rendering efficiency of large scale 3D scene,and the performance was stable,the high quality soft shadows could be rendered.

3D scene;soft shadow;percentage closer filtering;quad tree;neighborhood search

TP391.9

A

1673-1522（2017）04-0341-06

10.7682/j.issn.1673-1522.2017.04.001

2017-03-04；

2017-07-12

国家自然科学基金资助项目（61301233）；吉林省自然科学基金资助项目（20130101069JC）

袁昱纬（1988-），男，博士生。