Collision Detection - why GJK?

Started by
21 comments, last by Nagle 5 years, 11 months ago
Quote

 That energy was then distributed among the contact points in inverse proportion to their distance to contact.

This might be actually useful for warm-starting in the impulse based systems. How did you re-distribute the energy? I assume you would redistribute in a way that the net forces on the associated bodies are relatively stable between frames?

Advertisement

I wanted a more accurate simulation than games usually use. So, from that I'd compute the two most parallel faces and the plane through the midpoint of the closest points vector and normal to it. Then the two closest faces were projected onto that plane to get two polygons. The polygons were intersected. That's the contact polygon. Then the distance from the vertices of the contact polygon to each of the closest faces was computed, to get the distance to contact at each corner of the polygon.

That sounds exactly like what's described in this presentation

http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf

Very similar. Here's the comparable figure from my 1998 patent on spring-damper physics for ragdolls. Expired this year. The paper from Valve is from GDC 2015.

  fig8c.png.ef9aabcc788cfbb6265f0aa850ff2a5a.png

"Skin" and "Bone" contact model.

The rectangular collision objects 86-88 are rigid and are not allowed to interpenetrate. The visual geometry is out at the curved boundaries. With this approach, the closest-points vector 78-79 moves smoothly as two objects come close near a corner. If you use interpenetration and compute the collision as "shortest move to out of collision", the contact vector snaps sharply as a contact reaches a corner. In a system where the time step is variable (simulation and animation rather than real-time games) the integrator keeps cutting the time step to reduce error, trying to zero on where things suddenly changed. Timesteps can drop into the nanoseconds chasing that discontinuity. Don't want that. That's step one to smooth collisions.

Step two is multiple contact points. That takes care of what's called static indeterminacy, which is why a table with four legs not exactly the same length wobbles on a hard surface. You need some minimal springiness or error tolerance to get anything with more than three contact points to settle.

With both of these, contacts become differentiable. A tiny move will not produce a big change in forces. Now you can integrate stably.

This was for a spring-damper system. Those are more accurate, but slower. Games use impulse-constraint systems, which can be solved in constant time, but always look a little off, because there are big velocity changes in one frame time. Real-world large objects don't do that.

With enough compute power, spring-damper physics might come back. It's like ray-tracing - better, but expensive.

This topic is closed to new replies.

Advertisement