Minkowski Portal Refinement

Minkowski Portal Refinment (hereafter MPR), the collision detection component of XenoCollide, is a technique developed by Gary Snethem of Crystal Dynamics to identify intersection points for abritrary convex solids while avoiding some of the problematic aspects of GJK. The first component of my thesis is an atempt to integrate MPR in to the collision detection pipeline of Box2D an attempt to evaluate its performance claims against GJK for finding contact points, collision normals, and penetration depth, the three necessary components for collision resolution in a rigid body dynamics system.

Where illustrative I will highlight similarities and differences with GJK, but primarily the following is an explanation of how to implement an MPR collision detection scheme using the excellent description provided in Snethen [1]. I have used the images available at xenocollide.snethem.com.

The following assumes an understanding of the Support function and Minkowski difference concepts, and that the Support function of a Minkowski difference for a support vector n is simply:

Sb-a(n) = Sb(n) - Sa(-n)

Equation 1

That is, the support function for the Minkowski object B-A can be composed from the support functions for the separate objects.

The following pseudocode is reproduced from the article:

//Phase 1: Portal discovery
find_origin_ray();
find_candidate_portal();
while (origin ray does not intersect candidate)
{
choose_new_candidate();
}

//Phase 2: Portal refinement
while (true)
{
if (origin inside portal) return hit;
find_support_in_portal_direction();
if (origin outside support plane) return miss;
if (support plane close to portal) return miss; //this is a tolerance case
choose_new_portal();
}

Code Listing 2

The article proceeds with a description of each pseudocode line. I will reproduce this explanation and augment it with a diagram in 2D available from www.xenocollide.com.

How MPR works in 2D. From www.xenocollide.com

The graphic shows a typical Minkowski difference, and illustrates in 2D the various phases of collision detection. We can see the origin is inside the difference, so we know this represents a collision between the two shapes.

This graphic shows the find_origin_ray() step, where an interior point V0 is chosen. The point can be anywhere inside the Minkowski difference but for obvious reasons the geometric center or center of mass is convenient. The origin ray is the ray from this interior point V0 to O, the origin.

Here, the origin ray is used to define the first support vector n and the first support point is located.

Here, the perpendicular is used to find V2, the next support mapping. There are two choices for this vector; the direction chosen is the one towards the origin.

Using this normal, we find V2. The line segment between V1 and V2 comprises the portal through which the origin ray must pass. For the while (origin ray does not intersect candidate) { }
we simply check that the origin lies to the left and right respectively of V0V1 and V0V2, ie, the angle V1V0V2 contains the origin. If not, we can compute a new support vector in the choose_new_candidate() step.

We now pause to observe the graphic and note there are three spaces where the origin can be: the region inside the V0V1V2 simplex, inside the Minkowski difference but outside the V0V1V2 simplex, or with the angle V1V0V2 but outside the Minkowski difference. The Portal refinement stage is to refine the portal such that we can conclusively identify that the origin is inside or outside the Minkowski difference.

The remaining three images show the while (true) block of the Portal refinement stage. If the existing portal contains the origin (via a barycentric coordinate check or three half plane checks) then a collision has been detected and the algorithm can break. If not, the portal normal (ie the vector perpendicular to V1V3, away from V0) is used as a support vector and a new support mapping is computed. If the origin lies farther than the support mapping on this new normal, we know the origin is outside the support plane and therefore there is no collision. In the case shown above, the origin is inside this line, so the new support mapping is used to choose_a_new_portal(). We know V1, V3, and V2 form a triangle. We know that the origin ray (from V0 towards the origin) enters this portal. We determine which edge the origin ray would exit from, either V1V3 or V3V2. We construct an edge from V0 to V3 as shown in the middle image, and we determine which side the origin lies toward (V1V3 or V3V2). We preserve the support points of the exiting edge (in this case V1V3), constructing a new, refined portal, as shown in the final image.

The algorithm now repeats the while (true) loop and hits the exit condition (of the portal containing the origin) and exits.

The paper does not document how best to compute a final support normal and or separating distance, but outlines two possible solutions. I am not sure at this point in my research which is the better choice, but the solution chosen by the other in his solver is to project the origin ray out to the surface of the Minkowski difference (ie, use the origin ray as a final support mapping to compute the points on the surface where the collision occurred and then using this contact normal as the collision normal. It is, in the authors words efficient and simple but not, I think, particularly accurate. More investigation is needed here.

The approach I used in my GJK solver in the case of non-penetrating (ie within the convex radius) was to use the final support normal as my collision normal, find the relevant features for each object (line-line, line-point, point-point) and then do some basic computation for feature overlap along this normal to determine actual contact points and penetration depths. Perhaps a similar logic would be sufficient here.