CODEWITHSUNDEEP
mathcollision-detectionoverlap
Jack Wilsdon
Jack Wilsdon

Reputation: 7025

Getting 'depth' of overlap?

This is a pretty much platform-independant maths question. I have two squares, which are overlapping. I need to know the "overlap depth" (how much one shape has gone into another). I need this data to allow for proper collisions (move player back overlap depth). Is there a simpler way? Or am I better sticking to the following;

rA is a rectangle, and so ia rB.

depth.x = (rA.position.x - rB.position.x);
depth.y = (rA.position.y - rB.position.y);

This returns somewhat incorrect information, as instead of returning overlap depth, it returns the distance between rA and rB (to be expected). The issue is, I cannot work out the formula to find overlap depth of the two objects. Would I need to somehow factor in object sizes, even though I already know there is a collision?

It has been suggested that I can do depth.x = (rA.width/2) - (rA.position.x - rB.position.x). However, this would not work if rB was on the left, as it would do -10(example) - 50, which would be invalid (-60). I would prefer to keep away from lengthy if statements, and stick to just knowing how much they overlap. So, is it possible to work this out?

Upvotes: 2

Views: 384

Answers (1)

Michael Anderson
Michael Anderson

Reputation: 73460

I'm going to assume that your squares axis aligned, but show a technique that will work even if they are not.

General Result ( convex polygons )

The method relies on the Minkowski difference of the two sets, a common technique for finding intersections.

The Minkowski difference of two convex shapes is convex, and if both originating sets are polygonal then the resulting shape is polygonal. This means that it can be represented as a set of equations n_i.x>c_i where each ni is unit normal.

So an algorithm for determining if two shapes intersect is:

  1. Determine the Minkowskian difference of the two shapes.
  2. Determine whether the origin falls inside the Minkowskian sum (which is true if all the c_i<0 )

A measure of the depth is then max(c_i)

Special case for axis aligned squares

Now for two axis aligned squares the Minkowski sum is just another axis aligned square. Taking square A as centered at (cA_x,cA_y) with width WA and height HA we can express it as:

 A = { (cA_x + a WA/2, cA_y + b HA/2), where -1<=a<=1, -1<=b<=1 }

Similarly square B would be:

 B = { cB_x + c WB/2, cB_y + d HB/2), where -1<=c<=1, -1<=b<=1 }

Then the Minkowski Difference is

 A-B = { (cA_x - cB_x + a WA/2 - c WB/2, cA_y - cB_y + b HA/2 - d HB/2), where ... }
     = { (cA_x - cB_x + r (WA-WB)/2, A_y - cB_y + s (HA-HB)/2), where -1<=s<=1, -1<=r<=1 }

The 4 edges of A-B are then

 x > (cA_x-cB_x) - |WA-WB|/2
 y > (cA_y-cB_y) - |HA-HB|/2
 x < (cA_x-cB_x) + |WA-WB|/2
 y < (cA_y-cB_y) + |HA-HB|/2

The last two can be rewritten as

 x > -(cA_x-cB_x) - |WA-WB|/2
 y > -(cA_y-cB_y) - |HA-HB|/2

Thus we find that the depth of intersection is:

 min(
     (cA_x-cB_x) - |WA-WB|/2,
     (cA_y-cB_y) - |HA-HB|/2,
    -(cA_x-cB_x) - |WA-WB|/2,
    -(cA_y-cB_y) - |HA-HB|/2 )

With intersection only occurring if this depth is positive.

(Note: I've been working through the math as I write this, so its quite possible I've got a sign incorrect here or there... feel free to correct any such errors...)

Upvotes: 1

Related Questions