An effective paradigm for simulating the dynamics of robots that locomote and manipulate is multi-rigid body simulation with rigid contact. This paradigm provides reasonable tradeoffs between accuracy, running time, and simplicity of parameter selection and identification. The Stewart-Trinkle Anitescu-Potra time stepping approach is the basis of many existing implementations. It successfully treats inconsistent (Painleve-type) contact configurations, efficiently handles many contact events occurring in short time intervals, and provably converges to the solution of the continuous time differential algebraic equations (DAEs) as the integration step size tends to zero. However, there is currently no means to determine when the solution has largely converged, i.e., when smaller integration steps would result in only small increases in accuracy. The present work describes an approach that computes the event times (when the set of active equations in a DAE changes) of all contact impact events for a multi-body simulation, toward using integration techniques with error control to compute a solution with desired accuracy. We also describe a first-order, variable integration approach that ensures that rigid bodies with convex polytopic geometries never interpenetrate. This approach permits taking large steps when possible and takes small steps when contact is complex.
Dynamic simulation is a powerful application of today's computers, with uses in fields ranging from engineering to animation to virtual reality. This thesis introduces a new paradigm for dynamic simulation, called impulse-based simulation. The paradigm is designed to meet the twin goals of physical accuracy and computational efficiency. Obtaining physically accurate results is often the whole reason for performing a simulation, however, in many applications, computational efficiency is equally important. Impulse-based simulation is designed to simulate moderately complex systems at interactive speeds. To achieve this performance, certain restrictions are made on the systems to be simulated. The strongest restriction is that they comprise only rigid bodies. The hardest part of rigid body simulation is modeling the interactions that occur between bodies in contact. The most commonly used approaches are penalty methods, followed by analytic methods. Both of these approaches are constraint-based, meaning that constraint forces at the contact points are continually computed and applied to determine the accelerations of the bodies. Impulse-based simulation is a departure from these approaches, in that there are no explicit constraints to be maintained at contact points. Rather, all contact interactions between bodies are affected through collisions; rolling, sliding, resting, and colliding contact are all modeled in this way. The approach has several advantages, including simplicity, robustness, parallelizability, and an ability to efficiently simulate classes of systems that are difficult to simulate using constraint-based methods. The accuracy of impulse-based simulation has been experimentally tested and is sufficient for many applications. The processing of collisions is a critical aspect of the impulse-based approach. Efficient algorithms are needed for detecting the large number of collisions that occur, without missing any. Furthermore, the physical accuracy of the simulator rests upon the accuracy of the collision response algorithms. This thesis describes these essential algorithms, and their underlying theory. It describes how the algorithms for simple rigid body simulation may be extended to systems of articulated rigid bodies. To prove the method is truly practical, the algorithms have been implemented in the prototype simulator, Impulse. Many experiments performed with Impulse are described.