Armed Mine: Animation-driven physics in Doom 3

June 14, 2011 Physics

Player and non-player characters in games often play animations from a fixed set of pre-animated sequences, switching between animations when the internal state changes or a previous animation finishes. However, it requires a little more thought and technology when characters actually need to interact with other objects and characters in a complex dynamic and physically simulated world. Armed Mine is the name of a simulated creature for Doom 3 that achieves exactly that, using a custom extension to its physics engine.

Animation-driven physics

Suppose a game character needs react to the direct impact of a bullet on its body. Trying to achieve this accurately for all possible impact positions under all possible conditions using only an animation system would require an enormous set of available animations to choose from. Only then, impacts would fit nicely with the any previous pose and activity.

Alternatively, the animation system (and possibly other systems, like inverse kinematics) could be used to generate a frame-by-frame pose that acts like a target to drive an actual physically simulated character body towards. This would be a bit like having a virtual puppeteer (the animation system) control a simulated marionette (the simulated character body, or rag doll). Obviously, you could try to set the simulated pose instantly to mimic the target pose, but this would simply hamper and override the physics simulation, causing it to break in various ways.

Instead of using infinitely strong marionette strings, it’s better to drive the body by relatively weak virtual springs. This way, the physics simulation always has the final say. For example, the body would normally match the animations closely. But when shot, the body would receive a physical push from the impact. This impact will push the pose away from the target pose, stretching the springs. Consequently, the stretched springs will start to push back towards their rest length, restoring the actual pose to the target pose over the course of a (fraction of a) second.

Motor joints

The Doom 3 engine is one of the few fully featured game engines you can freely experiment with that also exposes a lot of the internal C++ code. It has its own rigid body physics engine capable of simulating ragdolls, but it doesn’t come with support to drive a simulated pose towards a target pose using relatively weak forces. What Doom 3 misses are motor joints. Motor joints are like regular joints connecting rigid physics bodies (e.g. the body parts of the simulated character body), but can be used to try to reach a target pose using only a limited force.

The Doom 3 physics engine, like most rigid body simulators, solves a large matrix each frame, filled with numerical specifics from all joints and contacts currently active. This matrix represents a set of linear equations that, once solved, limits all constrained bodies to allowed relative positions and orientations by applying corrective forces. Different joint and contact types result in different coefficients in their linear equations, leading to different corrective forces, but are otherwise treated identically. Consequently, the code that solves the matrix to find the constrained angular and position velocity of each body for the next frame doesn’t have to know about any specific joint types. As a result, it's possible to add new joint types with motor drive by basically adding the right coefficients in Doom 3's constraints matrix. What follows are the basics required to understand this process.

Solving constraints

The full constraint matrix can contain many constraints for many different bodies, but individual constraints in this matrix are typically assumed to define a relationship between two bodies. This relationship is only defined in terms of positional and angular velocities, not in positions and angles. More precisely:

\[J_1 \begin{bmatrix} \vec {v_1} \\ \vec {\omega_1} \end{bmatrix} + J_2 \begin{bmatrix} \vec {v_2} \\ \vec {\omega_2} \end{bmatrix}= \vec c\]

Here, \(J_1\) and \(J_2\) are the Jacobian first-order partial derivative matrices of a constraint function with respect to the 6-dimensional \(\begin{bmatrix} \vec {v_1} & \vec {\omega_1} \end{bmatrix}^T\) and \(\begin{bmatrix} \vec {v_2} & \vec {\omega_2} \end{bmatrix}^T\) vectors of the positional and angular velocity of body 1 and 2, respectively. In other words, each row of \(J_1\) defines how the error of some constaint would increase or decrease depending on changes in each of the 6 velocity dimensions of body 1. Likewise, \(J_2\) defines this for body 2. To constrain n degrees of freedom (DOFs) between the two bodies with a joint, exactly n constraints are needed, defined in the n rows of \(J_1\), \(J_2\) and \(c\) . The vector \(c\) defines the exact constraint error values for when both positional and angular velocities are zero.

A constraint function defines the relation between some (combination of) relative positions or angles between two bodies. For example, a ball-and-socket joint simply states that the 3D position of some fixed anchor point on body 1 should remain equal to some fixed anchor point on body 2, removing three degrees of freedom between the two bodies. The error of the three required constraints for the ball-and-socket joint is then simply the actual difference between the two anchor points in the x, y and z direction, respectively.

Each constraint is defined in a similar way. In each simulation step, all active constraints between all pairs of bodies are fed into the solver as sub matrices of the total constraint matrix. Then, this matrix is solved for a force vector \(\vec \lambda\) that will minimize all current constraint errors, including those caused by the current combination of \(v_1\), \(\omega_1\), \(v_2\), \(\omega_2\) vectors, i.e.:

\[M_1^{-1} J_1^T \vec \lambda = \frac{1}{\Delta t} \begin{bmatrix} \Delta \vec {v_1} \\ \Delta \vec {\omega_1} \end{bmatrix}\]

\[M_2^{-1} J_2^T \vec \lambda = \frac{1}{\Delta t} \begin{bmatrix} \Delta\vec {v_2} \\ \Delta \vec {\omega_2} \end{bmatrix}\]

\[J_1 (\begin{bmatrix} \vec {v_1} \\ \vec {\omega_1} \end{bmatrix} + \begin{bmatrix} \Delta \vec {v_1} \\ \Delta \vec {\omega_1} \end{bmatrix}) + J_2 (\begin{bmatrix} \vec {v_2} \\ \vec {\omega_2} \end{bmatrix} + \begin{bmatrix} \Delta \vec {v_2} \\ \Delta \vec {\omega_2} \end{bmatrix}) = c\]

Here, \(\Delta t\) is the time between subsequent simulation steps, and \(M_1\) and \(M_2\) are 6 x 6 matrices defining the mass and moments of inertia for bodies 1 and 2, respectively. The first two equations are simply generalized versions of \(F/m \, = \, (a =) \, \, \Delta v / \Delta t\). The third equation states that the current (possibly constraint violating) velocities, updated by the to-be-decided corrective delta velocities should result in a state that perfectly adheres to the constraint. Again, different constraint types only have to fill in the right coefficients of the above equations, and leave it to the solver to find the constraint force vector \(\vec \lambda\) that simultaneously minimizes the relative velocity errors of all active constraints for the current simulation step.

Note that the n x 1 \(\vec \lambda\) vector defines forces in terms of constraints (called Lagrange multipliers). Consequently, \(J_1^T \vec \lambda\) and \(J_2^T \vec \lambda\) represent the forces in terms of the 3 positional and 3 angular dimensions for body 1 and 2, respectively. Note that, because of the definition of \(J_1\) and \(J_2\), the force vectors \(J_1^T \vec \lambda\) and \(J_2^T \vec \lambda\) can only represent forces in constrained (combinations of) directions, but never in unconstrained directions.

Now, to use all the above in a physics simulation with active constraints, the following is repeated for each simulation update: Any external forces (like gravity, wind, springs, etc.) are applied, influencing the current body velocites. These new velocities might partially violate active constraints. In order to correct this, a new constraint matrix is built and solved for \(\vec \lambda\) . Delta velocities are calculated from this \(\vec \lambda\) and applied to correct the new velocities. Lastly, a simple integration scheme is applied to update the body positions given these velocities. This process is typically repeated dozens of times per second to keep the the simulation both accurate and stable enough for practical purposes.

Constraints in practice

The constraint equations as explained above are defined in terms of position and angular velocities. However, most joint types are typically defined in terms of relative positions and angles. But when the error of some relative position or angle between bodies is zero and is kept at zero, the time derivative of these constraint errors will also be zero. So, assuming a positional and/or angular joint constraint is satisfied in the previous frame, the constraint can be satisfied for the next frame by making sure the time derivative of the constraint error (defined in terms of positional and angular velocties) is zero. Conceptually, this is all that is needed to convert positional/angular joint constraints to velocity constraints. But in practice, it's a little more complicated.

Because the Jacobians represent only first order approximations to the exact time derivative of any angular constraint, and because both the solver and the integrator will suffer from cumulative inaccuracies, errors will eventually build up causing joints to drift over time. This cannot be prevented, but can be corrected. By offsetting the constraint equations, constrained bodies can be made to constantly accelerate in the direction opposite of any constraint error, minimizing the errors over time. These offsets are typically implemented using the \(\vec c\) vector in the constraint matrix. More generally, this vector can be (ab)used to accelarate towards any (relative) velocity, which means it can also be used to implement a motor drive.

Some joint types also need to limit the direction and magnitude of the corrective forces. For example, a contact joint (here, a joint is defined as any useful combination of constraint rows) should push intersecting objects out of each other, but should not pull non-intersecting objects towards each other. In other words, when a contact constraint error is modeled in terms of the amount of penetration in the direction of the surface normal, its \(\vec \lambda\) must be allowed to be positive, but not be allowed to be negative. Consequently, most physics engines, including Doom 3's own physics engine, allows you to specificy clamping bounds for the individual elements in the resulting \(\vec \lambda\) vector (in this case, [0, ∞]). Another use of this feature is to implement constraints 'softness'. For example, it can also be used in a motor drive constraint to limit the maximum force (i.e. the forces divided by the simulation update time step) that can be applied by a motor.

Driving ball-and-socket joints

For the Armed Mine project, I needed support for both hinge (elbow) and ball-and-socket (shoulder) joint motor drives. Doom 3 did already support both joint types without motor drive. Also, hinge joints in Doom 3 could already (abruptly) steer towards a given dynamic angle, as used to control the direction of the wheels of simulated vehicles. So, it only needed controllable clamping bounds for the steering constraint's \(\vec \lambda\) to make it a fully functional motor drive for hinge joints. In contrast, the standard Doom 3 ball-and-socket joint didn't support any form of steering or motor drive, so I extended the Doom 3 constraint code as explained next.

A ball-and-socket joint removes the three positional degrees of freedom from the relative movement between two bodies, while the 3 angular degrees of freedom between the bodies remain unaffected (ignoring the concept of joint limits here and throughout this article). A ball-and-socket motor drive, however, will complement the 3 hard positional constraints with 3 soft angular constraints that will try to push the relative orientation between two bodies towards a target orientation.

Suppose \(N_1\) and \(N_2\) are the initial 3 x 3 rotation matrices in some neutral pose during construction (where the constraint is met by definition) and \(R_1\) and \(R_2\) are the 3 x 3 rotation matrices in the current pose of bodies 1 and 2, respectively. The rotation matrix \(S\) is this frame's target orientation relative to the neutral pose in the local space of body 2. Consequently \((N_1^T \, N_2) \, S\) is the relative target orientation of body 2 in the local space of body 1. Then, by definition, the motor drive has reached it target pose when \(R_2\) is equal to the target rotation of \(\hat R_2 = R_1 \, (N_1^T \, N_2) \, S\). The world space rotation error of body 2 is therefore \(R_2 \, \hat R_2^T\).

The goal of the motor drive constrains is to control the relative angular velocity of body 1 and 2 in such a way that it minimizes \(R_2 \, \hat R_2^T\). Or, written in standard constraint form:

\[\begin{bmatrix} \vec 0_3 & \vec 1_3 \end{bmatrix} \, \begin{bmatrix} \vec {v_1} \\ \vec {\omega_1} \end{bmatrix} + \begin{bmatrix} \vec 0_3 & -\vec 1_3 \end{bmatrix} \begin{bmatrix} \vec {v_2} \\ \vec {\omega_2} \end{bmatrix}= \vec c\]

where \(\vec c\) is a function of \(R_2 \, \hat R_2^T\), (partially) minimizing this error in the current simulation step. \(1_3\) is the 3 x 3 identity matrix, and \(0_3\) is the 3 x 3 zero matrix. To reduce a factor \(r\) (0 < \(r\) < 1) of the error in one update with timestep \(\Delta t,\) let \( \vec c = r \vec \epsilon / \Delta t\), where \(\Delta t\) is the time between subsequent simulation steps, and \(\vec \epsilon\) is the product of the rotation angle and axis of the \(R_2 \, \hat R_2^T\) rotation matrix.

Ideally, \(r\) = 1, as this would result in a \(\vec \lambda\) vector (if let unclamped) that changes the relative angular velocity by \(\vec \epsilon / \Delta t\) , thus integrating to a difference in angles of \(\vec \epsilon\) in one simulation step. In other words, it would directly result in the full compensation for any error between \(R_2\) and \(\hat R_2\). In practice, however, this can result in jittery and unstable simulator behaviour. Hence, smaller values of \(r\) (e.g. 0.5) are normally used to solve this problem over multple steps, preferring stability over (potential) accuracy.

Note that the above \(J_1\) and \(J_2\) 3 x 6 matrices above have the nice property mapping the constraint space forces of \(\vec \lambda\) one-to-one to (positive and negative) angular forces (i.e. torques) and back. So, in this specific case, clamping \(\vec \lambda\) can also be interpreted as clamping torque. Consequently, as Doom 3 supports \(\vec \lambda\) clamping, it's easy to add limits to the maximum torque a hinge motor drive can use to reach a target pose: One simply has to limit the allowed range of the 3 elements of \(\vec \lambda\) to [\(-\tau_{max}\), \(\tau_{max}\)].

This concludes all the math needed to implement a custom ball-and-socket motor drive support in Doom 3. The resulting implementation for the Doom 3 engine can be freely downloaded below. If you do download it, please note that Doom 3 uses row vectors instead of the column vectors used throughout in this article. As a result, the code actually uses the tranposes of the matrices and reverses all mentioned matrix concatenations.

The Armed Mine

Once the motor joints were implemented, I was able to drive the position and pose of a game character with it. I designed a 'test subject' having mechanical as well as natural parts that would need both physics and animation to ‘come alive’. To translate this into a 3D animatable model, I reused some parts from other Doom 3 assets, and modelled, rigged and skinned the rest in Maya. Then, I imported this Armed Mine (it had one arm and would eventually be made to explode on contact, hence its name) into Doom 3 and defined its rigid body properties and joints. At that point it became a lifeless object that could, for example, be kicked, pushed and stacked in the a realistic way during gameplay.

Top left: Armed mine concept. Bottom left: Low-poly model in Maya. Bottom right: Bone rig for skeletal animation. Top right: Rigid bodies and joints in Doom 3, simulating its physical behaviour.

 

Next, I added custom code to procedurally animate the Armed Mine. Each frame, a target hand position is sampled from a cyclic curve predefined by a few 3D control points. This sampled position progresses through the cycle at a fixed rate. The curve's control points are transformed each frame from local space to world space and is skewed dynamically. This skewed cyclic hand position is responsible for propelling itself forward, but also for steering the main body in the direction of the player.

The new hand position and the previous pose of the main body are fed into a custom IK system to calculate the new shoulder, elbow and wrist angles. These angles were then passed over to a ball-and-socket shoulder joint and a hinging elbow joint motor drives as new target angles, allowing only limited finite forces to reach them. These, in turn, cause the physics simulation to adjust the position and orientation of the rigid bodies representing the different body parts. Lastly, the bones for the skinned graphics body parts are updated from the new physics state, finishing the preparation of the character to be rendered.

This all led to a game character that is capable of pushing itself off as a result of actual forces acting between the body parts and the floor. The combination of physics and animation resulted in a much more plausible and responsive behaviour in unexpected contexts. For example, after being blasted into an awkward pose, it will automatically try to pull its arm from under its body and do a push up to regain its normal upright position, without being programmed to do so.

Downloads

  • C++ source code extensions to the Doom 3 SDK 3, now fully supporting motor drives (or, steering) for the ball-and-socket and hinge joint types. All changes are marked with "//GDC".

Comments (1)

christian louboutin mary jane pumps
July 10, 2012

Admiring the commitment you put into your blog and detailed information you present. It's good to come across a blog every once in a while that isn't the same out of date rehashed information. Wonderful read! I've saved your site and I'm adding your RSS feeds to my Google account.

Leave a comment