[ODE] Swept collisions?

[nlin at nlin.net]

On Tue Sep 30 11:33:39 MST 2003, Mark Wayland (mwayland at torus.com.au) wrote:

> Is anyone planning swept collision additions to ODE?

Are swept collisions feasible to do with articulated rigid bodies? If so, how?
My understanding of swept collision methods is that you assume each body moves
unconstrained in a linear fashion over the course of the timestep, then you
find the intersection point of the swept volumes. However with articulated
rigid bodies, the motion over the timestep is likely to be constrained by
joints.

How could you account for this with a swept collision scheme?

The "proper" way would seem to be to sweep the path of the entire articulated
rigid body structure or "island" across the duration of the timestep, but this
requires expressing the entire constrained motion as an analytical function,
as well as then finding an intersection with this very weird-looking swept
volume (imagine the volume produced by sweeping the motion of a chain of cubes
over one timestep), so this analytical method is probably impossible (in
real-time, anyway) for several reasons.

Another possibliity would be to ignore the joints during the sweeping phase,
do swept collision on all pairs of primitives separately, and then do some
iterative "fix up" as a last step to "jiggle" the joints back into place,
but I'm not sure if that is a good idea in terms of computational cost (lots
of passes would probably be required - do swept collision, fix-up joints, which
may cause new collisions, so do the whole thing again...) or accuracy.

Furthermore, assuming a straight-line motion of each individual body in a
constrained structure may lead to spurious collisions. Imagine a high-speed
swinging pendulum whose arc almost grazes but does not touch a plane. The
constraint keeping the pendulum from flying away (i.e. the string) prevents
the pendulum from ever touching the plane, but doing a swept straight-line
collision of the instantaneous motion of the pendulum would, at the lowest
point of the arc, incorrectly lead to a collision between the pendulum and
the plane (because the instantaneous straight-line motion, extrapolated over
the timestep, fails to account for the restraining effect that the constraint
has, thus leading to the incorrect result that the pendulum collides with
the plane). This then causes some contact forces to be incorrectly generated,
which then leads to very unphysical behavior.

I imagine that in the general case, many such spurious collisions would occur
since the constraints, in general, violate the assumption of "straight line
motion over timestep" (or "simple motion over timestep") upon which swept
collision seems to depend.

Anyone else have other ideas?

-Norman