Tighter Frustum Culling and Why You May Want to Disregard It
Inaccurate Frustum Culling
Many popular frustum culling algorithms, including our own implementation, do not produce completely accurate results when large objects are present in the scene. Large objects located outside but near the corners of the view frustum often pass the frustum culling check even though they are completely out of view. For us, this is important not only for rendering performance, but also for prevention of unnecessary network requests for tiles that are not visible.
The issue is that most frustum culling algorithms check whether the object is entirely outside at least one of the frustum planes. If so, it is definitely not visible to the camera. This works fine for small objects, but because the planes extend infinitely and the frustum check only computes which side of the plane an object is on, larger objects are more likely to be on the interior of all planes even if they are not visible. Inigo Quilez has written a good article titled Fixing Frustum Culling which explains when the false positive occurs and offers one simple solution for solving it.
We can classify these false positives, visualized below, into two categories:
- Objects intersecting the near plane, but slightly too far to the top, bottom, or side to be visible
- Objects intersecting the far plane, but slightly too far to the top, bottom, or side to be visible
In order for these false positives to happen, the objects need to at least partially intersect two of the frustum planes. Large objects located near the corners of the frustum are particularly prone to falling into this scenario.
The Solution:
Instead of just checking if an object is totally outside of one of the frustum planes, it is suggested to additionally check whether the frustum is entirely outside one of the planes of the object bounds to eliminate most of these incorrect results.
Any intersection test is just a simplification of the more general Separating Axis Theorem (SAT) which states that two convex objects A and B do not intersect if there exists an axis such that the projections of the objects onto that axis are disjoint.
In a standard frustum check, we check which side of a plane the object is on. A plane is defined by a point and a normal and the test that we do is equivalent to projecting the object onto the normal of the plane. We know that the entire frustum is on one side of the plane so we check if the object we’re checking against is entirely on the opposite side. Such a case would result in disjoint projections.
The inaccuracy comes in the fact that we have not checked all possible planes! A full test involves checking every face normal as well as the cross product of all pairs of edges eA x eB, where eA is an arbitrary edge from object A and eB is an arbitrary edge from object B.
Standard Box-Frustum Intersection Check
OrientedBoundingBox.intersectCullingVolume = function(box, volume) {
var intersecting = false;
var planes = volume.planes;
// Check box intersection with each plane of the frustum
for (var k = 0, len = planes.length; k < len; ++k) {
var result = box.intersectPlane(Plane.fromCartesian4(planes[k], scratchPlane));
// If the box is outside any plane, there is no intersection
if (result === Intersect.OUTSIDE) {
return Intersect.OUTSIDE;
} else if (result === Intersect.INTERSECTING) {
intersecting = true;
}
}
// If intersecting is true, we intersect at least one plane,
// and therefore the frustum is not entirely contained in the box
return intersecting ? Intersect.INTERSECTING : Intersect.INSIDE;
}
More Complete Box-Frustum Intersection Check
OrientedBoundingBox.intersectCullingVolume = function(box, volume) {
// first do the standard frustum check to determine if
// the box is outside any planes of the culling volume
var intersecting = false;
var planes = volume.planes;
for (var k = 0, len = planes.length; k < len; ++k) {
var result = box.intersectPlane(Plane.fromCartesian4(planes[k], scratchPlane));
if (result === Intersect.OUTSIDE) {
return Intersect.OUTSIDE;
} else if (result === Intersect.INTERSECTING) {
intersecting = true;
}
}
// in case of false positive, check if the frustum is outside any planes of the box
if (intersecting) {
var points = volume.points; // array of the corners of the frustum
var length = points.length;
var diffs = scratchDiffs;
// Vectors from volume corners to the box center
for (var j = 0; j < length; ++j) {
Cartesian3.subtract(points[j], box.center, diffs[j]);
}
// Project the vectors from corner to box center onto the box's half-axes
intersecting = false;
for (var i = 0; i < 3; ++i) {
var axis = scratchCartesian1;
axis.x = box.halfAxes[3*i];
axis.y = box.halfAxes[3*i+1];
axis.z = box.halfAxes[3*i+2];
// Use squared length so we don't have to normalize
var axisLengthSquared = Cartesian3.magnitudeSquared(axis);
var out1 = 0;
var out2 = 0;
// For each slab of the box, check if all points are on one side
for (j = 0; j < length; ++j) {
var proj = Cartesian3.dot(diffs[j], axis);
// Check if the point is outside the box's slab
if (proj >= axisLengthSquared) {
out1++; // number of points outside of the positive slab
} else if (proj < -axisLengthSquared) {
out2++; // number of points outside of the negative slab
}
}
if (out1 === length || out2 === length) {
return Intersect.OUTSIDE;
}
intersecting |= (out1 !== 0 || out2 !== 0);
}
return intersecting ? Intersect.INTERSECTING : Intersect.INSIDE;
}
};
Terrain tiles near the camera are exponentially smaller than those far away and unlikely to yield incorrect results when culling.
Our Frustum is Enormous
Because Cesium is designed to simultaneously support rendering of objects extremely close to the camera and extremely far from the camera, our frustum is very, very large and can sometimes extend far out into space. One case where the inaccurate frustum check fails is when objects intersect the far plane but are actually too far to the side to be visible. Unfortunately, because we want the entire depth of objects to be visible, Cesium’s algorithm does not even use the far plane when culling primitives. In other engines where there are walls occluding far objects and the far plane does not have to be located at infinity, this optimization may prove more beneficial.
But Cesium uses multiple frustums! Aren’t there unnecessary duplicate draw calls between adjacent frustums?
Yes, this is entirely possible and actually happens most of the time. It is common for a tile only located in Frustum 2 to be rendered in both Frustum 1 and Frustum 2. It usually occurs when a terrain tile in Frustum 2 also intersects the far plane of Frustum 1 but is too far to the side of the screen to be visible.
The problem is further exaggerated because we bin objects into frustums based only on the bounding sphere’s radius and distance to the camera. As long as there is more than one frustum, this problem is very reproducible… but it only happens twice. While very inaccurate depending on the shape of the object, the bounding sphere test is extremely fast. For our datasets, the only situations where these unnecessary duplicate draw calls occur is at the sides of the screen. Relative to the hundreds of draw calls needed to render the rest of the frame, it hardly seems worthwhile to do a more expensive frustum culling check. In our tests, better culling at this stage resulted in a reduction of 2 or 3 draw calls at an additional cost of 2ms per frame.
The highlighted tile in red is located only in Frustum 2. However, it is rendered in both Frustum 1 and Frustum 2 because it intersects the far plane (green line) of Frustum 1.
Typical Camera Orientations
We now consider our most common camera orientations to assess how prone they are to false positive frustum checks. As discussed above, our frustum is so large that we never get false positives against the far plane, so here we will consider only objects near to the camera.
Eye-Level: At eye level, only terrain tiles are below the camera. Because we have adaptive LOD, these will not be sufficiently large to present a problem. Furthermore, unless the camera is passing under a tunnel, it is unlikely for there to be any large objects directly above the camera. The only situations of concern are those where the camera is adjacent to a large object but looking slightly away from it.
Top-Down: In this orientation the camera is looking down on terrain or buildings and there are little to no objects intersecting the camera’s near plane.
45-Degree: In this orientation, the camera is in the sky and is looking down at a diagonal angle at terrain or buildings. As with the Top-Down view, there are little to no objects intersecting the camera’s near plane.
Conclusions
Before jumping on optimizations, it is important to understand the situations where they work best and understand how they apply in a specific context. In Cesium, we use a small number of very large frustums. We do have large objects in the scene, but they are small relative to the size of the frustums. As a result, there are only a few regions of space which yield incorrect results when culling. Clustered shading (slide 31) is a context where better culling is significantly more important. The view frustum is diced into many, many small frustums. Not only are the frustums small relative to the size of objects, but there are also a large number of frustums. In this context, incorrect culling would happen with much greater frequency.
Cesium typically handles hundreds of visible objects with only a few false positives. Tighter culling is certainly appealing, but it is not worth an additional two milliseconds of CPU time to reduce the number of draw calls by a tiny fraction. Even if the extra checks were free, saving only a few draw calls is an optimization that may not produce noticeable changes. We may return to optimizing these checks in the future, but we believe that there are other parts of Cesium that offer larger and more effective opportunities to improve performance. Unless the benefits are clear and obvious, we want to avoid adding additional complexity that only yields theoretical improvements without quantifiable results. Stay tuned!