Efficient Penetration Depth Computation using Active Learning

Jia Pan, Xinyu Zhang and Dinesh Manocha¹
University of North Carolina at Chapel Hill


Abstract
We present a new method for efficiently computing the global penetration depth between two rigid objects using machine learning techniques. Our approach consists of two phases: offline learning and performing run-time queries. In the learning phase, we pre-compute an approximation of the contact space of a pair of intersecting objects from a set of samples in the configuration space. We use active and incremental learning algorithms to accelerate the pre-computation and improve the accuracy. During the run-time phase, our algorithm performs a nearest-neighbor query based on translational or rotational distance metrics. The run-time query has a small overhead and computes an approximation to global penetration depth in a few milliseconds. We use our algorithm for collision response computations in Box2D and Bullet game physics engines and observe more than an order of magnitude improvement over prior PD computation techniques.

Paper

Efficient Penetration Depth Computation using Active Learning (paper and supplemental)

SIGGRAPH Asia 2013, conditionally accepted


Video

Efficient Penetration Depth Computation using Active Learning (MP4)

---