加速光线和场景的求交

💡

如何用光线和盒子求交，来加速光线和场景的求交？

Uniform Spatial Partitions (Grids)

认为光线与格子求交很快，与物体求交较慢

在箭头处，如果发现光线穿过的格子有物体，会做一个光线和物体的求交，没有交点则忽略，有交点则表示与物体相交（红点处）。

💡

怎么样考虑格子的大小呢

Spatial Partitions

分布稀疏的地方少用格子，分布密集的地方多用格子。

空间分成树的形式，但人们不太用八叉树，因为八叉树与维度有关系，二维的就是四叉树。人们发明了一个办法，能让空间得到划分，且跟维度没关系——KD-Tree。

KD-Tree 二维下先横着切一刀，再竖直切一刀，再横着...。三维下就 x 轴切一刀，y 轴切一刀，z 轴切一刀不断循环。

BSD-Tree 是空间的一个二分的划法，但切法不是横平竖直的。前面说AABB，跟KD-Tree比不太好计算。且维度高的时候不好计算。

KD-Tree Pre-Processing

Data Structure for KD-Trees

Internal nodes store

split axis: x-, y-, or z-axis

split position: coordinate of split plane along axis

不一定划在中间，这里面有各种技巧

children: pointers to child nodes

No objects are stored in internal nodes

实际物体只存叶子节点上

Leaf nodes store

list of objects

Traversing a KD-Tree

如果光线和某一个格子没有交点，什么都不用做。如果有交点，那么光线可能和它两个子节点有交点，就都判一下。直到光线打到叶子节点，如果还没有叶子节点包围盒有交点，什么都不用做。如果打到叶子节点，且有交点，那就是光线需要和叶子节点中的所有物体都要求交。

⚠️

一个物体可能被存在多个叶子节点中。例如右下角 fhit 处的圆。（KD-Tree 不直观）

💡

怎么判断物体和包围盒做相交？很难，求包围盒和空间中三角形求交集是很难的事情，有算法，但不好写，所以最近十年渐渐不用 KD-Tree 了。

Object Partitions & Bounding Volume Hierarchy (BVH)

现在尝试从物体开始划分。

💡

划分到什么时候为止？例如一个节点里最多五个三角形。

💡

划分也可以按照 KD-Tree 来划分，某一层左右划分，某一层上下划分。保证空间均匀。

💡

KD-Tree 不管怎样，拿到一个节点分成两半，再考虑物体和节点的相交情况。 BVH 把物体分成两堆，重新求包围盒，一个物体只可能出现一个格子中。

⚠️

BVH 引起了一个问题：对空间的划分不是严格的划分开，包围盒可以相交。怎么划分很有讲究，有很多研究在做。

How to subdivide a node?

Choose a dimension to split

Heuristic #1: Always choose the longest axis in node

如果发现所有场景都在长条内，还是竖直来砍开，沿着最长的轴变短，使其均匀分布。

Heuristic #2: Split node at location of median object

如何把包围盒分成两半？取中间的三角形，使两边三角形数量差不多，保证树平衡，最大深度小，平均搜索时间少。

Termination criteria?

Heuristic: stop when node contains few elements (e.g. 5)

💡

一个序列（树），如何快速找到中位数？如果上来就把树排序，那就是 nlogn。对于任意一列数（无序），要找到第 i 大的数，快速选择算法，受快速排序启发，只对划分的某一边进行操作。O(n)

⚠️

物体动了要重新计算 BVH

Data Structure for BVHs

Internal nodes store

Bounding box

Children: pointers to child nodes

Leaf nodes store

Bounding box

List of objects

Nodes represent subset of primitives in scene

All objects in subtree


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;
}