Linear Collision Sweeping

[fork]

I was curious what are people doing with linear collision sweeping. It seems to me that one can't rely on just pure linear collision sweeping for detection. For example, what if a linear sweep doesn't detect two objects won't collide in the next time step but when you actually update the two objects (which of course now takes into account their rotation) they intersect.

I seem to be having this problem in trying to do time of impact calculations with just linear sweeping (although I haven't actually debugged all the way down to verify this).

Another question, is the problem of detecting the time of impact really just as hard in 2D as in 3D?

What would be nice is if somebody could weed through all the papers out there and list the really important ones here.

[dcoming]

I was curious what are people doing with linear collision sweeping. It seems to me that one can't rely on just pure linear collision sweeping for detection. For example, what if a linear sweep doesn't detect two objects won't collide in the next time step but when you actually update the two objects (which of course now takes into account their rotation) they intersect.

Its not an easy problem to solve for TOI with arbitrary rotations along with translation. There are closed form solutions for intersection tests between objects with translation or rotation when separate, but this is not possible when combined. It's comparable to attempting to algebraically solve for x in the following: y = x + sin(x)

You could try an approximation like "screw motions". The idea is to approximate an arbitrary rotation and translation with a series of screw motions, in which the rotation axis is the axis of translation. I believe this assumes linear translations; does anyone know how it handles non-linear translations? Its an approximation and requires a numerical root finder, but its an improvement over translation alone. Check this paper out:

B. Kim and J. Rossignac, ?Collision prediction for polyhedra
under screw motions,? in SM ?03: Proc. Eighth ACM Symposium
on Solid Modeling and Applications. ACM Press, 2003,
pp. 4?10.

Another question, is the problem of detecting the time of impact really just as hard in 2D as in 3D?

Actually, 2D has a lot fewer special cases to consider. Collision detection is certainly easier when you can possibly reduce the dimensions of the problem. I think Gino said something like that in his book.

What would be nice is if somebody could weed through all the papers out there and list the really important ones here.

I'm continually amazed at how many papers there are on collision detection. People already do tackle this issue though. Your best bet is to read a couple of survey papers and if the methods mentioned sound interesting, check the bibliography and read those papers. You could also check out what methods get referenced in books, but of course they won't include the very latest due to the time involvement to publish a book.

[fork]

So if I am trying to do TOI for a baraff implementation of collisions (in the special case of 2D physics only) what do you people recommend? The problem is that most papers out there are targeted for 3D, so what do you guys think is a strong way of doing it in the special case of 2D.