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.

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