I've been reading this article on using Minkowski Differences for game collision, but unfortunately stuck on a particular part. I managed to create the Minkowski differenced AABB, and collision detection works on any side. But I fail to understand (intuitively) how to get the penetration vector of said collision. 

Please note that this article uses the Y inverted, but I re-wrote the code and as I mentioned earlier, got collision detection working. Up in my implementation is +y.

Accoridng to this article: 

Quote

Quite conveniently, the penetration vector is simply the minimum distance from the origin to the Minkowski-differenced resultant AABB...

I'm guessing he's referring to the distance from the origin in Minkowski Space to the Minkowski differenced box? I really can't seem to wrap my mind around this penetration vector code to be honest  . He describes a function called closestPointOnBoundsToPoint, which does exactly that, but I'm not getting it. A Vector.zero is passed to the function, so in what situation do you pass something different? . If I can give a wild guess, I'm assuming it's due to the fact that if there's a collision, the Minkowski AABB will always surround the Minkowski space origin. I don't know if I'm right, I'm assuming. 

Hopefully somebody can point me towards the right direction. Below I'll share the code I have so far in order to get the Minkowski differenced aabb. If anymore information or code is needed, let me know. Thank you very much in advance!

// AABB constructor arguments: center, size of AABB
// Btw, this particular example collides.
const a  = new AABB (new Vec2(0, 0), new Vec2(1, 1));
const b  = new AABB (new Vec2(2, 0), new Vec2(1, 1));

const diff = Vec2();
diff.x = a.min.x - b.max.x;
diff.y = a.min.y - b.max.y;

const size = new Vec2();
size.x = a.size.x + b.size.x;
size.y = a.size.y + b.size.y;

// Minkowski AABB
const md    = new AABB();
md.center.x = (diff.x + size.x); 
md.center.y = (diff.y + size.y); 
md.size     = size;

// Check For Collision
if (md.min.x <= 0 && md.min.y <= 0 &&
    md.max.x >= 0 && md.max.y >= 0) {
       
    // Collision, but needing the penetration vector, so I can push object out :(
}
else {
    // No Colision.
}

Edit:

I tried visualizing the AABBs and noticed that the Minkowski AABB is a mirror of the point of collision but in some other space around the origin, let me call it Minkowski space for now.

I still don't understand how to get the penetration vector though. I'm guessing since the Minkowski AABB is a mirror of the point of collision, we can use the origin (Vector.zero) in Minkowski space to calculate the vector I can use as an offset. By the way, I'm sorry if I'm not using the right terminology.

You should use a different algorithm. Using GJK for this task is A) overkill, and B) will not help you resolve the collision. Here's an example algorithm in 2D that can be extended to 3D: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h#L1285-L1340

23 minutes ago, Randy Gaul said:

You should use a different algorithm. Using GJK for this task is A) overkill, and B) will not help you resolve the collision. Here's an example algorithm in 2D that can be extended to 3D: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h#L1285-L1340

Hey Randy thanks for the share, I appreciate it. Although I forgot to mention that I'm working on a fast paced 3D fps that uses some very basic physics. So I read that Minkowski Difference was a nice candidate, is that true?

I know I'll have to modify my code in order to avoid tunneling and consider the colliders velocities, but I wanted to understand the algorithm in its simplest form.  

By the way I finally understood how to get the "penetration vector". I like calling it an offset vector instead, since I use this returning vector to push the collider out.

Would this algorithm (plus modifications) still be a good idea for a fast paced fps game with physics, or maybe a better question, what would Minkowski Difference in terms collision be good for? What situations? Thanks!

Good questions. Minkowski stuff is useful to implement the GJK algorithm. GJK finds the two closest points between two convex sets. It does not do anything else -- if two shapes are colliding, all that is known after GJK runs is that they are colliding. It provides no information as to how, which is needed to resolve a collision.

I suggest using a very straight-forward function to quickly test to see if two AABBs are touching at all. This can be coded in SIMD pretty easily if you want an extra speed boost. Reading about Minkowski stuff will not help you here. Something like this (which I grabbed from here https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection?

function intersect(a, b) {
  return (a.minX <= b.maxX && a.maxX >= b.minX) &&
         (a.minY <= b.maxY && a.maxY >= b.minY) &&
         (a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}

If this function returns true, then you can use a more complicated function to compute penetration vector (axis of minimum penetration) and depth (like the function I linked you in my last post).

Also it would be wise to use a capsule for your player collider, for a variety of reasons! Mainly to make things easy to implement.

On 6/28/2018 at 10:17 PM, Randy Gaul said:

Good questions. Minkowski stuff is useful to implement the GJK algorithm. GJK finds the two closest points between two convex sets. It does not do anything else -- if two shapes are colliding, all that is known after GJK runs is that they are colliding. It provides no information as to how, which is needed to resolve a collision.

I suggest using a very straight-forward function to quickly test to see if two AABBs are touching at all. This can be coded in SIMD pretty easily if you want an extra speed boost. Reading about Minkowski stuff will not help you here. Something like this (which I grabbed from here https://developer.mozilla.org/en-US/docs/Games/Techniques/3D_collision_detection?

function intersect(a, b) {
  return (a.minX <= b.maxX && a.maxX >= b.minX) &&
         (a.minY <= b.maxY && a.maxY >= b.minY) &&
         (a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}

If this function returns true, then you can use a more complicated function to compute penetration vector (axis of minimum penetration) and depth (like the function I linked you in my last post).

Also it would be wise to use a capsule for your player collider, for a variety of reasons! Mainly to make things easy to implement.

Hey Randy thanks a lot for the great answer, very much appreciated. I'm definitely changing the algorithm to the more simpler version you're suggesting and changing my character to a capsule collider. Thanks again!