Moving Bounding Boxes colliding
Posted: Wed Dec 05, 2012 10:24 pm
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:
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.
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.
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
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
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.
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.
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