在上一讲里我们提到了Bounding Volumes,那么在一个3维场景中对物体进行划分呢?AABB太大了则加速没有效用,太小了则会效率低下,所以就引入了空间划分的算法。
Spatial Partitions
常见的空间划分有OCT - Tree,KD - Tree,BSP - Tree等。这里重点介绍下KD-Tree:
KD - Tree算法并不算复杂,求出光线与每个子节点的时间tmin,tmax然后一一对比求交
但是KD-Tree在实际运用中仍有缺点,一个是一个物体可能存在于多个叶子节点中,还有一个是三角形与AABB求交很复杂。
Bounding Volume Hierarchy (BVH)
BVH是以物体为基础的,划分算法(快速选择):