简述Shadow Mapping和Shadow Volume的新方法

简介

阴影渲染在真实感图形渲染中非常重要，它作为一种视觉上的提示，将场景的空间结构和物体的相对关系反馈给用户。研究表明，阴影的有无对用户认知空间物体位置具有重要作用[1]。然而，实时、高清的阴影渲染始终是一个有挑战性的问题。早年的计算机图形学研究中，两种高效的阴影渲染技术被提了出来，分别是阴影体算法（Shadow Volume Algorithm）[2]和阴影深度映射（Shadow Depth Mapping）[3]，后来许多阴影渲染技术都是在它们两者的基础上进行改进得到的。

Shadow Mapping的基本思想是，物体之所以会处在阴影当中，是由于在它和光源之间存在着遮蔽物。因此，首先我们以光源为视点，得到一个所有物体的深度图；然后将视点移回到摄像机，对每个像素点计算它和光源的距离，如果这一距离大于深度图中的深度，则说明该物体被遮挡了；否则，说明没有被遮挡。在光源不移动的情况下，无论摄像机位置如何移动，深度图都是不变的，因此将大大节省计算量。但它的缺陷是无法处理移动光源的情形。另一个缺陷在于，深度图是在像素上做的，因此天生具有锯齿。如果像素的分辨率不高，则锯齿现象会很明显；如果分辨率太高，则又很大地增加了计算量。

Shadow Volume的基本思想是，每个物体在光照下，投下了一个锥形的阴影体。如果我们观测的点在阴影体中，那么它就是阴影；否则它就不是阴影。具体实现上，可以分为Z-Pass[4]和Z-fail[5]两种方法。Z-Pass从摄像机位置出发，发射一条光线到目标点，当此光线从锥体的外部进入内部时，计数器加1；当光线从锥体内部出去时，计数器减1。显然，如果摄像机本身不在阴影中，那么如果最终计数器为正，则说明目标点在阴影中；如果计数器为0，则说明不在阴影中，如图1所示。

图1. 光线从摄像机向目标点出发，每次从锥体外部进入内部则计数器加1，内部进入外部则计数器减1。由计数器为正或为零，可以判断目标点是否处于阴影中[6]。

Z-Pass不能适用于摄像机本身在阴影中的情况，因为这样计数器可能为负。为此，[5]提出了Z-Fail算法，它的光线从足够远的地方出发（来保证在非阴影区域），先经过目标点，再终止在视点。由于出发点一定在非阴影区域，因此这时计数器就不会出现负值，如图2所示。

图2. 光线从远处向摄像机出发，每次从锥体外部进入内部则计数器加1，内部进入外部则计数器减1。由计数器为正或为零，可以判断目标点是否处于阴影中[6]。

本文探究Shadow Mapping和Shadow Volume在近年来的发展和进化，将以[7]和[8]为两种思路的代表方法，描述其核心思想和具体算法。

相关工作

不同的Shadow Mapping

在实际工程中，Shadow Mapping的一个主要问题在于自遮挡。由于浮点数和采样上的误差，如果我们以物体表面深度值作为Shadow Mapping中的基准，则由于小误差的缘故，一些深度略大于Shadow Mapping的表面点会被判定为在阴影中，从而形成自遮挡。[9]提出了一种中值Shadow Mapping（Midpoint Shadow Mapping）的方法，即不采用物体表面深度，而是物体和光源最近的两个面的平均，作为Shadow Mapping中的基准。这样，物体向光面和背光面的点计算时都有了一定的容错范围，解决了部分自遮挡的问题，如图3最左侧图所示。

图3. 左图为中值Shadow Mapping，中图和右图为中值 Shadow Mapping可能出现的阴影点误判情况[10]

对中值Shadow Mapping方法的一个拓展是双Shadow Mapping（Dual Shadow Mapping）[10]。它是为了解决中值Shadow Mapping中仍可能出现的少数阴影点误判问题而诞生的。双Shadow Mapping除了保存了深度信息外，还维护了一个自适应的偏置量（Bias），从而在一些特殊点上也能得到正确的阴影。

在双Shadow Mapping的基础上，[11]提出了一种对Shadow Mapping进行压缩的方法CSM（Compressed Shadow Maps），[7]的方法可以视为是[11]在高维上的拓展。[12]也提出了一种通过对Shadow Mapping深度进行编码的压缩方式，但[11]和[12]都没有完全挖掘Shadow Mapping的压缩能力。

不同的Shadow Volume

Shadow Volume的第一个实现是Z-Pass[4]，出于解决摄像机本身可能在阴影中的问题，[5]提出了Z-Fail算法。这两个算法往往使用OpenGL中的模板缓存（Stencil Buffer）来实现，但它们并没有解决Shadow Volume中最大的问题，即不必要地计算了许多阴影轮廓。一些方法尝试着减少部分阴影轮廓的计算，如[13]和[14]，但它们仍没有完整地解决这一问题。

[15]提出了另一类基于几何体的阴影渲染方法。对于一个三角形在光照下形成的锥体，[15]使用三个面（分别对应三条边）和三角形本身，将空间划分为被该三角形遮挡的部分，和未被该三角形遮挡的部分。然后，[15]对空间建立空间二分树（Binary Space Partitioning，BSP），从而将空间划分为被遮挡区域和未被遮挡区域。同时，由于树对于检索的优良性质，我们可以高效地查找空间中一点是否属于阴影区域。然而，建立空间二分树需要对许多平面进行求交和裁剪，且需要大量的存储空间和计算代价，同时因为一些数值计算上的不稳定性，因此[15]的方法实用性不强。

[16]在[15]的基础上进行了改进。它们在BSP的基础上增加了一个表示空间相交的子树，从而构建了一棵物体三叉树（Ternary Object Partitioning，TOP）。这一改变避免了裁剪操作，因此大大提升了稳定性和效率。而[8]的方法可以视为是[16]的进一步拓展。

高分辨率Shadow Mapping压缩

高分辨率的Shadow Mapping之所以效率较低，是因为高分辨率下的深度纹理难以快速地检索和遍历。深度纹理实质上就是图片，对于图片，我们有一些多分辨率分解的方法（如小波分解或四叉树分解），它们可以将低频的信息存储在粗粒度的层级，将高频的细节存储在细粒度的层级。通常，在有损压缩下，在细粒度上系数较小的项就会被移除，只留下系数较大的项，从而提升效率，因此细粒度的层级往往是稀疏的。但是对于无损压缩，我们就不能忽略细粒度上的小系数，从而细粒度的层级就不稀疏了，消耗的代价也就更大。

[7]的主要贡献是，找到一种Shadow Map的替代品，这一替代品可以增加分解后的稀疏性。具体而言，[7]使用光线照到物体表面的入口，和穿透物体从另一侧穿出的出口之间的区间，来替代原本单一的表面。显然，这和双深度Shadow Map是一致的。对于只有单面的物体，或者不封闭的物体，我们需要一个额外的深度上限，从而在这些像素上也形成区间。完成这一替代后，我们的目标就转化为如何在一系列的区间中，嵌入连续的平面，从而增强分解后的稀疏性。[7]首先提出了两种贪心的构造方法，得到区间中的连续深度平面；然后使用四叉树对这些平面进行编码；最后提出如何在此数据结构上，进行遍历和查询，从而完成阴影的渲染。

构建

第一个需要解决的问题是，如何对每个像素计算深度区间。区间下界显然就是模型的表面（即常规Shadow Map的值），区间上界来自于模型的“第二层”，它往往采用了深度剥离（Depth Peeling）[17]的方法。考虑从光源发射向像素的光线，以及一个初始化为0的计数器。当光线和模型的外表面相交时，计数器加1；当光线和模型内表面相交时，计数器减1。当光线第一次相交到模型，这就是区间下界；当计数器的值回归到0时（这里仅考虑了封闭模型，但考虑了封闭模型相交的情况），此时的交点就是区间上界。通过Depth Peeling算法，我们可以同时在所有像素上计算深度区间，因此是非常高效的。

得到每个像素上的深度区间后，我们需要找到一个区间内的、简化的、分解后稀疏的平面。然而，在模型简化问题中，对给定包围壳中简化表面的寻找，是一个已被证明的NP难的问题[18]。因此，[6]提出了两个基于贪心算法的自顶而下和自底向上的算法，从而完成高效的平面寻找。

自顶而下的构建

自顶而下的构建从最粗的粒度，即整个Map开始。对于所有的区间，我们找到一个最合适的深度值，它落在尽可能多的区间内。对于包含这一深度值的区间，它们将被标记，并将以此深度作为自身的深度；对于不包含这一深度值的区间，它们将被放在粒度更细的下一层进行处理。对于下一层，我们采用四叉树的方法，将Map分成了四块，对每块重复上述的操作，直到到达最细粒度的一层（即每个像素）或一整块所有像素均已被标记。它的伪代码如下：

算法1. 自顶而下的构建

上述过程没有描述如何找到“最合适”的深度值。一种简单的思路是，我们将深度离散化，然后遍历每一个区间，构建直方图统计。显然，“最合适”的深度值就是直方图中最高的那一个。然而，均匀离散化代价太大，因此我们对每个区间的上界和下界进行排序，并统计直方图，可以更高效地得到“最合适”的区间。如图4所示。

图4. 左图为各个深度区间，右图为深度区间的直方统计，从而找到“最合适”的深度

这一算法在最初需要 的复杂度用于排序，然后每一层需要遍历每个区间进行统计，复杂度为 ，而一共有 层，因此总复杂度仍为 。

自底向上的构建

自底向上的构建从像素开始。每次我们考察邻近的四个像素，类似地找到一个“最合适”的最大深度子区间，使它落在尽可能多的像素深度区间内。对于那些包含“最合适”区间的像素，我们就不再额外记录其区间值；对于不包含“最合适”区间的像素，我们将其保留。我们逐层向上，重复这样的构建，直到到达最粗粒度的层。它的过程如图5所示。

图5. 从左至右表明了自底而上的构建方法

由于一次只需要在四个区间内选择“最合适”的子区间，我们就不需要进行耗时的排序操作了。同时，虽然它的复杂度和自顶而下的构建一样（都是 ），但由于它的方法更适用于并行的架构，因此可以使用GPU进行加速。

四叉树压缩

四叉树包含了三种节点：叶子节点、内部节点和空节点。叶子节点仅含有32位的深度值。内部节点不仅含有32位的深度值，还需要保存树的连接信息。空节点不含有深度值，但也需要保存树的连接信息。

对于内部节点和空节点，我们使用8位来存储其4个子节点的状态（每个子节点2位），状态共有4种，即子节点不存在、子节点为叶子节点、子节点为内部节点和子节点为空节点。另外，有16位用于存储第一个子节点的指针，由于子节点和它的兄弟节点连续存储，因此只需要存储第一个子节点就够了。考虑到4字节的对齐，我们还要给内部节点和空节点加上1字节的空间（或者也可以将16位指针扩展到24位，但[6]中实验证明区别不大）。总之，内部节点占用了8个字节，空节点和叶子节点分别占用了4个字节。

树的遍历

树的遍历和普通四叉树遍历没有什么不同。对每一个节点，我们可以通过8位的子节点状态，加上16位的首子节点的指针，计算出每个子节点的指针，然后继续迭代。

树的检索

高效的检索也是Shadow Mapping的一个重要组成部分。出于避免锯齿的考虑，通常我们会采用PCF（Percentage Closer Filtering）[19]的方法。PCF方法指判断阴影时，并不判断一个像素是否在阴影区域中，而是在一个以该像素为中心的固定窗口中，对邻近像素的Shadow Map深度值求平均，以此平均数来判断是否为阴影。显然，它可以一定程度上解决锯齿的问题。

Shadow Map堆

二维上的四叉树压缩方法，可以很容易地拓展到三维的八叉树方法。我们可以将一系列Shadow Map叠成一个堆，然后用八叉树对整体进行类似的压缩。这样的方法可以渲染出面光源软阴影的效果，也可以渲染移动光源的效果。对于面光源，我们在光源上进行采样，从而将其视为多个带权的点光源；对于移动光源，我们需要提前获取光源的运动轨迹，提前计算好每个轨迹下的Shadow Map。面光源的效果如图6左图所示，移动光源效果如图6右图所示。

图6. 左图为面光源的效果，右图为移动光源的效果

基于聚类和度量树的实时阴影渲染方法

[8]的算法主要分成三步：聚类、度量树构建、度量树遍历。聚类是一个预处理的步骤，它将邻近的三角形面片聚类成一个簇，然后基于簇的包围体来计算阴影。聚类需要一定的权衡，即一方面聚类可以简化模型，聚类程度越高模型越简单；另一方面聚类后形成的包围体会给阴影带来误差，聚类程度越高也就意味着误差越大。[8]中选择了球状和胶囊状的包围体，也是出于平衡效率与效果的考虑得到的。

对于聚类好的簇，[8]定义了一个新的度量方式，并在新的度量方式下，对簇构建了树状结构。之所以需要新的度量方式，是因为在光源的视角下，球状和胶囊状的包围体将变成圆柱形和胶囊圆柱形，从而过去的度量方式不再适用了。[8]提出了新的基于角度的度量方式。

对于每个像素点，我们需要确定它们是否在阴影之中，因此，我们需要知道它们和簇之间的相对位置关系。由于有了度量树的数据结构，我们可以递归地完成这一遍历步骤。

聚类

聚类可以更加高效。对于 n n n个三角形面片，假设建立一棵树需要 O ( n log ⁡ n ) O\left( {n\log n} \right) O(nlogn)的复杂度，那么，当我们有一个聚类算法，每个簇中含有 p p p个三角形面片，再对簇进行建树，则复杂度将下降到 O ( n p log ⁡ n p ) O\left( {{n \over p}\log {n \over p}} \right) O(pn​logpn​)。[8]的算法不依赖特定的聚类算法，但显然，不同的聚类算法将产生不同的结果。

[8]采用的聚类算法如下。首先通过k-mean++算法找到一组中心点，这些中心点并不是随机分布的，而是彼此间距尽可能大，从而保证中心点尽量均匀地分布。然后，每个三角形面片被分配给距离它最近的中心点，形成这一轮迭代的簇。再次，中心点被重新调整为实际簇中各个三角形的中心。然后我们重复上述的步骤，直到结果收敛或每个簇中的三角形面片数量小于指定的阈值。

包围体构建

我们需要对每个簇构建包围体。我们期待包围体尽可能紧密地包围着簇，又希望包围体的结构尽可能简单，从而降低存储和运算时间。常见的包围体有轴对齐包围盒（Axis Aligned Bounding Boxes，AABB）和方向包围盒（Oriented Bounding Boxes，OBB）。但是，考虑到我们更关心在光线透射下阴影的形状，AABB和OBB投影后都成为了平截头体，因此形状并不简单。作为替代，[8]采用了球状包围体，这样投影后的形状就是圆柱体。但是球形常常不能很好地紧密包围三角形面片，因此[8]还采用了胶囊状的包围体。

我们还需计算簇的均值与方差。假设簇中的第 i i i个三角形面片的三个点为 p i p^i pi， q i q^i qi和 r i r^i ri，则它们的均值 μ \mu μ和方差 C C C的计算方式如下：

μ = 1 3 n ∑ i = 0 n ( p i + q i + r i ) \mu = {1 \over {3n}} \sum_{i = 0}^n \left( {{p^i} + {q^i} + {r^i}} \right) μ=3n1​i=0∑n​(pi+qi+ri)

C j k = 1 3 n ∑ i = 0 n ( p ′ j i p ′ k i + q ′ j i q ′ k i + r ′ j i r ′ k i ) {C_{jk}} = {1 \over {3n}} \sum_{i = 0}^n \left( {p'}_j^i {p'}_k^i + {q'}_j^i {q'}_k^i + {r'}_j^i {r'}_k^i \right) Cjk​=3n1​i=0∑n​(p′ji​p′ki​+q′ji​q′ki​+r′ji​r′ki​)

其中 n n n表示簇中的三角形面片总数， p ′ i = p i − μ , q ′ i = q i − μ , r ′ i = r i − μ p{'^i} = {p^i} - \mu ,q{'^i} = {q^i} - \mu ,r{'^i} = {r^i} - \mu p′i=pi−μ,q′i=qi−μ,r′i=ri−μ。

度量树构建

在传统Shadow Volume下，每个三角形面片投影的区域由四个平面组成（即三条边分别对应一个平面，原三角形一个平面，包围而成的不封闭几何体），为了判断空间一点是否在阴影区域，往往对空间建立空间二分树（Binary Space Partitioning，BSP）或物体三叉树（Ternary Object Partitioning，TOP）。然而，这些数据结构不适合于球状包围体和胶囊包围体的情况，因为它们在光照下形成了圆锥体和胶囊圆锥体。

假设 是一个集合，则在此集合上可以定义一个度量空间 ，其中， 满足如下条件：

• 非负性： ∀ x , y ∈ O , d ( x , y ) ≥ 0 \forall x,y \in O,d\left( {x,y} \right) \ge 0 ∀x,y∈O,d(x,y)≥0
• 对称性： ∀ x , y ∈ O , d ( x , y ) = d ( y , x ) \forall x,y \in O,d\left( {x,y} \right) = d\left( {y,x} \right) ∀x,y∈O,d(x,y)=d(y,x)
• 三角不等式： ∀ x , y , z ∈ O , d ( x , z ) ≤ d ( x , y ) + d ( y , z ) \forall x,y,z \in O,d\left( {x,z} \right) \le d\left( {x,y} \right) + d\left( {y,z} \right) ∀x,y,z∈O,d(x,z)≤d(x,y)+d(y,z)

对于如上定义的度量空间，我们可以构建一棵如下的度量树：首先选择一个 O O O中的一个元素 p p p，以及一个距离阈值 δ \delta δ。这一距离阈值自然地将 O O O分成了与 p p p距离小于 δ \delta δ的“近”子集 S n S_n Sn​，和与 p p p距离大于 δ \delta δ的“远”子集 S f S_f Sf​，即

S n = { x ∈ O ∣ d ( p , x ) ≤ δ } S f = { x ∈ O ∣ d ( p , x ) > δ } \begin{aligned} & {S_n} = \left\{ {x \in O|d\left( {p,x} \right) \le \delta } \right\} \\ & {S_f} = \left\{ {x \in O|d\left( {p,x} \right) > \delta } \right\} \end{aligned} ​Sn​={x∈O∣d(p,x)≤δ}Sf​={x∈O∣d(p,x)>δ}​

对于具体这一Shadow Volume的场景，由于包围体并非质点，因此元素之间存在最大距离和最小距离，则我们可以类似地将 O O O分成三份，即近子集 S n S_n Sn​、远子集 S f S_f Sf​和相交子集 S o S_o So​，构建三叉树，即

S n = { x ∈ O ∣ d f a r ( p , x ) ≤ δ } S f = { x ∈ O ∣ d n e a r ( p , x ) &gt; δ } S o = { x ∈ O ∣ d n e a r ( p , x ) &lt; δ &lt; d f a r ( p , x ) } \begin{aligned} &amp; {S_n} = \left\{ {x \in O|{d^{far}}\left( {p,x} \right) \le \delta } \right\} \\ &amp; {S_f} = \left\{ {x \in O|{d^{near}}\left( {p,x} \right) &gt; \delta } \right\} \\ &amp; {S_o} = \left\{ {x \in O|{d^{near}}\left( {p,x} \right) &lt; \delta &lt; {d^{far}}\left( {p,x} \right)} \right\} \end{aligned} ​Sn​={x∈O∣dfar(p,x)≤δ}Sf​={x∈O∣dnear(p,x)>δ}So​={x∈O∣dnear(p,x)<δ<dfar(p,x)}​

如图7所示。

图7. 左图实际几何体的关系，红色代表远物体，绿色代表近物体，黄色代表相交物体，虚线代表距离阈值。右图为左图构建的树，三个子树分别为远子树，近子树和相交子树

球体和胶囊体的角度距离

有了度量空间和度量树的宏观概念后，[8]提出了在球体和胶囊体的空间中度量的具体方法。由于这是一个投影体的空间，因此欧氏距离将不再适用。取而代之的，是[8]提出的角度距离，即在视角下两点之间的角度。假设光源为 O O O，空间内两点 A A A和 B B B与光源的连线为 O A OA OA和 O B OB OB，则 A A A和 B B B的度量距离为 d ( A , B ) = A O B ^ d\left( {A,B} \right) = \widehat {AOB} d(A,B)=AOB

。

假设一个球体，其中心点为 C C C，半径为 r r r，则球内所有点和 点的度量距离均小于 α = arcsin ⁡ ( r ∣ O C ∣ ) \alpha = \arcsin \left( {{r \over {|OC|}}} \right) α=arcsin(∣OC∣r​)。对于胶囊体，情况稍稍复杂。假设胶囊体轴上距离 O O O点最近的点为 X X X，则胶囊体内部的点 P P P和它对应的轴上的点 X ′ X&#x27; X′，则 P P P和 X ′ X&#x27; X′的度量小于 arcsin ⁡ ( r ∣ O X ′ ∣ ) ≤ arcsin ⁡ ( r ∣ O X ∣ ) \arcsin \left( {{r \over {|OX&#x27;|}}} \right) \le \arcsin \left( {{r \over {|OX|}}} \right) arcsin(∣OX′∣r​)≤arcsin(∣OX∣r​)。为了节约计算时间，我们就使用 α = arcsin ⁡ ( r ∣ O X ∣ ) \alpha = \arcsin \left( {{r \over {|OX|}}} \right) α=arcsin(∣OX∣r​)来估计。有了度量方式后，我们就可以定义两个体的近距离 d n e a r d^{near} dnear和远距离 d f a r d^{far} dfar：

d n e a r ( V 1 , V 2 ) = d ( C 1 , C 2 ) − ( α 1 + α 2 ) d f a r ( V 1 , V 2 ) = d ( C 1 , C 2 ) − ( α 1 − α 2 ) \begin{aligned} &amp; {d^{near}}\left( {{V_1},{V_2}} \right) = d\left( {{C_1},{C_2}} \right) - \left( {{\alpha _1} + {\alpha _2}} \right) \\ &amp; {d^{far}}\left( {{V_1},{V_2}} \right) = d\left( {{C_1},{C_2}} \right) - \left( {{\alpha _1} - {\alpha _2}} \right) \end{aligned} ​dnear(V1​,V2​)=d(C1​,C2​)−(α1​+α2​)dfar(V1​,V2​)=d(C1​,C2​)−(α1​−α2​)​

其中， V i V_i Vi​是以 C i C_i Ci​为中心， α i \alpha_i αi​为度量边界的包围体。

构建三叉度量树

构建度量树的过程和快速排序类似，首先，我们确定一个根包围体（作为根节点），以及一个度量阈值 ，然后我们根据每个包围体和根包围体的距离，将它们分为近子集、远子集和相交子集。三个子集分别作为根节点的三个子节点，然后每个子节点递归重复上述步骤。通常，根节点的选择可以是随机的，但[20]证明了选择一个和其他各个包围体距离尽可能大的包围体作为根节点是一个更好的选择。理想状态下的 可以将剩余的包围体均匀地分成两份，因此，它往往被选择为根包围体和其他包围体距离的中位数[21]。

遍历

对于目标点，首先和根节点的包围体求交，如果相交，则说明目标点在阴影中；如果不相交，则计算目标点和根节点的度量距离，如果距离小于 ，则在近子集和相交子集中重复上述步骤；如果距离大于 ，则在远子集和相交子集中重复上述步骤。此过程迭代进行，直到找到相交的包围体或遍历结束。以上步骤可以有三点优化：

第一，如果目标点比整棵子树上所有的包围体距离光源的度量距离更近，则我们就可以直接砍掉整棵子树而不需要做遍历。

图8. 左图和右图分别表示了球状和胶囊状包围体边缘插入的矩形板

第二，当我们对目标点和包围体求交时，我们需要将光线和包围体内部的每个三角形求交，这是相对耗时的。因此，在构建球状或胶囊状包围体时，我们在它们边缘插入两个矩形板，而使得所有三角形面片都落在两个矩形板中间，如图8所示。因此，求交时，我们首先对两个矩形板求交，如果和矩形板中间部分不相交，则就可以直接判定不相交。

第三，总是要搜索相交子集也是一个相对耗时的操作。因此，我们可以对相交子集定义一个最大度量和最小度量，即 ，只有在实际 时，才对相交子集进行遍历。

结果与讨论

[7]渲染的阴影效果如图9所示。图9的上图采用了32K32K分辨率的Shadow Map，下左图使用了33核窗口的PCF方法来防走样，下右图使用了5*5核窗口的PCF方法来防走样，从视觉上，[7]的方法可以渲染得到高清真实的阴影。

图9. [7]的阴影渲染效果

[7]和其他方法的对比如图10所示。传统Shadow Mapping方法只能处理16K*16K以下分辨率的阴影纹理；相比于Arvo的方法，[7]的方法不会随着分辨率的提高而效率显著下降；相比于Sintorn的方法，在同样的分辨率下，[7]的方法往往具有更高的效率。

图10. [7]和其他方法的对比

[8]的结果和PSV以及ShadowLib的结果做了对比，其渲染效果和消耗时间如图11显示。可以看到[8]同样可以对复杂场景进行阴影渲染。相比而言，[8]不太适合处理有不规则或者有大量孔洞的模型，因为Shadow Volume将把空间切得非常碎，从而消耗了更多的时间。但对于单一的表面模型，[8]的效率将高于其他方法。

图11. [8]的渲染效果以及和其他方法的对比

Shadow Mapping和Shadow Volume两种方法出发点十分简单，符合直觉，然而随着模型复杂度的增加、对实时渲染要求的提高、对视觉效果要求的提升、以及新硬件（如更好的GPU）的出现，给原来的方法带来了许多新的突破。两种方法的一个共性是，在几何空间或投影空间中，进行划分和建树，通过分治法的思想，来减少遍历所耗的代价。许多压缩的算法，比如薄壳中间面的计算、四叉树的简化、物体三叉树的定义、不同形状的包围体，都为阴影的计算和渲染起到了不同的作用。

但是，Shadow Mapping和Shadow Volume虽然在寻找光源直接产生的阴影上是精确的，且在许多场景中确实是适用的，但是，在一些材质更加复杂的场景中，比如含有能够反射或折射的材质的场景，光的来源将不仅仅只有光源，还有光的散射、折射和反射。这种情况下，简单优雅的传统方法就将失效，只有采用基于物理的方式，才能得到更加具有真实感的渲染效果。

参考文献

[1] G. S. Hubona, P. N. Wheeler, G. W. Shirah, and M. Brandt. The relative contributions of stereo, lighting, and background scenes in promoting 3D depth visualization. ACM Transactions on Computer-Human Interaction, 6(3):214.242, Sept. 1999.

[2] F. C. Crow. Shadow algorithms for computer graphics. Computer Graphics (SIGGRAPH '77 Proceedings), 11(2):242.248, 1977.

[3] L. Williams. Casting curved shadows on curved surfaces. Computer Graphics (SIGGRAPH '78 Proceedings), 12(3):270.274, 1978.

[4] HEIDMANN T.: Real shadows real-time.

[5] CARMACK J.: Z-fail shadow volumes.

[6] https://www.nvidia.com/docs/IO/8230/GDC2003_ShadowVolumes.pdf

[7] Scandolo, Leonardo, Pablo Bauszat, and Elmar Eisemann. “Compressed Multiresolution Hierarchies for High‐Quality Precomputed Shadows.” Computer Graphics Forum. Vol. 35. No. 2. 2016.

[8] Deves, François, et al. “Scalable real-time shadows using clustering and metric trees.” Proceedings of the Eurographics Symposium on Rendering: Experimental Ideas & Implementations. Eurographics Association, 2018.

[9] WOO A.: The shadow depth map revisited. In Graphics Gems III, Kirk D., (Ed.). Academic Press, 1992, pp. 338–342.

[10] WEISKOPF D., ERTL T.: Shadow mapping based on dual depth layers. Eurographics 2003 Short Papers (2003).

[11] ARVO J., HIRVIKORPI M.: Compressed shadow maps. Vis. Comput. 21, 3 (Apr. 2005), 125–138.

[12] RITSCHEL T., GROSCH T., KAUTZ J., MÜELLER S.: Interactive illumination with coherent shadow maps. In Proceedings of the 18th Eurographics Conference on Rendering Techniques (2007), EGSR’07, Eurographics Association, pp. 61–72.

[13] LLOYD D. B., WENDT J., GOVINDARAJU N. K., MANOCHA D.: Cc shadow volumes. In Proceedings of the Fifteenth Eurographics Conference on Rendering Techniques (2004), EGSR’04, pp. 197–205.

[14] STICH M., WÃˇDCHTER C., KELLER A.: Efficient and robust shadow volumes using hierarchical occlusion culling and geometry shaders. In GPU Gems 3. 2008, pp. 239–256.

[15] CHIN N., FEINER S.: Near real-time shadow generation using bsp trees. In Proceedings of the 16th Annual Conference on Computer Graphics and Interactive Techniques (1989), SIGGRAPH ’89, ACM, pp. 99–106.

[16] GERHARDS J., MORA F., AVENEAU L., GHAZANFARPOUR D.: Partitioned Shadow Volumes. Computer Graphics Forum, Proceedings of Eurographics 2015 (2015).

[17] EVERITT C.: Interactive order-independent transparency, 2001.

[18] AGARWAL P. K., SURI S.: Surface approximation and geometric partitions. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (1994), SODA ’94, Society for Industrial and Applied Mathematics, pp. 24–33.

[19] REEVES W. T., SALESIN D. H., COOK R. L.: Rendering antialiased shadows with depth maps. ACM Siggraph Computer Graphics 21, 4 (1987), 283–291.

[20] YIANILOS P. N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (1993), SODA ’93, pp. 311–321.

[21] UHLMANN J. K.: Satisfying general proximity / similarity queries with metric trees. Information Processing Letters 40, 4 (1991), 175 – 179.