Continuous Collision Detection

[TomatoSoup]

I'm working on a space game with proper physics. This means that ships are moving 10s to 1000s of times their own length each second. To resolve collisions I need a Continuous Collision Detection algorithm.

I've implemented the formula seen here, http://studiofreya.com/3d-math-and-phys ... n-spheres/ and it works pretty well. Implementing a spatial hash based on both position and velocity allows it me to track upwards of a thousand objects without lowering the framerate.

However, this implementation only supports circular colliders and all of my attempts to reduce more complex shapes to the base-case of sphere-sphere collisions have been futile.

Do any of the existing Love2d libraries support CCD? Is there some easy solution to this that I'm missing?

[Taehl]

I'm not too experienced with CCD, but have coded physics many times now. My advice would be this: Use your current CCD method. Use it for each star and planet (nice bonus: correct shape!), and also for each ship or station. Set their circle diameter so that the circle covers them entirely. Wait until it finds a collision, then worry about checking against complex shapes (using a different method if you prefer).

[TomatoSoup]

So I was going to rewrite my code so that the sphere-sphere worked the same way, but instead decompose sphere-poly and poly-poly collisions into a bunch of line-line collisions. The only thing I thought this method wouldn't handle was where two colliders were coincident (a smaller one inside the other) and stationary, so none of their corners would project into lines to actually collide. But this is a well-solved case! This is how typical colliders work! So I looked up polygon-polygon collisions.

http://www.codeproject.com/Articles/155 ... -Detection

This appears to be an algorithm that does what I'm looking for, but I'm not certain? It gives me if they're intersecting, and if they eventually will intersect, but it doesn't give a time to collision. It does give the minimum translation vector, which it says can push the polygons apart, but that seems odd to me, like it's giving a distance to push them apart from their resting positions after the timestep (which you don't specify).

I could test it but it's a lot of code to reimplement for not being certain that it works. And I'd still have to bring circles back in.

[Taehl]

Wouldn't time to collision basically be (mutual approach velocity / distance)?

[ivan]

A while ago I dabbled in continuous collisions but at the end I found that it's way too much work.
If you only have moving points/circles it may be worth to program it yourself, but otherwise,
you might as well use Box2D/love.physics with "SetBullet(true)".

Below is my poor attempt although it needs a lot more testing and work,
it's based on a book called Realtime Collision Detection.
https://bitbucket.org/itraykov/utils/sr ... /sweep.lua <-- main CCD lib
Dependencies:
https://bitbucket.org/itraykov/utils/sr ... roject.lua <-- nearest point lib
https://bitbucket.org/itraykov/utils/sr ... verlap.lua <-- static overlap tests
https://bitbucket.org/itraykov/utils/sr ... th/vec.lua <-- vector class