Shadow Mapping 阴影映射

光栅化着色中如何绘制阴影 How to draw shadows using rasterization

• 之前学习的光栅化着色在着色过程中只会局部地考虑该该着色点、光源、摄像机，对于全局的效果如其他物体、甚至该物体其他部分对该点的影响不会考虑
  • 在光栅化着色里，算某个点颜色时，用类似Blinn-Phong 的公式去算漫反射、高光，只看这个着色点本身，光源，摄像机/观察方向，其着色具有局部性，它不会主动考虑其他物体反射过来的光，详情见http://www.skyshin34.com/12329-2/
• 在光栅化着色中绘制阴影的一种方法是Shadow Mapping
  • Blinn-Phong 负责算被照到时的漫反射和高光，Shadow Mapping 负责判断这点有没有被挡住；它们通常一起用，而且都属于直接光照、局部范畴，不是全局光照
• Shadow Mapping本质是一种图像空间的做法，在生成阴影这一步不需要知道场景的几何信息，该方法会出现走样现象，经典的shadow mapping只能处理点光源的情况 An Image-space Algorithm, no knowledge of scene’s geometry during shadow computation, must deal with aliasing artifacts
• Shadow Mapping的核心思想是：如果有点不在阴影里，那么这个点可以被摄像机和光源都看到 Key idea: the points NOT in shadow must be seen both by the light and by the camera

阴影贴图的具体做法 Shadow Mapping

• 从不同视点，光栅化得到的像素覆盖关系和深度并不一样
• 从光源看向场景(在光源处做光栅化)，得到光栅图像(不重要)和深度图(二维数组，每个像素存放深度)

• 从视锥体位置看向场景（在摄像机处做光栅化），得到光栅图像(确定场景中哪些点对相机可见，图中并不是光栅化的追崇处理结果)和深度图(不重要)

• 把摄像机得到的图像中的每个像素所对应的世界空间中物体的点投影回光源处，得到该点在光源处的处存放的深度值，将此数值与该点到光源的距离做比较(注意用的是世界空间中的坐标，即透视投影之前的，通过在VS中把MV变换之后的顶点坐标存起来，直接传给PS取得)
  • if (计算距离 ==深度缓存) 则该点不在阴影里
  • if (计算距离 != 深度缓存) 则该点在阴影里，不能被光源看到的位置但可以被视锥体看到的位置就是阴影的位置

根据对比结果生成shadow map

之前我还想像素本身没有方向，那从像素发射的光线的方向是怎么决定的
但相机到该像素在像平面上的采样点会确定一条视线方向

可视化阴影贴图的过程 Visualizing Shadow Mapping

得到光源方向下的深度信息 The depth buffer from the light’s point-of-view

与shadow map比较深度信息得到阴影区域 omparing Dist(light, shading point) with shadow map

得到有阴影的场景 Scene with shadows

阴影贴图的问题 Problems with shadow maps

• 只能处理硬阴影(点光源) Hard shadows (point lights only)
• 质量取决于阴影贴图分辨率（基于图像空间的技术的问题）Quality depends on shadow map resolution (general problem with image-based techniques)
  很多游戏的场景分辨率很高，但是shadow map的分辨率很低导致阴影走样，产生锯齿
  游戏里设置的阴影质量就是在设置shadow map的分辨率
• 比较深度值是否相等涉及浮点数精度问题，会带来各种问题 Involves equality comparison of floating point depth values means issues of scale, bias, tolerance
• 即使有很多问题，阴影贴图的方法仍是早期3D动画和现在所有3D游戏中的基本阴影技术 Basic shadowing technique for early animations (Toy Story, etc.) and in EVERY 3D video game

软阴影 Hard shadows vs. soft shadows

• 有一定大小的光源照射物体会产生本影(Umbra)和半影(Penumbra)，会形成软阴影
• 如果形成了软阴影，一定是因为光源有一定大小，点光源不会形成软阴影

为什么要引入光线追踪 Why Ray Tracing?

光栅化不好解决全局的效果：软阴影、光泽反射(介于“镜面反射”和“漫反射”之间的一种反射)、间接光照 Rasterization couldn’t handle global effects well: Soft shadows, Glossy reflection, Indirect illumination

• 光栅化速度很快，但是质量相对低 Rasterization is fast, but quality is relatively low
• 光线追踪很准确，但是很慢 Ray tracing is accurate, but is very slow 
• 光栅化容易做到实时，光线追踪经常用于离线应用 Rasterization: real-time, ray tracing: offline
• 光线追踪一帧画面就需要花费一万个cpu小时 ~10K CPU core hours to render one frame in production

光栅化可以实现光线折射的多次追踪，但是很麻烦，并且也不能保证物理上的正确性

Whitted-Style 光线追踪

定义图形学中光线的性质 Light Rays

不同于光在波动学中的定义，对于图形学中的光线简化(并不是很正确、很物理)的定义：

• 光线是沿着直线传播(不考虑波动性) Light travels in straight lines (though this is wrong)
• 光线与光线不会发生碰撞(严格上也是错误的) Light rays do not “collide” with each other if they cross (though this is still wrong)
• 是从光源出发最终到达人眼的(在应用时，由于光路的可逆性，会采用人眼到光源的方法) Light rays travel from the light sources to the eye (but the physics is invariant under path reversal – reciprocity)

当你凝视着深渊时，深渊也在凝视着你——尼采 “And if you gaze long into an abyss, the abyss also gazes into you.” — Friedrich Wilhelm Nietzsche (translated)

光线仅弹射一次的光追

Whitted-Style光追，实际上只考虑了直接光照(包括多次固定能量损失比例的镜像反射，折射，但是没有漫反射的间接光，也就是如果一个光线路径找不到光源则忽略），即直接从光源照射到物体，然后物体反射光进入人眼。它并未考虑间接光照的影响，即别的物体反射的光打到另一个物体上再进入人眼。所以它不能很好的模拟全局光照的效果

算法过程

实际成像过程中，摄像机并不发光，真正发光的是场景中的光源；但由于光路可逆，在光线追踪中通常从摄像机出发发射视线，反向追踪最终到达该像素的光的来源

• 1.从相机出发，对每个像素发射一条主光线（view ray）。
• 2.求主光线与场景的最近交点。
  • 若没有交点，返回背景色。
  • 若有交点，得到交点位置、法线、材质等信息。
• 计算该交点的直接光照。
  • 对每个光源，从交点向光源发射一条阴影光线（shadow ray）。
  • 若阴影光线被遮挡，则该光源对该点没有直接贡献；若未被遮挡，则用局部着色模型（如 Blinn-Phong）计算该光源的直射贡献。
• 若材质具有镜面反射，则生成一条反射光线（reflection ray），递归追踪其返回的颜色。
  • 光线进行了多次弹射，在每一个弹射点都去计算着色的值，最后将所有的值按照一定权重都加到该像素中(考虑能量守恒，比如该例子中碰到球体后反射的光线占60%，折射的光线占40%，但这样近似其实很不准确，后面会用辐射度量学纠正)
  • 之所以说 Whitted-Style 不能完整处理全局光照，是因为它在交点处通常只递归追踪确定性的镜面反射光线和折射光线，而不会像处理漫反射全局光照那样，对半球上各个可能方向的入射/出射贡献进行采样与累积
• 若材质具有折射/透明属性，则生成一条折射光线（refraction ray），递归追踪其返回的颜色。
• 将直接光照、反射贡献、折射贡献按材质权重组合，得到该像素颜色。
• 对所有像素重复以上过程

有几百万个像素就要射出几百万根，所以对并行计算性能要求特别高

• 阴影贴图：从光源视角先渲染一张深度图，再判断当前点是不是比深度图里记录的更远，从而推断它是否被遮挡。Whitted 光线追踪：从表面点向光源发一条阴影光线（shadow ray），如果途中撞到东西，就在阴影里
• 所以二者都在做可见性测试，只是方式不同。可以把阴影贴图看成阴影光线测试的近似替代品

下面解决光线追踪的具体技术细节

光线-物体求交点

射线方程 Ray Equation

一条光线可以由起点(Origin)和方向(Direction)确定 Ray is defined by its origin and a direction vector

光线上的任意一点都可以用一个以t为自变量的函数来表示 Ray equation:

光线与隐式表面求交 Ray Intersection With Implicit Surface

• 与隐式表面相交，则交点p既满足射线方程，也满足表示隐式表面的函数
• 光线与球体相交 Ray Intersection With Sphere

\[ \begin{cases} Ray: r(t) = o + t d,\ 0 \le t < 1 \\ Sphere: (p – c)^2 – R^2 = 0 \end{cases} \Rightarrow (o + t d – c)^2 – R^2 = 0 \Rightarrow t = \dots \]

光线与一般隐式表面相交 Ray Intersection With Implicit Surface

\[ \begin{cases} Ray: r(t) = o + t d,\ 0 \le t < 1 \\ General\ implicit: f(p) = 0 \end{cases} \Rightarrow f(o + t d) = 0 \Rightarrow t = \dots \]

光线与显式表面求交 Ray Intersection With Triangle Mesh

• 对于显式表面的渲染，光线如何与三角形求交很重要 Rendering: visibility, shadows, lighting …
• 通过这个方法也可以判断一个点是否在物体内(点如果在封闭形状内，向外打一条光线，得到的交点数量一定是奇数) Geometry: inside/outside test

最简单的做法：遍历所有三角形 Simple idea: just intersect ray with each triangle

平面方程 Plane equation

一个平面可以由该平面的一个法向量 N与平面上的一个点 p’定义

平面上的任意一点 p可以用以下方程表示 Plane Equation (if p satisfies it, then p is on the plane):

• 求光线与三角形所在平面的交点 Ray-plane intersection
  • 光线与平面相交，则交点即满足射线方程也满足平面方程 \[ \begin{cases} Ray: r(t) = o + t d,\ 0 \le t < 1 \\ Plane: (p – p’) \cdot N = 0 \end{cases} \Rightarrow (o + t d – p’) \cdot N = 0 \Rightarrow t = \frac{(p’ – o) \cdot N}{d \cdot N} \] , \(check: 0 \le t < \infty\)
• 判断该点是否在三角形内(三次叉乘判断符号是否一致) Test if hit point is inside triangle
  • 算出交点还不够(这是和平面的交点)，还要满足这个点在三角形内，才能说这个点是光线和三角形的交点，即还要叉乘判断内外

每个像素点都要发出一个射线与每个三角面进行一次判断，效率极其低下

方法2: MT算法 Möller Trumbore Algorithm

一种更快的方法，直接求出光线与三角形所在平面的交点，他以另外一种方式描述了平面(重心坐标)，通过重心坐标判断是否在三角形内 A faster approach, giving barycentric coordinate directly

\(\vec{O} + t\vec{D} = (1 – b_1 – b_2)\vec{P_0} + b_1\vec{P_1} + b_2\vec{P_2}\)

该方程组有3个式子，3个变量，
等式左边是射线(光线)方程，t是未知量
等式右边是三角形的重心坐标，P0,P1,P2是三角形三个已知顶点，b1 和 b2 是P1,P2的权重，也是交点的重心坐标的两个分量，第三个分量可以1-b1-b2算出
所以未知量一共3个 t，b1，b2
对于有N个式子N个变量的线性方程组可以使用克莱姆法则(Cramer’s Rule)求解

• 对于求出的重心坐标表示的三角形所在平面的一点，\((1 – b_1 – b_2)\)，\(b_1\)，\(b_2\) 都为非负的，则该点在三角形内
  • 因为这表示这个点是三角形三个顶点的一个加权平均，而且权重都不为负、加起来正好等于 1，所以它只能落在三个顶点“围起来的范围里”，也就是三角形内部或边上

轴对齐包围盒 Axis-Aligned Bounding Box

目前求交算法的花销
一根光线与场景每一个三角形都判断一次是否有交点，找到最近的击中点(通过找最小的t)。
计算次数 = 像素个数 x 场景中所有三角面个数 x 反射次数，超级慢
加速方法:用简单的体积包住复杂对象

体积盒 Bounding Volumes

• 一种加速光线与表面求交的方法 将复杂的物体包裹在简单的形状内 Quick way to avoid intersections: bound complex object with a simple volume
• 计算时先计算光线是否与包围盒相交，如果相交再计算与物体的相交 Test BVol first, then test object if it hits

轴对齐包围盒 Axis-Aligned Bounding Box

• 包围盒是三组对面形成的交集 box is the intersection of 3 pairs of slabs
• 我们经常用的一种包围盒是轴对齐包围盒，该包围盒任何一个轴都是沿着坐标轴的 Specifically: We often use an Axis-Aligned Bounding Box (AABB)

光线与轴对齐包围盒求交 Ray Intersection with Axis-Aligned Box

• 对于二维情况下(两组对面)，我们分别看光线何时进入离开x平面和y平面，记录进入时间\(t_{min}\) 和离开时间\(t_{max}\)  ，则光线在这两组对面形成的长方形内部的位置即为前两段分别求出的交集

• 光线只有在进入所有成对的平板时，才进入盒子 The ray enters the box only when it enters all pairs of slabs
• 只要光线离开任何一对平板，光线就会离开盒子 The ray exits the box as long as it exits any pair of slabs
• 因此对于三维包围盒，\(t_{enter} = max\{t_{min}\}\)，\(t_{exit} = min\{t_{max}\}\)，当 \(t_{enter} < t_{exit}\) 时，光线在包围盒内传播了一段时间
• 考虑到光线是一条射线，而不是一条直线 如果 \(t_{exit} < 0\)，则包围盒在光线之后——没有交点 如果 \(t_{exit} \ge 0\)，且 \(t_{enter} < 0\)，则光线的原点在包围盒内——有交点
• 总结：当且仅当 \(t_{enter} < t_{exit}\ \&\&\ t_{exit} \ge 0\) 时，光线与轴对齐包围盒有交点
  • 在平面沿轴放置的情况下，求t的时候可以只用某一轴的信息，而不用整个坐标，计算量更小

AABB(轴对齐)，如何快速求交点(以与x轴对齐的面为例)？

为什么要使用轴对齐包围盒 Why Axis-Aligned?

• 在平面沿轴放置的情况下，求t的时候可以只用某一轴的信息，而不用整个坐标，计算量更小

光线方程：\(\boldsymbol{p} = \vec{o} + t \cdot \vec{d}\) 与x轴对齐的面：\(x = x_0\) 两者求交的方式很简单，明确目的：求 \(\boldsymbol{t}\) 仅看光线方程的x轴分量，公式可以变成 \(p_x = o_x + t \cdot d_x\)，三个已知量，t很容易得出 \(o_x\)：光线起点的x分量 \(d_x\)：光线的方向的x分量 \(p_x\)：目标平面的x值

– 求光线与面 \(x = x_0\) 的交点： \[ t = \frac{x_0 – o_x}{d_x} \] – 求光线与面 \(x = x_1\) 的交点： \[ t = \frac{x_1 – o_x}{d_x} \] — 也可以通过物理的方式记忆这个公式，\(t\) 是时间，\(x_0 – o_x\) 是两个点之间的水平距离，\(d_x\) 是水平方向的速度，时间 = 距离 ÷ 速度。

使用轴对齐包围盒加速光线追踪(不同加速结构) Using AABBs to accelerate ray tracing

均匀空间划分 Uniform Spatial Partitions (Grids)

• 空间被划分为规则的、大小相等的单元格或体素。
• 使用格子的划分方法在大量均匀分布的物体上比较有效 Grids work well on large collections of objects that are distributed evenly in size and space
  该方法在物体分布不均匀、有大量空旷区域的场景中表现不好，会出现”体育场中找茶壶“的问题 “Teapot in a stadium” problem

• 在光线追踪的过程中，只需要判断光线交到的是不是含有物体表面的格子，如果不是的话跳过，是的话和其中的物体求交（假设光线与物体求交很慢，与盒子求交很快）
  • 也可以选择进行光线与单元格内的物体相交检测： 这包括检查光线是否与单元格内的任何物体（例如三角形、球体等）相交。这可以使用光线与物体的相交算法（如光线与三角形的相交检测算法）来实现
• 如何知道一条光线会碰到哪一个盒子？最简单的想法，如果光线向右上方打，那么下一个经过的格子一定在右边或上边，只需要验证这两个格子即可，三维情况下也类似（如何光栅化一条线）

• 不同的格子数加速效果不同，既不能太密也不能太稀疏，经实际应用 #cells = C * #objs，其中C在三维中约为27时加速效果最好

 非均匀空间分割

八叉树 Oct-Tree 

• 先把三维空间切成八份（二维的话如图是四份），对于每一个子节点，再切一遍，以此类推
• 制定停止规则时，一般规定划分到有多少格子内为空的或有足够少的物体时停止
• 人们并不喜欢用八叉树，因为在二维这种划分方法是四叉树，三维是八叉树，维度更高，就是2的n次方叉树，维度更高会越来越复杂

KD树 KD-Tree（需要掌握）

• KD树和八叉树的划分方法几乎完全相同，只不过它每次沿着某一个轴砍开，并且只砍一刀
• 不一定砍正中间，每次节点的划分底下都只有两个子节点，空间被划分成类似二叉树的结果，
• 划分时为了均匀起见，xyz依次划分

BSP树 BSP-Tree 

• BSP树是一种对空间二分的划分方法，它每次选一个方向砍开，它和KD树的区别是它不是横平竖直的划分，而且它会有越高维越不好计算的问题（砍开二维用线，砍开三维用面，维度越高越复杂）

KD树的预处理 KD-Tree Pre-Processing

• 内部节点(如ABCD)存储：
  • 对齐的轴：x、y、z的其中一个
  • 分割的位置：分裂平面沿着轴的坐标
  • 节点指针：指向两个孩子节点的指针
• 叶子节点(如12345)存储：物体对象的列表

KD树的遍历过程 Traversing a KD-Tree

• 光线进入一个节点，判断其是否为叶子结点，
  • 不是叶子，判断光线与其两个子节点是否有交点
  • 是叶子结点，光线与其存放的所有物体求交点
• 递归，直到遍历完所有的相交的叶子结点为止。

KD树的问题

• 给出一个包围盒很难判定它和哪些三角形有交集(因为即使三角形的顶点与包围盒无交点实际也可能相交）
  并且一个物体和很多包围盒都有交集的情况下，会存在多个叶子节点内也是这个原因最近10年渐渐不用KD树的方法了

 物体划分和BVH结构 Object Partitions & Bounding Volume Hierarchy (BVH)

不划分空间，而是划分物体 (目前最常用的求交加速划分策略 )
从物体划分可以避免空间划分的一些问题，所以现在普遍采用BVH结构(BVH不涉及三角形和包围盒求交，避免了一个物体存在多个叶子节点内,但是BVH的划分并没有划分开，包围盒可能会相交，不过做到尽可能重叠少就好，这也是当今一个研究的方向)

根节点依然是最外层大包围盒

BVH数据的存储结构

• 中间节点存放
  1.包围盒
  2.孩子指针
• 叶子节点存放
  1.包围盒
  2.对象列表

BVH的预处理 Pre-Processing

• 找到场景包围盒 Find bounding box

• 递归地将对象集拆分为两个子集 Recursively split set of objects in two subsets
• 重新计算子集的边界框 Recompute the bounding box of the subsets

• 递归，对每个包围盒内部物体重复(1)中步骤，根据一定条件停止(如分到每个子集中不多于5个三角形) Stop when necessary
• 在每个叶子节点中存储物体 Store objects in each leaf node

BVH方法的包围盒有相交，但应当尽可能减少相交区域

• 划分节点的方法 How to subdivide a node? 
• 选一个维度进行划分，如选择最长的轴划分 Choose a dimension to split, Always choose the longest axis in node，这样能让划分出来的空间更均匀
• 取中间的物体(第n/2个三角形，可以使用快速选择算法，是快速排序的一部分) Split node at location of median object

BVH的遍历过程(类似于KD树的方法) BVH Traversal

Intersect(Ray ray, BVH node) {              
    if (ray misses node.bbox) return;       //光线和整个BVH节点不相交，什么也不发生

    if (node is a leaf node)                //如果光线与BVH的叶子节点相交
        test intersection with all objs;      //和节点内所有物体都求交
        return closest intersection;          //返回最近的交点

        hit1 = Intersect(ray, node.child1);   //如果相交的不是叶子节点，那光线与两个子节点都可能相交
        hit2 = Intersect(ray, node.child2);   //分别与两个子节点求交

        return the closer of hit1, hit2;      //返回最近的交点
}

以KD树为例的空间划分 Spatial partition (e.g.KD-tree) 

• 空间与空间之间没有交集 Partition space into non-overlapping regions
• 一个对象可以包含在多个区域中 An object can be contained in multiple regions

以BVH为例的物体划分 Object partition (e.g. BVH) 

• 将对象集划分为不相交的子集 Partition set of objects into disjoint subsets
• 每个集合的边界框可能在空间上重叠 Bounding boxes for each set may overlap in space