I couldn’t find much (helpful) info about this online, other than “just use SAT” in a sentence with no code or explanation.

Maybe my Google-Fu failed me. But considering Emil Persson labelled this a hard problem, perhaps it isn’t only me (note: Hard here does not refer to Hard NP. He just meant it’s not trivial)

Pyramid vs Frustum tests are useful because Pyramids are a good way to enclose a cone that fits relatively tight (i.e. it’s much tighter than a sphere, an AABB, or an OOB) and the test is needed for efficiently implementing Forward+, Clustered Forward, and tiled deferred shading pipelines.

The goals are:

1. No false negatives.
2. False positives should be kept to a minimum but is ultimately acceptable. The more our false positives are, the slower our performance.
3. Relatively easy and fast to compute.

After endlessly browsing and failing to find something that would satisfy me, I ended up resorting brute force. After all clustered forward was SIMD friendly (with SSE I could test 4 frustums against 1 pyramid at a time) and thread-friendly (each slice of clustered forward goes into its own thread)

The first attempts would be to test all 5 vertices of the pyramid to see if they’re inside the frustum, then test the 8 vertices of the frustum inside the Pyramid. This will not work because here’s a simple case where no vertex is inside anyone’s shape yet they are clearly intersecting:

So I went a different but similar route: If all 5 vertices lie in the negative side of a plane, then we don’t have a collision.

A frustum has 6 planes. A Pyramid has 5 vertices. So we need to perform 5×6 tests. In pseudocode:

intesects = true;
foreach plane : frustum
    oneVertexInsidePlane = false;
    foreach vertex : pyramid
        if vertex is in positive side of plane
            oneVertexInsidePlane = true;
    intesects &= oneVertexInsidePlane;

Let’s see this graphically:

But what about our edge case from before?

None of the 4 planes (in 2D it’s 4 planes, in 3D it’s 6) has all vertices in their negative side:

• Plane M has all vertices in its positive side
• Plane N has A & B in its positive side, C in its negative side
• Plane O has B & C in its positive side, A in its negative side
• Plane P has C in its positive side, A & B in its negative side.

That hard case we were worried? It’s not a problem anymore. It’s being handled correctly.

So we’re done right? Not quite.

Ruling out false positives

The problem with this algorithm, is that, as is, generates a lot of false positives:

In this screenshot, none of the planes has all vertices in their negative side, which means our algorithm thinks they’re intersecting; when they’re clearly not. This is essentially the same problem Iñigo Quilez warns about common Frustum vs AABB intersection code out there. It fails on the case where the pyramid is so much bigger than the frustum that it manages to cross every plane by doing it from the outside. Unfortunately for us, this is a very common scenario, so this level of false positives is not acceptable.

So I did what Iñigo suggested: reverse the roles!

After testing Pyramid vs Frustum; if we still think they collide; now check Frustum vs Pyramid: 8 vertices against 6 planes. Wait, 6? Yes I just added one more by inverting the normal of the pyramid’s far plane, treating the pyramid as if it were a frustum. I suspect this isn’t needed though.

Let’s check that last screenshot one more time, this time with roles reversed:

All 4 vertices (ABCD) are on the negative side of plane P. Now we correctly think this case does not intersect. Now it’s done!

Extending to 3D

A 3D frustum has 8 vertices and 6 planes.

A 3D pyramid has 5 vertices and 5 planes (I use 6)

That means we need 8 x 6 + 5 x 6 = 78 tests. Luckily each test consist in 1 dot product, 1 addition, 1 equality test and 1 ‘or’ operation.

That’s a lot of tests, but it can be done branchless or branchy, SIMD to test multiple frustums at the same time, and threadable. And the improvements are huge because the tests fit really tight. Personally I chose to do branchless because of SIMD, but to use a jump if all 4 SIMD lanes think there is no collision after Pyramid vs Frustum; in order to skip the Frustum vs Pyramid test.

Oh you want some code? Ok fine here it is:

struct Plane
{
    float3 normal;
    float d;
};
 
Plane pyramidPlanes[6];
float3 pyramidVertices[5];
 
Plane frustumPlanes[6];
float3 frustumCorners[8];
 
bool intersects = true;
 
//Do Pyramid vertices vs Frustum planes
for( int i=0; i<6; ++i )
{
    bool isAnyVertexInPositiveSide = false;
    for( int j=0; j<5; ++j )
    {
        float dotResult = dot( frustumPlanes[i].normal, pyramidVertices[j] ) + frustumPlanes[i].d;
        isAnyVertexInPositiveSide |= dotResult > 0;
    }
 
    intersects &= isAnyVertexInPositiveSide;
}
 
//Now do Frustum vertices vs Pyramid planes
for( int i=0; i<6; ++i )
{
    bool isAnyVertexInPositiveSide = false;
    for( int j=0; j<8; ++j )
    {
        float dotResult = dot( pyramidPlanes[i].normal, frustumCorners[j] ) + pyramidPlanes[i].d;
        isAnyVertexInPositiveSide |= dotResult > 0;
    }
 
    intersects &= isAnyVertexInPositiveSide;
}
//intersects now contains the final value.

You can early out whenever intersects becomes false.
Extending this method for Frustum vs Frustum is very easy. Just use 8 vertices instead of the 5 the pyramid has.

Oh you want a real case example with SIMD? Browse the Ogre3D repository then.

All in all I’m very happy with the results. So far my tests indicate all of our spotlights are being handled correctly, with very tight volumes as shown by our Debug Mode.

I came up with this algorithm on my own during a weekend. It’s not exactly the smartest one (i.e. 78 tests!) but fulfills all of our requirements (the GPU savings are huge and CPU impact looks negligible). If someone thinks it’s broken (i.e. has a false negative or false positive somewhere) or has some contribution to do, then let me know.

Update 2023-05-20

User jwwalker pointed out my algorithm works in 2D but when expanded to 3D the following case will result in a false positive:

I think he is correct. We’d have to research if:

1. This false positive is actually a problem (Forward+ is ok with some false positives, but they affect performance. See goals above); i.e. if in practice this happens very rarely, then it’s not a problem.
2. It’s possible to eliminate this false test with a CPU cost that is lower than the GPU cost of the false positive.