[ODE] box-box collisions

[Russ Smith]

> Russ, would you care to explain the current box-box collision algorithm
> (and maybe box-plane as well)?  I've been looking it over but the code is
> rather... dense :-)

to summarize: the standard 15-axis test is performed to check for box-box
intersection (6 face-normal tests and 9 edge x edge tests). for each axis,
the box-box penetration is recorded (penetration defined as the overlap of
the projection of the boxes to the test axis). the most penetrating axis
is used as the normal. if the most penetrating axis is an edge x edge then
the closest point between the closest box edges is used as the contact
point. otherwise the most penetrating axis is normal to the face of one
box so the deepest vertex (along this axis) of the other box is used.

it is this last case that should be modified to generate up to 3 contacts,
not just the one. one approach is to examine the three edges adjacent to
the most penetrating vertex and clip them to the box, thereby generating
three other points, and use the two that are deepest. i've not tried this,
so i don't know if it will work well, but this would be my first approach.

some other people's box-box code takes the following approach (or some
variant of it): compute the box-box intersection volume, take the vertices
of this volume as an initial contact point set, then do some kind of
culling to reduce the contact points to a manageable number. this approach
has three big drawbacks: (1) it's slow, (2) the culling process is not
well defined so this can lead to over-sensitive contacts, (3) for
edge-edge contacts, where there should only be one contact point, these
schemes nevertheless generate many points - and it takes a very smart
culling algorithm to reduce this to just one.

this illustrates a point i've made before: that collision detection for
dynamics is a more difficult problem that collsion detection alone: the
contact points that are generated must meet extra conditions so that the
resulting contact-driven motion will be stable. in particular:

  * contact points should be inside the collison volume.

  * contact points should not jump around unnecessarily if the object
    positions change slightly (these are called over-sensitive contacts).

  * the contact constraints should be far from singular. the worst thing
    that collision code can do is generate coincident contacts.

  * the contact set must depend only on the local surface properties, not
    on the global object properties.

  * the contact normal should be the most direct translational path to
    reducing penetration at a contact point. this condition is less
    necessary for stability than the others, but is still important.

russ.

--
Russ Smith
http://www.q12.org/