Loading... # Lec 13 ~ 14 Whitted风格光线追踪 ## 0. 阴影 Shadow 之前提到光栅化的着色,我们知道这是一种局部的现象,着色的过程中,我们只会考虑着色点自己,光源,以及摄像机,并不会考虑全局的情况。而事实上有遮挡的关系,是会有阴影的。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028011734.png?x-oss-process=image/resize,p_40) 一种实现阴影的解决方法是:**Shadow Map** ### 0.1 Shadow Map Shadow Map 适用于点光源,其关键思想是:**一个点若是被观测到在阴影中,则它必不能看见光源,但它可以看见相机**。 比如这样一张图:中间有两个椭球形挡住了光源 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026152557061.png?x-oss-process=image/resize,p_40) 对于视线观测到的左边的点,我们将其沿着光线方向看回去,发现可以看见点光源,所以这个点不处于阴影当中。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026153415355.png?x-oss-process=image/resize,p_40) 对于视线观测到的右边的点,我们将其沿着光线方向看回去,发现被椭球形阻挡了,无法看见光源,所以这个点处于阴影当中。 ### 0.2 Shadow Map 可视化 如图对于一个相对复杂的场景,左上角有一个点光源(一个白色小点)。左图为有阴影,右图为无阴影。 可以看出,相较于右图,左图木板上有球的阴影,而有的球上也有其他球投射的阴影。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026154107480.png?x-oss-process=image/resize,p_50) 我们从光源的视角看过去,记录并获取深度Z-Buffer: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026155221083.png?x-oss-process=image/resize,p_35) 接着对于视线内每一个像素,我们都让它沿着光源方向看回去,如果与先前 Z-Buffer记录的深度一致,说明光源可以看到这个点,那么说明这个点不在阴影中。 最后得到处于阴影中的部分: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026162548731.png?x-oss-process=image/resize,p_40) ### 0.3 存在的问题 Shadow Map这个方法存在一些问题: - 只适用于**点光源**(硬阴影) - 质量取决于**分辨率**,分辨率不足时会导致阴影的走样 - 存在**浮点比较**(深度比较的时候),会导致误差(比如上图中的模糊的阴影部分) 关于**软阴影、硬阴影**:其实就是当光源存在体积且体积较大时,会出现“半影”的情况,这就是软阴影。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026164131975.png?x-oss-process=image/resize,p_40) ## 1. 光线追踪 Ray Tracing 为什么需要光线追踪? 光栅化不适合处理**全局的信息**。比如软阴影,以及尤其在光线反射了不止一次的时候(间接反射)。 ![反射了多次的场景](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211026175107033.png?x-oss-process=image/resize,p_30) 光栅化相对较快,但同时也相对较慢。 而光线追踪是一种准确的方法,但是却也非常慢。 光栅化适用于实时的场景,而光线追踪适用于离线的场景 ### 1.1 基础光线追踪算法 我们需要对光线做一些假设: 1. **光线一定沿着直线传播** 2. **光线之间无法碰撞** 3. **光线路径可逆** #### 1.1.1 光线投射 Ray Casting ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028005100.png?x-oss-process=image/resize,p_60) 如图,从视线通过图像屏幕像素向场景中投射“视线”(eye ray),碰到的**第一个交点**(对应深度测试)会被投影到这个像素中,而且这个点显然是可见的,因为它“**可以看见光源**”。 这就是只考虑了一次弹射的光线投射。 #### 1.1.2 Whitted风格光线追踪 但是同时,这个物体可能会反射来自其他方向的 “**间接光照**”,比如上图中视线在圆形上反射后,来到了三角形上。在三角形上这个点同样可以接收到光源,将光源反射到圆形上,进而反射到人眼中。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028005133.png) 同样,如果圆形是一个透明体,还可能发生折射。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028005231.png?x-oss-process=image/resize,p_60) > https://blog.csdn.net/qq_38065509/article/details/106299336 下一步将这些所有交点与光源连接,称这些线为shadow rays(因为可以用来检测阴影),计算这些所有点的局部光照模型的结果,将其按照光线能量权重累加(该做法与**递归**过程等价,读者可以看看下方伪代码思考一下),最终得到近投影平面上该像素点的颜色。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028005625.png?x-oss-process=image/resize,p_60) 而这就是一个全局光照模型了,因为不仅仅考虑了直接光源的贡献,还考虑各种折射与反射光线的贡献。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20200524102958371.png?x-oss-process=image/resize,p_70) **Whitted风格光线追踪**模型会将每一个能被照亮的交点所计算出的着色加到视线所经过的屏幕像素上。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211028005431.jpg) ## 2. 光线与物体表面求交 ### 2.1 光线与隐式表面求交 我们先用**光源**与**光线方向**在数学上定义光线,其本质是一个射线: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028204148348.png?x-oss-process=image/resize,p_30) 接着我们以球为例,来探寻如何求光线与球体表面求交点 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028204436465.png?x-oss-process=image/resize,p_30) 一个交点的数学意义是:同时满足光线等式与球等式,故可以将光线等式代入球等式的 $p$ 中,求出 $t$: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028210557524.png?x-oss-process=image/resize,p_35) 我们将其推广到,对于所有给定了表面点与点关系的物体表面(隐式表面),都可以用这种方法求解交点: - 有光线等式: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028211338973.png?x-oss-process=image/resize,p_30) - 有隐式表面等式: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028211426518.png?x-oss-process=image/resize,p_30) - 将光线等式代入其中: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028211450870.png?x-oss-process=image/resize,p_30) - 求解得出 $t$,最小的t值即为最先相遇的交点 ### 2.2 光线与三角形面求交 对于大部分的显式曲面,实际上都是由很多的三角形面组成。所以与显式表面求交可以**等价于是与三角形面求交** 而对于光线与三角形求交这个问题,我们可以将其分解为: - **求光线与三角形面所在平面的交点** - **求这个平面上的交点是否在这个三角形面内部** ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028213047716.png?x-oss-process=image/resize,p_30) 我们先数学上定义平面: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028213211208.png?x-oss-process=image/resize,p_30) $$ p:(p-p')·N=0 $$ 其中$p'$ 是平面上任意一点,$N$是平面的法向量,以为法向量与平面上任意一向量垂直,点积为0。代数可以表示为:$ax+by+cz+d=0$ 接着就可以像隐式表面一样求交点: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211028214531314.png?x-oss-process=image/resize,p_30) 然后可以利用重心坐标([重心法](https://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html))判断交点是否在三角形内。 有一种更快的找到解的Moller Trumbore算法: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20211029012331.png?x-oss-process=image/resize,p_40) 利用**重心坐标**,直接将三角形内的点用变量 $b_1, b_2$ 表达出来,然后将其与 $t$ 一起利用克莱姆法则求解线性方程组。 ## 3. 加速求交 光线追踪相比普通光栅化,明显可以提升图像的质量。但是问题也很明显,就是开销大,速度慢,因为对于每一个像素都要将这条光线与 **所有的三角形面** 求交,更不必说还要考虑反射、折射。这在复杂的场景里面是不可接受的。为此,有多种加速的方法 ### 3.1 轴对齐包围盒 Axis-Aligned Bounding Box 与先前提到的光栅化包围盒一样,对于一个包围盒:如果光线与这个物体的包围盒不想交,必然也不会和这个包围盒内的物体相交,就可以减少很多不必要的运算量。 **轴对齐包围盒(AABB)**是**沿着 x/y/z 轴** 的三对平面将物体包围起来的一个立方体 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/20200528131009255.png?x-oss-process=image/resize,p_50) 接着我们以二维的视角对这个包围盒与光线求交,这个可以推广到三维空间,是一样的道理 我们对其中每一对平面都将之与光线求交点,会得到 3 对 $t$ 值(即使t为负值) 在下图的二维图像中有2对,但是图三中的那($t_{\min},\ t_{\max}$)对才是我们需要的(进入盒子的时间与离开盒子的时间) ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211029155834779.png?x-oss-process=image/resize,p_40) 那么我们要如何确定这对 $t$ 值?核心思想:只有同时进入3对平面内,才算是进入了盒子,一旦离开了任意一个对平面,就是离开了盒子。 所以具体的方法是: - 求出两个变量 进入时间 $t_\rm{enter}$ 和 离开时间 $t_\rm{exit}$ $$ \begin{align} t_\rm{enter} = \max(t_{\min1},\ t_{\min2},\ t_{\min3})\\ t_\rm{exit} = \min(t_{\max1},\ t_{\max2},\ t_{\max3}) \\ \end{align} $$ - 如果 $t_{\rm{exit}} < 0$ 说明光线从一开始就已经离开了,必不可能有交点 - 如果 $t_\rm{enter} > t_\rm{exit}$ 说明光线不存在同时在三个面内的时刻,即不存在交点 - 综上,有交点的条件即为:$t_\rm{enter} < t_\rm{exit}\ AND \ t_\rm{exit}>0$ - $t_\rm{exit}>0$ 但 $t_\rm{enter} < 0$ 的情况是光线一开始就在包围盒内 之所以会用与轴平行的包围盒,是因为交点便于求交点($t$) 我们先假设**光线与包围盒求交比光线与物体求交更快**。基于这个假设,我们可以先让光线与包围盒求交,再与包围盒内的物体求交。 ### 3.2 均匀空间划分Uniform Spatial Partitions (Grids) 我们可以将一个场景的包围盒,均匀的划分成数个包围盒: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101175057360.png?x-oss-process=image/resize,p_30) 一道光线从场景中穿过,我们只寻找与其相交的包围盒,判断这个包围盒内是否有其他物体。如果有,再判断光线与这个物体有没有相交。 比如下图中,在深蓝色的格子与一个物体相交,在此之前有2个有物体的包围盒,但是并不与物体相交。 关于怎么寻找相交的包围盒的问题,并不需要与所有的包围盒进行判断,我们可以用光栅化一条线时用的方法(**bresenham**)来做 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101175252883.png?x-oss-process=image/resize,p_30) 关于划分的数量选择: - 如果划分的包围盒特别少:几乎没有加速效果 - 如果划分的包围盒特别多:会有很多 **多余的、没有物体的 无效包围盒** 影响效率 关于使用场景: - 这样的方法适用于场景内均匀分布的很多物体的情况 - 对于一个空旷的场景,物体与物体之间距离很大,这样的方法效果就会很差(与上同理) ### 3.3 KD-Tree 空间划分 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/2020052811195387.png?x-oss-process=image/resize,p_70) 有3种常见的空间划分方法: - **Oct-Tree**,也就是八叉树,会将一个场景均等地划分成8块,对于每一个子节点,继续划分成8块,如此递归下去,直到达到终止条件 - **KD-Tree**,其每次将空间划分为两部分,且划分依次沿着x轴,y轴,z轴,即如图中所示,第一次横着将2维空间分为上下,第二次再竖着将上下两个子空间分别划分为左右部分,依次递归划分,终止条件与八叉树类似 - **BSP-Tree**,与KD-Tree类似,但是不再是横平竖直地沿着轴去分割 接下来详细介绍KD-Tree ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101184300388.png?x-oss-process=image/resize,p_30) 如上图所示,KD-Tree划分的过程像一个二叉树。内部节点不存储物体,叶子节点才存储物体信息 在下图中,有一道光线从场景中穿过,第一步是判断这个光线与整个场景的包围盒(A)是否有相交 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101184519970.png?x-oss-process=image/resize,p_30) 如果相交,接着判断光线与其2个子区域(1,B)是否相交 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101201033869.png?x-oss-process=image/resize,p_30) 如果有相交,且该节点**非叶子节点**,则继续对子空间进行**递归操作**,具体过程省略 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101202531750.png?x-oss-process=image/resize,p_30) 如果有相交,且该节点为**叶子节点**,则与其内所有**物体判断是否有交点** ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101202746448.png?x-oss-process=image/resize,p_30) - **优点**: 利用KD-Tree的结构来构建AABB的好处是倘若光线与哪一部分空间不相交,那么则可以直接省略该部分空间所有子空间的判断过程,进一步提升了加速效率 - **缺点**: 缺点是判断包围盒与物体的是否相交较难,因此KD-Tree的建立过程不是那么想象的简单,其次同一个物体可能被不同的包围盒同时占有,在每一个包围盒内都要重复存一次这个物体 ### 3.4 BVH & 物体划分 **BVH(Bounding Volume Hierarchy)**是业界内广泛应用的方法。BVH划分的不是空间,而是**物体** ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101205014599.png?x-oss-process=image/resize,p_40) 如图,将一个包围盒内的物体先划分成两部分,再重新求他们的包围盒 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101205104784.png?x-oss-process=image/resize,p_40) 同样,继续递归操作,直到达到终止条件。 ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101205810520.png?x-oss-process=image/resize,p_40) ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101205839311.png?x-oss-process=image/resize,p_40) 这样的划分方法,可以保证**每个物体只会出现在一个包围盒当中**,避免了KD-Tree的缺点 但是它同样有一个小缺陷,它所**划分的物体的包围盒可能会有交错**,不过影响并不大 关于如何划分包围盒的方法: - 永远沿着包围盒最长的轴划分 - 选择一个中位物体,使得左右两边的物体数量尽可能相等 (举例:选定一个轴,然后将所有包围盒内的三角形面的重心在这个轴上的坐标进行排序/用堆取中位数,这个三角形面当做中位物体) - ...... 最后得到一个BVH的伪代码参考: ![](https://irimskyblog.oss-cn-beijing.aliyuncs.com/content/image-20211101210913822.png?x-oss-process=image/resize,p_60) 最后修改:2021 年 11 月 10 日 02 : 23 AM © 允许规范转载