preface
As mentioned in my last blog post, the intersection of the ray with all the triangles in the model in the scene greatly affects efficiency and takes a lot of time, so an accelerated intersection will be carried out in the form of a bounding box. In this paper, the collision algorithm of OBB collision model is introduced
Collision model of OBB
Have you ever wondered why you need the OBB model? Suppose two characters collide in a scene, how do you tell if they collide? It’s probably because their colliders collide. So how do collisions come together (we’re only talking about the bounding box model of 2D rules here)?
Oriented Bounding Box OBB”(“Oriented Bounding Box) is a popular Bounding Box at present. The biggest characteristic of OBB is its direction arbitrariness, which makes it possible to surround objects as closely as possible according to the shape characteristics of the objects surrounded. The BoxCollider in Unity is actually an OBB model, which is not axisymmetric, but directional
OBB model
Collision algorithm analysis
To determine the collision of two OBB models, that is, the intersection of two rectangles, we can divide it into several steps. First of all, we can transform the problem: when two rectangles do not intersect, the separation of two rectangles can be regarded as multiple lines that can separate them.
When a rectangle is gradually moved so that at some point, there is only one intersection of the two rectangles, and the intersection is on one side of the rectangle, it is critical if and only ifOnly a straight line separates the two of themIn which case this line must be parallel to some side.
By observing the relationship between AB Proj and boxA, xVt Proj and yVt Proj of boxB, it can be concluded that:
AB proj > sum(Vt proj), then the rectangle is separated
AB proj = sum(Vt proj), then the rectangle is tangent
AB proj < sum(Vt proj), then the rectangles intersect
Check out some big guy’s code on the Internet
Reference post: www.cnblogs.com/hont/p/9501… Take the two sides of the two rectangles separately, and perform a total of four symmetries as the axis of symmetry
axis1 = (P1 - P0).normalized;
axis2 = (P3 - P0).normalized;
axis3 = (other.P1 - other.P0).normalized;
axis4 = (other.P3 - other.P0).normalized;
mDebugInternalAxisIndex = 0;
bool isNotIntersect = false;
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis1);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis2);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis3);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis4);
Copy the codeThis is taking the signed length to compare whether the projected line segments intersect
float x_p0 = xProject_P0.magnitude * Mathf.Sign(Vector3.Dot(xProject_P0, axis));
float x_p1 = xProject_P1.magnitude * Mathf.Sign(Vector3.Dot(xProject_P1, axis));
float x_p2 = xProject_P2.magnitude * Mathf.Sign(Vector3.Dot(xProject_P2, axis));
float x_p3 = xProject_P3.magnitude * Mathf.Sign(Vector3.Dot(xProject_P3, axis));
Copy the codeIntersection judgment:
if (yMin >= xMin && yMin <= xMax) return false;
if (yMax >= xMin && yMax <= xMax) return false;
Copy the code
Simple example diagram
using UnityEngine;
// OBB.cs
public class OBB : MonoBehaviour
{
public bool enableDebug;
public int debug_axisIndex;
int mDebugInternalAxisIndex;
public Vector2 size;
public Color gizmosColor = Color.white;
Vector2 P0 { get { return transform.localToWorldMatrix.MultiplyPoint3x4(-size * 0.5 f); } }
Vector2 P1 { get { return transform.localToWorldMatrix.MultiplyPoint3x4(new Vector3(size.x * 0.5 f, -size.y * 0.5 f.0)); } }
Vector2 P2 { get { return transform.localToWorldMatrix.MultiplyPoint3x4(size * 0.5 f); } }
Vector2 P3 { get { return transform.localToWorldMatrix.MultiplyPoint3x4(new Vector3(-size.x * 0.5 f, size.y * 0.5 f.0)); } }
Vector2 axis1, axis2, axis3, axis4;
// Add the following variables from the reference post to cache vector to reduce GC
Vector3 xProject_P0;
Vector3 xProject_P1;
Vector3 xProject_P2;
Vector3 xProject_P3;
Vector3 yProject_P0;
Vector3 yProject_P1;
Vector3 yProject_P2;
Vector3 yProject_P3;
public bool Intersects(OBB other)
{
axis1 = (P1 - P0).normalized;
axis2 = (P3 - P0).normalized;
axis3 = (other.P1 - other.P0).normalized;
axis4 = (other.P3 - other.P0).normalized;
mDebugInternalAxisIndex = 0;
bool isNotIntersect = false;
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis1);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis2);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis3);
isNotIntersect |= ProjectionIsNotIntersect(this, other, axis4);
return isNotIntersect ? false : true;
}
bool ProjectionIsNotIntersect(OBB x, OBB y, Vector2 axis)
{
xProject_P0 = Vector3.Project(x.P0, axis);
xProject_P1 = Vector3.Project(x.P1, axis);
xProject_P2 = Vector3.Project(x.P2, axis);
xProject_P3 = Vector3.Project(x.P3, axis);
float x_p0 = xProject_P0.magnitude * Mathf.Sign(Vector3.Dot(xProject_P0, axis));
float x_p1 = xProject_P1.magnitude * Mathf.Sign(Vector3.Dot(xProject_P1, axis));
float x_p2 = xProject_P2.magnitude * Mathf.Sign(Vector3.Dot(xProject_P2, axis));
float x_p3 = xProject_P3.magnitude * Mathf.Sign(Vector3.Dot(xProject_P3, axis));
yProject_P0 = Vector3.Project(y.P0, axis);
yProject_P1 = Vector3.Project(y.P1, axis);
yProject_P2 = Vector3.Project(y.P2, axis);
yProject_P3 = Vector3.Project(y.P3, axis);
float y_p0 = yProject_P0.magnitude * Mathf.Sign(Vector3.Dot(yProject_P0, axis));
float y_p1 = yProject_P1.magnitude * Mathf.Sign(Vector3.Dot(yProject_P1, axis));
float y_p2 = yProject_P2.magnitude * Mathf.Sign(Vector3.Dot(yProject_P2, axis));
float y_p3 = yProject_P3.magnitude * Mathf.Sign(Vector3.Dot(yProject_P3, axis));
float xMin = Mathf.Min(x_p0, x_p1, x_p2, x_p3);
float xMax = Mathf.Max(x_p0, x_p1, x_p2, x_p3);
float yMin = Mathf.Min(y_p0, y_p1, y_p2, y_p3);
float yMax = Mathf.Max(y_p0, y_p1, y_p2, y_p3);
if (enableDebug)
{
if (debug_axisIndex == mDebugInternalAxisIndex)
{
Debug.DrawRay(Vector3.Project(x.P0, axis), Vector3.one * 0.1 f);
Debug.DrawRay(Vector3.Project(x.P2, axis), Vector3.one * 0.1 f);
Debug.DrawRay(Vector3.Project(y.P0, axis), Vector3.one * 0.1 f, Color.white * 0.9 f);
Debug.DrawRay(Vector3.Project(y.P2, axis), Vector3.one * 0.1 f, Color.white * 0.9 f);
Debug.DrawRay(Vector3.zero, Vector3.one * 0.1 f, Color.black);
Debug.DrawRay(Vector3.zero, axis, Color.yellow);
Debug.DrawRay(xMin * Vector3.right, Vector3.one * 0.1 f, Color.blue);
Debug.DrawRay(xMax * Vector3.right, Vector3.one * 0.1 f, Color.cyan);
Debug.DrawRay(yMin * Vector3.right, Vector3.one * 0.1 f, Color.red * 0.5 f);
Debug.DrawRay(yMax * Vector3.right, Vector3.one * 0.1 f, Color.red * 0.5 f);
Debug.Log("(yMin >= xMin && yMin <= xMax): " + (yMin >= xMin && yMin <= xMax) + " frame count: " + Time.frameCount);
Debug.Log("(yMax >= xMin && yMax <= xMax): " + (yMax >= xMin && yMax <= xMax) + " frame count: " + Time.frameCount);
Debug.Log("(xMin >= yMin && xMin <= yMax): " + (xMin >= yMin && xMin <= yMax) + " frame count: " + Time.frameCount);
Debug.Log("(xMax >= yMin && xMax <= yMax): " + (xMax >= yMin && xMax <= yMax) + " frame count: " + Time.frameCount);
}
mDebugInternalAxisIndex++;
}
if (yMin >= xMin && yMin <= xMax) return false;
if (yMax >= xMin && yMax <= xMax) return false;
// We need to make a decision here
// if (xMin >= yMin && xMin <= yMax) return false;
// if (xMax >= yMin && xMax <= yMax) return false;
return true;
}
void OnDrawGizmos()
{
Gizmos.matrix = transform.localToWorldMatrix;
Gizmos.color = gizmosColor;
Gizmos.DrawWireCube(Vector3.zero, new Vector3(size.x, size.y, 1f)); }}Copy the codeusing System.Collections;
using System.Collections.Generic;
using UnityEngine;
// OBBTest.cs
public class OBBTest : MonoBehaviour
{
public OBB a;
public OBB b;
void Update()
{
var isIntersects = a.Intersects(b);
if (isIntersects)
{
a.gizmosColor = Color.red;
b.gizmosColor = Color.red;
}
else{ a.gizmosColor = Color.white; b.gizmosColor = Color.white; }}}Copy the codeThe effect
