Erwin Coumans wrote:
Is this at the beginning of the timestep (T0) or at the end?
Beginning, T0
Can you also explain it in terms of my picture with the red and green spheres?
Yes and no. If we are assuming a linear system, then your spheres would be approximated by a large number of polyhoderon. Then you would have a similar situation as in my figure, where at time T0, many vertices of the red (green) polyhedron approximation would be in potential contact with many edges of the green (red) polyhedron approximation. In the limit, you could include every vertex with every edge, but that is computationally intractable and we use techniques to prune the number of witness pairs.
If your spheres are implicit or smooth, then a nonlinear complementarity formulation must be used which will not require vertex/edge pairs, since they don't exist. If you are really interested in exact geometric representations, this is something we are exploring in our lab right now.
Most importantly, how are you using this witness pair info exactly?
The distance between each witness pair is included into the Stewart-Trinkle formulation, which does not allow this distance to become negative; thus preventing inter-penetration of the body. The complementarity constraint is between this gap "function" and the normal contact force. Since we don't really have a function for the gap, we take a tailor series approximation of it:
\psi_n + \partial \psi_n \over q * \Delta q + \partial \psi_n \over t * \Delta t
where psi_n is the value of the gap at time 0, \partial \psi_n \over q is the nonpenetration constraint jacobian, q is the configuration of the body, \partial \psi_n \over t arises for kinematically controlled bodies, and \Delta t is the step size.
It should be noted, the only difference between the Stewart-Trinkle formulation and the Anitescu-Potra, is the inclusion of the \psi_n term in the Taylor series expansion: ST includes it, AP does not.
How do you make sure at the end of the timestep they don't miss the collision or deeply penetrate? Do you adjust the velocity, or only integrate the position with a fraction so they come in touching contact?
(this 'fraction' is the time of impact)
By including every potential collision, we can guarantee we never miss it. Of course in practice this is infeasible. The ST formulation will not allow the gap to become less than 0 (thus no penetration). The AP form enforces the constraint at the velocity level, so some initial amount of penetation may occur, but after that AP prevents it from getting worse. (Aside: If you run the applet on my website and ram the sphere into the horizonal surface, you will see it penetrates the surface with AP, but not with ST. Also, if you cause penetration with AP, then switch the model to ST, the position level constraint kicks in, and the circle is forced out.).
If all possible contacts are identified at time T0, then we can guarantee (even with a fixed step size) that penetration will not occur at time T1. If a contact occurs during a time step, the complementarity condition between the gap function and the normal contact force will determine that the gap = 0 and the normal contact force > 0 at time T1. If contact does not occur, then the complementarity condition will be gap > 0, normal force = 0 at time T1. Note, this only allows for plastic collisions (no bounce). If a collision response is desired, the time of impact must still be determined and some impact law applied. Or you can cheat, and apply the collision response at the end of the time step.
It is possible! Actual implementations: Havok, Doom3, PhysX and many more. They all can prevent penetration using time of impact calculation in the collision detector, and a dynamics scheme that steps until the time of impact (or throwing away additional motion that would lead to penetration). Bullet collision detection calculates the time of impact, but the implementation is work-in-progress. The trick is to allow some 'tolerance' / 'allowed penetration' for the touching contacts (otherwise you get always zero time of impact).
Call me skeptical though. I deal with contact intensive systems, which would make these calculations "collision bound". Imagine trying to simulate sand in an hourglass. All of these time to impact calcuations will prevent progress of the simulation. Whereas we can have a fixed time step and guarantee progress.
Allowing penetration is not an option I personally approve of. It is not what physcally happens. The processes of how to resolve inter-penetrated bodies are very ad-hod at the moment, and without some sort of swept sphere computation to determine the incoming trajectory, can be wrong. I am more interested in the new locally-compliant models, where the bodies locally deform at the contact, and resolution is based on displacements instead of analytical techniques.
If you have any other questions please ask. I will attempt to read a little about these "continuous collision checker", to better understand them.
--Steve