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...

Games

Well now that you've seen some of my personal stuff, how about my team stuff? Well first I had a freshman text based rogue game, but I don't feel like digging it up and making a video of it at the moment. Instead, I'll just start with my sophomore game.



My sophomore game, Barrel Bros, was my first attempt at making a physics engine. I started out trying to be "fancy" by doing what was more or less a continuous engine, although I had no idea that's what it was at the time. At the end of the first semester, I had realized how bad of an idea this was. I'm not saying that continuous engines are bad, just a lot more complicated than they're worth most of the time. So over the break I converted this to a discrete engine that worked with impulses. Even though I had started down a better path at this point, I still had a very simplistic engine. Most notably, I had no rotation. So all of the barrel "rolling" was faked with game logic. The one cool thing that I had in this game though was "curves" for the barrels to roll on. I say "curves" because they were really just line segments being approximated as curves, but they achieved a good enough affect.

At the end of the year I decided to start work on my 3D engine for Junior year. This time though, I had a good idea of where to start and how to do things. I even decided to tackle the challenge of rotation...which isn't that bad. Here's a small video of our Alpha build:



Now this is me once again using my trial version of fraps to record this. Once we get to the later stages I'm sure we'll get a more official video, until then this will have to do.

So the first task I took on was collision detection. So I first set up the basics, sphere sphere. I then set up impulses to get those resolving correctly without friction. From there I decided to be extra adventurous and implement a new collision detection scheme I had heard about, MPR. MPR, or Minkowski Portal Refinement, is a collision detection algorithm that works on arbitrary convex polygons. It took me most of summer to get this working, but the results were quite nice. Unfortunately, MPR has some issues with long thin objects, and I also wanted better speed. So about 1 month ago I replaced most cases with specialized SAT tests. So at the moment MPR is not being used anywhere...But after that I had decided to do stacking which took a large amount of time.

Skipping forward to now, the main tasks I have left for this game in physics is to get raycasting to work efficiently for picking of objects and to write some swept collision tests since our player moves so fast. At the same time I'm working on constraints for my Physics class project. Hopefully I'll be able to get that running in the near future so I can get some videos of that up.

Soft Bodies

Soft Body dropping on ground:


Soft Body being poked on the ground:


I've decided not to fight blogspot for now and just go youtube...
Also a note I forgot to mention on the last post, to keep the size of the video down I'm recording at 30 fps. The actual simulation runs just fine at 60...

This is a video of my pressure model soft body.
First of all, this is all done with debug drawing. The black points are the point masses, the white lines are the springs, the red triangles are the faces, and the black lines are the normals of the faces.
Secondly, this is using Euler integration. I'm sure the results will look a lot better with Verlet or some higher order integrator. Another interesting thing I could do at some point is to construct the sphere using a geosphere instead of the standard stacks and slices approach. For all who do not know what geospheres are, they are spheres made of equilateral triangles. Doing this will make the simulation work a bit better because the lengths of the springs will be more standardized. The same issue will still crop up as seen on the video with the top of the sphere, since many points have to connect to one point. This causes extra osculation that is hard to get rid of with just an Euler integrator.

So how does it work? Well a soft body is very close to a cloth. Well how's a cloth made? A cloth is basically a set of point masses connected by springs. That's it, you just have to make sure that you have all the necessary springs (like next next neighbor) to make a cloth function properly. Now a soft body is just a wrapped cloth, without the next next neighbors, that you put a wind force inside of. More details are in these papers on the actual implementation:
http://www.ep.liu.se/ecp/010/007/ecp01007.pdf
http://panoramix.ift.uni.wroc.pl/~maq/soft2d/howtosoftbody.pdf

But basically you just apply forces to the points on each face while enforcing the ideal gas law pv = nrt. The exact specifics, as I've said before, I'll not go into details on because the paper does a better job than I will. Now how do I do collision with this thing? Well first, I just approximate the volume with the AABB of the soft body, which is used for the pressure model. I then use that as an early out to test with other objects AABB's. If the two AABB's intersect, then I just do point vs. object and resolve the impulse. At the moment I have the intersection limited to just OBB's, but I will add more at a later date.

So in conclusion for now, soft bodies are a very cool thing to have and something I would highly recommend implementing. The only issue is that it's hard to get any good use out of them or make them a key feature in a game. Also, if you use Euler, stability can be a bit of a problem as springs like to explode if you set values to high or to low.

Edit: was just bored so I re-added the ability to poke soft bodies, but this time I actually ray cast with each face and apply a force on those points...video link added to the top.

Stacking

So I decided to upload a small demo video of my stacking. Due to using the trial version of fraps, this was limited to 30 seconds.




This was a stack of a 2 x 20 x 2 tower of blocks. There are a number of things I'd like to point out in the video so that no one gets confused, most of which are related to debug drawing. The most notable one, the color change of the blocks represent them being put to sleep. Shortly after I turned wire-frame on, I turned of the ability for objects to sleep so that other debug info could be shown better. The small points and lines being drawn represent the collision point and normal. Combined with the ability to pause and step through the simulation, which I did not show here, these debug drawing features make it much easier to observe a whole scene and determine if anything is amiss.

Just a small note on how I am doing the physics in this simulation. First, collision detection is done using Separating Axis Theorem. Then collision response is done using impulses with a modified version of the resolution scheme mentioned in the paper "Non-convex Rigid Bodies with Stacking" which switches up the order of integration and resolution then follows up with a shock-step. The order to resolve and sleep objects is done with the aid of a contact graph which topologically sorts the collisions along the y-axis. In the near future I will put up a small videoof a pressure model soft body.

First Blog: Who am I?

Hello all who may read this, this is a blog to introduce who I am and what I'm passionate about. First of all, I'm currently a Senior at DigiPen Institute of Technology. Although I'm officially a Senior, this is my third year at DigiPen . This means that I'm on my third game, my Junior game.

For the past two years, I've been doing physics on my game teams. Sophomore year I had a simple engine with 2D spheres colliding with cubic bezier curves approximated as line segments. This year, I've moved up in the world of game physics and a dimension (3D now). I enjoy game physics both because of the challenge it provides and because of how fun it is to play around with. Hopefully I'll be able to get a demo or some videos soon so you can see what I'm working on, along with my past games.