这里回顾GAMES101 Lecture 14，这一讲完成了加速结构，介绍了辐射度量学。

课程主页：

课程作业：

课程视频：

本讲内容

  • 如何使用AABB加速光线追踪的计算过程，即如何加速和物体求交；
    • 均匀格子；
    • 空间划分；
  • 辐射度量学；

基本思路

  • 对于光线和物体求交的过程；
  • 我们先考虑光线和物体包围盒求交；
    • 如果和包围盒有交点，即和物体求交；

均匀空间划分（格子）

预处理

对于空间中的物体，首先找到包围盒：

其次将盒子划分为格子：

最后判定哪些格子中有物体表面（下图中标记为灰色）：

光线场景相交

有了之前的准备工作，可以介绍光线和场景的相交：

  • 光线穿按顺序穿过网；
  • 对于每个格子：
    • 测试与在该格子内所有物体的是否相交；

图示：

这里有个问题，就是如何判断光线和哪个格子相交，老师给出的方法如下：

  • 假设已经和格子a相交，根据光线的方向检查和a周围的格子是否相交，然后找到距离最近的格子；
    • 这也是光栅化一条线的方法；

这里的整体思路是尽量多做光线和盒子的求交，减少和物体的求交，那么加速效果如何呢？这和格子的分辨率有关。

格子分辨率

如果只有一个格子，那么：

如果格子太多，那么需要计算很多次光线和格子相交：

实际中，人们发现了一个启发式的方法，划分的格子数量为：

  • $cells =C \times objs$；
  • 在3维中，$C=27$；

小结

  • 格子法可以一定程度上加速；
  • 但问题是，如果物体分布不均匀，则会浪费很多计算量；
  • 一个缓解方式是非均匀划分；

非均匀空间划分

非均匀空间划分是指格子大小不同的划分：

说明：

  • Oct-Tree
    • 八叉树，将空间划分为8份；
    • 平面内为4份；
    • 对于$n$维空间，需要划分为$2^n$份，这样当维度增加，划分的工作了太大；
  • KD-Tree
    • 对Oct-Tree的改进，每次只对某个维度进行划分；
    • 选择划分的维度有一定技巧；
  • BSP-Tree
    • Oct-Tree的改进，每次对某个方向进行划分；
    • 但是计算不方便；

KD-Tree划分

这里介绍KD-Tree的例子。

第一次沿竖直方向划分：

第二次沿水平方向划分：

后续以此类推：

这样划分构成了一棵树：

  • 内部节点存储
    • 分割轴：x轴、y轴或z轴
    • 分割位置：分割平面沿轴的坐
    • 子节点：指向子节点的指针
    • 内部节点不存储物体
  • 叶节点存储
    • 物体列表

遍历KD-Tree

现在考虑如何遍历KD-Tree。

第一步发现和节点A有交点：

所以要判断和其子节点是否有交点：

因为子节点是叶节点，所以无需继续判断。所以接下来判断和另一个子节点是否有交点即可：

以此类推，继续进行上述步骤即可：

小结

对于KD-Tree：

  • 如果节点为叶节点：
    • 则判断和叶节点中的物体是否幼教；
  • 如果节点不是叶节点：
    • 如果和节点的包围盒有交点，则判断和其子节点是否有交点；

问题

  • 对于KD-Tree，很难判断包围盒和空间中的三角形是否有交集，这也是KD-Tree的弱点；
  • 另一个问题是，一个物体可能存在于多个叶节点中；

如何解决这些问题，需要介绍BVH。

Bounding Volume Hierarchy (BVH)

BVH的思路很简单：

  • 不从空间划分；
  • 从物体划分；

例子

第一步还是引入一个包围盒：

第二步将物体划分为两部分，然后分别求出包围盒：

以此类推：

小结

算法流程：

  • 查找边界框；
  • 递归地将物体集拆分为两个子集；
  • 重新计算子集的边界框；
  • 必要时停止；
  • 在每个叶节点中存储对象；

构造BVH

如何划分节点？

  • 选择要拆分的维度；
  • 启发式#1：始终选择节点中的最长轴；
    • 划分后的长度相同；
  • 启发式#2：在中间对象位置拆分节点；
    • 划分后的数量相同；

终止标准？

  • 启发式：当节点包含少量元素时停止
    （例如 5 个）；

BVH使用的数据结构

内部节点存储

  • 边界框；
  • Children：指向子节点的指针；

叶节点存储

  • 边界框；
  • 对象列表；

节点表示场景中的物体集合

  • 子树中的所有对象；

伪代码

Intersect(Ray ray, BVH node) {
    if (ray misses node.bbox) return;
    if (node is a leaf node)
        test intersection with all objs;
        return closest intersection;
        
    hit1 = Intersect(ray, node.child1);
    hit2 = Intersect(ray, node.child2);
    
    return the closer of hit1, hit2;
}

空间划分VS物体划分

  • 空间划分（例如KD-tree）
    • 将空间划分为不重叠的区域；
    • 一个对象可以包含在多个区域中；
  • 对象划分（例如BVH）
    • 将物体集划分为不相交的子集；
    • 每个集合的边界框可能在空间上重叠；

辐射度量学

动机

观察：

  • 在作业3中，我们实现了Blinn-Phong模型；
  • 光强度$I$为$10$；
  • 但是$10$什么？

另一方面：

  • Blinn-Phong模型很多假设不正确；

要回答，解决这些问题，就需要学习辐射度量学。

简介

辐射度量学测量系统和物体的照明，准确度量光的空间特性：

  • 新术语：Radiant flux, intensity, irradiance, radiance；

辐射度量在物理上准确地定义光照。

Radiant Energy and Flux (Power)

定义：Radiant Energy是电磁辐射的能量，以焦耳为单位，用如下符号表示：

定义：Radiant flux（power）是单位时间内发射、反射、传输或接收的能量：

即在单位时间内流过传感器的光子数量。

Radiant Intensity

定义：Radiant Intensity是点光源发出的每单位立体角的功率：

图示：

角和立体角

角度：圆上的对圆弧长度与半径之比。

计算公式：

圆的角度为$2\pi$。

图示：

立体角：球体对向面积与半径平方的比值：

计算公式：

球的立体角为$4\pi$。

计算公式：

图示：

可微立体角

在球面上，可以计算出立体角：

积分可得：

即球面的立体角为$4\pi$。在实际中，我们利用立体角表示方向。

Radiant flux（power）和Radiant Intensity的关系

将Radiant Intensity关于立体角积分，即可得到Radiant flux，图示：

公式：