Numerical techniques of rigid body simulation

Abstract

In recent years, the modeling of physical phenomena has become an integral part of computer applications in diverse areas from engineering to entertainment. This thesis focuses on a particular aspect of this modeling, the simulation of rigid bodies. Complicated simulations require the development of sophisticated collision detection systems and numerical techniques. Previous work in the field has almost exclusively been restricted to geometries that are convex or a union of convex pieces. One of the goals of this thesis is overcoming this restriction. Collision detection is only one of the many hurdles which arise in simulating collisions between rigid bodies. To calculate the appropriate response of colliding bodies, the point of contact between the bodies must be determined. Methods of contact point determination will also be discussed. This thesis also explores the issues of resolving simultaneous collisions and resting contact via the formulation of a linear complementarity problem (LCP). This method maintains the physical validity of the simulator, unlike penalty methods which are often used. Impulse based methods for resting contacts have been proposed and implemented by others, but cannot simulate simple structures, such as a stack of blocks. The LCP formulation allows these types of configurations, which are successfully simulated in this thesis. The culmination of this thesis is the development of a rigid body simulator. The numerical methods and algorithms employed are discussed and are compared to alternative techniques. The intention is that the reader use this thesis and its references to ease the process of writing a new simulator and gain insight into the methods used.