Games101-Ray Tracing (Acceleration) -L14

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