anyone managed to simulate a newton's cradle properly, where all the balls are in contact simultaneously? If there is a slight gap between the objects I can get it simulating properly, but if all the balls are in the LCP solver at the same time, I get the wrong result.
This is what I would like to see:
...
This is the result I'm getting:
...
I have a pretty standard Sequential Impulse style LCP solver.
We have a method of handling restitution that is similar to what has been suggested by Erin Catto in his GDC presentations. That's where you modify the target velocity ( velocity bias ) of your constraint to be the desired post-collision velocity ( -restitution*relativeVelocity ). This trick only works in the case of 2 bodies, which is a pretty boring newton's cradle
Possion's hypothesis treats collisions in two phases. A compression phase and a restitution phase. Our LCP solvers appear to only be handling the compression phase. The compression phase is all that is required to satisfy the non-penetration constraint. So that makes sense. But then we just ignore the impluse generated during restitution. It's like having a restitution of 0 all the time.
By altering the velocity bias, you are employing newton law of restitution ( why is Newton's rule a law and Possion's only a hypothesis? ). But that doesn't affect new velocities transfered around inside the LCP solver. Thus you get incorrect newton's cradle behavior.
I messed around a bit trying to keep track of seperate compression and restitution impulses, but to no avail. Any ideas or solutions out there? Maybe I should try updating the velocity bias in the solver as I iterate over the constraints.
IMHO, the spheres have a gap, even if they are touching. That is because reality uses the penalty method (e.g. Hertz contact for spheres). So there has to be some movement before force is built up.
The rigid body model with Lagrangian constraints doesn't require that small movement to react. So having the spheres initially touching is not representative of real system.
On the other hand, if it works with a gap, why worry?
Well, I tought about this a while ago as well, since what you describe is the typicall behavior when using simultaneous contacts. What happens is that you have contact points with zero relative velocity in my opinion. So when the outer ball hits the first ball the solver immadiately starts to propagate the velocity and he doesn't do this as expected. One idea I had was to ignore contact points with a relative velocity of zero. This should give you basically the same effect as with the gap.
I never implemented this though. I just thought about it when I read a huge thread about this topic on GameDev.net. Baraff discusses this also in one of his articles...
If you build the LCP based on Newton's restitution law then you get an unphysical result when you apply it to more than 2 bodies in simultaneous collision because the law is an empirical result of a collision between 2 bodies only. There are collision laws for more than 2 bodies, apparently, but I guess they're not likely to be useful.
[Sorry, this is really long: long story short, don't hit your head against this stuff too much, there's no perfect solution]
If you have something that works perfectly for Newton's cradle, it will give a nonsense result for an impulse applied to a "frame" of mass 1 exactly enclosing a row of several spheres all of mass 1 and colliding elastically with each other, since you get an infinite loop - see p.155 in Kenny Erleben's Physics Based Animation for a picture. You can also think of that example as Newton's cradle in a periodic world. You know all the things should just move together to the right at a lower speed, but you also know that on a non-periodic only the last ball should pop out. What gives? [more on that later] To my knowledge, there is no perfect way to resolve both of these situations in the same framework without starting to code special cases.
Now to go OT: what Erin said reminds me of an interesting thought experiment - suppose you put a rubber band around the middle two (of four) balls in a Newton's cradle, arranged somehow so that the middle two balls were bound tightly but the contact was still metal on metal, assumed to be perfectly elastic. Let's say that it's a massless theoretical spring that can only pull, connecting the two, if you'd rather avoid practical difficulties.
In the limit of an infinitely strong spring (or at least as strong as the molecular network of connections holding the metal itself together), we can certainly consider the two middle balls to be a single rigid body of twice the weight, right? Which means that the physical result will be that the incoming ball gets reflected back a bit instead of coming to a complete stop (I think with -1/3 the original velocity, if I remember correctly).
So let's play with that spring constant. In the limit that it goes to zero, we must be back to the original unadorned Newton's cradle, since there is no force on either ball. In that case the incoming ball is exactly stopped upon collision. For finite spring constants, the outgoing velocity of the incoming ball depends in some (possibly complicated) way on the spring constant.
The obvious next question is, what the heck does a spring constant that only pulls the middle two balls together have to do with the collision with the first particle? You would think that once the first (incoming) ball transferred its momentum to the second, the first ball would be completely and utterly removed from the situation, and thus would always have exactly zero velocity coming out. It's not as if the second ball will push back any harder if it's connected by a spring to the third ball - that spring can only pull the second ball further to the right, never in the opposite direction.
In my opinion, the resolution here is to realize that the spring between the middle balls serves to pull them a little bit closer into their contact zones, slightly further up the potential energy scale than they would be if separated; this means that while the first ball is still colliding with the second one, the second one is also colliding, but a bit faster, with the third, so it is dumping off its momentum a little quicker than it would be if it wasn't connected. That means that it takes more momentum from the first particle than it would have otherwise - this relates a lot to what Erin mentioned about movement being necessary on a microscopic scale, even though the balls just sit there macroscopically. Essentially, the pulling force of the spring changes the collision speed of the middle two balls, and the faster this transfer is compared to the interaction between the first and second, the closer they are to being considered a single unit instead of two separate ones.
In real life I suspect that even if you did set up a situation like this, unless you had an extremely strong spring the balls would behave almost exactly as if independent; I think the amount of normal force you need to significantly impact the momentum transfer speed is quite a bit higher than a simple rubber band would provide. I could be wrong, though, I've never tried it and it ultimately is an experimental problem.
It's worth thinking about what it would take for a solver to accurately handly this type of physics. It's not as simple as letting the restitution depend on the normal force, because we don't want to lose energy by having any inelasticity in our collisions. From a macroscopic perspective, the problem is distinctly non-local - the first collision's resolution depends critically on the details of the second one, and so on down the line. This suggests that maybe a global solver is necessary, though even there, I'm not sure what to make it solve...the problem is actually underspecified from the macroscopic variables we like to use, so we would at least need another variable relating to the steepness of the microscopic collision envelope's potential energy curve (we might even need to specify the whole curve). There is probably a way to formulate this so that an iterative approach could be used, but I haven't thought too much about it.
Eh, what the hell, this is so long anyways, let's go back to the balls-wrapped-by-frame example at the top - this is resolved microscopically by the realization that even though the collision train keeps going forever, in reality, at any one point in time, one of the objects, either one of the balls or the frame, is moving with the exact velocity that you imparted in the initial impulse, even if it only moves a fraction of a millimeter before the next collision (keep in mind Erin's point that there is always some space, however tiny, between balls). Thus the entire thing will move just fine, and the problem is not with the assumption of perfect elasticity; rather, it is with the presumption that we can divorce the collision period from the dynamics period. Sometimes they overlap completely, critically, and perpetually.
To see why it is "incorrect" to attempt to end the collision phase in this example, look at the energy: this is perhaps the best example of the fact that what is kinetic energy from the microscopic point of view becomes "lost" energy (and thus the collisions appear inelastic) when you try to average motion over many particles. In the microscopic view, one particle always has velocity v, leading the KE to be .5v^2; in the macroscopic, all the particles appear to have velocity v/N, where N is the number of balls plus one (for the frame), so the KE is .5*N*(v/N)^2 = .5 v^2 / N. Any way you cut it, if you force the collision phase to end, you've cut the energy in the system by a factor of N, despite the fact that every collision is perfectly elastic.
You can take this further, and start thinking about putting the "frame" into a Newton's cradle, drawing connections/differences between that and the spring example...I'll leave that to you, I've already gone on way too long. It's interesting stuff, though, worth thinking about to really understand the problems here.
There are some other thought experiments that show that macroscopic outcome of a collision often depends so critically on microcollisions that it's all but impossible to find the "correct" outcome without actually going through the microscopic simulation (one example: heavy ball incoming from the left, hitting a light ball at rest, restitution 1, which then bounces off a wall immediately to its right with restitution 1 - the outgoing velocity of the small ball depends on the exact mass ratio and distance to the wall, and is almost impossible to determine without simulating every one of the thousands of back and forth collisions between the two, though the large ball is, for all intents and purposes, almost exactly reflected).
I'm not entirely convinced that a solver cannot be designed to deal with all these things in a reasonable manner, but it would have to be incredibly subtle, and though I've considered some possibilities, I don't have anything that works yet...if anyone has ideas, I'd love to hear them.
IMHO, the spheres have a gap, even if they are touching. That is because reality uses the penalty method (e.g. Hertz contact for spheres). So there has to be some movement before force is built up.
Agreed. This happens at the speed of sound through the material, though, which is a bit finer resolution that 30 fps.
On the other hand, if it works with a gap, why worry?
That only applies to the first series of impacts. I would need to have some way of artificially maintaining a gap so bodies are only added to the solver after they penetrate ( similar to Dirks method ), which I don't want to do. I would actually like to put contacts into the LCP solver before they even become contacts. That helps the bullet-through-paper problem. Kind of a speculative contact.
I'm worried specifically this week because a billards mini-game isn't working properly. Specifically the initial break, which can be handled by putting a gap in there. So really not much of a problem, since 99% of the rest of the game involves 2 body situations.
I think a solution lies in seperately modeling compression and restitution phases in teh solver. And using Poissons hypothesis as my restitution law. I have a feeling it's going to involve a silly # of iterations, so maybe it wont be feasible in the end. Or maybe it's a matter of tracking compression vs restitution properly.
I just thought about it when I read a huge thread about this topic on GameDev.net
Good grief, insanity abounds.
Looks like the shock-step approach works for JigLib.
There is no gap between the balls. If you want to know how this works, take a look at my paper "Constraint-based collision and contact handling using impulses".
Jan - I saw the videos (very nice work, btw!) and took a look through your paper, and I had a couple questions. Based on a quick reading, it seems that one distinction between your method and SI (at least as far as solving Newton's cradle goes) is that in SI one iterates over the contacts several times, only partially solving the velocity constraints at each step, whereas in your scheme you completely solve each velocity constraint during each pass, iterating until no unsolved constraints remain. Thus SI causes the impulse to spread itself over all the balls, but your scheme keeps the impulse transmission crisp and clean so it can pop the last ball out the other side without any artifacts. Is that correct, or am I misreading?
Is your method guaranteed to terminate, and is it possible to force a bound on the time taken in the solver loop? From my reading, I worry that in the face of cyclical collisions (as would happen if you shot to break in pool but forgot to remove the rack from the balls first) you might end up with an infinite loop, whereas SI's "spreading" of impulse is actually the desired behavior there.
I imagine what would be ideal is to ease from one behavior to the other as the iteration count goes up, thus getting the best of both worlds.
Jan - I saw the videos (very nice work, btw!) and took a look through your paper, and I had a couple questions. Based on a quick reading, it seems that one distinction between your method and SI (at least as far as solving Newton's cradle goes) is that in SI one iterates over the contacts several times, only partially solving the velocity constraints at each step, whereas in your scheme you completely solve each velocity constraint during each pass, iterating until no unsolved constraints remain. Thus SI causes the impulse to spread itself over all the balls, but your scheme keeps the impulse transmission crisp and clean so it can pop the last ball out the other side without any artifacts. Is that correct, or am I misreading?
This is correct.
Is your method guaranteed to terminate, and is it possible to force a bound on the time taken in the solver loop? From my reading, I worry that in the face of cyclical collisions (as would happen if you shot to break in pool but forgot to remove the rack from the balls first) you might end up with an infinite loop, whereas SI's "spreading" of impulse is actually the desired behavior there.
The example would end with the rack and the balls moving away. The only problem you could get is if the rack is fixed and the balls are moving. This would terminate with all balls loosing their velocity. I don't have yet a mathmatical proof but I have never had a model where the simualtion didn't terminate.
