Stacking - revisted

Now that I've finished putting up previous games and some videos, I think I should go into some more of the details of how I implemented my stacking with impulses. Stacking is one of those things that seems like it should just work, but with computers it doesn't. Therefore it's one of those things that almost every physics developer attempts to make their engine do. So how do you do it?

The main thing that makes all the difference is changing up the integration scheme as described by Fedkiw. The actually implementation I used is a slight alteration of what was done in jiglib. This process is as follows:
Integrate velocity and position (cache previous values)
Detect Collisions
Revert velocity to the beginning of the frame
Resolve Collisions
Revert position to the beginning of the frame
Integrate velocity
Resolve Contacts
Shock Step
Resolve Penetration
Integrate Position

The main difference between this implementation and the Fedkiw approach is the "ghost collision" that happens. When objects are tested for collision, they are tested at where they will be at the end of the frame, but then later moved back to the beginning of the frame. This can cause collision to happen a frame early. Either way, since I am performing discrete collision detection, there will be a visible error. The question is, which is more preferable, too much penetration or too much separation? This approach favors too much separation, which tends to be a harder thing for a user to catch. The one strange caveat I'm working on now is how to fit swept collisions into this. I plan to sweep between the old and the current position (since I will have just integrated) and figure out what the first time of collision is for all objects that are being swept. From there I will just move the object to that time and treat it the same as all other objects. This is not quite a correct answer, but I hope the results will be good enough that no one can tell.

So all you have to do is just swap the ordering of integration and resolution around and you get awesome and perfect stacks, right? Unfortunately, no. I mean, this is stacking, you can't get it that easily. There are some extra tricks, most of which are described in the Fedkiw paper, that you have to do.

So before I delve deeper into the extra things, I'd like to clarify some terminology. A collision is when two objects hit each other with a large separating velocity. A contact is when they have a small relative velocity. You can avoid using a threshold for this technique, however I chose to use some epsilon to denote a "collision" as being either a collision or a contact. Just a note, I will now use the term manifold to avoid confusion with the word collision as demonstrated by the previous sentance.

Now onto the tricks! First, when resolving the manifolds, multiple iterations are required to get good results. I personally iterate over collisions and contacts 10 times each. Now you may be asking yourself, "Why would you iterate over collisions?" The reason in the case of collisions is to propagate energy through the system. Imaging you're playing pool and there's a line of balls next to each other. Without iteration, the first ball hits the second and the frame ends with ball 1 not moving and ball 2 moving. Now if you iterate an extra time, the energy of ball 2 transfers into 3 and so on. Anywhere from 5 to 10 should get accurate enough results for any game. Now to answer the other half of the question, what about contacts? Well first, I must confess that there are more hidden details in iterating over the contacts. When iterating over the contacts, you need to actually use a negative coefficient of restitution. You should start your counter just next to -1 (but not at) and end at 0. This should be written so that it depends on the number of iterations you are doing. Now what does using a negative coefficient actually do? It slows down the objects. The reason we want to do this is so that no object is favored in contact resolution over another and so that no pair of objects is set to have 0 separating velocity initially. Instead, this allows blocks to slowly respond to contacts before their separating velocity is killed. The best example of this is a seesaw like problem. If there is a stack on one side and a block comes flying down on the other side, without the negative epsilons the seesaw won't even move. With one iteration only the top block in the stack will move. This is a harder one to understand than with collisions, but you can think of it as also being for the propagation of energy.

Now that I have unveiled those hidden facts, I should bring up the order in which these collisions should be resolved. To get a stable stack, it tends to be best to work from the ground up. To do this in an efficient manner, a contact graph is needed. With the graph you can topologically sort your collisions and get the appropriate order to resolve them in. The way I represent my contact graph is with a Hash Map for nodes, for in edges and for out edges. To sort the graph, you just need to work your way down the in edges until there is nothing below you. From there you add all of your out edges and work your way back up. If done correctly this will ensure that no object gets resolved before anything that is below it. Now I've been told that iterating over the stack in a consistent pattern can lead to slow drift over time. The solution to this would be to alternate between iterating forwards and backwards, but I have not done this so I can not attest to the results.

So, the last ambiguous step, the shock step. What is the shock step? Well it's just a step where you treat the bottom object as if it had infinite mass. This will make the stack suddenly stabilize by forcing the top objects to get out of the way of the bottom ones. This step tends to be crucial, as most stacks will not stand for very long without it. The problem with this is that it is an incredibly over-aggressive stabilization attempt. The issue is that this allows any object that would fall if it were on the top of the stack to not fall if it is in the middle. This can lead to towers that would normally fall being able to stand upright. You can get the "staircase" issue, which is when you have a tower of blocks going off to one side that will not fall. The shock step forces a quick local solution that causes some global behavior to be ignored. However, this tends not to be a huge issue for games because the "staircase" tends not to happen naturally.

Now the last thing that should be done to get good stacks is sleeping. Sleeping is a two-fold benefit, it helps stabilize the stacks and it speeds up the simulation. The are many different ways to sleep an object, but the approach I use is to put the object to sleep if it has a linear and angular velocity below some threshold for a set amount of time. Unfortunately, these values tend to be simulation dependent, so toy around with something until it looks good. Even if you have good stablitity in your stacks without sleeping, add it in for speed. There's no point in checking and object that is not moving for collision with another non-moving object. Now that we've put objects to sleep, we have to somehow deal with waking them up. Obviously, if an object is hit hard enough, it will get a velocity imparted into it that should bring it above its threshold for sleeping. So waking up an individual object is not a hard thing to do. But what if there was an object on top of a sleeping block? I'm sure you've seen games where you can knock out a bottom block and the top ones float, well that's exactly this situation. In order to correct it you need to somehow know if there is an object above any other object. If only we had some way to know this, oh wait, we have our contact graph. So now, if we wake up a sleeping object we can wake up anything that is above it, which will in turn wake up those above it.

So that's most of what you have to take care of to get good stacks with impulses. These stacks will not be as good as one with constraints, but constraints are a lot harder. However, constraints can also do a lot more. Once I get my own constraint system up I'll post something up on those too. Maybe I'll even have some power-point slides...