Ray Tracing – Acceleration

1.Uniform Spatial Partitions (Grids)

Assumptions:
- 判断光线是否与物体相交是耗时的
- 判断光线是否与 bounding box 相交是容易的 

预处理完结后，求出光线穿过的每个盒子，判断盒子里是否有物体，如果有，则判断光线是否与物体相交，这样防止了和空间中所有物体计算是否相交。

减速构造根本思维：多做光线和盒子求交，防止做光线和物体求交。

缺点：仍须要计算所有光线走过的格子。

2.Spatial Partitions（空间划分）

根本想法：改良（1.）中的格子划分形式，对于空阔的中央少用一些格子（即格子设置更大），密集的中央多用一些格子（即格子设置更小），有利于解决上面这一经典案例（图中存在着大量空阔区域，用对立的格子划分形式会比较慢）

San Miguel Scene(经典场景), 10.7M triangles

Examples：（ 重点：KD-Tree）

场景的减速构造预处理要在光线追踪计算之前做完！

 执行流程：对以后节点采纳某种划分形式 (x\y\z), 失去两个子节点，而后对于子节点持续划分。理论的物体 \ 三角形只寄存在叶子节点上 

 问题：1. 一个物体可能呈现在多个叶子节点中
2.KD-Tree 的建设须要思考三角和盒子的求交（简单）

3.Bounding Volume Hierarchy (BVH)

属于 Object Partitions（物体划分），利用宽泛！

3.1 根本流程

BVH 对物体进行划分，每次划分为两堆，而后别离求出 bounding box，持续划分，再次从新计算 bounding box，反复以上过程，划分形式能够竖直 \ 程度等不做限度（如顺次抉择 X 轴，Y 轴，Z 轴），最终使得每个叶子节点中三角形数量较少，空间中物体的划分尽量平均。

Summary: Building BVHs
• Find bounding box 
找到以后节点物体的突围盒
• Recursively split set of objects in two subsets 
递归地将以后物体分为两堆
• Recompute the bounding box of the subsets 
从新计算两堆物体的突围盒
• Stop when necessary 
适宜的时候进行（每个叶子节点中三角形数量较少，空间中物体的划分尽量平均）• Store objects in each leaf node
物体存储在叶子节点中 

3.2 性能剖析

相较于 KD-Tree 的劣势： 每一个物体肯定严格属于一个节点 。因而省去了三角形和 bounding box 求交的问题。

存在的问题：并没有严格将空间”划分开“，即 bounding box 可能相交。因而在 ” 划分 ” 方面比拟考究。

Heuristics of subdivision
Choose a dimension to split 
• Heuristic #1: Always choose the longest axis in node 
• Heuristic #2: Split node at location of median object
即选定最长轴划分，划分界线为排序后位于中位的物体。

【补充：疾速抉择算法】

问题：对于 n 个无序数组成的序列，找出其中第 i 大的数。
工夫复杂度：O(n)

BVH 中用这一算法实现对于大小居中物体的查找。

3.3 存储构造

Data Structure for BVHs
[Internal nodes store]
• Bounding box 
• Children: pointers to child nodes 
[Leaf nodes store]
• Bounding box 
• List of objects

3.4 伪代码

Intersect(Ray ray, BVH node) 
{if (ray misses node.bbox) return; // 若光线与 bounding box 不相交，完结
    // 若相交，分为是否是叶子节点
     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;
}

4. 减速构造的比拟：Spatial vs Object Partitions

4.1 Spatial partition (e.g.KD-tree)

• Partition space into non-overlapping regions 
空间划分，划分的节点之间不重叠
• An object can be contained in multiple regions
毛病：一个物体可能被划分到多个区域中 

4.2 Object partition (e.g. BVH)

• Partition set of objects into disjoint subsets 
长处：物体划分到不相交的子集，不会呈现同一个物体被划分到不同的节点
• Bounding boxes for each set may overlap in space
毛病：不同节点所占空间可能重叠