前言

​ 若您写过光线追踪会发现光线追踪计算时间是非常非常长的,计算次数 = 像素数量 x 三角形面的个数 x 弹射次数，因此本篇将着重介绍如何对光线追踪进行加速、加速方法有哪些

轴对齐包围盒

• 为什么使用包围盒？在这之前我们遍历场景中所有物体的所有面来判断光线是否和三角形面相交，但仔细思考若光线都没和物体相交，那么他不可能和物体中的三角形面有交点

• 

• 定义.轴对齐包围盒(Axis-Aligned Bounding Box,AABB)是一种由三对平面的交集构成的包围盒，其中任意两轴两两垂直

• 

• 为什么使用AABB？因为求\(t\)时，只需使用某一轴的信息，不必使用整个坐标，与点乘相比更容易
  

AABB和光线求交

​ 以2维的AABB包围盒为例.如下图，左边的图计算x轴上最先进来的交点\(t_{min}\) 和最晚出去的\(t_{max}\),中间的图计算y轴上的，最后在综合前两个计算结果：

1. 只有当光线进入了所有平面，才是真正地进入了包围盒：\(t_{enter} = max(t_{min})\)
2. 只要当光线离开了任一平面，就算是真正地离开了包围盒：\(t_{exit} = min(t_{max})\)
3. 当且仅当\(t_{enter} < t_{exit}，t > 0\)成立时，才有交点
4. 若t小于0，说明盒子在光线背后；若\(t_{exit} >= 0, t_{enter} < 0\)，说明光线起点在盒子内部
   

找AABB

​ 虽然知道为什么使用AABB，但我们还不知如何对场景划分形成不同的AABB，而找AABB的过程是对空间的划分，接下来将介绍几种划分空间的方法并分析他们的优劣

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

• 大致思路：将空间划分为多个均匀的AABB，根据光线找出相交的方格，再判断该方格中是否存有物体信息，有则进一步求交

​ 步骤：

1. 在目标场景找一个包围盒
   
2. 均匀划分该包围盒
   
3. 在和物体相交的网格上存储物体信息。该步求得可能含有物体的放个
   
4. 判断光线是否和有物体的网格相交(Bresenham画线算法软光栅从零开始——Bresenham’s Line - 爱莉希雅 - 博客园 (cnblogs.com))，若是则对 网格中的平面求交；若不是则跳过
   

该方法确定划分的网格数是优化的关键，方格少没有加速效果，方格多又吃性能

• 缺点：对于场景较为空旷且复杂的场景表示不尽如人意，如下图找茶壶
  
• 适用：适合场景中分布大量且均匀的物体
  

空间划分

​ 从上个方法看出，该方法划分的是同样大小的网格，但缺点是部分空旷的地方它无需用到过多网格，过于浪费，因此我们可以在有物体的地方使用密集的网格，没有物体的地方使用稀疏的网格，也就衍生出以下方法：

八叉树(Oct-Tree)

• 思路：每次将三维空间分为8个相等的部分，再递归的对子空间再进行和父空间相同的划分
• 停止条件：划分到一定程度还没物体就停止划分
• 缺点：维度越高，复杂度越高。因为对于二维需要四叉树，三维八叉树，也就是说n维\(2^n\)叉树

KD-Tree

1. 意义：为了解决八叉树的缺点，又衍生出了空间的划分和维度无关的方法——KD-Tree
2. 思路：每次只以某一轴将空间划分为两部分，最终结果类似二叉树
3. 划分规则
   1. 依次以x轴,y轴,z轴划分，使空间划分的更均匀
   2. 划分的位置由空间中三角形面的分布决定
   3. 叶子节点存储对应空间的所有物体或三角面的信息,最终的物体一定在叶子节点上
   4. 当划分的空间太小或空间内含有少量三角形时停止划分
4. 例子：对于2维物体划分方式如下
   
   
   

• 光线和物体求交的步骤

  如下图的划分方式
  

  1. 判断光线是否最外层的包围盒相交
     
  2. 若相交，则判断是否它的子空间相交，先判断左空间，若有则继续判断右空间，然后对它们的子节点继续递归判断
     
     
     
     
     
     

• 缺点

  1. 判断包围盒和三角形面的相交很难
  2. 若一个物体和很多包围盒都有交集，它可能会存在于多个叶子节点

• 优点：忽略部分压根不会相交的空间的判断过程

物体划分

​ 为了解决空间划分的问题，又衍生出了物体划分的方式——Bounding Volume Hierarchy(BVH)

BVH

• 思路：以对象作为划分依据

• 步骤

  1. 找到场景中最大的包围盒
     

  2. 以合适的划分点 将最大的包围盒内的三角形面划分为两部分
     

     可以看到，包围盒会产生重叠，但三角形面只被存储在唯一的包围盒中

  3. 递归
     

• 划分规则

  1. 每次划分选最长的轴
  2. 划分点根据所有三角形面的重心坐标的中位数

• 伪代码
  

reference

GAMES101