基于光源空间透视的平行分割阴影图算法

郭 钊，范 湘 涛，谭 剑

(1.中国科学院遥感与数字地球研究所数字地球重点实验室，北京 100094；2.中国科学院大学，北京 100049)

基于光源空间透视的平行分割阴影图算法

郭 钊1,2，范 湘 涛1，谭 剑1

(1.中国科学院遥感与数字地球研究所数字地球重点实验室，北京 100094；2.中国科学院大学，北京 100049)

随着地理信息系统应用的深入，在真三维空间中处理问题已成为一种趋势，而实时阴影对提高三维场景的真实感和沉浸感非常重要。目前主流的平行分割阴影图算法对大尺度场景兼容性好，但在细节层次的渲染方面质量不高，而光源空间透视阴影图算法在细节层次渲染方面精度很高，但是对大尺度场景难以覆盖。针对该问题，提出了一种基于光源空间透视的平行分割阴影图算法，也称为光源透视平行分割阴影图算法。该方法将光源空间透视阴影图算法中透视锥体的透视变换矩阵应用于平行分割阴影图算法对各个子视锥体的渲染阶段并生成产生形变的阴影深度图，通过该方法减小其阴影走样误差。并且在计算透视变换矩阵的过程中，提出了一种确定阴影图形变程度的算法,使该算法更好地适应于不同大小的场景。实验结果表明,该算法通过提高视锥体近平面附近阴影采样率有效地解决了在平行分割阴影图算法中存在的阴影透视走样的问题。在对大规模场景的渲染方面，该算法在细节层次的表现要明显优于平行分割阴影图算法，满足了大尺度场景和精细建筑模型的阴影渲染需求。

三维地理信息系统；光源空间透视阴影图；平行分割阴影图；数字地球科学平台

0 引言

对于三维地理信息系统[1]，实时阴影[2]是实现其真实性、增强其沉浸感所必不可少的一部分。当前，三维场景中阴影的实现技术主要分为两类[3]，即：体阴影法和阴影图法。体阴影法精度较高,不过该算法的效率与场景复杂度直接相关，故该算法的应用具有一定的局限性。而阴影图算法虽然在精度上不如体阴影算法，但由于其效率与场景复杂度无关，所以被广泛应用于大尺度场景和结构复杂场景。

阴影图算法最早是由Williams提出的一种用于Z缓存生成场景中物体阴影的方法[4]，也被称为标准阴影图算法(Standard Shadow Maps,SSM)，该算法原理简单，易于实现，不过走样问题较为严重。为了解决标准阴影图算法的走样问题，Stamminger等提出了透视阴影图算法(Perspective Shadow Maps,PSM)[5]，该算法通过对相机视图空间进行透视变换以解决透视走样问题。Wimmer等为了解决PSM算法中光源方向改变与产生奇点的问题又提出了光源空间透视阴影图算法(Light Space Perspective Shadow Maps,LisPSM)[6]。而后，通过对相机视图空间采用不同的透视变换算法或采用不同的阴影图采样方式分别提出了梯形阴影图算法(Trapezoidal Shadow Maps,TSM)[7]、对数透视阴影图算法(Logarithmic Perspective Shadow Maps,LogPSM)[8]、改进的实时反走样透视阴影图算法[9]以及透视-曲变阴影图算法[10]。Alia等通过对阴影图进行不规则采样，提出了无锯齿阴影图算法(Alias-Free Shadow Maps,AFSM)[11],不过由于目前硬件不支持非规则采样，该方法实现比较困难。

以上算法虽然在某些场景中能取得较好的阴影显示效果，但是在对大规模场景进行实时渲染生成阴影时，误差往往很大，故而多采用平行分割阴影图(Parallel Split Shadow Maps，PSSM)算法[12-14]实现，也可将这种实现方法称为CSM(Cascaded Shadow Maps)算法[15]、基于层渲染的CSM算法[16]或Z-Partitioning算法[17]，以上算法的实现思想大致相同，相比而言第一种算应用更广，不过这些方法仍然存在透视走样问题。

为了反走样，解决锯齿形边界问题，提出一些方法用来优化阴影图的边界，如百分比邻近滤波方法(Percentage Closer Filtering,PCF)和方差阴影图方法(Variance Shadow Maps,VSM)。张文晓等将VSM算法与SSM算法结合以绘制植物阴影[18]，刘松平将VSM与PSSM算法结合得到其混合算法[19]。

数字地球科学平台是由中科院遥感与数字地球所研发的一款数字地球系统，类似于Google 公司推出的Google Earth，其场景具有大尺度空间范围，也具有局部精细结构。所以，为了解决PSSM算法中的透视走样问题，使数字地球科学平台中的三维场景阴影渲染更为细腻、真实，本文基于LisPSM算法对PSSM算法进行改进，提出了一种光源透视平行分割阴影图算法(Light Perspective Parallel Split Shadow Maps,LPPSSM)。

1 相关算法介绍

PSSM算法是一种沿视锥体的Z轴方向切割视锥体从而生成若干个子视锥体，然后对这些子视锥体进行分步渲染分别生成对应的阴影图，进而对这些阴影图进行处理最后生成阴影的一种广泛应用于大规模场景的阴影图渲染算法，其原理如图1a所示。

LisPSM是一种光源空间透视投影的阴影图参数化方法，通过对视锥体进行透视变换，然后控制阴影图参数以控制其深度值的采样方式生成阴影图，最后达到减小阴影走样误差的目的,是一种典型且运用广泛的阴影图参数化方法。也有文献[17]将阴影图参数化方法称为阴影图的变形，其原理如图1b所示。

图1 PSSM算法与LisPSM算法原理示意

Fig.1 Principle of PSSM algorithm and LisPSM algorithm

由于PSSM算法与LisPSM算法原理不同，故具有不同的特点。PSSM算法具有如下优势：1)可以打破计算机硬件对阴影图像分辨率大小的限制；2)提高了阴影区域的采样率；3)通过应用合适的视锥体切割算法，可以有效地分配不同区域阴影的采样率，使阴影有更好的视觉效果。上述优势使得PSSM算法可以很好地用于大场景阴影渲染。但是与传统的阴影图算法一样，PSSM算法在阴影生成的过程中会产生阴影透视走样的问题，从而使产生的阴影不够精细。相比于PSSM算法，LisPSM算法的优点有：第一，解决在传统阴影图算法中存在的阴影图走样问题；第二，通过改变阴影图深度值的采样方式提高视锥体近剪裁面附近的采样率，以提高阴影的质量。这两点优势使得LisPSM算法在较小的场景中对阴影细节的表现有较大的优势。不过在对大场景渲染时，由于阴影图大小受硬件的限制，导致阴影图采样率不够，锯齿现象明显等问题。

2 改进算法的实现

2.1 算法概要

LPPSSM算法是基于LisPSM算法对PSSM算法进行改进所得，主要应用于大规模场景阴影实时渲染，两种算法步骤对比如图2所示，其中num是指视锥体的切割总个数，i是指切割的第i个子视锥体。图2b中虚线部分是LPPSSM算法相对于PSSM算法改进的地方，是针对PSSM算法的透视走样问题所做的改进，主要分为两部分：一是生成阴影深度图，这一步骤从透视变换步骤之前放到透视变换步骤之后进行；二是在PSSM算法的基础上添加了两个步骤，即确定形变参数n与构建透视锥体并计算其透视矩阵。

图2 PSSM算法与LPPSSM算法流程

Fig.2 The process of PSSM and LPPSSM algorithm

2.2 计算透视锥体透视变换矩阵

构建透视锥体并计算其透视变换矩阵主要是为了将透视变换矩阵作用于视锥体分割后的子视锥体，使其产生形变，从而提高近平面的阴影深度图采样率，为下一步阴影深度图的绘制做准备。

对切割后的子视锥体构建透视锥体P，并将其作用于子视锥体，即构建一个虚拟的视锥体作用于子视锥体，进而通过虚拟视锥体的矩阵变换使子视锥体产生一定的形变(图3)。因此构建透视锥体P并作用于子视锥体的过程也就是计算透视锥体变换矩阵并作用于子视锥体使其产生形变的过程。具体优化方法如下：

传统PSSM算法的变换矩阵为：

(1)

(2)

图3 透视锥体作用于子视锥体产生形变过程示意

Fig.3 The deformation process of the view frustum under the action of the perspective frustum

2.3 参数n的确定

由透视锥体变换矩阵计算过程中的步骤4)可知，参数n，即透视椎体P的参考点p到其近平面的距离，它会直接影响阴影图形变的强度。n的值越小阴影图形变强度越大，反之越小。n与P和子视锥体V之间的关系如图4所示，n和f分别为透视锥体近平面与远平面距离，Zn和Zf分别为视锥体近平面和远平面距离，eye为视点，Z为视锥体z轴方向，Z′为透视锥体z轴方向。由于透视锥体变换矩阵要作用于多个深度不同的子视锥体，传统的n值确定方法在这里并不适用，所以根据LPPSSM算法中各个子视锥体深度不同的特点来确定参数n。由于n的确定与子视锥体的Znear、Zfar相关，故根据子视锥体的Znear、Zfar定义自由参数n,即：

(3)

其中:c为相关性参数，其取值范围为(0，1)，Zfar、Znear分别对应于各个子视锥体的近平面和远平面。

图4 参数n与透视锥体P和子视锥体V的关系示意

Fig.4 The relationship between parameternwith perspective frustumPand view frustumV

2.4 阴影图的生成

由图2可知，PSSM算法是先生成阴影深度图再进行光源视锥体透视变换，这样透视变换无法作用于阴影深度图，也无法减小透视走样。在改进算法LPPSSM中，则是先计算透视锥体的透视矩阵与光源视锥体的透视矩阵，然后将它们作用于子视锥体，最后生成阴影深度图。现在得到的阴影深度图面对的是完成了透视变换后的场景，故阴影深度图也会产生形变[7]，即近平面的场景相对于远平面的场景变大，这样就增加了近平面的采样率。

由文献[6]可知阴影图在视锥体近平面产生的透视走样误差会大于远平面的透视走样误差，通过提高视锥体近平面的阴影采样率可以在一定程度上减小近平面产生的透视走样误差，使近平面的阴影细节程度更为细腻，同时使整体的误差分布更为均衡，这种阴影成像方式更为符合人眼的视觉特征。

3 实验结果与分析

本文使用数字地球科学平台中的大规模场景“北京奥林匹克公园”作为实验模型，使用开源三维引擎Open Scene Graph (OSG)[20]结合面向GPU的编程语言GLSL实现。实验中分别用LisPSM、PSSM及LPPSSM算法对北京奥林匹克公园模型进行渲染，3种算法阴影图的分辨率均为1 024×1 024，PSSM算法和LPPSSM算法均将场景划分为3层。光源为平行光源，视锥体为正交投影视锥体。本文的实验平台所使用的操作系统为Windows 8.1 专业版 64位，处理器为英特尔 i5-2320 3.00 GHz 四核，内存为金士顿 DDR3 1333 MHz 8 GB，显卡为Nvidia GeForce GTX 550 Ti 2 GB。

实验一：PSSM算法与LPPSSM算法阴影深度图对比。将北京奥林匹克公园场景定位到某一视点，然后用两种算法分别对该场景进行阴影渲染，在相同分辨率下，得到的阴影深度图如图5所示，其中第一行是全景图，第二行是第一行框圈中部分的放大图。通过计算得到PSSM算法放大图的像素值为7378,LPPSSM算法放大图的像素值为25 168。对比第一行两张阴影深度图可知，PSSM算法得出的阴影深度图在近平面处有较大的空白，大大浪费了深度图像素，相比之下由于LPPSSM算法使用了参数n的确定算法来控制阴影图的形变，从而在一定程度上消除了对像素的浪费。通过对比第二行阴影图与其像素值可知，LPPSSM算法得到的阴影深度图像素值明显高于PSSM算法，从而可以有效地提高阴影的渲染质量。

图5 PSSM算法与LPPSSM算法阴影深度图对比Fig.5 The difference of shadow depth map between PSSM and LPPSSM

实验二：LisPSM算法、PSSM算法与LPPSSM算法的实现结果对比。3种算法的效果如图6(见封2)所示，从上向下分别为各个算法所对应的正常图、分割示意图(分割效果由红、绿、蓝3种颜色表示)、深度图为正常图的红框区域放大图。通过分割示意图可以清晰看出场景被划分出了3块区域；通过对比深度阴影图可以看出LPPSSM算法得出的3个阴影深度像素值均大于PSSM算法；通过对比红框区域放大图可以看出LPPSSM算法的阴影质量明显高于其他两种算法。

4 结论

本文针对具有精细模型结构的大尺度场景阴影渲染质量不高的问题，结合PSSM算法和LisPSM算法的优势，提出了一种光源透视平行分割阴影图算法。该算法基于LisPSM算法对PSSM算法在透视变换和阴影图参数化方面进行优化以消除透视走样，减小阴影走样误差，提高阴影质量。在对PSSM优化的过程中提出了控制阴影图形变强度的方法，以使其更好地适用于不同规模的场景。在数字地球科学平台中实测后，由实验结果可知，该算法在保证大尺度场景兼容性的同时，大大提高了局部场景阴影的细腻程度，有效地提高了数字地球科学平台阴影渲染的普适性，并为其他类似研究提供了有益参考。本文虽然对大规模场景阴影的渲染质量有显著提高，但是并未提高阴影的渲染效率，如何利用GPU的并行渲染特性[21]提高阴影的渲染效率将是下一步的研究方向。

[1] 朱国敏，马照亭，孙隆祥，等.城市三维地理信息系统中三维模型的快速构建方法[J].地理与地理信息科学,2007,23(4):29-32.

[2] EISEMANN E,SCHWARZ M,ASSARSSON U,et al.Real-Time Shadows[M].Boca Raton:CRC Press,2011.93-97.

[3] GUO J,XU X Y,PAN J G.Present status of shadow generation algorithms based on shadow maps[J].Journal of Compute-Aided Design and Graphics,2010,22(4):579-591.

[4] WILLIAMS L.Casting curved shadows on curved surface[C].Computer Graphics Proceedings,Annual Conference Series,ACM SIGG RAPH,Atlanta,1978.270-274.

[5] STAMMINGER M,DRETTAKIS G.Perspective shadow maps[C].Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH,San Antonio,2002.557-562.

[6] WINMMER M,SCHERZER D,PURGATHOFER W.Light space perspective shadow maps[C].Proceedings of Eurographics Symposium on Rendering,Norrkoping,2004.143-151.

[7] MARTIN T,TAN T S.Anti-aliasing and continuity with trapezoidal shadow maps[A].Proceedings of Eurographics Symposium on Rendering[C].Norrkoping,2004.153-160.

[8] LLOYD D B,GOVINDARAJU N K,QUAMMEN C,et al.Logarithmic perspective shadow maps[J].ACM Transactions on Graphics,2008,27(4):1-39.

[9] WU T,CHENG Y Q,ZHANG Y J.Improved real-time anti-aliasing perspective shadow maps algorithm and its implementation[J].Computer Engineering and Design,2011,32(10):3435-3439.

[10] YE Q,FU X,JIA N X,et al.Perspective-distorted shadow maps[J].Journal of Computer-Aided Design & Computer Graphics,2014,26(10):1681-1688.

[11] AILA T,LAINE S.Alias-free shadow maps[A].Proceedings of Eurographics Symposium on Rendering[C].Norrkoping,2004.161-166.

[12] ZHANG F,SUN H Q,XU L L,et al.Parallel-split shadow maps for large-scale virtual environments[A].Proceedings of ACM International Conference on Virtual Reality Continuum and its Applications[C].Hong Kong,2006.311-318.

[13] ZHANG F,SUN H Q,NYMAN O.Parallel-Split Shadow Maps on Programmable GPUs[M].Boston:Addison-Wesley Professional,2007.203-238.

[14] ZHANG F,SUN H Q,XU L L,et al.Hardware-accelerated parallel-split shadow maps[J].International Journal of Image and Graphics,2008,8(2):223-241.

[15] ENGEL W.Advanced Rendering Techniques[M].Hingham:Charles River Media,2006.197-206.

[16] HAO Y,LI Y.Layered-based CSM[J].Computer Engineering and Design,2012,33(10):3883-3886.

[17] LLOYD D B,TUFT D,YOON S E,et al.Warping and partitioning for low error shadow maps[C].Proceedings of Eurographics Symposium on Rendering[A].Nicosia,2006.215-226.

[18] ZHANG W X,TANG L Y,CHONG C,et al.Plant shadow algorithm improving and rendering based on shadow map[J].Journal of Fuzhou University(Natural Science Edition),2013,41(5):850-857.

[19] LIU S P,XIAO D G.Hybrid algorithm of PSSM and VSM in shadow rendering[J].Computer Engineering,2015,41(2):228-233.

[20] WANG R,QIAN X L.Open Scene Graph 3D Rendering Engine Design and Practice[M].Beijing:Tsinghua University Press,2009.131-162.

[21] MA S,LIANG X H,YU Z,et al.Light space parallel-split shadow maps based on programmable GPUs[J].Journal of Compute-Aided Design and Graphics,2010,22(3):388-395.

Parallel Split Shadow Map Algorithm Based on Light Space Perspective

GUO Zhao1,2,FAN Xiang-tao1,TAN Jian1

(1.Key Laboratory of Digital Earth Science,Institute of Remote Sensing and Digital Earth,Chinese Academy of Sciences,Beijing 100094；2.University of Chinese Academy of Sciences,Beijing 100049,China)

With the deeper application of geographic information system,to solve problem in real 3D space has come to be a trend.It is very important for real-time shadow rendering to improve the sense of reality and immersive of virtual 3D scene.For now,Parallel Split Shadow Maps (PSSM) algorithm is a powerful method which is widely used for large-scale virtual environments rendering.But the detail of the shadow is kind of rough,compared with other shadow map algorithm with perspective projection parameterization method.On the other side,the Light Space Perspective Shadow Maps (LisPSM) is good at rendering the detail of shadow.But it cannot cover the large-scale scene,due to the limitation of hardware.So to improve the shadow performance of large-scale virtual scene,the advantages of both methods are combined,and Parallel Split Shadow Maps algorithm on Light Space Perspective is proposed,which is also called Light Perspective Parallel Split Shadow Maps (LPPSSM).The realization of this algorithm is to use LisPSM method to render every child view frustum,after the split of parent frustum which is done by PSSM method.With the utility of perspective transformation,the shadow map aliasing error is reduced greatly and the shadow map perspective aliasing error is removed.During the process of perspective transformation matrix′s calculation,another algorithm is proposed to help calculate a parameter,which is used to determine the strength the shadow map wraps.And this can help to make this method to suit different size of scenes,and combining LisPSM algorithm and PSSM algorithm in a much better way.By making a comparison between LisPSM algorithm,PSSM algorithm and LPPSSM algorithm,the shadow map shape of LPPSSM algorithm is similar to LisPSM algorithm,which is much different from PSSM method.The shape of former one is like a trapezoid,while the other one is like a rectangle.And the shadow quality is different too.From the result of the test,it can be seen clearly that the shadow quality of LPPSSM algorithm is much higher than the other ones.By combining the advantages of LisPSM algorithm and PSSM algorithm,the LPPSSM algorithm is proposed.This algorithm can help to solve the problem of low shadow quality when using PSSM algorithm to render a large scale 3D scene.And the algorithm proposed to calculate the parameter of shadow wrap can make the LisPSM algorithm match to PSSM algorithm much better.The result of test shows that LPPSSM algorithm solved the shadow map perspective aliasing problem,improved the shadow performance,and satisfied the need of rendering large scale space environment models and accurate architectural scene models with good shadow quality.

3D geographic information system;light space perspective shadow maps;parallel split shadow maps;digital earth science platform

2015-07-01；

2015-10-19

国家自然科学基金项目(41201399)

郭钊(1990-)，男，硕士研究生，研究方向为数字地球与虚拟现实。E-mail:guozhao@radi.ac.cn

10.3969/j.issn.1672-0504.2016.01.008

TP391.9

A

1672-0504(2016)01-0039-05