裁剪和空间管理
今天想谈谈游戏引擎中 Culling 模块。
当场景中的可渲染对象很多，而当前会被渲染的对象相较甚少的时候，我们通常会启用一个 culling 的过程。Culling 会想办法剔除一些当前不必渲染的对象，避免这些对象提交到 GPU ，让 GPU 承担剔除的过程。这样可以减少 CPU 到 GPU 的带宽。
最基本的 Culling 是用相机的视锥体和对象做一个相交测试，如果对象和视锥体不相交，则可判定它不必渲染；复杂的 Culling 还包括遮挡测试，如果一个对象完全被墙体挡住，那么也不必渲染。这篇只谈前者。
很容易得知，Culling 算法的复杂度上限为 O(n) 。即，我们把场景中的每个对象逐一和视锥体做一次相交判断即可。这里的 n 为场景中元素的个数。
当 n 特别大的时候，通过巧妙地设计数据结构，我们则有可能把复杂度降低。但如何做到呢？
因为视锥体参与算法的主要是它的空间属性，所以被测试对象可以用其空间信息做一些组织，减少相交测试的次数。这就是按空间位置对对象做管理的动机。
本质上来说，Culling 模块的数据结构，就是对场景上的对象按空间属性重新分组。每个组，组内元素有一些共性。视锥体可以和这些共性做一次判定，得到的结果可以分为三类：
- 该组对象全部包含在视锥体内。
- 该组对象全部不在视锥体内。
- 该组对象部分存在视锥体内。
对于第一、二类结果，我们可以一次性的得到一组对象和视锥体的相交测试结果。对于第三类情况，假设我们每个组内还继续分成若干子集，那么就可以递归这个过程。
无论以什么基准分组，最终都会组织为这样的树结构：先将全部对象粗分为若干组，每个组内再细分为子组，依次递归，直到最后不可分的组内有适当数量的元素。这样，Culling 算法的时间复杂度就降低为 O(log N) 。
综上所述，我们可以看到，以树结构对场景中所有对象分组是核心，怎样分组是次要的。不同的分组方式在不同的情况下可能有不同的效果。很难有普适最好的方法。
第二，Culling 是一个优化流程。有没有 Culling 过程，结果都是正确的。我们可以将 Culling 模块看作是一个加速查找的 Cache ，有了 Culling 模块，渲染层更容易挑选出需要渲染的对象。所以从设计上来说，我们应该把 Culling 定义成一个可选的加速 Cache 层，其数据结构不可喧宾夺主，变成引擎的核心容器。
强调第二点，是因为场景管理模块通常天然有一棵场景树，特别类似 Culling 的需求。很多人喜欢附带的把它附加上空间分割的内涵，供 Culling 模块使用。典型的实现就是在场景树的中间节点保持维护着子节点的包围盒的并集。我认为这种设计是不可取的。
下面我们来看空间管理的思路。为了方便解说，以 2D 空间为例，但所有算法都很容易推广到 3D 空间。
如果你的对象均匀的分布在场景中，那么最简单和自然的方法是用等距网格把空间切分为等大的正多边形。用正方形、三角形、六边形均可。从实现上看，正方形相对简单。
3D 空间往往也是用 2D 网格。这是因为大多数场景在纵向上的对象分布几乎都贴近地面，不太需要在高度轴上细分管理。如果有需要，我们也可以扩展成 3D 网格。
等距网格的好处是数据结构简单。如果对象数量不算太多，我们甚至不需要分层。从空间位置，可以 O(1) 的快速定位到子空间的位置。对象移动导致从一个子空间迁移到另一个子空间中，管理成本非常低。
但是，缺点也非常明显。如果空间很大，对象分布不均匀时，管理太多的格子的空耗成本非常大。解决方案就是将网格分级，先用粗狂的分割方案将空间粗略分开。如果子空间中对象总数不多时，就不再细分；否则，再将子空间分割成若干更小的空间。
在这个指导思想之下，权衡实现的复杂度成本，就得到了四叉树这种数据结构。
我们从空间中心，沿着两个相互垂直的坐标轴，将空间切分成四份；然后根据需要，将对象数量很多的象限，递归的切割成四个子空间。如果将这个思路推广到 3D 空间，那就是八叉树。
可以看到，四叉树就是对等距网格的改良。降低对象稀疏之处子空间的管理成本。但是，这个方案也有缺点：
- 对于无限空间，不太容易选取切割点。
- 通过空间位置定位子空间的复杂度从 O(1) 上升到了 O(log N) 。
- 对象是有体积的，如果对象穿过了切割线，对象的归属问题比较麻烦。
那么，有没有改进方案呢？
让我们回头来看最初：我们要做的是按空间对对象递归分组，以达到用 O(log N) 裁剪对象的目的。无论我们是用四叉树还是八叉树，只不过是树的层次上子节点的数量不同而已。既然可以每级的分叉可以是 4 或 8 ，很自然的可以想到，最简洁的分割方式应该是二叉树。
也就是说，我们可以每次对空间一分为二，然后根据需要对左右两个子空间递归分割。最后的效果是一样的，但数据结构可以更紧凑、算法可以实现的更高效。这里、和坐标轴对齐的分割线，在子空间的原点开始分割，都不是必须的。
如果我们可以用任意角度的直线在任意位置对空间一分为二，至少可以解决上面的问题 3 。因为我们总能找到不把对象一分为二的切割线。如果游戏场景里有大量的墙壁就更好了，我们沿着墙切割就好了。那么每个子空间都能迅速判定出在每堵墙的左边还是右边。甚至我们能把这些对象相对一个子空间排出一个的前后次序来。
没错，这就是大名鼎鼎的 BSP 。
用任意斜度的直线（或 3D 空间中的平面）分割空间，算法上可能涉及更复杂的数据运算。我们还可以退回一步，如果我们保持切割线和坐标轴对齐，但是在切割点上则不从中心点，而是选择恰当的地方，效果可能更好。
比如，每次切割子空间的时候，我们都选一个坐标轴平行线，让分割后的左右子空间均衡的容纳相同数量的对象。这样的效率肯定是最高的。（对于 2D 平面）因为每次切割都可以选择 X 轴平行或和 Y 轴平行。为了让切割后的子空间更接近正方形（这样对和视锥体相交测试更友好），我们每次选较长的方向一分为二最好。
如果这样做，最终每个子空间容纳的对象数量都大致相当。不像四叉树，这次我们可以保持一个完整的二叉树。即每个叶子节点的深度都是一致的。
储存完全二叉树不管从空间管理还是算法处理上都有极大的优势。我们知道，储存一个 n 层完全二叉树，只需要一块 2^n - 1 个连续 slot 空间即可。甚至不需要额外保存子节点的引用，因为本节点的索引乘二后，就可以计算出左右子节点的位置。
这样我们可以回避上面的问题 2 ：空间位置定位子空间的复杂度又退回了 O(1) 。
没错，这就是大名鼎鼎的 K-D Tree 。
一般，我们以对象的中心点做 K-D tree 的子空间切分线的标准。但对象是有体积的，有些对象可能压线。这样就会导致最视锥体判定的时候可能出错：有的子空间不在视锥体内，但是对象因为压线的缘故超出了子空间的范围，实际是在视锥体内的。
怎么解决呢？
方法是，我们只以对象中心点和分割线去判定对象的归属。但每个子空间都重新根据内部的对象的包围盒计算出一个整体的包围盒。也就是说，相邻一对子空间的包围盒很可能有重叠之处。通过包围盒的计算，也很好的解决了无限空间的分割问题。
没错，这就是大名鼎鼎的 BVH (bounding volume hierarchy) 。
最后，我们来谈谈 K-D Tree/ BVH 的实现细节。
在做空间二分的时候，一个最重要的需求就是怎样把 n 个对象依某个坐标轴上的位置分成两组。也就是，怎样把无序的 n 个数组分成大小两组，大组集合中的每个数字都大于小组集合中的数字。
如果偷懒的话，我们可以对这组数组做一次 qsort ，然后从中间分开。时间复杂度为 O(N log N) ，空间复杂度为 O( log N ) （递归深度）。但其实更好的针对性算法可以把空间复杂度降低到 O(1) ，速度也能更快。
因为我们要的是分组而不是有序。所以我们可以像 qsort 的 inplace 算法那样，先找一个标点。因为迟早要计算整体包围盒，所以我倾向于选取包围盒长轴的中点，而不是 qsort 那样选取其中一个元素。以这个标点对所有元素二分。
如果刚好得到要求，就结束。否则对超出数量的一侧继续这个过程。
例如，如果需要对 8 个元素对分为 4:4 ，如果第一趟分为了 3:5 ，则只需要继续对 5 的一侧分为 1:4 , 而不必再处理 3 的一侧。这个过程就不再需要递归，而作简单循环即可。
另一个问题是，我们到底需不需要对 K-D Tree 做动态调整。
我的想法是，不是那么必要，仅在需要的时候做即可。一个静态的 K-D Tree 更好实现、更好维护。因为大多数场景中，大比例的可渲染物件都是位置不变的。我们可以用大量的静止物体构建一个 K-D Tree 作为空间的大致划分方案。每个节点其实只需要保存切割方向和切割线的位置。（btw ，如果想要紧凑的数据结构，可以把切割方向 2bit 编码到切割线这个 float 的内部。这样，保存一颗完整的 K-D tree 只需要 2^n 个 float ）
我在设计时，倾向于不在 BVH 数据结构中保存对象引用列表，而仅维护一个包围盒。无论是静态物体还是动态物体，都参与子空间的包围盒的计算。从简化角度看，包围盒可以只扩大而不减少。如果演变得非常畸形的话，可以考虑重建整个空间结构。
记住：空间划分仅仅是 Cache ，而 Cache 可以根据实际需求去设计失效和重建的规则。
其实，我们并不需要太深的树层次。或许 10 层就足够了（可以划分出 512 个子空间）。如果场景特别的大，我认为应该按区域分成多颗树。而大型物件（如山体，巨型建筑）和小型物件也应该分属不同的容器。这样，方便用和摄像机的距离做初筛。
那么，每个空间树，就可以用一块固定的内存承载，实现起来非常简单，重建也很容易。甚至还能直接对这个 Cache 做持久化。
struct kdtree {
float split[KDTREE_NODES];
struct boundingbox box[KDTREE_NODES];
};
void kdtree_build(struct kdtree *space, int n, struct boundingbox *aabbs);
int kdtree_insert(struct kdtree *space, const struct boundingbox *aabb);
const struct boundingbox * kdtree_box(struct kdtree *space, int index);
这是我设计的核心 api 。build 方法可以通过 n 个包围盒构建一个 kdtree 结构来。然后我们可以不断地 insert 包围盒对象，可以获得这个对象所在的 slot 编号。至于这个 slot 最终保存了哪些对象，是用户额外储存的，这里的数据结构仅维护包围盒。
因为 culling 只是一个优化过程，使用完全独立的数据结构。我认为甚至它可以放在额外线程中处理。因为我们可以每次把视锥体扩大，交给 culling 线程做判定。而不必急于拿回 culling 结果。
虽然我们每次得到的 culling 结果都是过去提交的请求，但是，如果当前的视锥体在请求时提供的范围内（请求时扩大了），那么就可以直接用结果。否则，可以跳过 culling 直接渲染（或在本地做一次 O(n) 的 culling ）