Frustum: IntersectsBox function can produce incorrect results

[gkjohnson]

Description

The Frustum.intersectsBox function can produce a false positive in some cases where a box outside the frustum is large enough and positioned such that it crosses multiple frustum planes and therefore is not marked as separated by a single plane. This article suggests that checking whether the planes of the box separate the shapes will provide a more consistent result (though still not perfect in all cases). In order to do that we'd likely need to store or compute the edge points of the frustum.

This is related to 3DTilesRendererJS. We were using an OBB / Frustum intersect function based on the three.js AABB implementation and were seeing that a lot of tiles were visible despite being a large distance from the camera.

cc @WestLangley

Reproduction steps

Configure a box and frustum such that they produce the error case (See jsfiddle)

Code

See jsfiddle.

Live example

https://jsfiddle.net/89rtuaqp/2/

The box is colored red if it intersects the visualized camera frustum.

Screenshots

Version

161

Device

No response

Browser

No response

OS

No response

[WestLangley]

For further reference, see Unity's implementation.

[gkjohnson]

Looks like the Babylon.js implementation is wrong, as well. Though I do see some notion online that these imperfect intersection tests are used under the assumption that the improved performance of the test is worth the trade off of missing some cases. If that's something we want it would be nice to at least document or rename the function Frustum.intersectBoxFast or something.

Unity's implementation appears to be based on Inigo's article that I linked. Here's another implementation from MathGeoLib using separating axis theorem, though it's more general: link.

One issue now, though, is that all these implementations require knowledge of the frustum corner points which are not stored in the Frustum class. Of course we can compute these from the planes with the assumption that a frustum is well formed but this will break if the user sets the frustum to use invalid values for the frustum (ie three parallel planes) or be subject to floating point error in some cases (almost parallel planes). The points are easy to calculate if we have the matrix used to derive the planes, which I expect is the 99.9% case for setting it.

[AlaricBaraou]

There is an issue in the example @gkjohnson matrix.multiplyMatrices( camera.projectionMatrix, camera.matrixWorldInverse ); it should be matrix.multiplyMatrices( frustumCamera.projectionMatrix, frustumCamera.matrixWorldInverse ); But then to trigger the bug with the frustum with this configuration you have to increase the scale to something like box.scale.set( 8, 1, 8 );

Here is an updated example with an attempt at extending the Frustum class to handle this case. I based the solution on the article shared without much considerations for the perf nor looking at what Babylon does etc, maybe there is a better option out there. https://jsfiddle.net/sxfuh1pr/18/ adding && frustum.boxInFrustum( bounds ) after frustum.intersectsBox( bounds ) remove this type of false positive without impacting creating false negative as far as I know,

[gkjohnson]

A tighter frustum intersection function has been implemented for 3d tiles renderer here in https://github.com/NASA-AMMOS/3DTilesRendererJS/pull/483 for oriented bounding boxes. The ExtendedFrustum class generates and caches the corners of the frustum when setting the frustum matrix. The points are generated by finding the intersection of 3 of the planes that form of the frustum.

These points could be generated as-needed if we don't want to cache them but either way this presupposes that we know which planes intersect to form a corner. However right now with the current set function it's not possible to know which planes form corner because it's explicitly stated that no order is implied:

Sets the frustum from the passed planes. No plane order is implied.

If the set function were more structured (or did not exist) this would be easier to solve. I suppose we could try to figure out the structure by analyzing the planes but that seems more complicated and error prone.