Managed version of GeometryUtility.TestPlanesAABB

I'm trying to implement GeometryUtility.TestPlanesAABB in managed code since I need it to be callable on a thread and having the intersection information would be useful for optimization.

I found several threads on the internet with implementations - they all do basically the same thing. I have implemented the code but it doesn't work. Does anyone know why? Perhaps a handedness issue? Here is the code in C#

Code (CSharp):

1.     /// <summary>
2.     /// https://www.gamedev.net/topic/512123-fast--and-correct-frustum---aabb-intersection/
3.     /// https://www.gamedev.net/topic/672043-perfect-aabb-frustum-intersection-test/
4.     /// </summary>
5.     /// <param name="planes"></param>
6.     /// <param name="bounds"></param>
7.     /// <returns></returns>
8.     public static bool TestPlanesAABBInternal (Plane [] planes, ref Bounds bounds)
9.     {
10.         var testResult = TestPlanesResults.Inside;
11.  
12.         Vector3 vmin, vmax;
13.  
14.         for(int i = 0; i < 6; ++i)
15.         {
16.             // X axis
17.             if(planes[i].normal.x > 0)
18.             {
19.                 vmin.x = bounds.min.x;
20.                 vmax.x = bounds.max.x;
21.             }
22.             else
23.             {
24.                 vmin.x = bounds.max.x;
25.                 vmax.x = bounds.min.x;
26.             }
27.  
28.             // Y axis
29.             if (planes[i].normal.y > 0)
30.             {
31.                 vmin.y = bounds.min.y;
32.                 vmax.y = bounds.max.y;
33.             }
34.             else
35.             {
36.                 vmin.y = bounds.max.y;
37.                 vmax.y = bounds.min.y;
38.             }
39.  
40.             // Z axis
41.             if (planes[i].normal.z > 0)
42.             {
43.                 vmin.z = bounds.min.z;
44.                 vmax.z = bounds.max.z;
45.             }
46.             else
47.             {                
48.                 vmin.z = bounds.max.z;
49.                 vmax.z = bounds.min.z;
50.             }
51.  
52.             if (Vector3.Dot (planes[i].normal, vmin) + planes[i].distance > 0)
53.                 return false;
54.             if (Vector3.Dot (planes[i].normal, vmax) + planes[i].distance >= 0)
55.                 testResult = TestPlanesResults.Intersect;
56.         }
57.  
58.         return testResult == TestPlanesResults.Inside || testResult == TestPlanesResults.Intersect;
59.     }
60.  

 

I think you are way off here. This method is intended to be used with planes that represent a viewing frustum. That means that they are not shaped as a cube. Something as "planes.normal.z > 0" seems to assume being axis aligned, which it doesn't need to be. The bounding box will be, but the planes can be rotated arbitrarily.

A bounding box is outside if all it's 8 corners are on the outside of any of the planes. A corner is outside of the plane if the (signed) distance to the plane is higher than zero. This distance can be calculated by taking the dot product between the corner position and the plane normal and then subtracting the plane distance (to the origin.)

In pseudo code:

Code (csharp):

1.  
2. foreach plane { // Don't hard code it to 6
3.     bool outside = true;
4.     foreach corner {
5.         distance = Vector3.Dot(plane.normal, corner) - plane.distance; // Signed distance to plane
6.         if (distance <= 0.0) outside = false;
7.         if (!outside) break;
8.     }
9.     if (outside) return false;
10. }
11. return true;
12.  

And then the corners of the (axis aligned) bounding box are:
- minX, minY, minZ
- minX, minY, maxZ
- minX, maxY, minZ
- minX, maxY, maxZ
- maxX, minY, minZ
- maxX, minY, maxZ
- maxX, maxY, minZ
- maxX, maxY, maxZ

 

Thanks. I might just implement this for now. The algorithm I (copied) looks like it originally came from here:

http://www.lighthouse3d.com/tutorials/view-frustum-culling/geometric-approach-testing-boxes-ii/

and it certainly appears to be intended for frustrum culling AABBs.

 

Can you share your code, which not only defines the intersection but also its type? I could not implement the pseudocode presented in the working version (((

 

Oops forgot about this request. Here you go. Keep in mind that even with this version, if you are going to run this a bunch of times against the same frustum, it is much faster to precalculate the normal/distance for the planes and send those in rather than query them for each cull. In my code I have that broken out as a few extra methods. Also, again, if running this over a large number of bounds, you would also want to precalc the boundsmin/max since grabbing those from a bounding box is quite expensive over several thousand.

If you don't want the intersection test, which does have a performance cost, you can send in false for intersection test. This will just give you an inside/outside result without a possible intersection result.

Also of course this method is threadable unlike Unity's methods.

Code (CSharp):

1.        
2.  
3.         public enum TestPlanesResults
4.         {
5.             /// <summary>
6.             /// The AABB is completely in the frustrum.
7.             /// </summary>
8.             Inside = 0,
9.             /// <summary>
10.             /// The AABB is partially in the frustrum.
11.             /// </summary>
12.             Intersect,
13.             /// <summary>
14.             /// The AABB is completely outside the frustrum.
15.             /// </summary>
16.             Outside
17.         }
18.  
19.         /// <summary>
20.         /// This is crappy performant, but easiest version of TestPlanesAABBFast to use.
21.         /// </summary>
22.         /// <param name="planes"></param>
23.         /// <param name="bounds"></param>
24.         /// <returns></returns>
25.         public static TestPlanesResults TestPlanesAABBInternalFast (Plane [] planes, ref Bounds bounds)
26.         {
27.             var min = bounds.min;
28.             var max = bounds.max;
29.  
30.             return TestPlanesAABBInternalFast (planes, ref min, ref max);
31.         }
32.  
33.         /// <summary>
34.         /// This is a faster AABB cull than brute force that also gives additional info on intersections.
35.         /// Calling Bounds.Min/Max is actually quite expensive so as an optimization you can precalculate these.
36.         /// http://www.lighthouse3d.com/tutorials/view-frustum-culling/geometric-approach-testing-boxes-ii/
37.         /// </summary>
38.         /// <param name="planes"></param>
39.         /// <param name="boundsMin"></param>
40.         /// <param name="boundsMax"></param>
41.         /// <returns></returns>
42.         public static TestPlanesResults TestPlanesAABBInternalFast (Plane [] planes, ref Vector3 boundsMin, ref Vector3 boundsMax, bool testIntersection = false)
43.         {
44.             Vector3 vmin, vmax;
45.             var testResult = TestPlanesResults.Inside;
46.  
47.             for(int planeIndex = 0; planeIndex < planes.Length; planeIndex++)
48.             {
49.                 var normal          = planes [planeIndex].normal;
50.                 var planeDistance   = planes [planeIndex].distance;
51.  
52.                 // X axis
53.                 if(normal.x < 0)
54.                 {
55.                     vmin.x = boundsMin.x;
56.                     vmax.x = boundsMax.x;
57.                 }
58.                 else
59.                 {
60.                     vmin.x = boundsMax.x;
61.                     vmax.x = boundsMin.x;
62.                 }
63.  
64.                 // Y axis
65.                 if (normal.y < 0)
66.                 {
67.                     vmin.y = boundsMin.y;
68.                     vmax.y = boundsMax.y;
69.                 }
70.                 else
71.                 {
72.                     vmin.y = boundsMax.y;
73.                     vmax.y = boundsMin.y;
74.                 }
75.  
76.                 // Z axis
77.                 if (normal.z < 0)
78.                 {
79.                     vmin.z = boundsMin.z;
80.                     vmax.z = boundsMax.z;
81.                 }
82.                 else
83.                 {              
84.                     vmin.z = boundsMax.z;
85.                     vmax.z = boundsMin.z;
86.                 }
87.  
88.                 var dot1 = normal.x * vmin.x + normal.y * vmin.y + normal.z * vmin.z;
89.                 if (dot1 + planeDistance < 0)
90.                     return TestPlanesResults.Outside;
91.  
92.                 if (testIntersection)
93.                 {
94.                     var dot2 = normal.x * vmax.x + normal.y * vmax.y + normal.z * vmax.z;
95.                     if (dot2 + planeDistance <= 0)
96.                         testResult = TestPlanesResults.Intersect;
97.                 }
98.             }
99.  
100.             return testResult;
101.         }
102.  

 

Sorry for the necro. In the code above, you check the dot product of what you're calling vmin to determine if whether bounds is outside or inside but in the lighthouse algorithm, it's actually the check for vmax. I think you've flipped the names for these variables. Am I correct?

 

Honestly it has been a loong time since I looked at this. I don't use this code anymore. But I am pretty sure when I implemented it I had to change something from the basis algorithm to make it work. I used this code pretty heavily at the time for culling large numbers of instances. I could see the culling at run-time in the scene view, and I never noticed an issue at run-time or edit time. I think it does work.

 

Oh it works. I'm just referring to the naming being flipped.

 

For the furure me and others, here is the fast version that works with the job system and burst compiler:

Code (CSharp):

1.  
2. using Unity.Mathematics;
3. using Unity.Collections;
4.  
5. public bool TestPlanesAABB(NativeArray<Plane> planes, Bounds bounds)
6.  
7. {
8.     for (int i = 0; i < planes.Length; i++)
9.     {
10.         Plane plane = planes[i];
11.         float3 normal_sign = math.sign(plane.normal);
12.         float3 test_point = (float3)(bounds.center) + (bounds.extents * normal_sign);
13.  
14.         float dot = math.dot(test_point, plane.normal);
15.         if (dot + plane.distance < 0)
16.             return false;
17.     }
18.  
19.     return true;
20. }

 

Not all heroes wear capes, thanks brother.

 

How does this implementation look like in Unity. I would like to implement it for looking for objects in the camera frustum.