Rigid Body Dynamics

March 14, 2006

System summary.

The animation is finished, all of the rag doll scenes are integrated, and they look pretty cool. I wish I could have run some with more guys at once, but oh well.

So here's a final rundown of the current system.

It is implemented entirely in MEL - the few functions we had working in the C++ API ended up being trivial to rewrite, and Maya was having issues finding the MLL's half of the time anyway. So currently all of the actual code running the rag doll simulation is mine, but that statement is misleading, because I really just ported large parts of it to MEL, copying Eric and Jedrik's code over line by line.

The characters in the simulation are implemented as spheres with a distance constraint hierarchy. The spheres have their movement simulated independently, with all collisions resolved, and then the distance to parent constraints are applied. This is currently done only once per frame, but even when it is incorrect it is hidden by the IK handles and is generally fixed by the next frame.

A simplified character model is used, with fewer joints and IK handles at the point where each sphere is simulated. The IK handles are parented to the spheres and follow them, causing the model to do so as well.

The movement and constraints are integrated using Verlet integration, as detailed earlier. This allows easier computation of the effects of constraints on velocity and momentum.

Collision responses are handled by Newtonian impulse equations.

Finally, as the simulation runs the positions of the characters are keyframed and baked. So the simulation is run once and the resulting animation is used in other animations.

In order to make the scenes easier to set up, bomb objects can be placed around the characters, causing an explosive force relative in magnitude and direction to the position of the character relative to the explosion center.

The animation looks great ;-)

-Mike

March 5, 2006

Maya Cleanup.

The baked animation works (it sends a guy in a complete flip before he crashes into the ground head first), but I had to clean up some of the keyframes. Occasionally, especially with the head (which has fewer joints between the IK handle and its parent) there will be popping in the animation solution. So I ran through and deleted the popping keyframes.

-Mike

March 4, 2006

Maya scene setup.

I've stripped down the MEL implementation as much as I can. It runs through fewer constraint iterations at a larger timestep than before, so while it still isn't close to real time it is fast enough to run tests with several characters at once. We're going to set up three or so scenes of characters being hit by rocks, bake in the simulation, and Cara will add those to the scenes of the big fights.

To facilitate this, I've added a knowledge of "bombs" to the simulator. You can place a sphere called "bomb1" or "bomb2" etc in the scene and based on its explosiveness and radius all the characters in its blast will be affected. I've got one scene baked in with this system, and Jedrik and Eric are working on two more.

There were a lot of problems with the IK handles bending the wrong way as the spheres moved around the body. I solved these by using locators for the IK pivot position vectors, and parenting the locators to the body. So the character will now bend correctly relative to himself 99% of the time.

March 3, 2006

Jedrik and I have most of the maya integration working. The videos are posted as number 5 and 6 on the main procedural page. I rewrote large sections of the code in MEL script, which means it runs really slow. How much slower? We were running 60fps for one figure in the OpenGL version. The MEL/Maya version runs at about 1 frame/5 seconds with one character. Luckily, the way the scenes are laid out we shouldn't have too many guys under the control of this sytem at once, and we can leave them to calculate for a while in batch.

Currently the only component that is acting up is the sphere-sphere reaction. So in the videos, the character's arm can pass through his body.

To make the system work, Cara rigged up a simplified version of the paper character. He has minimal arm/leg joints, and IK handles at each of his extremities. The IK handles are parented to spheres at each extremity - one each for hand, leg, center of mass, chest, and head. The spheres are what we run the simulation on. When the sphere gets updated, it moves the IK handle, and moves the character. As you can see in the preliminary tests, this seems to work quite well, and the only thing we have left from a technical side is fixing the integration of the sphere collision module. Although it is not seen the video, the character does react correctly to the ground plane.

We will meet again tonight to fix this problem and spend the weekend setting up and testing the actual scenes using the rag doll system.

-Mike

March 2, 2006

Met to work on integrating the code with Maya. Jedrik has been working on this. From what he's found we'll have to rewrite a lot of the code to get it to fit into Maya. I guess we should have learned the API before we wrote the code instead of assuming that we could go back and forth.

The other application API's I have used let you call them from your own program, instead of compiling individual DLLs that the program then gives you access to. Oh well.

Since Jedrik's the only one who knows the API, and Eric was already helping him, I started work on a plan B - having the physics code run in batch and output a mel script that applied all of its changes.

-Mike

Feb 28, 2006

Here are the videos I was talking about.

Pendulum

Linked Fall

The color changes indicate when two spheres are touching.

-Mike

Feb 20, 2006

Code passes tests 1-6. I should have a video up later today of a parent object with five children being bounced around. I'm starting work on giving joints a limit on their angles.

Rigid Body Dynamics is currently several days behind the Timeline, mostly due to having to rewrite the entire module three times. It is almost to where it can be used, though. We will be meeting tonight to integrate more and set out our group timeline for this week.

-Mike Ford

Feb 19, 2006

Salvation.. maybe.

I found an article in gamasutra (link requires free registration):

Physics System from Hitman

This system is very different from any of the others I found in my research, but seems to solve the articulation constraint problems in a very easy numerical way.

Integration Problem

The integration is solved using an algorithm called Verlet integration. Instead of storing a velocity seperately, the instantaneous velocity is calculated from the last position. This is plugged into the standard formula for integrating position from acceleration and velocity. The end result is that to apply constraints, you need only move the object into the correct position, and all other factors will adjust themselves. This passed the pendulum test on the first check! Moreover, while it is not as accurate as RK4, it does not accumulate error, so over time most issues sort themselves out, with only minor glitches in between that in a large scene are rarely noticed.

Multiple Constraint Problem

The article also presents a very numerical solution to the problem of multiple constraints (such as when a child object hits the floor). The algorithm solves each constraint individually, updating the object's position on each constraint. It then iterates through all the constraints again, constantly updating, until either all constraints are met, or a limit is reached (current the code uses 10 as an upper limit). While this is not a "correct" solution, it converges to a correct solution generally very quickly, and will at least converge within a few frames.

Implementing these two methods, the code current passes tests 1-3. There is an issue in the collision between two spheres that I am still investigating.

I had to modify a lot of the collision response code, as it depends on updating the velocity directly. By hiding the implementation of the velocity through a few more methods, I'm still using most of eric's original algorithm.

I have had, however, to disable all orientation calculations. I've decided it will be easier to try to re-integrate them once all linear calculations and constraints are working.

-Mike Ford

Feb 18, 2006

There seem to be issues with the way that Advanced Animation with Direct X says to handle articulated figures. The spring impulse does not account for rotation around the joint. So the child objects follow the parent statically. If you have two links connected together, with the parent static and the child under the influence of gravity, the child does not form a pendulum like it should to appear like a realistic joint, it sits statically in the air joined rigidly to its joint point.

So I tried implementing the character as being connected by actual springs, with constants and a rest length. This showed quite clearly the limitations of our integration. Advanced Animation presented Euler Integration without actually describing it, and since it is simpler to implement, our current system uses it. When springs are introduced to the equation, objects are very quickly sent flying off of the screen.

I see a few options to fix this:

• Implement a more correct integrator (this will require a refactoring of some of the code, mostly in how forces are added to an object).
• Figure out if there was something I missed in Advanced.
• Find another simple cheat method.
• Implement correct constraints as discussed in the research listed earlier, involving writing a full differential equation solver. I really don't want to do this.

For now I am investigating other options. In the mean time, I have come up with a series of tests that a current implementation must pass to be able to run our characters. In order of complexity:

1. Pendulum test - parent is fixed, single child is under gravitation influence and should form a pendulum oscillation at a nominally fixed distance.
2. Follow test - parent is given a velocity. Single child should follow it with noticeable joint action (ie, child should still react to gravity and rotate around the joint).
3. Drop onto floor - linked parent and child fall to the floor such that they do not hit at the same time. Neither should penetrate the floor, and the child should stay at the correct distance the whole time. This tests the application of multiple constraints at once.
4. Perpetual motion machine - Parent with one child on either side on the same axis. Children should bouncing off of each other and back while swinging on their links like those cheap "perpetual motion" machines with the little clicky balls.
5. Multiple children - Parent with four children going through all the above tests and showing correct bounce both amoung the children and between the children and the floor.
6. Joint restriction - Adding limitations to the movement of the children - instead of swinging all around the parent, they will be restricted to a certain join angle range.
7. Child orientation - Children will stay in the correct orientation in relation to the parent

At point 6, we can have a working simulation with the tweaking. The difference is whether the location of the children controls skeleton joint locations in maya or whether they control the actual mesh that they bound. Our originial design calls for the latter, as we are unsure what will happen with numerical innaccuracies between our simulation and the join link requirements in maya.

-Mike Ford

Feb 17, 2006

Articulated figures.

The general structure of our approach is based off an approach from Advanced Animation with Direct X. Characters are replaced by a simplified structure (we use a lot of spheres). The position and linkage information between the spheres is pulled out of Maya using the API (hopefully - Jedrik is working on it, if not we will be parsing text files) and then fed into our independent simulator. The simulator will run its calculations (currently it works for bodies without articulation constraints) and then push the new positions of the spheres back to Maya for every frame.

The join system will be represented as a tree structure with each sphere a node. The spheres will know where they link to their parent, and that's about it. Unlike a more correct simulation, children exhert no forces on their parent - so someone cannot, for instance, be dragged along by their arm. After all forces are calculated as though the spheres were all unlinked, children are translated by an instantaneous impulse back to the position of their linkage to the parent,and the angular moment induced by this change is added into the object's state. This should cause arms to follow a character throw into the air, which is the goal of our use of rigid body dynamics in this animation.

If this does not work acceptably, the infrastructure will still be in place to replace these fake spring with actual spring linkages, and tweak the constants on them.

Currently I have written the code for this, but I am waiting on an update on some refactoring that Eric is doing of the general collision detection and response module to integrate it and begin testing.

Code is here

• Friday 18 - Integrate articulated figures code and debug it. Get it "working" for a generic figure.
• Saturday-Sunday 18-19 - Work with Cara to create the "stay-puff marshmallow man" version of the character. Integrate Jedrik's Maya API code or some other workaround to get positions and orientations in and out of Maya.
• Beginning of next week - Tweak constants and methods for figure movement using characters in the scene until we have something that looks good.
• After that - Help with whatever is needed on the other shots.

-Mike Ford

Feb 16, 2006

Well, that was fun.

I coded up an acceleration structure, but hadn't tested it yet when I realized that we hadn't run time trials on our collision detection to see if we actually *needed* acceleration. Theoretically it should be better (all the articles noted a need for some sort of structure), but for our purposes was it required?

I got Eric to run some timing tests with several hundred objects colliding at once. Even at 600 objects (which should be roughly 30 characters, probably more than we'll have actually under the control of the rigid body dynamics) it ran at several frames per second.

The pathfinding for flocking behavior was significantly slower than this, but still usuable even with hundreds of characters. Both of these tests were run using the naive O(n^2) appproach to the problem, where every character checks every other character. They told me that it was fast enough for their purposes, and that we shouldn't waste man hours on the acceleration structure any more. So rather than debug it, I'm moving on to handling articulated figures.

The moral of the story? Modern computers are really freaking fast, and our procedural work in maya doesn't have to run in real time.

Feb 11, 2006

Found a much better acceleration algorithm.

Sort all object axis-aligned bounding boxes separately by x, y, and z minimums.

Go through the list, opening boxes at min and closing at max.

Return all objects for which all three overlap.

This run in nlog(n) with a quicksort algorithm. However, because object positions change only a little between frames, the update can be done with an insertion sort. This allows for a close to best case linear time algorithm.

Feb 7, 2006

Started coding up the acceleration framework for the design. For ease of implementation, we're going to use a grid with a user-defined spacing that we'll have to tweak. Each object will be binned into which boxes of the grid its bounding box intersects. The accelerator will have an accessor to get at the different RigidBody objects contained in it, and a GetClosest(int bodyNumber) method which will return a list of the objects sharing a box with the object at index bodyNumber.

The pseudocode for our rag doll physics will run as follows. It is based off a combination of scholarly research and examplse of working game implementations:

For each object
Update position and velocity based on current forces and velocity
For each object
Get nearest objects
Detect intersections.
calculate new velocity based on conservation of momentum at collision
check constraints (if two connected boxes have drifted apart, translate the child so that it is touching)


There are a few potential issues with this approach. The first is that collisions are only detected in regular intervals using Euler integration. This is a relatively weak method of integration. However, it is much more straightforward to implement than 4th-order Runge-Kutta, and was used by many of the working examples I found online and in the game industry. We will implement it this way and be prepared to switch to Runge-Kutta if the results are unsatisfactory.

Similarly, our method of collision detection is rather weak, processing again only at specific intervals. It is possible that having multiple objects collide in between our steps at high velocities would cause objects to pass through each other. There are solutions to this, but again I am not sure they are necessary for the level of simulation and visual effect we are going for. The best solution I have found goes as follows: when you find the first collision, back up the simulation to where the objects actually colliding, calculate their new velocities, and continue the simulation until this next collision. In this case you end up calculating the whole thing multiple times for each time step, as you must constantly evaluate the actual time of all collisions, then back up to the time of the first one and start the simulation over again. If only a few collisions occur at any given frame, this would not be so bad, although more complicated to program. If you are trying to simulate collisions between many objects at once, this becomes much more complicated. Again, while non-trivial this can be easily grafted into the existing algorithm should we find we need a finer level of simulation to get the effects we desire.

We are also only detecting collisions on a bounding box or sphere level, rather than an arbitrary mesh level.

Finally, even if we do not implement a correct and complete constraint system (although I have read several methods of doing so), we could considering a real spring system to connect our articulated figures rather than the simple forward kinetics shown above. In the system we currently plan on using (gleaned from a game design book), a force on a figure's hand will not cause the rest of the body to feel anything. Since the use of this system will be mostly for animating the death sequences and flight of death stick bodies, where the overall movement of the figure will be mostly caused by the center of mass "root" of the figure, again I am not sure that this will be an issue, and we will implement it only as necessary.

Works in progress

Current Accelerator Header

Current Rigid Body Header

Jan 30, 2006

Met with Eric today to work out what we'd learned from our research. We've got a pretty clear idea of the project. We're going to use conservation of momentum to handle collisions, and springs of some sort to handle our articulated bodies. If we have time after we get this working, we may attempt some sort of real constraint system, but we don't expect to have time for it.

Jan. 24, 2006

• Baraff 89
• Baraff 91
• Baraff 92
• Hahn 88
• Kokkevis 04
• Moore 88
• Zhao 04

I also found the following web links.

• Chris Hecker's Rigid body Dynamics Information
• Physically Based Modeling: Principles and Pratice. The lecture notes are very helpful