How can I get penetration depth from Minkowski Portal Refinement / Xenocollide?
- by Raven Dreamer
I recently got an implementation of Minkowski Portal Refinement (MPR) successfully detecting collision. Even better, my implementation returns a good estimate (local minimum) direction for the minimum penetration depth.
So I took a stab at adjusting the algorithm to return the penetration depth in an arbitrary direction, and was modestly successful - my altered method works splendidly for face-edge collision resolution!
What it doesn't currently do, is correctly provide the minimum penetration depth for edge-edge scenarios, such as the case on the right:
What I perceive to be happening, is that my current method returns the minimum penetration depth to the nearest vertex - which works fine when the collision is actually occurring on the plane of that vertex, but not when the collision happens along an edge.
Is there a way I can alter my method to return the penetration depth to the point of collision, rather than the nearest vertex?
Here's the method that's supposed to return the minimum penetration distance along a specific direction:
public static Vector3 CalcMinDistance(List<Vector3> shape1, List<Vector3> shape2, Vector3 dir)
{
//holding variables
Vector3 n = Vector3.zero;
Vector3 swap = Vector3.zero;
// v0 = center of Minkowski sum
v0 = Vector3.zero;
// Avoid case where centers overlap -- any direction is fine in this case
//if (v0 == Vector3.zero) return Vector3.zero; //always pass in a valid direction.
// v1 = support in direction of origin
n = -dir;
//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)
{
//Debug.Log("Could find no points this direction");
return Vector3.zero;
}
// v2 - support perpendicular to v1,v0
n = v1.Cross(v0);
if (n == Vector3.zero)
{
//v1 and v0 are parallel, which means
//the direction leads directly to an endpoint
n = v1 - v0;
//shortest distance is just n
//Debug.Log("2 point return");
return n;
}
//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
//Debug.Log("Could not reach edge?");
return Vector2.zero;
}
// 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
//Debug.Log("Could not reach edge after portal?");
return Vector3.zero;
}
// 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 )
{
//Debug.Log("Do plane test here");
float T = n.Dot(v2) / n.Dot(dir);
Vector3 pointInPlane = (dir * T);
return pointInPlane;
}
// 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");
//Debug.Log("Do plane test here");
return Vector3.zero;
}
// 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 Vector3.zero;
}
}
