Advanced Character Physics

Articulated Bodies

It is possible to connect multiple rigid bodies by hinges, pin joints, and so on. Simply let two rigid bodies share a particle, and they will be connected by a pin joint. Share two particles, and they are connected by a hinge. See Figure 7.

This approach makes it possible to construct a complete model of an articulated human body. For additional realism, various angular constraints will have to be implemented as well. There are different ways to accomplish this. A simple way is using stick constraints that are only enforced if the distance between two particles falls below some threshold (mathematically, we have a unilateral (inequality) distance constraint, |x2-x1|>100). As a direct result, the two particles will never come too close to each other. See Figure 8.

Particles can also be restricted to move, for example, in certain planes only. Once again, particles with positions not satisfying the above-mentioned constraints should be moved – deciding exactly how is slightly more complicated that with the stick constraints.

Actually, in Hitman corpses aren’t composed of rigid bodies modeled by tetrahedrons. They are simpler yet, as they consist of particles connected by stick constraints in effect forming stick figures. See Figure 9. The position and orientation for each limb (a vector and a matrix) are then derived for rendering purposes from the particle positions using various cross products and vector normalizations (making certain that knees and elbows bend naturally).

For collision with the environment, which consists of triangles, each stick is modeled as a capped cylinder. Somewhere in the collision system, a subroutine handles collisions between capped cylinders and triangles. When a collision is found, the penetration depth and points are extracted, and the collision is then handled for the offending stick in question exactly as described in the beginning of Section 5.

Naturally, a lot of additional tweaking was necessary to get the result just right.

Comments

This section contains various remarks that didn’t fit anywhere else.

Motion control
To influence the motion of a simulated object, one simply moves the particles correspondingly. If a person is hit at the shoulder, move the shoulder particle backwards over a distance proportional to the strength of the blow. The Verlet integrator will then automatically set the shoulder in motion.

This also makes it easy for the simulation to ‘inherit’ velocities from an underlying traditional animation system. Simply record the positions of the particles for two frames and then give them to the Verlet integrator, which then automatically continues the motion. Bombs can be implemented by pushing each particle in the system away from the explosion over a distance inversely proportional to the square distance between the particle and the bomb center.

It is possible to constrain a specific limb, say the hand, to a fixed position in space. In this way, one can implement inverse kinematics (IK): Inside the relaxation loop, keep setting the position of a specific particle (or several particles) to the position(s) wanted. Giving the particle infinite mass (invmass=0) helps making it immovable to the physics system. In Hitman, this strategy is used when dragging corpses; the hand (or neck or foot) of the corpse is constrained to follow the hand of the player.

Handling friction
Friction has not been taken care of yet. This means that unless we do something more, particles will slide along the floor as if it were made of ice. According to the Coulomb friction model, friction force depends on the size of the normal force between the objects in contact. To implement this, we measure the penetration depth d_p when a penetration has occurred (before projecting the penetration point out of the obstacle). After projecting the particle onto the surface, the tangential velocity v_t is then reduced by an amount proportional to d_p (the proportion factor being the friction constant). This is done by appropriately modifying x^*. See the Figure 10. Care should be taken that the tangential velocity does not reverse its direction – in this case one should simply be set it to zero since this indicates that the penetration point has seized to move tangentially. Other and better friction models than this could and should be implemented.

In Hitman, the collision system works by culling all triangles inside the bounding box of the object simulated (this is done using a octtree approach). For each (static, background) triangle, a structure for fast collision queries against capped cylinders is then constructed and cached. This strategy gave quite a speed boost.

To prevent objects that are moving really fast from passing through other obstacles (because of too large time steps), a simple test if performed. Imagine the line (or a capped cylinder of proper radius) beginning at the position of the object’s midpoint last frame and ending at the position of the object’s midpoint at the current frame. If this line hits anything, then the object position is set to the point of collision. Though this can theoretically give problems, in practice it works fine.

Another collision ‘cheat’ is used for dead bodies. If the unusual thing happens that a fast moving limb ends up being placed with the ends of the capped cylinder on each side of a wall, the cylinder is projected to the side of the wall where the cylinder is connected to the torso.

Miscellaneous
The number of relaxation iterations used in Hitman vary between 1 and 10 with the kind of object simulated. Although this is not enough to accurately solve the global system of constraints, it is sufficient to make motion seem natural. The nice thing about this scheme is that inaccuracies do not accumulate or persist visually in the system causing object drift or the like – in some sense the combination of projection and the Verlet scheme manages to distribute complex calculations over several frames (other schemes have to use further stabilization techniques, like Baumgarte stabilization). Fortunately, the inaccuracies are smallest or even nonexistent when there is little motion and greatest when there is heavy motion – this is nice since fast or complex motion somewhat masks small inaccuracies for the human eye.

A kind of soft bodies can also be implemented by using ‘soft’ constraints, i.e., constraints that are allowed to have only a certain percentage of the deviation ‘repaired’ each frame (i.e., if the rest length of a stick between two particles is 100 but the actual distance is 60, the relaxation code could first set the distance to 80 instead of 100, next frame 90, 95, 97.5 etc.).

As mentioned, we have purposefully refrained from using heavy mathematical notation in order to reach an audience with a broader background. This means that even though the methods presented are firmly based mathematically, their origins may appear somewhat vague or even magical.

For the mathematically inclined, however, what we are doing is actually a sort of time-stepping approach to solving differential inclusions (a variant of differential equations) using a simple sort of interior-point algorithm (see [Stewart] where a similar approach is discussed). When trying to satisfy the constraints, we are actually projecting the system state onto the manifold described by the constraints. This, in turn, is done by solving a system of linear equations. The linear equations or code to solve the constraints can be obtained by deriving the Jacobian of the constraint functions. In this article, relaxation has been discussed as an implicit way of solving the system. Although we haven’t touched the subject here, it is sometimes useful to change the relaxation coefficient or even to use over-relaxation (see [Press] for an explanation). Since relaxation solvers sometimes converge slowly, one might also choose to explicitly construct the equation system and use other methods to solve it (for example a sparse matrix conjugate gradient descent solver with preconditioning using the results from the previous frame (thereby utilizing coherence)).

Note that the Verlet integrator scheme exists in a number of variants, e.g., the Leapfrog integrator and the velocity Verlet integrator. Accuracy might be improved by using these.

Singularities (divisions by zero usually brought about by coinciding particles) can be handled by slightly dislocating particles at random.

As an optimization, bodies should time out when they have fallen to rest. To toy with the animation system for dead characters in Hitman: Codename 47, open the Hitman.ini file and add the two lines “enableconsole 1” and “consolecmd ip_debug 1” at the bottom. Pointing the cursor at an enemy and pressing shift+F9 will cause a small bomb to explode in his vicinity sending him flying. Press K to toggle free-cam mode (camera is controlled by cursor keys, shift, and ctrl).

Note that since all operations basically take place on the particle level, the algorithms should be very suitable for vector processing (Playstation 2 for example).

Conclusion

This paper has described how a physics system was implemented in Hitman. The underlying philosophy of combining iterative methods with a stable integrator has proven to be successful and useful for implementation in computer games. Most notably, the unified particle-based framework, which handles both collisions and contact, and the ability to trade off speed vs. accuracy without accumulating visually obvious errors are powerful features. Naturally, there are still many specifics that can be improved upon. In particular, the tetrahedron model for rigid bodies needs some work. This is in the works.

At IO Interactive, we have recently done some experiments with interactive water and gas simulation using the full Navier-Stokes equations. We are currently looking into applying techniques similar to the ones demonstrated in this paper in the hope to produce faster and more stable water simulation.

Acknowledgements

The author wishes to thank Jeroen Wagenaar for fruitful discussions and the entire crew at IO Interactive for cooperation and for producing such a great working environment.

References

[Baraff] Baraff, David, Dynamic Simulation of Non-Penetrating Rigid Bodies, Ph.D. thesis, Dept. of Computer Science, Cornell University, 1992. http://www.cs.cmu.edu/~baraff/papers/index.html

[Mirtich] Mirtich, Brian V., Impulse-base Dynamic Simulation of Rigid Body Systems, Ph.D. thesis, University of California at Berkeley, 1996. http://www.merl.com/people/mirtich/papers/thesis/thesis.html

[Press] Press, William H. et al, Numerical Recipes, Cambridge University Press, 1993. http://www.nr.com/nronline_switcher.html

[Stewart] Stewart, D. E., and J. C. Trinkle, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Friction”, International Journal of Numerical Methods in Engineering, to appear. http://www.cs.tamu.edu/faculty/trink/Papers/ijnmeStewTrink.ps

[Verlet] Verlet, L. "Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules", Phys. Rev., 159, 98-103 (1967).

[Witkin] Witkin, Andrew and David Baraff, "Physically Based Modeling: Principles and Practice", Siggraph ’97 course notes, 1997.
http://www.cs.cmu.edu/~baraff/sigcourse/index.html

________________________________________________________