[ODE] contact joints / attaching them

[nlin at nlin.net]

On Sat, Oct 11, 2003 at 12:31:24PM +0200, Flavien Brebion wrote:
> Sweep collisions have been discussed to death on this list
> before, and from what i remember the conclusion was that ODE
> was unable to do it at the moment.

ODE is a general-purpose _articulated_ rigid body simulator. The
presence of links and constraints between bodies means that the rigid
body motion is not simple and must, in general, be numerically simulated
(as opposed to analytically integrated).

My opinion is that _detection_ of (potential) collisions using a swept-volume
method with ODE is feasible (perhaps even trivially easy) but inaccurate;
however, actually _handling_ a missed collision (i.e. overlap of swept
volumes) is harder. 

As for detection of potentially missed collisions, given the old world
state, step the world one step, and create linearly swept volumes for each
body that moved, then check if any volumes intersect. If so, then you had a
(potential) collision over the course of the timestep. Of course, the bodies
don't move linearly over timesteps due to the presence of joints (see my
pendulum example in a previous mailing list posting), but maybe this can be
used as a rough mostly-accurate approximation.

The big question is, what do you do, in general, if you detected that 
the swept volumes intersect? With simple rigid bodies with no joints and easy
convex geometry, you can analytically compute the first time of contact,
back up the simulation to that point, and resume. But with articulated
rigid bodies this is much more difficult because the motion of the entire
articulated structure is very complicated. So we can't analytically compute
when the time of collision was: instead, we have to back up all the way to
time t-1, restep the entire simulation by a smaller timestep, and see if
there are any (swept) collisions. This must be repeated until a small-enough
timestep is found which generates no penetrations. As described in section 
11.3 of the ODE documentation:

   "automatically choosing a non-penetrating step size is problematic for
    an articulated rigid body simulator (the entire ARB structure must be
    stepped to account for the first penetration, which may result in very
    small steps). "

If you want to do swept collisions on only geometrically simple (i.e.
no arbitrary mesh) single bodies that aren't connected to any others
with any joints (no motors, no sliders, no hinges), then you can do
that, it would be easy and accurate, and it would work. But remember that
this is only a small, special-case solution, which doesn't work when
articulated structures are part of the configuration. If you want accurate
simulation with no missed collisions of lots of high-speed objects and
complicated articulated structures like ragdolls (good example: a character
throwing a high-speed punch to the head of another character, and you want
totally accurate collision detection of when one guy's hand hits the other
guy's head, both of which are moving at high speed), then you have to pay the
price: rewind the simulation, take a smaller step, until either no swept
volumes intersect or you find (within an epsilon tolerance) the first instant
of contact, and re-simulate everything from there. This would likely grind
your simulation down to a nerve-wrackingly slow pace, but that's what you
have to do if you need this kind of accuracy.

-Norman