Erwin Coumans wrote:There should be no difference between 1st order velocity-level or 0-order position-level constraint solving in combination with CCD and CP. In both cases, at the time of impact, a discontinuity happens and contact constraints have to be solved, and the direction of motion typically changes. This means the time of impact queue needs to be recomputed for objects involved. So even with velocity-level solving the position and velocity of objects involved change. Why do you think that position level differs?
The problem is the "contact constraints have to be solved" part -- at the TOI, you _can't_ solve position constraints because they aren't violated!! I may be boneheadedly missing something.. my understanding is that CCD with a velocity-level solver is iterative, with each pass through looking something like this:
-advance to TOI
-solve collision (modify velocity of 2 objects)
-continue (i.e calculate next TOI/interacting pair)
As you said, rather than solving the collision, you can add it to a list and solve it together with the other constraints.. the problem is that since the velocities aren't changed, objects still pass through each other (before the solver step, during the "generate constraints" swept-collision step) and this incorrect movement can generates other constraints which should never exist, and which cause problems (fighting each other or "ghost" collisions between two non-touching objects).
The only solution I could find is to perform some simple collision-type queries, which is where I am currently. The other alternative was, as you mentioned earlier, to just move to the time of first impact and stop, however this tends to undermine one of the big advantages of this solver, which is that it supports large mass ratios (1:100).. if you stop at time of first impact, you get heavy objects stopped dead by tiny ones. Probably some rule-based solution might work, but I gave up on it.
I think a better approach might be to use a velocity-level solver for the CCD part (again, I might be totally wrong about what everyone else is doing, but AFAIK this just means cancelling the velocity of the contact point along the collision normal).
Predictive generation of contacts is exactly what CCD is about: it gives you the next time of impact and contact points. This means you simply simulate up to the next toi. So if we assume that CCD provides this information, what exactly is the problem?
As I mentioned, the problem is that you can't actually do anything useful at the TOI, since the error is at the velocity level.
Shallow penetration should not cause issues, but it is possible to combine CCD with zero-penetration. Doom 3 and later idSoftware games use zero penetration, in combination with some clever rules between objects that are in contact. Jan Paul van Waveren provided me a paper and further information that will be part of a chapter on continuous collision detection in my upcoming book. In practice of several games we found it works very well to allow a little bit of penetration. Especially in contact situation, allowing a tiny bit of penetration reduces the number of TOI events dramatically.
I definitely agree that being able to deal with some amount of overlap is important, since it _always_ happens in practice (especially when you're not a numerical computing genius). My system can handle penetration in that objects which are penetrating will be pushed out of each other, BUT only if collision constraints were generated before they were penetrating (i.e using distance queries, not penetration-depth). So far this works great, and lets us handle concave shapes -- the only problem being the usual super-thin + super-fast-rotating objects, in which case my predictive collision generation fails (since it's a linear approximation).
Is your system 2D or 3D? If 2D, how does stability compare to Box2D?
2D; I actually haven't been able to build Box2D for about a year (at some point Erin changed something which broke compilation under code::blocks and it's never worked for me since.. plus I haven't had the energy to fight with stupid c++ build crap) so I'm not sure about the recent state, but it's much better behaved than the split-impulse solver for articulated bodies.
The main thing is that you don't need to tweak anything, it just converges -- you can randomly position the objects and they'll snap together, without any "only move things by X amount per iteration" type hacking -- and it can handle large mass ratios. I don't know about stacking -- friction is still being figured out -- but for articulated characters it's great.
It's the Muller PBD-solver, applied to rigid bodies. I'm not an expert on numerical solvers, but I _think_ it's a non-linear solver, similar to "damped least-squares fit". At least, the third formula on this page looks very similar to the formula presented in the PBD solver:
http://en.wikipedia.org/wiki/Gauss-Newton_algorithm
One great thing I've noticed is that if the situation is impossible (i.e a chain of bodies with the two ends anchored too far from each other) it doesn't explode/oscillate like the impulse-based solvers tend to do, it just gets as close as it can to a solution.
by the way, concave-concave collision deserves its own topic. Bullet's penetration-based method seems to work pretty well in actual games, including for concave objects. For better quality I would recommend using convex decomposition. It is possible to use 3D concave triangle meshes in Bullet and ODE (like GIMPACT etc), but it convex decomposition gives better stability and contact information. Havok and Ageia PhysX also avoid concave triangle meshes in favor of convex decomposition.
[/quote]
My main gripe with convex decomposition is that it assumes static/rigid shapes, and we're trying to do very fluid, morphing vector shapes. We've even got some "skinned physics" working -- collision geometry verts can be bound (with different weights) to multiple bones, and constraints involving the geometry will correctly adjust the bones' states. Not sure if this is super-useful/needed though
The main issue we're running into is the software-engineering side -- it's really difficult for us not-great-coders to figure out a nice system which hides everything, so that the solver doesn't care whether things are skinned or rigid, and just treats everything generically as a big pile of DOF and constraints involving the DOF.
