Modeling restitution

Your problem is likely that velocity is not propagating across the balls within a single timestep. So what happens is you get one collision over one timestep, then a bounce, and so on and so forth. This will quickly lead to many balls bouncing in many directions.

In real life velocity can propagate near instantaneously through all balls. You will need to do something like: build a graph of all balls in contact, and iterate many times over this graph while enforcing your constraints. Sequential impulses should be able to converge, so long as you build a system of all balls and let the system propagate velocities over the bodies through many iterations.

One trick that most physics engines have used for a while now, is to let rigid bodies penetrate slightly with a slop parameter. This parameter lets the narrow phase detect that two volumes intersect, without forcing the solver to move geometry out of an intersecting configuration. Often times when the configuration is no longer intersecting, internal graph data structure edges are broken, and the system is fragmented, unable to converge globally.

Hope this makes sense!

It actually is propagating immediately, since there are 8 velocity resolution steps currently. I think that's actually *why* it's not working, because if the velocity can propagate between steps, then the initial velocity used to calculate bias is no longer correct. I need a way to update bias inbetween steps, to account for propagated velocities, which should also force balls to bounce apart. If I reduce it to just one step, it starts working as expected, at least for a smaller number of balls (order starts to matter).

I do have that "slop" parameter, except it works the opposite way and creates contacts when objects are within a certain distance.

Hmm. In that case maybe you should try the shock propagation idea, where you lock a rigid body after it has been solved. This way you can ensure energy travels through the system in one direction. Otherwise sequential impulses might just spread around the velocity in an unrealistic way. It would be nice to see a graph or visualization of the propagation in any case.

How would you tell which way it should travel? I looked up some articles and they seem to suggest topological sort in the direction of gravity, so bottom objects resolve first, but in a general case we don't know where the impulses are coming from - for all we know it could be both ways.

I tried tweaking my solver to introduce restitution at different points, I can get it to propagate the impulses all the way through the chain, but then it goes back and tries to reduce the lambdas because it thinks they're too high (since balls are moving apart). Maybe there's some way to do it properly, by dynamically updating a lower limit on lambdas or something?

Would be cool to see a visualization of velocity propagation against different numbers of iterations on the first frame of collision with all spheres. Where has all the velocity gone with one iteration? With ten? With ten thousand?

The non-penetration constraints only say that the spheres can not inter-penetrate. It says nothing about where specifically all the energy in the system goes, and there can indeed be many "valid" solutions.

Another idea, just to get your cradle looking good: You can try separating the stand-still spheres ever so slightly. This way only one collision is solved in isolation at a time, and will prevent the solver from smearing your energy backwards through the system over many iterations. This might be sort of tricky with discrete collision, but with a continuous stepper should make for a really good looking cradle.

I don't have a way to visualize separate collision steps (rendering is completely detached from the physics engine atm), but I went through it in the debugger and it takes several iterations (like 4, depending on which order it decides to resolve everything in) to move everything nicely from the first two balls to the last two as expected, but then it starts going back and messing everything up - basically whenever it runs across a contact in which the balls are already separating (from restitution), it tries to adjust velocities back.

That gap trick worked, but now after the collision the balls aren't vertical anymore, so they start swinging back slowly, and after several swings it doesn't look so good anymore.

Yes this is expected. Sequential impulses will smear the velocities across the system in a manner dependent on your order of constraint solving. If you imagine there are four balls, each penetrating equally to their neighbor, and then think of how many different solutions could be valid here, there are infinite. So long as in the next step energy is conserved and the constraints are satisfied, this means the solver converged. The balls may teeter mostly to the left, mostly to the right, or almost all energy could be transferred to strictly an end ball.

This sort of thing reminds me of the "pool ball problem". Two pool balls are on a pool table touching tangentially. A third ball with some velocity strikes just between both balls. In a sequential solver one constraint must be satisfied before the other. The order of operations will result in two different solutions. Solving for a "real-life" solution can be difficult as well, since the system formed will be overdetermined with no direct solution.

Ah well, so most engines just ignore this and move on? Unless some system can figure out the propagation graph, but idk if that's possible to do for a generic complex scene.

Pool ball worked fine for me though, the two balls roll away at equal angles and the third ball rolls backwards slightly (or even forward, depending on friction).

Well maybe Dirk has an opinion, but I'm pretty sure modern physics engines are just modelling the constraints and calling it "good enough". Since typically in a scene with more than two rigid bodies human intuition isn't actually all that great at noticing situations without a real solution. Sequential impulses, being iterative, can find the minimum even in overdetermined or otherwise not directly solvable situations, making it "look nice" in most situations.

Even in real life a newton's cradle can fairly easily start behaving like your webpage simulation, and does not behave perfectly for long.

One other thing worth experimenting with, if you have the time, is to use soft contact constraints. Since in real life the balls are not perfectly rigid, maybe you can tune the cradle's soft contact settings and get closer to the behavior you like. Of course this isn't going to get you a general "perfect solution", but could be fun to try. I personally have never implemented a soft contact constraint, so I'm not sure exactly what that would look like.

3 hours ago, d07RiV said:

Ah well, so most engines just ignore this and move on?

Well not all of them but lots of single developer made ones do. Physics engines like Bullet, Newton and Nvidia Physics can all resolve this.

If I had to say what is wrong it would be the order that the code executes. Have you tried first resolving all the math for a given step then animating it?

2 hours ago, Scouting Ninja said:

Well not all of them but lots of single developer made ones do. Physics engines like Bullet, Newton and Nvidia Physics can all resolve this.

If I had to say what is wrong it would be the order that the code executes. Have you tried first resolving all the math for a given step then animating it?

If by "this" you meant magically move energy in the system in a realistic manner, then no they definitely can not. But if you meant, it's possible to tune the setup to make a Newton's cradle, then of course that's possible. But the behavior is not a natural emergence that can be easily replicated in other situations...

For the games I've worked on, we use physics engines on things that we need to look "physically plausible" (destruction debris, tossed objects, etc.), but not on things that need be precise (e.g. character movement). In other words, we treat game physics engines as decorative tools, and we don't base core game mechanics on unsupervised physical simulation.

For things we need to be precise controls over, we always use specialized logic outside of the physics engine.

If a Newton's cradle never interacts with anything, then I'd just have it animated (simulating it physically is a waste of processing power). If it can interact with other objects, then I'd still have it animated, but physicalize it when touched by other objects. Once it's physically interacting with other objects, I doubt physical precision would be a concern, unless the Newton's cradle is the absolute major focus of the game.

1 hour ago, Randy Gaul said:

If by "this" you meant magically move energy in the system in a realistic manner

I meant solving energy in a system in a Mathematical manner. You could solve it on paper as well. To be clear, I am talking about calculating the results of each impulse and then rendering it; not simulating all internal energies.

https://en.wikipedia.org/wiki/Newton's_cradle the wiki here explains it in a very simple manner and many people have emulated it.

2 hours ago, Randy Gaul said:

But the behavior is not a natural emergence that can be easily replicated in other situations...

If you had a known situation where you needed it you could find a solution, but emulating it all the time; yes that is impossible for now.

It's definitely possible to simulate with some methods. In my old school project 2D solver it worked perfectly, because it handled contacts one at a time, so it took multiple frames to propagate the impulse. But that solver has tons of other limitations.

I was specifically asking about more general case solvers that can handle complex scenes. If all contacts are resolved simultaneously (iteratively or not), then it seems there is no way to specify which particular solution you're looking for.

Oh well, thanks anyway.

So I asked Dirk specifically, and he says LCP formulation cannot solve Newton cradle, and this is specifically a well-known topic in literature. I believe he referred to work by Kauffman.

Basically affirming what d07RiV and myself were talking about earlier.

This is a good discussion of the problem:

http://www.cs.columbia.edu/cg/rosi/

In a nutshell there exist two collision/contact models I am aware of: simultaneous and sequential. For the Newton Craddle you need to propagate velocity sequentially in the right order to get the right behavior. It is probably something I would investigate for a pool game. For everything else simultaneous contact is really a good choice from my experience. Note the sequential impulses are really a simultaneous model since it solves the LCP formulation of the problem. It does not sequentially propagate velocity as the name might (incorrectly) suggest.

I'm a little lost in the terminology here. Which model is sequential and which is simulatenous? Does simulatenous imply that you try to solve all contacts at the same time, or is it the same as iterating through them multiple times?

I also found an old discussion here https://pybullet.org/Bullet/phpBB3/viewtopic.php?p=&f=4&t=1584

Jan Bender claims that the method in his paper handles newton cradle correctly, but the description of how it handles collisions seems identical to the classic constraint solver.