[Wiki/HOWTO] Oriented Bounding Box in Unity ... finally ? eek !

Hi everyone !

I've been looking for an oriented bounding box to use from within a custom editor I'm developing in Unity but I couldn't find any, except for flaming debates about the laziness of Unity team to bring us one ... anyway, today I'm sharing this with you:

https://github.com/aybe/MathGeoLib.Exports

This is a C# wrapper around the outstanding MathGeoLib library, I haven't implemented everything because it's really huge, however, I brought the necessary stuff for a decent OBB from within Unity (see the picture above).

It's pretty fast at OBB'ing and easy to use,

The thing I absolutely wanted to add was the ability to serialize it since it's naturally not a cheap operation on huge meshes. Personally I didn't need more than getting its position, extent and axes to be able to draw bounds in my editor, however, I felt it needed a few more methods for querying against it (e.g. point inside, distance, etc) so I've implemented quite a few of them but not all since there's really a lot of them which would imply porting even more types, i.e. snowball effect .

So there you are, OBB from within Unity, grab the zip release at the first link I've posted and see the instructions. Basically you drag and drop native plugins and drop the C# files into your project, things should go smoothly then.

Many thanks to the original author of the library .

Hope you'll like it, share your comments/feelings/reviews/whatever !

PS I didn't add XML comments but the methods and parameters names are evocative enough for a natural usage, in doubt, see the original author documentation in the header (4th link I've posted); my wrapper does nothing funny in between, it just passes data back and forth between managed and native worlds.

PS The only change I made to the native library was to enable static linking, DLL is a bit bigger but you won't need any extra Visual C++ redistributable to drag along with your project (a good thing).

Cheers

 

I haven't had a need for an OBB yet, but I'm curious about the process of obtaining one.

I'm also curious why you reached for that MathGeoLib package. Was it for better native performance over massive meshes?

Not having made an OBB routine myself, I would speculate that the way it is done is to:

1. iterate all tris to get all used verts in local space:
- generate a "grow as needed" bounds around that (six axis-facing plane equations, in x, y, z)

2. Apply GameObject's rotation/translation/scaling to the six planes to get the final OBB

Am I missing something essential?

In any case, I am glad you solved your problem, and props to you for sharing it here. Never know who it might help!

 

This is cool looking project.
I was working on my own OBB / AAB other day, but with ECS in mind.
However, there is bounds in GameObject, which automatically provides Bounding box of mesh, when applying box collider for example.

So my question is, out of curiosity, what are your motives, to implement own OBB?

Also, wouldn't be worth, trying move into ECS, or at least jobify OOB calculations?

 

I used this library because it's the one that worked and was fast. GeometricToolsEngine was very slow, couldn't built ApproxMVBB with its chain of dependencies. What's not trivial is finding the orientation, then you might get something providing you have the skills but will it run fast ?

A cheap and easy way to OBB via a GO's transform seems weird; its orientation don't necessarily mean the real orientation, so you might be coincidentally close but not always. For ECS and stuff, it looks nice but as said before, it's re-inventing the wheel.

I needed this because I was bored to each time use Alt+click when framing an object in scene to rotate and see it from the front, now I can save many mouse clicks and time in the end .

 

Fair enough, since you found way to make it work for you

Well not really reinventing. Is just converting, to bust performance. If you really need it any faster of course. Otherwise, probably is not worth it at this point.

 

You know what, I was actually tempted to try do it first like, 'sounds simple, right ?' or 'challenge accepted' . But just look at the code, it is FMA, AVX and SSE enabled, the author is definitely in charge !

And guess what, even though I've got GeometricToolsEngine to build, it under-performed by magnitudes in Release build for the same set of points even though I've set its 'maxThreads' parameter to my value of 'std::thread::hardware_concurrency'. You'd see a small CPU burst but then nothing; I've paused debugging and it was stuck in filling vectors ... OTOH, in MathGeoLib this sorting phase happens instantly, even in a Debug build.

I'd rather have a finely-tuned, single-threaded process, than a bells and whistles that performs abysmally .

PS I'm not saying that GeometricToolsEngine is bad, it's an excellent showcase library but to me it's clear that MathGeoLib outperforms it in terms of speed even though it's single-threaded.

 

Thats fine. No stress about it
What works best. In the end, no one want spend forever, on writing scripts

 

My motto would be 'always stay simple when it comes to coding' since it naturally becomes complex, but more often than not I forget to apply this principle to myself and get stuck into gory details .

This time I didn't fall on the trap of 'you can do it bro, it's only a 3d box (but remember, one that's rotated !)' You must delegate things out somehow if you want to advance on your personal coding projects, otherwise you'll be still here after the Big Crunch .

 

Thx for offer, but I will stay with what we got so far in Unity
I got plenty for now, to type anyway, so I wont get bored.

 

That's really neat!

Oriented bounding boxes are great for fast, approximate checking for overlap. Once it's calculated, it's almost as fast as an AABB (just need to transform the point you're checking to the oriented BB's space), and it gives a much better approximation

 

That's great! Thank you.

I was just looking at implementing this https://pdfs.semanticscholar.org/a76f/7da5f8bae7b1fb4e85a65bd3812920c6d142.pdf
and was not looking forward to it.

 

nice stuff!
How do you use it in a project in Unity?

 

Hey! Nice stuff, I've been looking at getting something like this for a while, but never got around to actually writing it.

I'm a bit confused though: Why are you defining the rotation of the bounding box as 3 separate Vector3? Wouldn't it be simpler to define the rotation euler angles?

What do the Axis1, 2 and 3 represent?

Thanks!

 

Hey! Looks nice, but take a look at my code below, maybe I am doing something wrong, because I can't get any time gain when using this - compared to Unity Bounds:

Code (CSharp):

1. for (int i = 0; i < meshes.Length; i++)
2. {
3.     Mesh ms = meshes[i].sharedMesh;
4.     int vc = ms.vertexCount;
5.     Debug.Log("ms.vertexCount " + ms.vertexCount.ToString());
6.     for (int j = 0; j < vc; j++)
7.     {
8.         if (i == 0 && j == 0)
9.         {
10.             if (_useMathGeo)
11.             {
12.                 obb = new OrientedBoundingBox(meshes[i].transform.TransformPoint(ms.vertices[j]), Vector3.zero, go.transform.right, go.transform.up, go.transform.forward);
13.             }
14.             else
15.             {
16.                 bounds = new Bounds(meshes[i].transform.TransformPoint(ms.vertices[j]), Vector3.zero);
17.             }
18.         }
19.         else
20.         {
21.             if (_useMathGeo)
22.             {
23.                 obb.Enclose(meshes[i].transform.TransformPoint(ms.vertices[j]));
24.             }
25.             else
26.             {
27.                 bounds.Encapsulate(meshes[i].transform.TransformPoint(ms.vertices[j]));
28.             }
29.         }
30.         if (j > 150) break;//for testing, otherwise it would take ages
31.     }
32. }
33. if (_useMathGeo) bounds = new Bounds(obb.Center, 2 * obb.Extent);

It takes exactly the same amount of time no matter if using OrientedBoundingBox or Unity's Bounds.
I was actually trying to get it to work with gameobjects with around 40 meshes, from 0.2 to 24k vertices each.

 

The goal of an oriented bounding box is not to be faster than an AABB, it's to give a more accurate representation of the original geometry.

If it's actually as fast, then that's great, because it's fundamentally having to do more work.

 

However it's also fast.
But after replacing transform and transformPoint from the above code - with matrix4x4 and MultiplyPoint3x4 - the calculation time has dropped in my case by orders of magnitude, from hours to seconds.
Moreover I have moved it from the main thread so the bound box calculation is not a bottleneck in my project any more. Thanks @aybeone for sharing this.

 

Can you tell me how to plug in this OBB in a unity project? Not very sure what I should do.

 

You can find everything in the first post in this thread and in the links inside it.

 

@tomekkie2 mind sharing how you used the matrix? Modified the sample code in this thread like so and it instead increased the time!

Code (CSharp):

1. Matrix4x4 m;
2.  
3. for (int i = 0; i < meshes.Length; i++)
4. {
5.     Mesh ms = meshes[i].sharedMesh;
6.     int vc = ms.vertexCount;
7.     m = Matrix4x4.TRS(meshes[i].transform.position,meshes[i].transform.rotation,meshes[i].transform.localScale);
8.     Debug.Log("ms.vertexCount " + ms.vertexCount.ToString());
9.     for (int j = 0; j < vc; j++)
10.     {
11.         if (i == 0 && j == 0)
12.         {
13.             if (_useMathGeo)
14.             {
15.                 obb = new OrientedBoundingBox(m.MultiplyPoint3x4(ms.vertices[j]), Vector3.zero, go.transform.right, go.transform.up, go.transform.forward);
16.             }
17.             else
18.             {
19.                 bounds = new Bounds(meshes[i].transform.TransformPoint(ms.vertices[j]), Vector3.zero);
20.             }
21.         }
22.         else
23.         {
24.             if (_useMathGeo)
25.             {
26.                 obb.Enclose(m.MultiplyPoint3x4(ms.vertices[j]));
27.             }
28.             else
29.             {
30.                 bounds.Encapsulate(meshes[i].transform.TransformPoint(ms.vertices[j]));
31.             }
32.         }
33.         if (j > 150) break;//for testing, otherwise it would take ages
34.     }
35. }
36. if (_useMathGeo) bounds = new Bounds(obb.Center, 2 * obb.Extent);

 

How can I integrate the oriented bounding box? I am trying to get the vertices from a Plane that intersect with the bounds of a rotated cube. I am trying to get the points from a Plane that intersect with the boundaries of a cube. The problem is, the calculation is based on the AABB and is therefore useless for rotated cubes. For this calculation I need the oriented bounding box. Can someone help me?



On the first picture you see a cube with an axis aligned bounding box (AABB)

And this is my target:


Here is my code that I used to calculate it:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4.  
5. public class Intersection : MonoBehaviour
6. {
7.     public GameObject m_MyObject, m_NewObject;
8.     Collider m_Collider, m_Collider2;
9.     private List<Vector3> inboundsVertices = new List<Vector3>();
10.     private bool drawVertGizmos = false;
11.  
12.     void Start()
13.     {
14.         //Check that the first GameObject exists in the Inspector and fetch the Collider
15.         if (m_MyObject != null)
16.             m_Collider = m_MyObject.GetComponent<Collider>();
17.  
18.         //Check that the second GameObject exists in the Inspector and fetch the Collider
19.         if (m_NewObject != null)
20.             m_Collider2 = m_NewObject.GetComponent<Collider>();
21.     }
22.  
23.     void Update()
24.     {
25.         //If the first GameObject's Bounds enters the second GameObject's Bounds, output the message
26.         if (m_Collider.bounds.Intersects(m_Collider2.bounds))
27.         {
28.             CheckVertices(m_MyObject, m_Collider2.bounds);
29.             drawVertGizmos = true;
30.         }
31.     }
32.  
33.     void OnDrawGizmos()
34.     {
35.         if (drawVertGizmos)
36.         {
37.             DrawVertexGizmos();
38.             DrawBoundingBox();
39.         }
40.     }
41.  
42.     void DrawBoundingBox()
43.     {
44.         Gizmos.color = Color.yellow;
45.         Gizmos.DrawWireCube(m_NewObject.transform.position, m_Collider2.bounds.size);
46.     }
47.  
48.     void DrawVertexGizmos()
49.     {
50.         foreach (Vector3 vertex in inboundsVertices)
51.         {
52.             Gizmos.DrawSphere(vertex, 0.04f);
53.         }
54.     }
55.  
56.     void CheckVertices(GameObject obj, Bounds bounds)
57.     {
58.         inboundsVertices.Clear();
59.         if (obj == null)
60.             return;
61.         MeshFilter mf = obj.GetComponent<MeshFilter>();
62.         if (mf == null)
63.             return;
64.         Vector3[] verticesToCheck = obj.GetComponent<MeshFilter>().mesh.vertices;
65.         foreach (Vector3 vertex in verticesToCheck)
66.         {
67.             Vector3 pos = obj.transform.TransformPoint(vertex);
68.             if (bounds.Contains(pos))
69.             {
70.                 inboundsVertices.Add(pos);
71.             }
72.         }
73.     }
74. }

 

Found a solution if anyone is interested:

Code (CSharp):

1. using UnityEngine;
2. using System.Collections;
3. using System.Collections.Generic;
4. using MathGeoLib;
5.  
6. public class Intersection : MonoBehaviour
7. {
8.     public GameObject m_MyObject, m_NewObject;
9.     Collider m_Collider, m_Collider2;
10.     private List<Vector3> inboundsVertices = new List<Vector3>();
11.     private bool drawVertGizmos = false;
12.  
13.     [SerializeField]
14.     private OrientedBoundingBox obb;
15.  
16.     void Start()
17.     {
18.         //Check that the first GameObject exists in the Inspector and fetch the Collider
19.         if (m_MyObject != null)
20.             m_Collider = m_MyObject.GetComponent<Collider>();
21.  
22.         //Check that the second GameObject exists in the Inspector and fetch the Collider
23.         if (m_NewObject != null)
24.             m_Collider2 = m_NewObject.GetComponent<Collider>();
25.     }
26.  
27.     void Update()
28.     {
29.         float xAngle = m_NewObject.transform.eulerAngles.x;
30.         float yAngle = m_NewObject.transform.eulerAngles.y;
31.         float zAngle = m_NewObject.transform.eulerAngles.z;
32.         Quaternion rotation = Quaternion.Euler(xAngle, yAngle, zAngle);
33.         Matrix4x4 m = Matrix4x4.Rotate(rotation);
34.  
35.         Vector3 xRotation = new Vector3(m.m00, m.m10, m.m20);
36.         Vector3 yRotation = new Vector3(m.m01, m.m11, m.m21);
37.         Vector3 zRotation = new Vector3(m.m02, m.m12, m.m22);
38.  
39.         obb = new OrientedBoundingBox(m_Collider2.bounds.center, m_NewObject.transform.localScale / 2, xRotation, yRotation, zRotation);
40.         //If the first GameObject's Bounds enters the second GameObject's Bounds, output the message
41.         if (m_Collider.bounds.Intersects(m_Collider2.bounds))
42.         {
43.             CheckVertices(m_MyObject, obb);
44.             drawVertGizmos = true;
45.         }
46.     }
47.  
48.     void OnDrawGizmos()
49.     {
50.         if (drawVertGizmos)
51.         {
52.             DrawVertexGizmos();
53.             //DrawBoundingBox();
54.         }
55.     }
56.  
57.     void DrawBoundingBox()
58.     {
59.         Gizmos.color = Color.yellow;
60.         Gizmos.DrawWireCube(m_NewObject.transform.position, m_Collider2.bounds.size);
61.     }
62.  
63.     void DrawVertexGizmos()
64.     {
65.         foreach (Vector3 vertex in inboundsVertices)
66.         {
67.             Gizmos.DrawSphere(vertex, 0.04f);
68.         }
69.     }
70.  
71.     void CheckVertices(GameObject obj, OrientedBoundingBox bounds)
72.     {
73.         inboundsVertices.Clear();
74.         if (obj == null)
75.             return;
76.         MeshFilter mf = obj.GetComponent<MeshFilter>();
77.         if (mf == null)
78.             return;
79.         Vector3[] verticesToCheck = obj.GetComponent<MeshFilter>().mesh.vertices;
80.         foreach (Vector3 vertex in verticesToCheck)
81.         {
82.             Vector3 pos = obj.transform.TransformPoint(vertex);
83.             if (bounds.Contains(pos))
84.             {
85.                 inboundsVertices.Add(pos);
86.             }
87.         }
88.     }
89. }

Here is the result:

 

Does not work on Mac M1 (2020.3.1f1) because of DllNotFoundException

The error message sounds:
DllNotFoundException: MathGeoLib.Exports MathGeoLib.OrientedBoundingBox.Enclose (UnityEngine.Vector3 point) (at Assets/virtualPlayground/Boxes/Dim-Boxes/MathGeoLib.Exports.v0.1/MathGeoLib/OrientedBoundingBox.cs:209)

Is there a fix?

My guess is some of these lines at the beginning of the OrientedBoundingBox.cs need an update:

Code (CSharp):

1. using System;
2. using System.Runtime.InteropServices;
3. using JetBrains.Annotations;
4.  
5. #if UNITY || UNITY_EDITOR
6. using Plane = UnityEngine.Plane;
7. using Vector3 = UnityEngine.Vector3;
8. #endif
9.  
10. #pragma warning disable IDE1006 // naming rules blah blah blah
11.  
12. // ReSharper disable once CheckNamespace
13. namespace MathGeoLib
14. {
15.     [PublicAPI]
16.     [Serializable]
17.     [StructLayout(LayoutKind.Sequential)]
18.     public sealed class OrientedBoundingBox
19.     {
20.         #region Native
21.  
22.         private static class NativeMethods
23.         {
24. #if UNITY || UNITY_EDITOR
25.             private const string DllName = "MathGeoLib.Exports";
26. #else
27.             private const string DllName = "MathGeoLib.Exports.dll";
28. #endif
29.  
30.             [DllImport(DllName)]
31. .............

 

It uses a native library, which the OP compiled for Windows. You need to compile that for Mac.

 

Thank you.
The problem is I am using it in AssetStore asset and I am using Windows myself.
This error has been reported by asset user, using this asset on Mac.
I guess I can't recompile that for mac while do it being on Windows?

Maybe someone is also using this library on Mac and could share the mac plugin with me?