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 subdivisionChoose 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毛病：不同节点所占空间可能重叠