News for hackers. Stuff that matters.
Re:Automatic Differentiation (2009) by Animats on Saturday January 02, 2016 @01:06AM (#10825284)
I had a need for this in an unrelated problem area - ragdoll physics. In 1996-1997 I came out with Falling Bodes, the first ragdoll physics system that worked right. It was a spring-damper system, not an impulse-constraint system like most game engines; this produces more accurate and better looking collisions, but is more expensive computationally. So it was used as an animation tool, not for games.

The rigid body dynamics system used Featherstone's algorithm. This models a tree of links and joints, a skeleton. You put in forces and torques at each joint, and the algorithm computes accelerations at each joint and the root node. Those accelerations then have to be integrated to get velocities and positions. As positions change, so do contact forces. If you don't want to get interpenetration in collisions, the contact forces must be allowed to become very large. We used exponential springs as the contact model to achieve this.

Numerically, this means integrating a very stiff system of differential equations. Explicit integration, like Runge-Kutta 4, works, but you have to monitor the error term and cut the time step when necessary. During the early parts of a hard collision, the time step may have to drop into the microsecond range. This is why this approach doesn't work well for games; it's not constant-time. (If you don't cut the time step, your simulation goes "sprong", and things go flying off into space. Some games still do this.)

An alternative is to use implicit integration, where you work backwards to solve the next step to be consistent with the previous one. Implicit integration works with larger timesteps on stiff systems. (There's still error, but it acts in the direction of draining energy from the moving system, which is much better than adding it.) This requires gradients of the function that the Featherstone algorithm is computing. The brute-force approach is to compute the gradients (the Jacobian) by perturbing each input by a small amount, running the Featherstone algorithm, measuring the differences, and obtaining the slopes numerically. This is slow.

Ideally, you'd like to have analytical Jacobians. That's where automatic differentiation would help. Differentiating Featherstone's algorithm analytically is hard, but might be possible today.

We used SD/Fast, which is a C code generator for Featherstone's algorithm. Straightforward implementations of Featherstone have lots of switches and conditionals as they deal with the topology of the skeleton being simulated. SD/Fast took in the link and joint description and turned out C code for that structure. This gets rid of most of the conditionals. It unwound the code more than you'd want to do today; there was much loop unrolling at the source level. (Before superscalar CPUs, unwinding loops was a win; today, tiny tight loops are a win.)

Anyway, it's possible that the tools being developed in machine learning could be applied to game physics in that way. At the visual level, the difference is that big objects bounce like big objects, with slower collision rebound times. In impulse-constraint systems, all bounces are instantaneous, which is why, in video games, everything seems to be too light.

There are no comments on this comment yet.