【GAMES-202实时渲染】2、软阴影02（VSM、Moment Shadow Mapping、SDF距离场软阴影）

1 PCF的数学原理：Filter / Convolution

\qquad 在shadow map上应用PCF算法做深度测试的时候，不是与单个纹素作比较，而是周围一圈$n\times n$个记录的深度是否遮挡住了该着色点，最后进行加权平均得到一个(0,1)的值，作为该着色点可见性（阴影软硬程度）的描述。

这个算法的过程，在数学上称为卷积

可以用这个简化的公式表示：$[w\ast f](p)=\sum _{q\in N(p)}w(p,q)f(q)$

符号	意义
$f(p)$	返回着色点p实际深度与shadow map上的深度的比较结果，非0即1
$[w\ast f]$	$\ast$为卷积符号，表示对函数$f$应用一个卷积
$[w\ast f](p)$	被卷积后的函数$f$在传入着色点$p$后应该返回什么值
$q\in N(p)$	p点附近的一个点q
$w(p,q)$	q点对应的权值，可以根据q到p的距离得到
$\sum _{q\in N(p)}w(p,q)f(q)$	shadow map上，把p邻域的一个点q深度与p实际深度作比较(非0即1)，再乘以对应的权值，然后对每个q的加权后的结果进行相加，得到$[0,1]$内一个数作为着色点的visibility返回

PCSS更详细的公式是这个：

$$V(x)=\sum _{q\in N(p)}w(p,q)\cdot {\chi }^{+}[D_{SM}(q)-D_{scene}(p)]$$

符号	意义
$V(x)$	Visibility 着色点可见性,从0到1变化 0为纯黑色，1为不在阴影内
${\chi }^{+}$	符号函数，LaTex符号：\chi，读音“铠”，很多人也读作"卡"，卡方分布${\chi }^2$也是这个符号。自变量大于0返回1，小于0返回0
$D_{SM}$	q点在shadow map中记录的深度
$D_{scene}(p)$	场景中着色点p的实际深度
$w(p,q)$	q对应的权值

有了严谨的数学表达式，我们可以严谨的定义一下错误的理解PCSS所对应的数学表达式是什么样的

• PCF不是filtering shadow map，即对周围深度做平均，然后用平均深度跟着色点p深度进行比较，这样结果必然非0即1
  $V(x)\ne {\chi }^{+}\{[w\ast D_{SM}](q)-D_{scene}(p)\}$
• PFC也不是在最终生成有锯齿的硬阴影的图像上，做filtering
  $V(x)\ne \sum _{y\in N(x)}w(y,x)V(y)$，x对应图像中的某个点，y是x附近某个点，V是图像

2 PCSS回顾

• Step1：Blocker Search
  \quad\ \:  对于每个着色点p，找到shadow map上一块区域，计算遮挡物的平均深度，把区域所有texel都找一遍，判断是不是遮挡物，如果是遮挡物，则累加，最后除以遮挡物的个数。
• Step2：Penumbra Estimation
  \quad\ \ \:   公式算出W_半影，根据这个得到filter size
• Step3：Percentage Closer Filtering

这些步骤里，哪些特别慢？

• 第1、3步，每个着色点都要遍历深度图上一大片区域的纹素，并且这两步里面都要这样遍历，就很费性能
• 想要阴影够软，需要大的filter size，大filter size 导致计算缓慢。

工业界较多的做法是在该区域里随机采样(稀疏采样)，而不遍历区域中每一个像素，这样虽然快，但是结果会比较多噪点。如果要修复这些噪点，还可以用一些图像空间的方法来降噪。这一块技术在实时光追的课程中会说到

另一种比较好的解决方式，是VSSM

---

3 Variance Soft Shadow Mapping(VSSM)

\qquad 方差软阴影映射：是对PCSS算法的改进，可以更快得出近似的结果

3.1 VSSM对PCF的优化

PCSS中的 Percentage Closer Filtering目的是什么？

• 找到着色点对应到shadow map上周围某区域中，比该着色点深度更浅的点的比例是多少
• 也就是，在搜索区域内有多少比shading point深度更浅的像素
• 类比于找到这场考试里比我成绩更好的学生们，看我的排名占百分之几

---

我想知道我的排名，但我又不想挨个看每个学生的成绩，咋办?

• PCF原本的做法，遍历每个学生，相当于生成一个直方图如下，成绩比我好的占比多少一目了然
• 不那么准确但特别近似的方法：得到一个正态分布曲线（normal distribution）
  定义正态分布需要两个条件：均值（期望）、方差
  均值决定了波峰在哪，方差决定区间范围
  

---

VSSM的第一个核心思想Key idea： 快速计算得到一个区域的深度均值(mean)和方差(variance)

(1) 求均值(Mean/Average)

• MIPMAP（效果不如SAT，但是还不错）
• Summed Area Tables(SAT)

(2) 求方差(Variance)

• $Var(X)=E(X^2)-E^2(X)$ —— 借助数学公式，通过两种期望值，就能求得方差

$Var(X)$	X区域的方差
$E(X^2)$	X区域所有深度值的平方的期望（这就需要额外用一个通道存放$d^2$）
$E^2(X)$	X区域的所有深度值的期望的平方（用原本的shadow map即可算出）

所以求方差需要额外对深度图中每个深度额外开一个通道，存放平方深度

(3) 根据均值和方差，得到呈正态分布的PDF —— 实际上不需要这一步(有切比雪夫不等式可跳过此步骤)

• 欲得到shadow map 上某块区域上比着色点更近的纹素的百分比
• 计算概率密度函数PDF(Probability Density Function)阴影部分面积。
  

PDF：用某一区间上的积分来刻画随机变量X落在这个区间中的概率
CDF：CDF求导就是PDF，PDF对某区域求积分 == CDF对某块区域做减法，即${\int }_{-3}^{-1}PDF(x)dx=CDF(1)-CDF(-3)$

要得到上面的概率密度函数(分布)，还是挺麻烦的，而且相对来说还是"过于精确"，从而下面VSSM算法又找到一个经典不等式

---

3.1.1 切比雪夫不等式(Chebychev’s inequality)

$$P(x>t)\le \frac{\sigma }{{\sigma }^2+(t-\mu {)}^2}$$
$$\mu :mean{\sigma }^2:variance$$

• 通过这个不等式，可以得到：随机变量取值超过 $t$ 的概率，即超过t的数量占比多少
• 不需要知道该随机变量分布长什么样（实际上正不正态都不太重要），只需要知道该分布的期望和方差
• 也就是上面第(3)步没用了

这个不等式用在PCF上，直接可以得知深度超过t的texel的百分比P，P直接就是该点的Visbility值

这个"约等式"，有个条件，就是t必须在均值的右边，否则值是不准的。但在实时渲染里的实践中，就算在左边，效果依然很好

2.1.2 VSSM加速PCF的步骤总结

• 生成shadow map的同时，生成一张存放深度的平方的平方深度图(Square depth map)。两个通道分别存放即可，不需要额外一张texture，很划算
• 求深度图上某区域的均值，MipMap，不用循环，O(1)
• 求平方深度图上某区域的均值，依旧MipMap，O(1)
• 知道两个均值，根据公式$Var(X)=E(X^2)-E^2(X)$得到方差
• 根据切比雪夫不等式$P(x>t)\le \frac{\sigma }{{\sigma }^2+(t-\mu {)}^2}$，直接求出该点可见性Visibility

现在来看，是否完美解决了第三步PCF特别慢的问题？—— 是

• 生成多张MipMap、一张平方深度图，开销很小，因为GPU对于一张图生成MipMap速度特别快，可以认为几乎不花时间，另一个没有介绍的(SAT)的生成相对慢一点
• 不需要循环遍历区域所有像素，然后一个个的比较，最后加权求和，很大程度的减少了计算量

---

PCSS第一步：Blocker search特别慢的问题还没解决

Blocker search

• 求平均的遮挡物的深度，把区域所有texel都找一遍，判断是不是遮挡物，如果是遮挡物，则累加，最后除以遮挡物的个数，如着色点深度为7，则应该计算shadow map上蓝色部分的深度作为平均遮挡物深度
  
• 这一步实际上不是区域上所有纹素的平均，而是那些z<t的纹素记录的深度求平均，很慢

3.2 VSSM对Blocker Search的优化

目标：得到遮挡物的平均深度 $Z_{occ}$

Key idea：搞些小手段，弄到非遮挡物的平均深度$Z_{unocc}$

首先两者一定满足这个等式
$$\frac{N_1}{N}{Z}_{unocc}+\frac{N_2}{N}{Z}_{occ}=Z_{Avg}$$
$N_1$：非遮挡物纹素个数，$N_2$：遮挡物纹素个数，$N$：总的区域纹素个数，$Z_{Avg}$：总的区域深度均值

• 这两个权重刚好又能用切比雪夫近似（用近似的方法得到深度大于/小于目标值t的点所占比例）
  $$\frac{N_1}{N}=P(x>t)，\frac{N_2}{N}=1-P(x>t)$$
• 整个区域的平均深度$Z_{Avg}$可以通过MipMap范围查询得到
• 我们想要得到$Z_{occ}$，则还有个未知量$Z_{unocc}$没算出来，
• 大胆近似：$Z_{unocc}=t$ ，结束

$Z_{unocc}=t$，这个近似看起来就很疯狂了，但是也还是有道理，就认为所有不能遮挡着色点的场景点都分布在跟着色点同一个平面，这样肯定会在某些场景出现问题，但基本上可以忽略。总而言之大胆假设，渲染图看起来是对的，他就是对的！相比于那一丁点误差，极大的节省了计算量，是非常划算的。

---

VSSM能够做到这个效果

VSSM效果非常好，但是工业界依然更倾向于随机采样，得到有噪点的阴影结果，因为稀疏采样相对VSSM来说还是更快，噪声可以在成图之后，运用图像处理的一些技术去降噪

VSSM可以理解为PCSS的加速版本，虽然现在大多数还是用PCSS+区域随机采样做软阴影，但是VSSM依然值得学习，因为它所用到的近似的思想是非常值得学习的，妙蛙。

---

3.3 范围查询（MIPMAP和SAT）

• VSSM的关键是切比雪夫近似，切比雪夫近似的关键是均值
• 因此VSSM算法最关键的点：快速获得某区域均值
• 范围查询的这两种方法，都是一种 预计算
  • MIPMAP：简单、速度快，不准
  • SAT：准

3.3.1 MIPMAP

• 特点：快速、近似、正方形
  
• 因为是插值，所以不准确。当查询区域在某层上不太对齐像素格的时候，需要双线性插值。
• 同时当查询范围为方形但不是 $2^n$ 时，还要再进行一次层间插值，即三线性插值
• 如果查询区域是长方形区域查询，还得加入各向异性过滤
• MIPMAP怎么搞都是有误差的，相比之下如果查询范围小的话，误差可以接受

3.3.2 SAT（Summed Area Table）

• 它可以得到百分百准确范围查询结果，但是计算花销肯定比MIPMAP要多
• 它是与前缀和(prefix sum)算法息息相关的数据结构
• 均值 = 总和 / 个数，因此范围求均值其实就等价于范围求和

（1）一维前缀和算法

• SAT这种数据结构实际上就是对输入的数组做一个 预处理。

• 先花费O(n)的时间从左到右走一遍，同时做累加操作，并存入数组SAT中。

• 最后SAT上任意的一个元素就等于原来数组从最左边的元素到这个元素的和。

• 此时我们要求某区域（比如上面数组第4个到第6个元素）的和，直接用SAT数组的第6个元素-第3个元素

（2）二维前缀和算法

一个轴对齐的矩形，蓝色矩形内元素总和 = 左上角大绿色矩形 - 左边一个长条矩形 - 上边长条矩形 + 左上角小矩形

• 等式右边的四个矩形，共同的特点：都从左上角出发
• 跟一维一样，这里也可预计算一个SAT表，每个元素存放的是左上角到当前元素的和
• 求任何区域的和，只需要查表4次（图中白点）就可以得到精准的区域和。

图中的两个坐标轴可以不用看，把左上角当做数组起点。也可以就把数组起点放在左下角，重新推一遍上述的计算过程。

二维SAT建立步骤（妙）

• 对数组每一行建立SAT，数组的每个元素存放的是当前行从左边第一个元素到当前点的和
• 在第一步生成的SAT表上，再对每一列做累加，生成另一个张SAT
• 此时的SAT每个元素，存放的才是数组起点到当前点的一个矩形区域内的元素总和
• 乍一看复杂度为$O(n^2)$，但是如果算法写得好，充分利用GPU的并行计算，还是挺快的

GPU对于算法的复杂度，不能直接断定$O(n^2)$的算法一定比$O(n)$更好，还要考虑并行度

4 Moment Shadow Mapping

这是非常前沿的算法，因为图像空间的降噪的盛行，PCSS重新上位，这个算法也渐渐没人用了实现起来也相对比较麻烦。

4.1 VSSM算法的局限性

VSSM做了很多假设，因此结果相当近似且有局限性

• 上图所示，VSSM算法在类似树枝这种特别多且复杂的场景时，假设是正态分布确实可以得到比较好的近似结果
• 如果是右边这种场景就不行，着色点连向光源在shadow map上周围的像素记录的深度分布，就应该接近三个遮挡物深度，形成三个峰值。那么深度分布采用正态分布就特别不准确

现在考虑如下蓝色深度分布错用红色正态分布进行VSSM计算

• 不是正态分布强行按正态分布算就会出现漏光or过暗的结果，因为切比雪夫计算结果不准确(偏大或偏小)。阴影某些地方过暗可以接受，但是漏光、偏白就接受不了
• 比如上图这种情况，错误的用红色曲线代替蓝色，本来蓝色部分，深度大于t的假设为30%，结果红色计算结果是50%，阴影就变白了

漏光(Light leaking)

• 很明显这辆车子的深度并不是正态分布，因为车是镂空的，从漏光处连向光源，在shadow map上的周围一圈的深度基本击中在车的底板构件的深度值附近以及车顶的框架深度。强行用正态分布来计算，就会出现漏光
• 但是过暗基本看不出来，可以忽略
  

4.2 矩(Moment)

为了解决VSSM的其中一个问题：深度分布描述不准确

提出这种方法：引入更高阶的moments(矩)来得到更加准确的深度分布情况

Moments

• 定义五花八门
• 最简单的一种：就是记录一个数的1,2,3,4…n次方，$x,x^2,x^3,...$记录多少次方就表示保留多少矩
• VSSM记录了深度图的1、2次方，就等于用了前两阶的矩
• 这样多记录几阶矩就能得到更准确的结果
• 保留前m阶的矩，就能生成台阶数为m/2的阶跃函数，可以看做类似于泰勒展开式一样，项数越多，拟合得就越好，一般来说4阶就够用。
• 下图可以看到，绿色曲线就是4阶矩对应的阶跃函数，可以很好的拟合PCF曲线，如果是3阶、2阶效果就很差，2阶就是VSSM用的正态分布PDF对应的PCF的曲线
  

Moment shadow mapping VS Variance soft shadow mapping
优势：非常好的结果、修复漏光现象
劣势：多一些存储空间，多一些计算量

最后，怎么通过前4阶矩得到 2个台阶的阶跃函数，请参考Peters的论文(发表于2015年)

---

5 距离场软阴影 Distance field soft shadows

SDF做软阴影效果不错，但是下面还是系统的介绍一下SDF的概念和一些主要应用

5.1 有向距离场SDF(Signed Distance Field)

在之前几何章节中已经简单的学过有向距离场 SDF（Signed Distance Field），具体可以参考GAMES101笔记。有向距离场 在下文中就简称为距离场、SDF、距离函数

---

距离函数 ：在空间中任何一点，给出其到物体边界的最小距离（可以带符号(方向)，物体内部为﹣，物体外部为+）。

• SDF在之前是用来更好的描述复杂平滑的几何模型的
• 比如已知两个物体的SDF，我们将两个SDF进行混合操作得到一个新的SDF。这个新的SDF中距离为0的点组成了新物体的边界，并且非常精准

距离函数可视化

• 左图：直接把二维面上的SDF记录的每个点的值打印出来，A的内部(负数)显示成黑的，外部则根据其数值0到1，黑到白
• 右边：类似于等高线的等值线，同种颜色的线上的所有点到A边界的数值相同
  

帮助理解SDF的例子：blend一个运动的边界

(1) 下图描述的是A、B为物体在两个时刻上的不同位置，我们想要得到在AB的中间时刻他的位置在哪里

• 假如在AB时刻分别拍一张照片，黑色表示物体，黑白交界处为物体的表面。对两张图每个像素做线性插值Lerp(A,B)，得到的是中间一块灰色带的错误结果，这并不是我们想要的结果，正确结果应该是物体运动到整个图片的正中间位置。
  

(2) 用 有向距离场SDF 来表示物体在A、B两个时刻的状态

• 把AB分别用SDF(A)，SDF(B)表示出来后，依然是做线性插值，但是是对两张图任意一个点的SDF值做插值,就能够得到正确的预期的结果
• 之后再把图像恢复成物体在世界中的表示即可（SDF(A)可以看做是计算A的距离场，$SD{F}^{-1}$就是其逆运算，通过SDF求得原本物体的几何表示）
• 如果记A的时刻为0，B时刻为1，则图中表示的是t = 0.5物体所在位置，想让其运动取不同的t做多次插值就行了。
  

距离场优点：不用关注物体之间的拓扑关系，就能做很好的blending

学术前沿：SDF背后的理论与最优传输(Optimal Transport)密切相关，在渲染中的应用也是一个研究方向。

5.2 SDF的应用

5.2.1 Ray Marching

Ray Marching：已知场景的SDF，用一根光线与SDF所表示的隐含表面求交，也叫 sphere tarcing

• 其背后一个非常巧妙的思想：任意一点的SDF我们是已知的，比如在$P_0$ 点时，$SDF(P_0)$为半径做一个圆，在这个圆内无论是哪个方向前进，只要不超过这个半径，都不可能碰到其他物体。也就是说，SDF其实相当于定义了空间内每一个点的 安全距离
  
• 因此在做 Ray SDF Tracing 时，假设光线在点$P_0$发出，朝着图中所示的方向前进，我们知道半径在$SDF(P_0)$之内不可能碰撞，因此可以不做任何碰撞判断，直接移动到$P_1$处。在$P_1$点又能查到$SDF(P_1)$，又可以走一段安全距离，一直走到某一个点的SDF足够小，代表足够接近物体表面，可以开始求交，或者某一方向走了非常远仍然没有找到足够小的SDF则舍弃这条光线。因此停止递归的条件有两个：SDF小于某个值 or 传播距离大于某个值

场景中，每个物体都有一个SDF，描述该物体在当前场景中的隐含边界。有多少物体就要存储多少个SDF，这是一种非常大的存储量消耗，因此如何压缩其存储空间就是一个热点研究方向。

---

5.2.2 SDF生成软阴影

这个方法不准确，但是还不错，主要思想：通过SDF得到一个大概的 遮挡百分比，用1减去它就得到visibility项了，具体做法：

• 将安全距离的概念进行延伸，在任意点的sdf可以获得一个 安全角度
  
• 我们取着色点P 往图示方向发射光线，可以获得光线上的某一点a的安全距离SDF(a)，在这个距离内不会有碰撞 等价于 P新生成一条光线射向圆内任意一点都不会碰撞，而新旧光线夹角就是 安全角度
• 比如：从P点连向光源(点光源就行)，在这个方向上所有的点安全角都蛮大的，说明几乎不被遮挡，Visibility项约为1。反之被遮蔽的可能越高。
  • safe angle越小，阴影越深。
  • safe angle越大，阴影越浅。

---

安全角度的计算

• 我们以o为起点，沿一个方向做Ray Marching，经过每个点都会得到一个安全距离SDF( P )，以安全距离为半径作圆，求切线，然后切线与光线的夹角就是每个点的安全角度
• 取所有点计算出来的安全角 最小 的一个 作为这条光线的 safe angle
  
• 具体计算方法，以P1为例简单的反三角函数就能算出
  ${\theta }_1=arcsin(\frac{SDF(P)}{|p-o|})$
  但是反三角函数计算量挺大的，在shader中我们非常不愿意看到
  
• 近似： 用$\frac{SDF(p)}{|p-o|}$作为安全角度的近似值，对其乘以k，再限定到1以内，其结果就是visibility的值，k作用是控制阴影的半影范围的。
  k越大，SDF不需要很大就能让结果接近1，可见性从0到1变化快，半影范围小，阴影越硬
k越小，则需要很大的SDF才能接近1，半影范围大，阴影越软
  

---

SDF做软阴影的优缺点

• 优点：SDF是一个快速的高质量的软阴影生成方法(比shadow map快)
• 缺点：需要极大的存储空间、预计算SDF的时间很长、动态的物体需要每帧重新计算SDF、SDF物体不好贴纹理