Search code examples
openglgraphicsdirectxlwjglopentk

Correct frustum aabb intersection

I need 100% correct frustrum aabb intersection test for use with frustrum culling. The following link explains why most implementations fail at 100% correct test and provides a solution.

http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm

However, is that solution even not a 100% correct? Can you think of a case where that fails? I think I can, but hard to explain. Could you provide a better solution if you think this doesnt work?

Solution

  • You are right, the given solution is not 100% correct.

    What he is trying to do is the so called Separating Axis Theorem (or Hyperplane separation theorem).

    In the first half he's testing the axis defined by the planes of the frustum and in the second half he's testing the axis defined by the AABB. This is both correct and required for the SAT test.

    What he is missing though are the axis defined by the cross product of pairs of edges, one from each polyhedron. An AABB has 3 unique edges ( edges that have an unique direction) and a frustum has 6 unique edges. So the code is missing an overlap test on 3*6=18 possible separating axis.

    A single overlap test for a given axis looks like this:

    • Project all points of object A onto that axis. This will result in an intervall I1.
    • Project all points of object B onto that axis. This will result in an intervall I2.
    • If I1 does not overlap I2 a separating axis is found and A does not intersect B.
    • If I1 overlaps I2, this is not a separating axis -> test the next axis.