视锥体剔除

视锥体

先看看来自 Wikipedia 的好图 ——

我们把人眼（相机）的视觉范围抽象成了“视锥体”

由 6 个平面 包围而成：

1. 近裁剪面 (Near Plane)： 离摄像机最近的那个矩形面。贴在脸上的东西不画
2. 远裁剪面 (Far Plane)： 离摄像机最远的那个大矩形面。超过这个距离（比如 10公里外的山）就不画了
3. 左、右、上、下 侧面： 由你的屏幕比例（如 16:9）和视野角度（FOV，比如常见的 90度视野）决定的四个斜面。

只有被视锥体包围住的物体，才会被渲染出来

包围盒

视锥体和空间物体求交的时候，不可能通过遍历顶点来进行计算 —— 假设老婆的模型是个有着100w顶点的超高精度的模型？ —— 那这简直就是计算灾难，简直不能计算一点（

于是提出包围盒的概念 —— 即用一个简单的几何体包围空间物体，接着求交的时候只需计算包围盒和视锥体即可，大大降低时间复杂度。

最粗糙的 —— AABB 包围盒，即使用一个平整的、各个边水平或者垂直坐标轴的立方体来包围住整个空间物体。

空间划分算法

也是一种优化算法，用于组织场景中的物体，

利用包围盒解决了顶点数太多导致的难以计算的问题，那么空间划分可以比较方便的解决空间物体数量过多的事 —— 其核心思想 —— 不要去管理物体，去管理“空间”。

常见的算法有：四叉树 (Quadtree)，八叉树 (Octree)，层次包围盒 (BVH) 等

（等新坑详细说明这些算法？）

实际上都不太复杂，以 BVH 为例子

1. 找相邻的小 AABB，套成一个大的 AABB （形成节点
2. 递归把大的 AABB 合成成更大的 AABB
3. 直到空间只剩下一个 AABB （ Root 节点

然后在求交剔除的时候，如果和大的AABB都没有交，那么一定和小的AABB没有交，那么一定和叶子节点的场景物体没有交 —— 直接跳过！

这样就成功将全局遍历的时间复杂度从 $O(N)$ 的暴力检索，暴降到了 $O(\log N)$ 的树形检索。

GPU-Driven 视锥体剔除

经过了包围盒和空间划分的优化之后，由于所有物体数据和相机数据（位置信息等）都是在运存中存储，所以容易想到在 CPU 上执行求交操作，然后进行视锥体剔除的计算进行判断。

但是这对于 CPU 来说依旧很贵

• CPU 还需要在一个时间切片内做物理、游戏逻辑等许多运算
• 空间划分 / 物体结构存储可能是“离散”的，Cache Miss 等的问题很容易爆发
• CPU 需要在执行完剔除之后再提交 Drawcall，GPU 在等待期间可能处于空闲的状态，算力浪费

与此同时，我们在渲染的时候也需要将位置信息等上传到 GPU 上，那么为何不直接在 GPU 上做利用 SIMT 做剔除运算呢？然后直接渲染 ——

于是提出 GPU-Driven 的视锥体剔除

• CPU 把包围盒信息塞进 Array
• 传入 SSBO （Shader Storage Buffer Object）
• GPU 开始进行剔除，执行 Compute Shader
• CPU 发起 Indirect Draw，GPU 执行绘制指令

留个钩子 ——

• CPU 和 GPU 同步物体数据如何优化？
• GPU 执行绘制时候的优化方法
• 深度测试中如何优化视锥体剔除过程
• 等