Moving Bounding Boxes colliding

[kikito]

As you may or may not know, I've been working on version 2.0 of bump.lua (my collisions lib) for a while now. The new version is a complete rewrite, test driven. It's already matched what bump.lua could do and adds a couple things here and there (segment queries being one of the new additions).

I've maybe grown a bit ambitious, and started studying the "pass-through" problem. Pass-throughs happen when items are moving so fast that they "go through" each other without collisions being detected.

I've been studying a way to eliminate them, and I think I'm into something. The best part? It seems that detecting (and correcting) pass-throughs, is more expensive than ignoring them, but it's not a huge difference in computation.

I've been studying something called the Minkowsky Difference. You can read more about them in Collision Detection for Dummies. Here i'll just say that they are basically geometric objects that express a spatial relation between two other objects, and that they have very useful properties for collision detection.

Bump.lua deals with axis-aligned bounding boxes (aabbs) only. And it turns out that the Minkowsky Difference of two aabbs is another aabb. And it's also extremely easy to calculate. See for yourselves:

Code: Select all

function aabb.getMinkowskyDiff(l1,t1,w1,h1, l2,t2,w2,h2)
  return l2 - l1 - w1, -- left
         t2 - t1 - h1, --top
         w1 + w2, -- width
         h1 + h2 -- height
end

Once the MD is calculated, lots of interesting things can be done. For example, if the MD of two aabbs contains the point in 0,0, then the two aabbs are intersecting. When this happens, the minimum displacement vector is the nearest point to 0,0 in the MD perimeter.

More significantly, calculating the point in time were two moving aabbs collide can be also done relatively easily. You just need to intersect the MD with a segment representing the relative displacement between the two boxes (which can be done using another algorithm, called liang-barsky, in very few steps).

I'm attaching a demo of what I have so far.

Screen Shot 2012-12-05 at 11.14.26 PM.png (4.52 KiB) Viewed 4366 times

Control is done via the mouse. Clicking any button will switch between moving the red box, it's "velocity" (displacement, to be precise), then the green box and its "velocity", and then back to the red box. Esc exits.

moving-aabbs-collision.love

(2.05 KiB) Downloaded 272 times

The Minkowsky Difference of the two boxes is represented in blue, as well as the relative displacement vector. The origin of coordinates is in the center of the screen, to make the MD easier to see. You can visually check that when the boxes intersect, the MD contains 0,0, and that when the relative displacement vector crosses it, the boxes intersect later in time.

I still have to clean up the code a bit before I can integrate it in bump.lua, but I'm happy with how it's turning out and I wanted to share it

[dreadkillz]

Continuous collision detection is a very interesting subject. If you're really into that, you could also visit the bullet or box2d forum and talk to the authors about some techniques.

This is pretty cool though combining your previous post for line intersecting test with the Minkowski Sum.

For the curious: Kikito's algorithm is a variation of this paper link

Or read the paper: Gino van den Bergen “Ray Casting against General Convex Objects with Application to Continuous Collision Detection”

[kikito]

Hey, thanks for the comments.

I really didn't read any paper for this one. Only Collision Detection for Dummies ... and google and stackoverflow. . I confess I'm not capable of reading those academic pure-math papers. I'd rather parse a hairy piece of code, even if it's C++. The fact that I'm considering only aabbs helps immensely. The only vector math I need is to calculate the relative displacement

One thing I'm planning to do is making bump.lua continuous but a posteriory. It'll let the user move the objects however he wants, and then let him know where did they collide with other objects and the vectors that would correct the positions, even if that means moving the objects "backwards" significantly. At least according to wikipedia, this way of doing things is novel (and thus probably wrong).

An extra benefit I forgot to mention is that when an object collides with another, it is "moved backwards" in the opposite direction it had. This is a bit more natural than what I was doing before (where the objects only moved along one coordinate - x or y).

[dreadkillz]

Yes I understand. I only posted the paper because I have done some research on this before and recognized your findings. Plus math is a bit easier for me to understand than programming (this is something I just do for fun).