koobas.hobune.stream
Calculate collision between 2 rotated boxes without using BoxCollider (MATH)
I am developing a 3D grid system for my game so I'll have to calculate box collisions dozens of times per frame. I need to find a way to calculate the collision between 2 boxes given the position, size, and rotation. Adjacent boxes shouldn't detect collision. NOTE: I don't know any advanced math
It would be preferred if you fill in the gaps of the following function:
bool Intersects(Vector3 positionA, Vector3 sizeA, Quaternion rotationA, Vector3 positionB, Vector3 sizeB, Quaternion rotationB)
{
//content...
//returns true if both boxes collide
}
Intersects(new Vector3(0f, 0f, 0f), Vector3.one, Quaternion.Euler(Vector3.zero), new Vector3(1f, 0f, 0f), Vector3.one, Quaternion.Euler(Vector3.zero));
//adjacent boxes should return FALSE
Well, there are several ways how to do a box - box intersection test. Most physics systems would first apply an AABB check to determine if the boxes could even possibly collide and only do the actual collision test when necessary. However if you really only have two boxes you want to check, that probably doesn't matter.
One way would be to use the seperating axis theorem. This involves to project all corners of both boxes onto the normals of each shape and check for an overlap there by checking the min / max value along those axis. While in 2d using the 4 axis (two for each box) is enough, in 3d it is not sufficient to check the 6 (3 for each box) axis. In addition to those we also have to check all the crossproduct combinations between the 3 axes of both boxes. So we have to check 6+ 3*3 == 15 axes in the worst case. The great thing about this approach is once you found a seperating axis, you an immediately terminate and return false. Only when all 15 checks show an overlap, the boxes really overlap. I quickly hacked this together
private struct Box
{
public Vector3 pos, n1, n2, n3;
public float min, max;
private void UpdateMinMax(Vector3 aPos, ref Vector3 aNormal)
{
float p = Vector3.Dot(aPos, aNormal);
if (p > max) max = p;
if (p < min) min = p;
}
public void GetMinMax(ref Vector3 aAxis)
{
min = float.PositiveInfinity;
max = float.NegativeInfinity;
UpdateMinMax(pos + n1 + n2 + n3, ref aAxis);
UpdateMinMax(pos + n1 + n2 - n3, ref aAxis);
UpdateMinMax(pos + n1 - n2 + n3, ref aAxis);
UpdateMinMax(pos + n1 - n2 - n3, ref aAxis);
UpdateMinMax(pos - n1 + n2 + n3, ref aAxis);
UpdateMinMax(pos - n1 + n2 - n3, ref aAxis);
UpdateMinMax(pos - n1 - n2 + n3, ref aAxis);
UpdateMinMax(pos - n1 - n2 - n3, ref aAxis);
}
}
private struct TwoBoxes
{
public Box A, B;
// returns true if there is no overlap, false if they do overlap
public bool SAT(Vector3 aAxis)
{
A.GetMinMax(ref aAxis);
B.GetMinMax(ref aAxis);
return A.min > B.max || B.min > A.max;
}
}
public static bool Intersects(Vector3 positionA, Vector3 sizeA, Quaternion rotationA, Vector3 positionB, Vector3 sizeB, Quaternion rotationB)
{
TwoBoxes data = new TwoBoxes();
data.A.pos = positionA;
data.A.n1 = rotationA * Vector3.right * sizeA.x;
data.A.n2 = rotationA * Vector3.up * sizeA.y;
data.A.n3 = rotationA * Vector3.forward * sizeA.z;
data.B.pos = positionB;
data.B.n1 = rotationB * Vector3.right * sizeB.x;
data.B.n2 = rotationB * Vector3.up * sizeB.y;
data.B.n3 = rotationB * Vector3.forward * sizeB.z;
if (data.SAT(data.A.n1)) return false;
if (data.SAT(data.A.n2)) return false;
if (data.SAT(data.A.n3)) return false;
if (data.SAT(data.B.n1)) return false;
if (data.SAT(data.B.n2)) return false;
if (data.SAT(data.B.n3)) return false;
if (data.SAT(Vector3.Cross(data.A.n1, data.B.n1))) return false;
if (data.SAT(Vector3.Cross(data.A.n1, data.B.n2))) return false;
if (data.SAT(Vector3.Cross(data.A.n1, data.B.n3))) return false;
if (data.SAT(Vector3.Cross(data.A.n2, data.B.n1))) return false;
if (data.SAT(Vector3.Cross(data.A.n2, data.B.n2))) return false;
if (data.SAT(Vector3.Cross(data.A.n2, data.B.n3))) return false;
if (data.SAT(Vector3.Cross(data.A.n3, data.B.n1))) return false;
if (data.SAT(Vector3.Cross(data.A.n3, data.B.n2))) return false;
if (data.SAT(Vector3.Cross(data.A.n3, data.B.n3))) return false;
return true;
}
I don't have time to test this right now, but I did just check it quickly in .NET fiddle and the first tests seems to work. This solution should not allocate any memory. First I thought to actually passing all the data to the nested functions. However that would be rather slow since all arguments have to be pushed onto the stack. Then I thought I could simply pack the data into a struct and pass that by ref to avoid the massive data copy. Then I realised I could simply place the methods directly into the structs ^^. This cuts down the argument count and should be a bit faster (at least in theory) and is a bit cleaner / easier to read.
This solution definitely works although as a note for future viewers, I first perceived the sizeA and sizeB parameters to function as the total size of the boxes but later found out they functioned as box extents. Halving those two parameters at the beginning of the function fixed the problem for me. Boxes that are directly adjacent to each other will also register collision to be true although I've decided to just reduce the box sizes by 0.01f to solve this issue.
There are many built in methods for detecting collisions:
Physics2D.OverlapBox https://docs.unity3d.com/ScriptReference/Physics2D.OverlapBox.html
Vector2.Distance https://docs.unity3d.com/ScriptReference/Vector2.Distance.html
Raycasts https://docs.unity3d.com/ScriptReference/Physics.Raycast.html
Collider2D.IsTouching https://docs.unity3d.com/ScriptReference/Collider2D.IsTouching.html
I did consider these solutions, although I thought it was quite overkill to have to instantiate a GameObject with a BoxCollider to check for physics raycasts only for the use in one function. I am developing a 3D grid system for my game so I'll have to calculate box collisions dozens of times per frame.
