Efficient Collision Detection for Real-time Simulated Environments

This thesis describes a new model for rapid physical simulation called sparse dynamics. The method employs a simplified object representation to quickly identify likely object interactions. These are then flagged for more detailed analysis. As actual collisions are rare in a sparsely popu-lated environment, efficiency is greatly increased. The first phase uses deterministic Newtonian mechanics to predict future collisions analytically, obviating the need to simulate small uniform time steps. The detailed phase makes use of a near-constant time polyhedral distance tracker to minimize the expense of complicated objects. The current system can handle interactions involving linear and accelerated motions (includ-ing gravity), wind resistance, user manipulations, and to some extent supporting contacts and fric-tion. Methods are discussed to further extend this list. Timings indicate sparse dynamics provides a large speed improvement over more traditional methods. In particular we are able to simulate full collision detections for a simple environment containing 500 polyhedra at real-time speeds. Even in highly realistic or complicated environments, we expect a speed up by an order of magnitude or more