# How can I test if my rotated rectangle intersects a corner?

I have a square, tile-based collision map. To check if one of my (square) entities is colliding, I get the vertices of the 4 corners, and test those 4 points against my collision map. If none of those points are intersecting, I know I'm good to move to the new position.

I'd like to allow entities to rotate. I can still calculate the 4 corners of the square, but once you factor in rotation, those 4 corners alone don't seem to be enough information to determine if the entity is trying to move to a valid state.

For example:

In the picture below, black is unwalkable terrain, and red is the player's hitbox. The left scenario is allowed because the 4 corners of the red square are not in the black terrain.

The right scenario would also be (incorrectly) allowed, because the player, cleverly turned at a 45* angle, has its corners in valid spaces, even if it is (quite literally) cutting the corner.

How can I detect scenarios similar to the situation on the right?

I finally got a decent collision detection implemented. I wound up using a 3d version of XenoCollide / Minkowski Portal Refinement, a la Gary Snethen in Game Programming Gems 7.

I've created a C# implementation of MPR below. It will return the direction of the minimum penetration vector. I know it's possible to return actual collision points, but I've not been able to implement that part, yet.

At any rate, here's the code for Minkowski Portal Refinement (MPR) / XenoCollide in 3d:

using System.Collections;
using System.Collections.Generic;

//make the associated dot / cross products easier to read
public static class Vector3Extensions
{
public static float Dot(this Vector3 op1, Vector3 op2)
{
return Vector3.Dot(op1, op2);
}

public static Vector3 Cross(this Vector3 op1, Vector3 op2)
{
return Vector3.Cross(op1, op2);
}
}

public static class MPRCollision {

//points used by the algorithm
static Vector3 v0;
static Vector3 v1;
static Vector3 v2;
static Vector3 v3;
static Vector3 v4;

//if the difference in iteration is less than this,
//we aren't going to (can't!) converge.
static float kCollideEpsilon = 1e-3f;

static Vector3 GetSupport(List<Vector3> shape, Vector3 direction)
{

Vector3 point = shape[0];

for(int i = 1; i < shape.Count; i++)
{
//is the current point more "direction" than our result point?
if ( (shape[i] - point).Dot(direction) > 0 )
{
//new result point
point = shape[i];
}
}
return point;

}

public static bool CheckCollide(List<Vector3> shape1, List<Vector3> shape2,
Vector3 center1, Vector3 center2, ref Vector3 penVector)
{
//holding variables
Vector3 n = Vector3.zero;
Vector3 swap = Vector3.zero;

// v0 = center of Minkowski sum
v0 = center2 - center1;

// Avoid case where centers overlap -- any direction is fine in this case
if (v0 == Vector3.zero) v0 = new Vector3(0, 0.00001f, 0);

// v1 = support in direction of origin
n = -v0;

//get the differnce of the minkowski sum
Vector3 v11 = GetSupport(shape1, -n);
Vector3 v12 = GetSupport(shape2, n);

v1 = v12 - v11;

//if the support point is not in the direction of the origin
if (v1.Dot(n) <= 0)
{
//return the direction of the origin, because we're not colliding
if (penVector != null) penVector = n;
return false;
}

// v2 - support perpendicular to v1,v0
n = v1.Cross(v0);
if (n == Vector3.zero)
{
//v1 and v0 are parallel, which means
//the origin is within the first portal?
n = v1 - v0;

if (penVector != null) penVector = n.normalized;
return true;
}

//no early outs yet, so get the new support point
Vector3 v21 = GetSupport(shape1, -n);
Vector3 v22 = GetSupport(shape2, n);
v2 = v22 - v21;

if (v2.Dot(n) <= 0)
{
//can't reach the origin in this direction, ergo, no collision
if (penVector != null) penVector = n;
return false;
}

// Determine whether origin is on + or - side of plane (v1,v0,v2)
//tests linesegments v0v1 and v0v2
n = (v1 - v0).Cross(v2 - v0);
float dist = n.Dot(v0);

// If the origin is on the - side of the plane, reverse the direction of the plane
if (dist > 0)
{
//swap the winding order of v1 and v2
swap = v1;
v1 = v2;
v2 = swap;

//swap the winding order of v11 and v12
swap = v12;
v12 = v11;
v11 = swap;

//swap the winding order of v11 and v12
swap = v22;
v22 = v21;
v21 = swap;

//and swap the plane normal
n = -n;
}

///
// Phase One: Identify a portal

while (true)
{
// Obtain the support point in a direction perpendicular to the existing plane
// Note: This point is guaranteed to lie off the plane
Vector3 v31 = GetSupport(shape1, -n);
Vector3 v32 = GetSupport(shape2, n);
v3 = v32 - v31;

if (v3.Dot(n) <= 0)
{
//can't enclose the origin within our tetrahedron
if (penVector != null) penVector = n;
return false;
}

// If origin is outside (v1,v0,v3), then eliminate v2 and loop
if (v1.Cross(v3).Dot(v0) <= 0)
{
//failed to enclose the origin, adjust points;
v2 = v3;
v21 = v31;
v22 = v32;
n = (v1 - v0).Cross(v3 - v0);
continue;
}

// If origin is outside (v3,v0,v2), then eliminate v1 and loop
if (v3.Cross(v2).Dot(v0) < 0)
{
//failed to enclose the origin, adjust points;
v1 = v3;
v11 = v31;
v12 = v32;
n = (v3 - v0).Cross(v2 - v0);
continue;
}

bool hit = false;

///
// Phase Two: Refine the portal

int phase2 = 0;

// We are now inside of a wedge...
while (phase2 < 20)
{
phase2++;

// Compute normal of the wedge face
n = (v2 - v1).Cross(v3 - v1);

n.Normalize();

// Compute distance from origin to wedge face
float d = n.Dot(v1);

// If the origin is inside the wedge, we have a hit
if (d >= 0 && !hit )
{
if (penVector != null) penVector = n;
hit = true;
}

// Find the support point in the direction of the wedge face
Vector3 v41 = GetSupport(shape1, -n);
Vector3 v42 = GetSupport(shape2, n);
v4 = v42 - v41;

float delta = (v4 - v3).Dot(n);
float separation = -(v4.Dot(n));

if (delta <= kCollideEpsilon || separation >= 0)
{
//Debug.Log("Non-convergance detected");
if (penVector != null) penVector = n;
return hit;
}

// Compute the tetrahedron dividing face (v4,v0,v1)
float d1 = v4.Cross(v1).Dot(v0);

// Compute the tetrahedron dividing face (v4,v0,v2)
float d2 = v4.Cross(v2).Dot(v0);

// Compute the tetrahedron dividing face (v4,v0,v3)
float d3 = v4.Cross(v3).Dot(v0);

if (d1 < 0)
{
if (d2 < 0)
{
// Inside d1 & inside d2 ==> eliminate v1
v1 = v4;
v11 = v41;
v12 = v42;
}
else
{
// Inside d1 & outside d2 ==> eliminate v3
v3 = v4;
v31 = v41;
v32 = v42;
}
}
else
{
if (d3 < 0)
{
// Outside d1 & inside d3 ==> eliminate v2
v2 = v4;
v21 = v41;
v22 = v42;
}
else
{
// Outside d1 & outside d3 ==> eliminate v1
v1 = v4;
v11 = v41;
v12 = v42;
}
}
}

return false;
}
}
}

• -1 "I kind of fixed it, here's all my code" is a really unsatisfying answer. What did you change? What was the intuition behind your changes? – Anko Dec 23 '12 at 13:45
• @Anko What are you referring to? – Raven Dreamer Dec 23 '12 at 14:16
• You had collision code. Then you changed something and to fix a problem with it, right? What did you change? – Anko Dec 23 '12 at 15:23
• @Anko You mean my edit? I was missing an "=" in a "<=". This meant the code did not detect contact collisions in some cases. – Raven Dreamer Dec 23 '12 at 15:39
• I get it now. In that case, your code is properly helpful. I'd like to upvote instead, but apparently SE "locks in" downvotes unless the answer is edited. :/ I've put in a small clarifying edit for peer review and will fix my vote when that gets through. Thanks for explaining! – Anko Dec 23 '12 at 16:21