apparent error in frustum/frustum intersection test Topic is solved

Discussion area about developing with Ogre-Next (2.1, 2.2 and beyond)


Post Reply
jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

apparent error in frustum/frustum intersection test

Post by jwwalker »

I was trying to understand how the PlanarReflections library works, and saw a comment referring to an algorithm at www.yosoygames.com.ar/wp/2016/12/frustum-vs-pyramid-intersection-also-frustum-vs-frustum/. That article is also used in OgreForwardClustered.cpp. The web page no longer exists, but I found it in the Wayback Machine:

https://web.archive.org/web/20190501231 ... s-frustum/

The article first discusses a 2D version, and then basically says that we'll do the same thing in 3D. The idea is that if a face of one polyhedron has all of the vertices of the other one on its outside, then the polyhedrons don't intersect. That works in 2D, but can produce false positives in 3D. Here's a configuration of 2 cubes that are not separated by any face.

Image

jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

Re: apparent error in frustum/frustum intersection test

Post by jwwalker »

Correction: The page does still exist. If I enter just the given path www.yosoygames.com.ar/wp/2016/12/frustum-vs-pyramid-intersection-also-frustum-vs-frustum/ into the address bar in Safari, it somehow gets translated to https://www.yosoygames.com.ar/2016/12/frustum-vs-pyramid-intersection-also-frustum-vs-frustum/, which doesn't exist. Note the missing /wp/ part in the path. But if I explicitly add https:// to the path given in the comments, it works.

User avatar
dark_sylinc
OGRE Team Member
OGRE Team Member
Posts: 5292
Joined: Sat Jul 21, 2007 4:55 pm
Location: Buenos Aires, Argentina
x 1278
Contact:

Re: apparent error in frustum/frustum intersection test

Post by dark_sylinc »

Thanks! I've updated my post with your counter example.

Please note that this frustum/frustum test is not used in PlanarReflections.
It's only used for Forward Clustered; and false positives are allowed but potentially undesirable:

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.

The page does still exist. If I enter just the given path www.yosoygames.com.ar/wp/2016/12/frustu ... s-frustum/ into the address bar in Safari, it somehow gets translated to

Looks like Ogre forums default links to HTTP (eww), and my HTTP to HTTPS redirect is broken... again.

Edit: Looks like I'm a grandpa who doesn't remember his own code he wrote. I can see PlanarReflections::update is using the same algorithm.

User avatar
dark_sylinc
OGRE Team Member
OGRE Team Member
Posts: 5292
Joined: Sat Jul 21, 2007 4:55 pm
Location: Buenos Aires, Argentina
x 1278
Contact:

Re: apparent error in frustum/frustum intersection test

Post by dark_sylinc »

OK now that Grandpa Matias has started to shaken his memory a bit; I'm starting to remember:

First, I didn't realize of the false positive, so I reused the same algorithm (since I already had optimized code) for Planar Reflections assuming it was perfect.

Second, for ForwardClustered, the camera is often subdivided into 16x8x24 = 3072 sub-frustums.

If, for example, we have 500 spot lights on scene, we must do 3072 x 500 = 1.536.000 frustum vs frustum tests. This is... expensive.
In fact ForwardClustered is quite CPU intensive (you can notice your CPU fans go up in Forward3D sample when in Clustered mode).

We use full SIMD and threading to share the load.

A full SAT test would be perfect, but it would be even more expensive.

Now the PlanarReflections is a different thing; because you typically have just 1 camera frustum and... I don't know... 1-5 actors? Most people who want to use Planar reflections would use it either for a bit of furniture or a lake/ocean.

Even if you have 1000 actors (which means 1000 tests), we'd still be far away from 1.536.000 tests.

Therefore spending more CPU cycles to take care of false negatives in planar reflections is a reasonable thing to do, whereas in Forward Clustered, it's a questionable decision.

jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

Re: apparent error in frustum/frustum intersection test

Post by jwwalker »

Oh, I hadn't noticed that you were the author of that site! Oops! I did read the part where you said your goals allowed false positives, but there's also a section heading "ruling out false positives". So I'm glad you clarified the fact that you only ruled out false positives in the 2D case.

The general algorithm for determining whether two convex polyhedra intersect involves projecting their vertices onto a set of lines, not only the lines normal to the faces but also cross products of an edge from one polyhedron and an edge from the other polyhedron. A frustum has 12 edges, but some are parallel so you really only need to use 6 edges from each. A box has even more parallelism, having 3 edge directions. At least in the PlanarReflections case one of the polyhedra can be considered a degenerate box rather than a degenerate frustum.

jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

Re: apparent error in frustum/frustum intersection test

Post by jwwalker »

@dark_sylinc One more thing that's puzzling me about the culling code in PlanarReflections::update. There's a section headed by the comment "Test all 4 quad vertices against each of the 6 frustum planes." But when I see for instance

Code: Select all

                tangentDir = actorsPlanes->planeNormals.yAxis() * actorsPlanes->xyHalfSize[1];
                vertexPoint = actorsPlanes->center + tangentDir;

it looks to me like it's testing the midpoints of the edges, not the corners of the quads.

User avatar
dark_sylinc
OGRE Team Member
OGRE Team Member
Posts: 5292
Joined: Sat Jul 21, 2007 4:55 pm
Location: Buenos Aires, Argentina
x 1278
Contact:

Re: apparent error in frustum/frustum intersection test

Post by dark_sylinc »

You're right. That looks wrong. It's calculating the midpoints.

The edges would need:

Code: Select all

ArrayVector3 tangentDir, vertexPoint, xMidpoint, yMidpoint;

xMidpoint = actorsPlanes->planeNormals.xAxis() * actorsPlanes->xyHalfSize[0];
yMidpoint = actorsPlanes->planeNormals.yAxis() * actorsPlanes->xyHalfSize[1];

tangentDir = xMidpoint + yMidpoint;

and

tangentDir = xMidpoint - yMidpoint;

So that the code ends up:

Code: Select all

ArrayMaskR vertexMask = ARRAY_MASK_ZERO;
ArrayReal dotResult;

ArrayVector3 tangentDir, vertexPoint, xMidpoint, yMidpoint;      

xMidpoint = actorsPlanes->planeNormals.xAxis() * actorsPlanes->xyHalfSize[0];
yMidpoint = actorsPlanes->planeNormals.yAxis() * actorsPlanes->xyHalfSize[1];

tangentDir = xMidpoint + yMidpoint;
vertexPoint = actorsPlanes->center + tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint ) - frustums[k].negD;
vertexMask =
  Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, ARRAY_REAL_ZERO ) );

vertexPoint = actorsPlanes->center - tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint ) - frustums[k].negD;
vertexMask =
  Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, ARRAY_REAL_ZERO ) );

tangentDir = xMidpoint - yMidpoint;
vertexPoint = actorsPlanes->center + tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint ) - frustums[k].negD;
vertexMask =
  Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, ARRAY_REAL_ZERO ) );

vertexPoint = actorsPlanes->center - tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint ) - frustums[k].negD;
vertexMask =
  Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, ARRAY_REAL_ZERO ) );

mask = Mathlib::And( mask, vertexMask );

Are you able to test those changes so I can push that?

jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

Re: apparent error in frustum/frustum intersection test

Post by jwwalker »

That looks like an improvement, but now I'm getting a false negative in the next phase of the computation, where frustum corners are tested against actor planes.

So, the idea is that we want to verify that for every actor plane, some frustum corner is on the inner side of it, yes? And the inner side is where the dot product of the normal with the corner is greater than a certain number. Hence we should use inward-facing normals. but when I see for instance

Code: Select all

                // North plane
                actorPlaneNormal = actorsPlanes->planeNormals.yAxis();

that looks to me like you're using a normal that faces away from the north edge of the actor quad.

User avatar
dark_sylinc
OGRE Team Member
OGRE Team Member
Posts: 5292
Joined: Sat Jul 21, 2007 4:55 pm
Location: Buenos Aires, Argentina
x 1278
Contact:

Re: apparent error in frustum/frustum intersection test

Post by dark_sylinc »

I took a look and... you're right? :shock: :shock: how did this even work?

The planes are defined in PlanarReflectionActor::updateArrayActorPlane and indeed the axes in PlanarReflections::update are incorrectly flipped.

The code AFAICT should be:

Code: Select all

// Test all 4 quad vertices against each of the 6 frustum planes.
for( int k = 0; k < 6; ++k )
{
    ArrayMaskR vertexMask = ARRAY_MASK_ZERO;
    ArrayReal dotResult;

ArrayVector3 tangentDir, vertexPoint, xMidpoint, yMidpoint;

xMidpoint = actorsPlanes->planeNormals.xAxis() * actorsPlanes->xyHalfSize[0];
yMidpoint = actorsPlanes->planeNormals.yAxis() * actorsPlanes->xyHalfSize[1];

tangentDir = xMidpoint + yMidpoint;
vertexPoint = actorsPlanes->center + tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint );
vertexMask =
    Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, frustums[k].negD ) );

vertexPoint = actorsPlanes->center - tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint );
vertexMask =
    Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, frustums[k].negD ) );

tangentDir = xMidpoint - yMidpoint;
vertexPoint = actorsPlanes->center + tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint );
vertexMask =
    Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, frustums[k].negD ) );

vertexPoint = actorsPlanes->center - tangentDir;
dotResult = frustums[k].normal.dotProduct( vertexPoint );
vertexMask =
    Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, frustums[k].negD ) );

mask = Mathlib::And( mask, vertexMask );
}

if( BooleanMask4::getScalarMask( mask ) != 0 )
{
    // Test all 8 frustum corners against each of the 6 planes (5+1).
    ArrayVector3 actorPlaneNormal;
    ArrayReal actorPlaneNegD;
    ArrayReal dotResult;
    ArrayMaskR vertexMask;

// Main plane (positive side)
actorPlaneNormal = actorsPlanes->planeNormals.zAxis();
actorPlaneNegD = actorsPlanes->planeNegD[0];
vertexMask = ARRAY_MASK_ZERO;
// Only test against the vertices from the near frustum. If they're all
// in the negative side of this plane, then this plane is looking
// away from the camera
// for( int l=0; l<8; ++l )
for( int l = 0; l < 4; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );

// Main plane (negative side)
actorPlaneNormal = -actorPlaneNormal;
actorPlaneNegD = -actorsPlanes->planeNegD[0];
vertexMask = ARRAY_MASK_ZERO;
for( int l = 0; l < 8; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );

// North plane
actorPlaneNormal = -actorsPlanes->planeNormals.yAxis();
actorPlaneNegD = actorsPlanes->planeNegD[1];
vertexMask = ARRAY_MASK_ZERO;
for( int l = 0; l < 8; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );

// South plane
actorPlaneNormal = -actorPlaneNormal;
actorPlaneNegD = actorsPlanes->planeNegD[2];
vertexMask = ARRAY_MASK_ZERO;
for( int l = 0; l < 8; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );

// East plane
actorPlaneNormal = -actorsPlanes->planeNormals.xAxis();
actorPlaneNegD = actorsPlanes->planeNegD[3];
vertexMask = ARRAY_MASK_ZERO;
for( int l = 0; l < 8; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );

// West plane
actorPlaneNormal = -actorPlaneNormal;
actorPlaneNegD = actorsPlanes->planeNegD[4];
vertexMask = ARRAY_MASK_ZERO;
for( int l = 0; l < 8; ++l )
{
    dotResult = actorPlaneNormal.dotProduct( worldSpaceCorners[l] );
    vertexMask =
        Mathlib::Or( vertexMask, Mathlib::CompareGreater( dotResult, actorPlaneNegD ) );
}
mask = Mathlib::And( mask, vertexMask );
}

I also got rid of all the ARRAY_REAL_ZERO since the following are equivalent:

Code: Select all

if( actorPlaneNormal.dotProduct( worldSpaceCorners[l] ) - actorPlaneNegD >= 0 )
  foo();

// vs

if( actorPlaneNormal.dotProduct( worldSpaceCorners[l] ) >= actorPlaneNegD )
  foo();
jwwalker
Goblin
Posts: 224
Joined: Thu Aug 12, 2021 10:06 pm
Location: San Diego, CA, USA
x 17
Contact:

Re: apparent error in frustum/frustum intersection test

Post by jwwalker »

dark_sylinc wrote: Tue May 23, 2023 10:20 pm

I took a look and... you're right? :shock: :shock: how did this even work?

Well, in the common case where a mirror is totally in view, each of the planes of the mirror's actor will have some frustum corners on one side and some frustum corners on the other side, so whichever way you point the normals, you won't conclude that the actor is disjoint from the viewing frustum. But I was looking at cases where just a corner of a mirror is visible.

And yes, your new code seems to be working correctly, thanks!

User avatar
dark_sylinc
OGRE Team Member
OGRE Team Member
Posts: 5292
Joined: Sat Jul 21, 2007 4:55 pm
Location: Buenos Aires, Argentina
x 1278
Contact:

Re: apparent error in frustum/frustum intersection test

Post by dark_sylinc »

Awesome!

I also added a routine so the UI shows how many actors are being culled in the sample.

I've backported the fix all way back to Ogre 2.2 (2.1 is EOL).

Post Reply