引言
GAMES101现代图形学入门是由闫令琪老师教授。今天我们来讲光线追踪的第二部分，包括加速结构和辐射度量学。
Announcements
Grading of resubmissions — we’re working on that
GTC news: DLSS 2.0
GTC news: RTXGI
Personal feeling
- Offline rendering techniques will soon become real-time
- Current real-time rendering techniques will still be useful
Next lectures won’t be easy
Using AABBs to accelerate ray tracing
Uniform grids
假如场景非常复杂，我要去用光线和场景中任何一个物体求交。现在我已经知道如果可以把一些物体包围在盒子里，那我先跟盒子求交再考虑是否需要和物体求交，这里就是直接应用这样一个思想：
Preprocess – Build Acceleration Grid
- 我先找到这么一个场景，在做光线追踪之前对场景做预处理，把场景的包围盒找出来，当然图中的包围盒不是最小的包围盒。
- 找到包围盒后把盒子分成一堆格子，图中二维的场景分解出二维的格子：一个个小方块。
- 划分格子后我们判定哪些格子里面可能有物体，与物体相交的这些格子我们标记为某个类型，图中涂成了灰色。
Ray-Scene Intersection
在预处理之后我就知道在这些场景里有一些格子，中间可能有一些物体。那么现在我就可以做光线追踪，光线从左出发朝右上角去，它会率先和第一个格子相交，发现有交点但格子里没有东西，所以不用做与实际物体相交这么一个操作（这里我们假设光线与盒子求交是非常快的，与实际物体求交是非常慢的）。
当光线到中间蓝色格子时光线与它有交点，而且格子里面有物体，这说明光线有可能与格子内物体相交。这时我们再做一个光线与物体的求交，发现与物体没有交点；而当光线在深蓝色格子时，发现光线与物体相交，那我就找到了一个交点，同样道理我们可以找到所有交点。
加速结构的原理其实就是多做光线与盒子求交，尽量避免光线与物体求交。
Grid Resolution?
在格子稀疏的极端情况假设我们把整个空间划分为1*1的格子，基本和不划格子一模一样不会有任何加速的意义。
另一种极端情况是格子太密集，意味着我们要做好多次光线与格子求交，效率下降。
正常情况下人们发现了一些实际应用效果不错的规律，划分格子#cell的数量可以通过常数C与物体数量#objs相乘得到，在三维空间中C大约为27。
Uniform Grids – When They Work Well
Grids work well on large collections of objects that are distributed evenly in size and space.
格子提供的加速效果在上例展示的比较好，在这个场景各个地方都有一些几何的物体，它们在场景中分布比较均匀，这样的场景格子的加速结构效果比较好。
Uniform Grids – When They Fail
“Teapot in a stadium” problem.
对于这个场景比上个场景相对空旷，好比在一个大的运动场光线经过好久才与实际格子相交，但在此之前我们进行了大量关于格子的无效判断，所以如果场景分布的并不均匀，格子方法可能并不奏效。
Spatial partitions
格子的大小个数是相同的，但事实上在一些稀疏的地方我们不需要这么多格子，我们可以在空旷的地方用大一些的格子，而在一些密集的地方再用小一点的格子。
Spatial Partitioning Examples
空间划分这个问题很早很早就有了，在计算几何上大家有各种各样的研究。图形学作为一个应用，在上面有三种空间划分结构：Oct-Tree八叉树（二维情况是四叉树），通过这种方式我们把空间切成一些不均匀的块并且把它组织成了树结构。
但人们不喜欢用八叉树，在其他维度的情况下八叉树的表现不是很好。人们发明了一种办法能让空间得到划分并且与维度无关，这就是KD-Tree。它与八叉树几乎完全相同，只不过每一次它找到格子总是沿着某一个轴把它砍开，如图第一次切分形成上下两块，对上下两个块再分别竖直砍一刀，左边和右边继续做下去水平砍一刀……整个空间就被划分成类似于二叉树的结构，每个节点只有两个叉只会分成两个区域，并且从我们刚才描述的过程中可以看到水平与竖直的划分是交替的，这样一来我们可以保证空间均匀的划分方式。
同样道理还有很多划分方法，比如上面的BSP-Tree，通过对空间进行二分，与KD-Tree的区别是不是横平竖直的砍。而AABB的好处是横平竖直都是平行的非常好计算，这样的话BSP-Tree在这方面赶不上KD-Tree，并且在高维情况下不容易计算，三维情况可能就需要一个面来划分，更不用说更高维情况可能需要超平面越来越复杂。
KD-Tree Pre-Processing
KD-Tree是在光线追踪之前提前做好的，我们需要提前做好这个加速结构。
首先场景包围在最大的盒子A中，我们假设沿着竖直方向划分为两部分：蓝色部分与绿色部分。
对于蓝色部分与绿色部分我们都需要进行划分，但这里我们展示其中的一半以绿色部分为例做解释，蓝色部分如法炮制即可。可以看到绿色部分B也被分为绿色和橙色两个部分，以此类推划分出C、D等等，它最后就会形成一个树。
Data Structure for KD-Trees
Internal nodes store
- split axis: x-, y-, or z-axis
- split position: coordinate of split plane along axis
- children: pointers to child nodes
- No objects are stored in internal nodes
Leaf nodes store
- list of objects
对于任何一个节点，我都应该知道它应该沿着哪个轴划分，并且划分在哪儿。对于中间节点一定有它的子节点，既然划分一次一定有两个子节点，而实际物体不存在中间节点，只存在叶子节点上。
Traversing a KD-Tree
这个结构如何让我们加速光线追踪的呢？假设有一个光线从左上到右下，首先场景有一个最大的包围盒A，判定是否和A有交点，发现和A有交点，那么光线就有可能和盒子的左边和右边两个子节点有交集：
这时需要考虑是否和最大的盒子A的子节点有交点，发现1号蓝色区域的$t_{min}、t_{max}$，假设这棵树就是这样，那么1就是叶子节点，那么这个光线就需要和1叶子节点的所有物体求交：
同样道理，两个子节点都需要判定是不是有交点，跟右边的B区域求交发现也有交点。光线既然和B相交，那么就有可能和其子节点2和C相交：
在区域2中依然有交点，但2是叶子节点，那么我需要和叶子节点所有物体求交：
在和区域2判定交点之后欧还需要和C判定交点，发现同样有交点：
同样道理继续判定和3有交点，并且3是叶子节点，和所有物体求交。最后求交到$t_{hit}$，而区域5没有交点，所以光线没有必要判定和区域5是否有交点：
大家可以发现道理很简单：如果光线和某一个格子没有交点，那么什么都不用做；如果光线和某一个格子有交点，那么我就知道光线和它的两个子节点可能有交点，所以都看一下直到光线打到叶子节点，如果和叶子节点还没有交点那么什么都不用做；如果打到叶子节点并且光线和叶子节点有交点，那么叶子节点所有物体都要求交。
通过KD-Tree的建立，我们可以利用这种类似二分查找的方法找到这个光线和什么样的物体有交点。
对于KD-Tree有一个明确的问题：场景由三角形构成，而通过空间划分方式给出包围盒，我得知道它和哪些三角形有交集。这是一个非常非常难的事情，很不容易写对，算法是有的，但你很难判断三角形是否和立方体有交集。也许有人觉得只要判定三角形一个顶点在盒子里就算相交，但实际上有一种情况三角形三个顶点都不在盒子里但却是相交的（三维空间中一个很小的盒子垂直插在平面三角形内部）。
这也是为什么近十年大家渐渐不用KD-Tree的原因之一。另外一个问题是图中有的圆圈和很多AABB都有交集，如果这些盒子都是叶子节点，那么每个节点都要存这个物体，也就是说一个物体有可能出现在多个叶子节点里。这个性质并不怎么好，人们不希望这样，我们希望一个物体只在一个叶子节点里，KD-Tree在这一点上并不直观。
Object Partitions & Bounding Volume Hierarchy (BVH)
人们发现另一种划分方法，这次的划分不是从空间做起，而是从物体做起。这就是我们要介绍的Object partition，而这种划分形成的加速结构也被称为BVH。这种加速结构得到了非常广泛的应用，在图形学里无论实时还是离线光线追踪大家都是用这种结构，因为它解决了刚才KD-Tree的两个问题。
Bounding Volume Hierarchy (BVH)
一开始给定一个场景，我们拿盒子包起来。BVH把物体（图中为三角形）组织成两个部分，把这两部分重新求它的包围盒形成两个节点。
同样道理继续划分物体，以之前蓝色的节点为例再分为蓝、绿两部分三角形，继续重新计算包围盒。以此类推划分到一个包围盒比如只剩下五个三角形为止。
Summary: Building BVHs
总结一下BVH的过程：
- 找到包围盒
- 递归的把任何一个包围盒中的物体拆成两个部分，并且两个部分重新计算包围盒
- 正常情况下当我觉得叶子节点有足够少的三角形就停止
Building BVHs
How to subdivide a node?
- Choose a dimension to split
- Heuristic #1: Always choose the longest axis in node
- Heuristic #2: Split node at location of median object
Termination criteria?
- Heuristic: stop when node contains few elements (e.g. 5)
那么实际上如何去划分一个节点，我们可以选一个维度去划分，跟KD-Tree学习每一次选择一个不同的维度保证均匀。还有一些其他的技巧，为了让这些节点在空间中有均匀的分布，我每一次只沿着最长的轴进行划分；人们发现一个节点知道沿着某一个轴划分，取中间的物体将其分成两半，可以保证划分后两边三角形数量差不多，这棵树接近平衡。
Data Structure for BVHs
Internal nodes store
- Bounding box
- Children: pointers to child nodes
Leaf nodes store
- Bounding box
- List of objects
Nodes represent subset of primitives in scene
- All objects in subtree
BVH中间节点只存包围盒和它子节点的指针，叶子节点才存实际的物体。
BVH Traversal
如果光线与整个BVH节点都不相交，那么什么也不会发生；如果光线和包围盒相交有两种可能：如果本身是叶子节点，这种情况需要光线和所有物体求交，返回最近的交点；如果不是叶子节点那么就算中间节点，光线可能与它的两个子节点有交点，那么我们分别递归求出子节点的交点，返回最近的那个。
Spatial vs Object Partitions
Basic radiometry
Radiometry — Motivation
Observation
- In assignment 3, we implement the Blinn-Phong model
- Light intensity I is 10, for example
- But 10 what?
Do you think Whitted style ray tracing gives you CORRECT results?
为什么要提辐射度量学呢？之前我们光照强度定义为10，那么这个10是什么？10个？不合理吧，它肯定得有单位，有自己的物理意义，而之前的Blin-Phong模型我们把它极大的简化为一个数，那肯定是不对的。另一方面我们做的Whitted风格的光线追踪真的真实吗？大家一看就知道非常假，看上去肯定不是真实存在的场景，因为我们中间做了各种各样的简化。
辐射度量学是一个精准的给我们实际光的物理量的一个方法，我们把光精确定义出来，包括物体表面如何和光进行作用精确的表述出来，涉及光源、材质、光线的传播方法等等。只有这样我们才能得到最精确的结果，而整个一套路径追踪的体系都是建立在这个基础上的。
Radiometry
Measurement system and units for illumination
Accurately measure the spatial properties of light
- New terms: Radiant flux, intensity, irradiance, radiance
Perform lighting calculations in a physically correct manner
My personal way of learning things:
- WHY, WHAT, then HOW
辐射度量学讲的是如何去描述光照，它定义了一系列方法和一系列的单位，它能给我们光各种各样的空间属性。并且辐射度量学仍然是基于几何光学来做的，我们认为光线仍然以直线传播，没有波动性。总的来说，辐射度量学是一个在物理上准确定义光照的方法。
Radiant Energy and Flux (Power)
Radiant Energy and Flux (Power)
- Radiant Energy：电磁辐射能量理解成光源辐射的东西肯定永远是能量，首先我们用能量描述它，单位是焦耳。可以想象太阳能板在太阳照射时会发热，再把它转化为电能存下来
- Radiant Flux：flux人们又经常叫它power，是单位时间的能量，直译为辐射通量/辐射功率，得到的类似于功率，单位为瓦特或流明。还是以太阳能为例，你照的时间越长能量越多，分析这个问题时肯定要固定某一个短时间，考虑单位时间的性质
Flux
flux这个概念还可以从另外一个角度定义。我们知道光线传播辐射各种各样的光子，如果我们有一个感光的平面如上图所示，单位时间通过光子的数量我们就认为是flux。这很好理解，一个灯泡看上去更亮是因为它辐射出更多的光子，也就是灯泡看上去有多亮。
Important Light Measurements of Interest
有了上面两个概念我们就可以研究其他的一些物理量，比如说光源会辐射出各种各样的能量，我们如何去定义这些东西；还要定义任何一个物体表面它会接收到多少能量；光线在传播过程应该用什么方法来定义：
- 一个光源它往四面八方都有可能辐射能量，我会定义一个方向性的跟能量相关的概念：Radiant Intensity，有时人们会直接说Intensity，直译为辐射强度
- 一个物体表面它接收多少光的能量，这个概念叫做Irradiance
- 光线在传播中应该如何度量它的能量，我们用的是Radiance这个概念
Radiant Intensity
单位立体角的辐射强度很好理解，但什么是立体角？
Angles and Solid Angles
数学上角的定义一般是弧度，我们认为一个角从圆心出发往某一方向张开一定角度，它会打到圆弧上面对应一段弧长，那么我定义角度就是弧长/半径，整个圆的角度是$2 \pi r / r = 2\pi$。大家可以发现对圆的缩放并不影响角度，因为弧长和半径会同步缩放，所以这个定义比较合理。
立体角就是角度在三维空间中的延伸。在三维空间中我们找一个球，从球心出发形成某一个有一定大小的锥。这个锥会打到球面上，对应球面上的一个面积。立体角的定义就是这个锥对应的球面面积/半径的平方，也是弧度制在空间中的延伸，整个球对应的立体角为$4 \pi r^2 / r^2 = 4\pi$。这就是立体角的定义，说白了就是空间中的角有多大。
Differential Solid Angles
我们平常会定义单位立体角。对于一个单位立体角，我们就找一个单位的面积/半径平方，现在通过离z轴的夹角$\theta$和绕z轴旋转的夹角$\phi$定义一个球面上唯一的方向。如果我们取一个单位面积认为是一个矩形，应该算出长和宽各是多少，但我们发现横着的边的长度就是$d\phi$，竖着的这条边就是$r\sin{\theta}$长度，通过这种方式定义出小方块的面积应该是$r^2\sin{\theta d\theta d\phi}$，带入立体角公式得到$\sin{\theta}d\theta d\phi$。
对于整个一个球来说，如果我要把它所有方向对应的单位立体角积分就是整个球对应的立体角。
Isotropic Point Source
我们定义一个点光源，Radiant Intensity定义就是一个光源在任何一个方向上的亮度，它总共的亮度是Radiant Flux，除以单位立体角，也就是从任意方向看过去它的亮度。根据积分结果，如果一个点光源均匀辐射出能量，那么任何一个方向上对应的Radiant Intensity就是它的power/4pi，得到方向上所谓的强度。
Modern LED Light
实际上看一个LED灯泡的瓦数是和白炽灯相比，实际上它的能量开销很低。如果我认为该灯泡向四面八方辐射的能量是一样的，那我可以算任意一个方向的intensity，65坎德拉算出来就是某一方向对应的intensity。