图形学入门笔记5: 空间加速结构
在光追渲染中，我们需要对物体和射线的相交进行判断；在物理模拟中，我们需要对物体之间的碰撞进行检测。如果我们采用暴力算法，那么每一帧都需要大量时间计算射线或者碰撞检测。所以我们需要一些更加高效的方式来进行检测，这就需要我们用空间加速结构进行加速。 今天主要记录几种在渲染和模拟中比较常用的方法
- Spatial Hashing (Uniform Grid)
- Spatial Hierarchy (Octree, Kd Tree, BSP tree)
- Bounding Box Hierachy (BVH)
Spatial Hashing
Spatial Hashing的思路是将空间划分为Uniform
Grid，每个Grid中存储着与其相交的三角形或者粒子。这里我有看到两种在不同情况下使用Spatial
Hashing的情形，第一种是三角形，第二种是粒子。
对于三角形来说，同一个三角形可能存在于多个Grid当中，而一个Grid可能也会存在多个三角形。如下图所示：
当然，上面这种存储方式，是会造成问题的。由于很多格子中可能没有三角形，所以会造成不必要的空间分配。因此，正如名称中的哈希所表示的，我们可以将这种空间划分表示为object-cell键值对的list，然后根据cell的ID进行排序，然后就可以形成下面的结构。
在查找的时候，可以直接访问cell的下标。在寻找和三角形overlap的cell的时候，可以通过三角形的bounding
box和空间中的cells进行计算。在碰撞检测时，首先计算出当前三角形所相交的区域，然后通过Spatial
Hashing访问到这些区域中的三角形，这些三角形就是有可能产生碰撞的三角形对，之后用于做后续的检测。
现在这种排布仍然存在一些问题。因为Cell的ID是按照顺序定义的，在访问的时候会存在cache
locality的问题。当访问左右两侧的Cell中的三角形的时候，我们在访问一些连续的内存，可以成功利用cache缓存。但是当我们访问上下的Cell的时候，Spatial
Locality就比较差。为了解决这个问题，有人提出了Morton
Code的方法，用一种细分的Z字型结构指定Cell的ID，可以有效提高Spatial
Locality。 
现在我们的Cell的ID是我们预先确定好的，也就是整个空间是一个bounded的空间。但是在实际情况中，我们需要考虑unbounded的空间，一个理论上无限的空间。所以，我们可以使用哈希函数去生成Cell的ID，比如下面这个函数：
1
2
3
4hashCoords(xi, yi, zi) {
var h = (xi * 92837111) ^ (yi * 689287499) ^ (zi * 283923481);
return Math.abs(h) % this.tableSize;
}cellStart，大小为哈希表的大小+1; -
cellEntries，大小为所有物体的数量 算法流程如下： 1.
将每个Cell中的物体数量写入cellStart数组中 2.
cellStart计算前缀和 3. 填入cellEntries数组
1
2
3h => object所在Cell的哈希值
cellStart[h]--
cellEntries[cellStart[h]] = object1
2
3
4
5h => cell id
int start = cellStart[h]
int end = cellStart[h+1]
for (int i = start; i < end; i++)
object = cellEntries[i]
具体的代码实现参考pages/tenMinutePhysics/11-hashing.html
Spatial Hierarchies
采用Uniform Grid的方法在光线求交的时候效率不高，因为没有hierarchy的结构，所以在大部分场景中仍然会有很多不必要的计算。因此，我们可以将空间划分为树状结构，可以产生以下三种划分的方式
- Octree(八叉树)：将空间递归的细分为等大的八个子空间
- Kd-tree：交替的按照轴对空间进行划分
- Bsp-tree：Kd-tree在Kd-tree的基础上，移除了axis-aligned的限制，以任意方向对空间进行递归的划分
Bounding Box Hierachy (BVH)
BVH是一种按照物体进行划分的空间加速算法。首先找到所有物体的一个包围盒，然后递归的将物体分成两个子集，并计算新的包围盒，当包围盒中的物体达到一定的数量的时候，停止继续细分，将所有物体存储在叶子节点当中。
使用BVH也可以进行碰撞检测，流程如下。从叶子节点开始，向上一层一层进行碰撞检测。
