Erwin Coumans wrote:oh man. guys , are you still okay 20 yrs later? the algorithm Nagle provided looks good.
Gino's iterative approach of retrieving the contact points is pretty straighforward and simple to implement, as the Nagle approach seems to be a bit more work and has more preconditions on the input.
Does Nagle's solution have important benefits ?
Erwin CoumansGino is working on interpenetrating bodies, which
is a slightly different problem. I preferred to work with
non-overlapping bodies, which results in a physics system
that always has some airspace between bodies. (I hid
this from the user in Falling Bodies by using a slightly
smaller geometry for collision than for graphics, which
I call a "skin and bone" model. The "bones" never
quite touch, but the "skins" do. It's a good model for
character work.)
The closest-points vector between two nearby
bodies is well-behaved in a way that the penetration
depth vector for overlapping bodies is not. The
penetration depth vector, remember, is the shortest
move that will get the two bodies out of contact.
There are cases where that vector can suddenly change
direction by a large angle in response to an arbitrarily
small move of one of the bodies. The visible effect of
this is that two bodies forced into contact suddenly
move sideways, rather than apart. That's why I
didn't like penetration vectors.
But Gino has taken the next step, which is to
compute the volume intersection of the two bodies
(I think). That's better behaved than the penetration
vector, just as the contact polygon, which I compute,
is better behaved than the closest points vector.
So Gino has an improvement over Steven Cameron's
previous work on penetration vector extensions
to GJK.
Because I was
building a system that used spring/damper collisions
with implicit integrators, it was highly desirable
to avoid all discontinuities in forces as the bodies
move. Implicit integrators behave badly over
discontinuities, and making the system to be
integrated continuous everywhere improved
system behavior.
The original poster is building a Baraff-type
impulse/LCP constraint type system, which has a different
set of problems than a spring/damper system. But
it, too, needs a well-behaved contact area.
I think that Gino's algorithm will produce
a well-behaved contact area, provided that something
is done to prevent the penetration depth from
becoming too deep. "Too deep" needs to be
formalized. At some depth, the penetration direction
to get out of the contact jumps to another face,
which can result in unexpected sideways moves of
bodies in contact. That needs to be avoided by
the levels above collision detection.
All this finicky stuff is the difference between
"sort of works most of the time" and "works robustly".
It's not fun, but you've got to do it before you ship.
(Or license a physics engine and pay someone else
to suffer.)
John Nagle
Animats
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 297 |
Nodes: | 16 (2 / 14) |
Uptime: | 101:55:50 |
Calls: | 6,660 |
Calls today: | 2 |
Files: | 12,209 |
Messages: | 5,334,975 |