视锥剔除

《Optimized View Frustum Culling Algorithms for Bounding Boxes》阅读笔记

剔除的目的是减少要绘制不可见的物体，视锥剔除（View Frustum Culling，VFC）是使用一个平头四棱锥和场景中物体做可见性测试，实现快速剔除

为了加速视锥和场景物体的相交测试速度，我们会使用Bounding Volume（比如AABB、OBB、Sphere）来代替物体进行测试

视锥剔除可以并行计算，也可以使用BSP-trees加速

基础数学知识

点与面

已知一个面的法线（已经归一化）为$\mathbf{n}$，沿着法线方向平移面，直到原点在面上，这个过程的移动距离为$d$

已知一个点的坐标$\mathbf{x}$，$\mathbf{x}$同时也是从原点指向这个点的向量，点到移动后的平面的距离是$\mathbf{n}\cdot\mathbf{x}$

所以，如果一个点在移动前的面上，那么应该满足
$$
\mathbf{n}\cdot\mathbf{x}+d=0
$$
通过这个公式，我们就可以快速判断点是否在平面上

线与面

一条线是两个点，如果两个点带入$\mathbf{n}\cdot\mathbf{x}+d$的符号是相反的，说明两个点在面的两侧，说明线与面相交

AABB与面

AABB是轴向包围盒，根据面的法线方向，就能知道AABB哪一个对角线轴最垂直于这个面，判读那这个对角线和面的关系，就能得到AABB和面的关系

我们还可以将这个对角线放在LUT里，加速之后几帧的相交检测（毕竟帧是连续的，我们可能会高频做相同面和对角线的相交检测）

AABB视锥剔除

投影空间简单比较

还有一种和上述不同的方案，即将视锥和AABB转化到相机的透视投影空间，此时视锥变成一个立方体，于是就可以判断投影后的AABB和一个长方形视锥的相交关系，这个计算十分简单只需要算6次比较

if (cube1_max[0] < cube2_min[0] or cube1_min[0] > cube2_max[0] or
    cube1_max[1] < cube2_min[1] or cube1_min[1] > cube2_max[1] or
    cube1_max[2] < cube2_min[2] or cube1_min[2] > cube2_max[2]):
    return False
else:
    return True

但这个方法缺点也很明显：需要做一个投影计算（很费）

世界空间六个面替代视锥

我们可以将视锥是为六个平面，做六个平面和AABB的相交测试，若发现在AABB在视锥平面外，说明未相交，不可见

bool testVisible(AABB aabb, Camera camera)
{
    vec3 center = aabb.bound.center;
    vec3 halfSize = abs(aabb.bound.max - aabb.bound.min) * 0.5;
    for(auto& plane : camera.frustumPlanes)
    {
        SideResult side = testSide(plane, center, halfSize);
        if(side == SideResult::OutSide)
        {
            return false;
        }
    }
    return ture;
}

作者的方案

八分检测

如图，我们使用轴将视锥切成八份，每一份是一个octant，每个octant都分到了三个外平面（图中加粗部分），若一个物体在视锥内，则必须在每一个octant的三个外平面的内侧

对于一个AABB，他的中心点到corner的距离（其实就是半个主对角线长度）必须要小于视锥中心点到视锥平面的距离，也就是下图$d_2 \le d_1$。

这个检测的消耗特别小，不过不够准（必要不充分）

视锥中心点到六个平面的距离可以在每一帧计算前全局做一次

标记视锥平面

如果一个物体在一个视锥平面内侧，说明这个物体的所有子物体都在这个视锥平面内侧，那么我后面对子物体进行视锥剔除时不需要再用这个平面进行计算了

在AABB上维护一个bitfield，记录这个物体是被六个平面中哪些平面裁掉的

连续性

TR：Translation and Rotation

帧是连续的，我们让AABB记录一个bitfield和一个buffer，bitfield记录这个物体是被哪些平面裁掉，buffer记录AABB距离六个平面的距离

如果一个物体在上一帧不可见，且视锥只移动了非常小的距离，那么这一帧这个物体大概率还是不可见
如果一个物体被视锥左平面剔除（可以复用“标记视锥平面”里的bitfield），那么视线向右转（不超过$180^{\circ}$）时，这个物体依然会不可见
如果相机只做移动，那么视锥平面到所有BV的最短距离均变化相同的值$\Delta d$（这个值可以全局只做一次），我们比较上一帧AABB到移动轴向两个平面的距离和$\Delta d$，即可判读这个物体可见性是否变化