Fast and exponential-time are generally contradictory terms in Computer Science. Nevertheless, we have developed an exponential-time algorithm (in the number of contact points) that not only runs in O(n3) time typically, but is even faster than competing O(n3) methods in general. This method produces frictional effects and is energetically consistent.
- This work is currently under review.
We have developed an exact, robust contact method that runs in time O(n3) in the number of contact points. Our method is numerically robust, requires no special operations research codes, simulates Coulomb friction (sliding, sticking, and rolling), and is compatible with arbitrary integrators (Euler, Runge-Kutta, Verlet, etc.).
- Evan Drumwright and Dylan Shell. "A Robust and Tractable Contact Model for Robotic Simulation". Proc. of the 24th ACM Symp. on Applied Computing (SAC). Honolulu, 2009. (to appear)
Advanced penalty method for rigid body simulation
My advanced penalty method works by applying forces over the volume of penetration, rather than applying a force due to only a single, virtual spring and damper at the point of deepest penetration. Applying forces at multiple points reduces the oscillation that emerges from the standard approach. Additionally, I use an integrative term to reduce steady-state error, which permits less stiff gain constants to be used for the virtual springs and dampers; the resulting equations of motion are much more stable numerically.
- Evan Drumwright. A Fast and Stable Penalty Method for Rigid Body Simulation. IEEE Trans. on Visualization and Computer Graphics. vol. 14, no. 1, pp. 231-240, January/February, 2008.