Optimization-based animation

A new paradigm for rigid body simulation is presented and analyzed. Current techniques for rigid body simulation run slowly on scenes with many bodies in close proximity. Each time two bodies collide or make or break a static contact, the simulator must interrupt the numerical integration of velocities an accelerations. Even for simple scenes, the number of discontinuities per frame time can rise to the millions. An efficient optimization-based animation (OBA) algorithm is present which can simulate scenes with many convex three-dimensional bodies settling into stacks and other crowded arrangements. This algorithm simulates Newtonian (second order) physics and Coulomb friction, and it uses quadratic programming (QP) to calculate new positions, momenta, and accelerations strictly at frame times. The extremely small integration steps inherent to traditional simulation techniques are avoided.Contact points are synchronized at the end of each frame. Resolving contacts with friction is known to be a difficult problem. Analytic force calculation can have ambiguous or non-existing solutions. Purely impulsive techniques avoid these ambiguous cases, but still require an excessive and computationally expensive number of updates in the case of many simultaneous contacts. It is shown informally that even taking into account advances in stiff integration techniques, penalty force methods cannot overcome this issue of running time in highly crowded scenes. New algorithms are presented that calculate simultaneous impulses to resolve collisions and static contacts under the Coulomb friction model. The simultaneous impulses are the solution to a QP. In addition, the algorithms apply bouncing at distance and freezing of bodies to further speed up the simulation. When added to the implementation of OBA, these new algorithms increase the speed of the simulation by a factor of up to 30.The component algorithms of OBA can be used individually in any existing simulator when this is desirable. Position update and momentum calculation can be hybridized with traditional methods when realism requires it. Non-convex bodies are simulated as unions of convex bodies. Links and joints are simulated with bi-directional constraints. Analysis of the algorithm and discussion of example simulations are provided