Frustum Culling

相比 Occlusion Culling，在 3D 引擎中更广泛使用的剔除技术其实是 Frustum Culling 和 Face Culling 面剔除，后者实现比较简单。

# 算法

1. 基础相交测试 the basic intersection test
2. 平面一致性测试 the plane-coherency test
3. 八分测试 the octant test
4. 标记 masking
5. 平移旋转一致性测试 TR coherency test

视锥体 VF 通过 6 个平面定义：
如果点 x 位于平面的外部，或者说“正面”，代入后则 > 0。
http://www.lighthouse3d.com/tutorials/view-frustum-culling/geometric-approach-extracting-the-planes/
> The planes are defined such that the normal points towards the inside of the view frustum. Testing if an object is inside the view frustum is performed by computing on which side of the plane the object resides. This can be done computing the signed distance from the point ot the plane. If it is on the side that the normal is pointing, i.e. the signed distance is positive, then it is on the right side of the respective plane. If an object is on the right side of all six planes then the object is inside the frustum.

## 基础相交测试

精确测试开销很大，对于视锥体的每一个平面，检测包围盒位于外部，内部，相交三种情况。

如果在一次测试中包围盒位于正面，说明包围盒位于视锥体外，就可以终止测试。
如果包围盒位于所有平面背部，说明包围盒位于视锥体中，其余情况说明包围盒和视锥体的平面相交。
对于测试结果为相交的包围盒，我们继续测试它的孩子结点。

⚠️需要注意的是包围盒中心位于灰色区域时，尽管包围盒并不相交，但是测试结果却是相交。这是和测试相交的方法相关的。

那么如何确定一个包围盒和平面相交呢？
> 很自然，我们会想到使用包围盒的 8 个顶点与视锥体平面进行测试。但实际上，这样做并不必要，只需要使用离平面最近和最远的包围盒对角线上的两个顶点即可。我们将这两个顶点分别叫做 n- 顶点 和 p- 顶点 ，其中 p- 顶点 到平面的有向距离大于 n- 顶点 。


具体伪代码如下：

那么如何确定 p- 和 n- 呢？通过下面的查找表，根据平面法向量的 xyz 分量符号，就可以确定 p- 和 n-。

这里给出目前算法的实现，(a,b,c) 是平面的法线坐标：
```c++
int AABBvsFrustum(AABB *b, FRUSTUM *f)
{
float m, n; int i, result = INSIDE;

for (i = 0; i < 6; i++) {
PLANE *p = f->plane + i;

m = (p->a * b->v[p->nx].x) + (p->b * b->v[p->ny].y) + (p->c * b->v[p->nz].z);
if (m > -p->d) return OUTSIDE;

n = (p->a * b->v[p->px].x) + (p->b * b->v[p->py].y) + (p->c * b->v[p->pz].z);
if (n > -p->d) result = INTERSECT;

}
return result;
}
```

## 平面一致性测试

> 假设一个节点在上一次的视锥体测试中位于其中一个视锥体平面正面。如果视锥体进行微小地移动，这一结点在这一次测试中仍有很大的概率完全位于视锥体外，应该首先进行可以快速剔除的这一节点的视锥体平面测试。

检测结果处于 outside 的平面 `idx` 保存在 `start_id` 中，在后续检测中优先进行这个面的检测：
```c++
int AABBvsFrustum(AABB *b, FRUSTUM *f, int in_mask, int *out_mask)
{
float m, n; int i, k = 1 << b->start_id, result = INSIDE;

PLANE *sp = f->plane + b->start_id; *out_mask=0;

// 优先进行上一次处于外部的平面测试
if (k & in_mask) {

m = (sp->a * b->v[sp->nx].x) + (sp->b * b->v[sp->ny].y) + (sp->c * b->v[sp->nz].z);
if (m > -sp->d) return OUTSIDE;

n = (sp->a * b->v[sp->px].x) + (sp->b * b->v[sp->py].y) + (sp->c * b->v[sp->pz].z);
if (n > -sp->d) { *out_mask |= k; result = INTERSECT; }

}

for (i = 0, k = 1; k <= in_mask; i++, k += k)

if ((i != b->start_id) && (k & in_mask)) {
PLANE *p = f->plane + i;

m = (p->a * b->v[p->nx].x) + (p->b * b->v[p->ny].y) + (p->c * b->v[p->nz].z);
if (m > -p->d) { b->start_id = i; return OUTSIDE; } // 保存外部平面的 idx

n = (p->a * b->v[p->px].x) + (p->b * b->v[p->py].y) + (p->c * b->v[p->pz].z);
if (n > -p->d) { *out_mask |= k; result = INTERSECT; }

}

return result;
}
```

## 八分测试

视锥体通常都是对称的，划分成 8 个象限后，在检测对称的包围盒（例如球体）时

对于非球体的包围盒：
包围盒满足它的中心到它的顶点距离必须小于视锥体中心到视锥体平面的最小距离，满足这一性质后，包围盒如果没有和离它最近的三个视锥体平面(一个象限的外平面)相交，也就不会和其它象限的外平面相交。

但是实现起来比较困难：
> The comparison of two distances are needed that are computed after any change in the geometry of the AABB and the VF. These computations are called heavily in dynamic scenes so after the activating of this test the VFC is slowed down. Because of this we do not find this test useful and we will not introduce its relatively complicated implementation.

## 标记

和遮挡剔除时类似，对于场景中的层次性结构 bounding volume hierarchies (BVHs)，例如 SceneGraph，如果一个包围盒已经完全处于视锥体内部，其子节点的包围盒也就不需要检测了。这就需要通过节点标记实现。

在遍历层次结构时，可以将父节点和视锥平面的相交情况通过 mask 传入：
```c++
int AABBvsFrustum(AABB *b, FRUSTUM *f, int in_mask, int *out_mask)
{
float m, n; int i, k, result = INSIDE; *out_mask=0;

for (i = 0, k = 1; k <= in_mask; i++, k += k) if (k & in_mask) {

PLANE *p = f->plane + i;

m = (p->a * b->v[p->nx].x) + (p->b * b->v[p->ny].y) + (p->c * b->v[p->nz].z);
if (m > -p->d) return OUTSIDE;

n = (p->a * b->v[p->px].x) + (p->b * b->v[p->py].y) + (p->c * b->v[p->pz].z);
if (n > -p->d) { *out_mask |= k; result = INTERSECT; }

}
return result;
}
```

JS 实现可以参考后续的 WebGL - Cesium 实现。

## 平移旋转一致性测试

http://www.lighthouse3d.com/tutorials/view-frustum-culling/further-optimization/

# WebGL 实现

调研了 OSG、Clay.gl、Three.js、Cesium 等实现。

## OSG

虽然内部也提供了包围盒的检测，但是 OSG 默认使用了包围球。因此上面算法中的“平面一致性”和“标记”优化都有所体现。
首先来看 OSG.js 中的实现。在 OSG 中 CullVisitor 会遍历场景树，对每个节点判断 isCulled。
上面的“标记”优化体现在 getCurrentResultMask，节点父节点的 _resultMask 存储在栈中：
```javascript
isCulled: (function() {
var bsWorld = new BoundingSphere();
return function(node, nodePath) {
// 父节点在视锥内，直接剔除
if (this.getCurrentCullingSet().getCurrentResultMask() === 0) return false;

// 省略对 bsWorld 应用变换

// 检测包围球
return this.getCurrentCullingSet().isBoundingSphereCulled(bsWorld);
};
})(),
```

在视锥（polytope）中定义了包围球检测方法：
```javascript
containsBoundingSphere: function(bs) {
var polytopeBack = this._maskStack.back();
if (!polytopeBack || !bs.valid()) return true;

this._resultMask = polytopeBack;
var selectorMask = 0x1;

for (var i = 0; i < this._planeList.length; ++i) {
if (this._resultMask & selectorMask) {
var res = Plane.intersectsOrContainsBoundingSphere(this._planeList[i], bs);
if (Plane.OUTSIDE === res) {
// totally outside a clipping set.
return false;
} else if (Plane.INSIDE === res) {
// subsequent checks against this plane not required.
this._resultMask ^= selectorMask;
}
}
selectorMask <<= 1;
}
return true;
},
```

平面和包围球求交，判断球半径和球心到平面距离即可：
```javascript
intersectsOrContainsBoundingSphere: function(plane, bSphere) {
if (!bSphere.valid()) return Plane.OUTSIDE;
var position = bSphere.center();
var radius = bSphere.radius();
var d = this.distanceToPlane(plane, position);
if (d < -radius) {
return Plane.OUTSIDE;
} else if (d <= radius) {
return Plane.INTERSECT;
}
return Plane.INSIDE;
},
```

## Clay.gl

从注释也能看出 clay.gl 参考了「Optimized View Frustum Culling Algorithms for Bounding Boxes」🔗
并且使用了包围盒进行检测。
首先 clay.gl 中视锥的包围盒是一个 AABB 包围盒，而不是最精确的平截头。这也是为后续两个包围盒求交提供便利。
```javascript
var Frustum = function() {
this.boundingBox = new BoundingBox();
}
```

如果包围盒与视锥不相交，或者包围盒位于近平面或者远平面之外，则裁减掉：
```javascript
isFrustumCulled: (function () {
// http://www.cse.chalmers.se/~uffe/vfc_bbox.pdf
var cullingBoundingBox = new BoundingBox();
var cullingMatrix = new Matrix4();
return function(object, camera, worldViewMat) {

var geoBBox = object.boundingBox;

// 包围盒转换到 view 坐标空间
cullingMatrix.array = worldViewMat;
cullingBoundingBox.transformFrom(geoBBox, cullingMatrix);

if (object.frustumCulling) {
// 不相交，裁剪
if (!cullingBoundingBox.intersectBoundingBox(camera.frustum.boundingBox)) {
return true;
}

cullingMatrix.array = camera.projectionMatrix.array;
if (
cullingBoundingBox.max.array[2] > 0 &&
cullingBoundingBox.min.array[2] < 0
) {
// Clip in the near plane
cullingBoundingBox.max.array[2] = -1e-20;
}

cullingBoundingBox.applyProjection(cullingMatrix);

var min = cullingBoundingBox.min.array;
var max = cullingBoundingBox.max.array;

// 位于近平面或者远平面之外
if (
max[0] < -1 || min[0] > 1
|| max[1] < -1 || min[1] > 1
|| max[2] < -1 || min[2] > 1
) {
return true;
}
}

return false;
};
})(),
```

可见 clay.gl 的视锥裁剪并不是最精确的，而是使用了视锥包围盒加快剔除速度。

## Three.js

https://github.com/mrdoob/three.js/issues/56
相较之下，Three.js 使用了精确定义的视锥：
```javascript
function Frustum( p0, p1, p2, p3, p4, p5 ) {
this.planes = [
( p0 !== undefined ) ? p0 : new Plane(),
( p1 !== undefined ) ? p1 : new Plane(),
( p2 !== undefined ) ? p2 : new Plane(),
( p3 !== undefined ) ? p3 : new Plane(),
( p4 !== undefined ) ? p4 : new Plane(),
( p5 !== undefined ) ? p5 : new Plane()
];
}
```

但是也只是基础的相交测试，后续的优化方式例如“平面一致性”，“标记”等手段并没有使用。

## Babylon.js

相比之下 Babylon.js 的视锥剔除策略更全：
https://doc.babylonjs.com/how_to/optimizing_your_scene#changing-mesh-culling-strategy
> By default, BABYLON applies the most accurate test to check if a mesh is in the camera frustum.
You can change this behaviour for any mesh of your scene at any time (and change it back then, if needed) this the property mesh.cullingStrategy.

一共提供了 4 种策略：
• Standard : the more accurate and standard one (exclusion test)
• Bounding Sphere Only : faster but less accurate (exclusion test)
• Optimistic Inclusion : mesh center inclusion test then standard exclusion test, for meshes almost always expected in the frustum. Same accuracy than the standard test.
• Optimistic Inclusion Then Bounding Sphere Only : mesh center inclusion test, then bounding sphere exclusion test only. Same accuracy than the bSphereOnly test, interesting for almost always in the frustum meshes.

先进行包围球的检测，然后才是包围盒。个人认为这种支持各个 mesh 自己来定义裁剪策略的方式很不错：
```typescript
// Culling/boundingInfo.ts

public isInFrustum(frustumPlanes: Array>, strategy: number = Constants.MESHES_CULLINGSTRATEGY_STANDARD): boolean {
let inclusionTest = (strategy === Constants.MESHES_CULLINGSTRATEGY_OPTIMISTIC_INCLUSION
|| strategy === Constants.MESHES_CULLINGSTRATEGY_OPTIMISTIC_INCLUSION_THEN_BSPHERE_ONLY);
if (inclusionTest) {
if (this.boundingSphere.isCenterInFrustum(frustumPlanes)) {
return true;
}
}

if (!this.boundingSphere.isInFrustum(frustumPlanes)) {
return false;
}

let bSphereOnlyTest = (strategy === Constants.MESHES_CULLINGSTRATEGY_BOUNDINGSPHERE_ONLY
|| strategy === Constants.MESHES_CULLINGSTRATEGY_OPTIMISTIC_INCLUSION_THEN_BSPHERE_ONLY);
if (bSphereOnlyTest) {
return true;
}

return this.boundingBox.isInFrustum(frustumPlanes);
}
```

但是同样的也只是最基础的实现，并没有应用后续的优化手段。比如在包围盒的检测中，还是会尝试 8 个顶点，并不会使用 p- 和 n-，也没有应用平面一致性的优化手段。

## Cesium

相比之下，Cesium 就参考了上面那篇「Efficient View Frustum Culling」🔗论文的做法：
https://cesium.com/blog/2015/08/04/fast-hierarchical-culling/

由于父节点和视锥的每个平面只有 内部 和 相交 这两种情况，因此可以使用 01 掩码（6位表示六个面）表示。
这样的好处是如果父节点在平面内部则子节点可以跳过检测：

> In order to pass this state efficiently down the BVH, a bit mask is used. For plane number k, the kth bit of the bit mask is 1 if the parent node is intersecting plane k, and 0 if it is inside. If the parent node is outside, the children will not be traversed at all. Since we are using JavaScript, we use a 32-bit integer as our bit mask. (A frustum has only 6 planes, so this is plenty.)

下图很好的展示了 A-BC 层次结构的判定流程：

内部、外部以及与 6 个面相交三种情况的 32 位掩码定义如下：
```javascript
CullingVolume.MASK_OUTSIDE = 0xffffffff;
CullingVolume.MASK_INSIDE = 0x00000000;
CullingVolume.MASK_INDETERMINATE = 0x7fffffff; // 和6个面都相交 0111 1111
```

将 parentPlaneMask 传入，完全按照“标记”的优化算法实现：
```javascript
CullingVolume.prototype.computeVisibilityWithPlaneMask = function(
boundingVolume, // 包围盒
parentPlaneMask // 掩码
) {
if (parentPlaneMask === CullingVolume.MASK_OUTSIDE
|| parentPlaneMask === CullingVolume.MASK_INSIDE) {
// 父节点完全位于视锥内或者外部，直接返回
return parentPlaneMask;
}

var mask = CullingVolume.MASK_INSIDE;

var planes = this.planes;
for (var k = 0, len = planes.length; k < len; ++k) {
// 构建当前面的掩码 0x0010
var flag = (k < 31) ? (1 << k) : 0;
if (k < 31 && (parentPlaneMask & flag) === 0) {
// 父节点处于当前面内部，可以跳过
continue;
}

// 父节点和当前面相交，需要进一步判断当前节点
var result = boundingVolume.intersectPlane(Plane.fromCartesian4(planes[k], scratchPlane));
// 包围盒完全位于外部，直接返回
if (result === Intersect.OUTSIDE) {
return CullingVolume.MASK_OUTSIDE;
} else if (result === Intersect.INTERSECTING) {
// 和当前面相交，对应位置为1，继续检测下一个面
mask |= flag;
}
}
return mask;
};
```

另外作者也开了关于应用“八分测试”的 ISSUE，但是还没有实现
https://github.com/AnalyticalGraphicsInc/cesium/issues/4787

# 参考资料

「Optimized View Frustum Culling Algorithms for Bounding Boxes」[🔗](http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/vfcullbox.pdf.gz)
「Efficient View Frustum Culling」[🔗](http://old.cescg.org/CESCG-2002/DSykoraJJelinek/)
「视锥体剔除AABB和OBB包围盒的优化方法」[🔗](https://zhuanlan.zhihu.com/p/55915345)
「Unreal - Visibility and Occlusion Culling」[🔗](https://docs.unrealengine.com/Engine/Rendering/VisibilityCulling#viewfrustum)
「Lighthouse3D - View Frustum Culling」[🔗](http://www.lighthouse3d.com/tutorials/view-frustum-culling/)
「Cesium - Fast Hierarchical Culling」[🔗](https://cesium.com/blog/2015/08/04/fast-hierarchical-culling/)
「Cesium - Hierarchical Culling With Children Bounding Volumes」[🔗](https://cesium.com/blog/2017/02/17/hierarchical-culling-with-children-bounding-volumes/)
「Some Notes and Possible Optimizations」[🔗](http://www.lighthouse3d.com/tutorials/view-frustum-culling/some-notes-and-possible-optimizations/)

The issue names no repository file or test. Start by reviewing the cited frustum-culling references and the Three.js, Babylon.js, and Cesium implementations described here; define the desired TypeScript/WebGL scope and acceptance checks before implementation.

Written by the indexing model from the issue text.