Publications

Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner. This paper is not only a stake in the sand on what has been done, it also seeks to give the reader deeper insights to help guide their future research.

We propose a position-based approach for large-scale simulations of rigid bodies at interactive frame-rates. Our method solves positional constraints between rigid bodies and therefore integrates nicely with other position-based methods. Interaction of particles and rigid bodies through common constraints enables two-way coupling with deformables. The method exhibits exceptional performance and stability while being user-controllable and easy to implement. Various results demonstrate the practicability of our method for the resolution of collisions, contacts, stacking and joint constraints.

Die physikalisch-basierte Simulation von Starrkörpern und deformierbaren Festkörpern ist ein wichtiges und aktuelles Forschungsgebiet in der Computergraphik und ein essentieller Bestandteil in vielen Anwendungen, wie z.B. Virtual Prototyping, Computeranimationen, Spiele, Spezialeffekte in Filmen oder Trainingssimulatoren. Dabei stehen oft interaktive Simulationen im Vordergrund, in denen ein Benutzer in Echtzeit mit den simulierten Körpern interagieren kann. Dadurch werden hohe Anforderungen an die Geschwindigkeit und Stabilität der Simulationsverfahren gestellt.

In dieser Arbeit werden interaktive Simulationsmethoden für Mehrkörpersysteme, Textilien und inkompressible deformierbare Volumenkörper vorgestellt. Außerdem wird gezeigt, wie die Simulation durch den Einsatz GPU-basierter Methoden deutlich beschleunigt werden kann.

Die dynamische Simulation gewinnt im Bereich der virtuellen Realität immer mehr an Bedeutung. Sie ist ein wichtiges Hilfsmittel, um den Grad der Immersion des Benutzers in eine virtuelle Welt zu erhöhen. In diesem Anwendungsbereich ist die Geschwindigkeit des verwendeten Simulationsverfahrens entscheidend. Weitere Anforderungen an das Verfahren sind unter anderem Genauigkeit, Stabilität und eine einfache Implementierung. In dieser Arbeit wird ein neues impulsbasiertes Verfahren für die dynamische Simulation von Mehrkörpersystemen vorgestellt. Dieses erfüllt, im Gegensatz zu klassischen Verfahren, alle Anforderungen der virtuellen Realität. Das vorgestellte Verfahren arbeitet ausschließlich mit Impulsen, um mechanische Gelenke, Kollisionen und bleibende Kontakte mit Reibung zu simulieren.

Eine der am weitesten verbreiteten Methoden zur Simulation von mechanischen Starrkörpersystemen ist die Lagrange-Faktoren-Methode (LFM). Die impulsbasierte Dynamiksimulation ist ein neuer alternativer Ansatz zur Simulation solcher Systeme. Durch den direkten Vergleich werden in dieser Arbeit die Vor- und Nachteile der beiden Methoden aufgezeigt. Dazu wird neben einer Laufzeit- und Genauigkeitsmessung zusätzlich ein informeller Vergleich durchgeführt und die Ergebnisse diskutiert.

This paper describes an impulse-based dynamic simulation method for articulated bodies which has a linear time complexity. Existing linear-time methods are either based on a reduced-coordinate formulation or on Lagrange multipliers. The impulse-based simulation has advantages over these well-known methods. Unlike reduced-coordinate methods, it handles nonholonomic constraints like velocity-dependent ones and is very easy to implement. In contrast to Lagrange multiplier methods the impulse-based approach has no drift problem and an additional stabilisation is not necessary. The presented method computes a simulation step in O(n) time for acyclic multi-body systems containing equality constraints. Closed kinematic chains can be handled by dividing the model into different acyclic parts. Each of these parts is solved independently from each other. The dependencies between the single parts are solved by an iterative method. In the same way inequality constraints can be integrated in the simulation process in order to handle collisions and permanent contacts with dynamic and static friction.

Die dynamische Simulation gewinnt im Bereich der virtuellen Realität immer mehr an Bedeutung. Sie ist ein wichtiges Hilfsmittel, um den Grad der Immersion des Benutzers in eine virtuelle Welt zu erhöhen. In diesem Anwendungsbereich ist die Geschwindigkeit des verwendeten Simulationsverfahrens entscheidend. Weitere Anforderungen an das Verfahren sind unter anderem Genauigkeit, Stabilität und eine einfache Implementierung.

In dieser Arbeit wird ein neues impulsbasiertes Verfahren für die dynamische Simulation von Mehrkörpersystemen vorgestellt. Dieses erfüllt, im Gegensatz zu klassischen Verfahren, alle Anforderungen der virtuellen Realität. Das vorgestellte Verfahren arbeitet ausschließlich mit Impulsen, um mechanische Gelenke, Kollisionen und bleibende Kontakte mit Reibung zu simulieren.

In this paper a new method for handling collisions and permanent contacts between rigid bodies is presented. Constraint-based methods for computing contact forces with friction provide a high degree of accuracy. The computation is often transformed into an optimization problem and solved with techniques like linear or quadratic programming. Impulse-based methods compute impulses to prevent colliding bodies from interpenetrating. The determination of these impulses is simple and fast. The impulse-based methods are very efficient but they are less accurate than the constraint-based methods because they resolve only one contact between two colliding bodies at the same time. The presented method uses a constraint-based approach. It can handle multiple contacts between two colliding bodies at the same time. For every collision and contact a non-penetration constraint is defined. These constraints are satisfied by iteratively computing impulses. In the same iteration loop impulses for dynamic and static friction are determined. The new method provides the accuracy of a constraint-based method and is efficient and easy to implement like an impulse-based one.

A dynamic simulation method for multi-body systems is presented in this paper. The special feature of this method is that it satisfies all given constraints by computing impulses. In each simulation step the joint states after the step are predicted. In order to obtain valid states after the simulation step, impulses are computed and applied to the connected bodies. Since a valid joint state is targeted exactly, there is no drift as the simulation proceeds in time and so no additional stabilisation is required. In previous approaches the impulses for a multi-body system were computed iteratively. Since dependencies between joints were not taken into account, the simulation of complex models was slow. A novel method is presented that uses a system of linear equations to describe these dependencies. By solving this typically sparse system the required impulses are determined. This method allows a very fast simulation of complex multi-body systems.

This paper describes a system for dynamic simulation of linked rigid bodies in real-time. The system was developed to simulate mechanical behaviour in VR applications. An extension for a 3D modelling tool was developed which provides the possibility to model a VR scene including the geometries and mechanical parameters of all rigid bodies and the properties of the joints between them easily. For the dynamic simulation an impulse-based method is used. The distinguishing feature of this method is that all kind of constraints are satisfied with the iterative computation of impulses. The advantage of this iterative technique is that it is fast and accurate results can be achieved. The dynamic simulation system uses efficient collision detection methods. For every collision that is detected a contact region between the objects is determined to provide an accurate collision response.

At first we will give a short introduction to the new impulse-based method for dynamic simulation. Up till now impulses were frequently used to resolve collisions between rigid bodies. In the last years we have extended these techniques to simulate constraint forces. Important properties of the new impulse method are: (1) Simulation in Cartesian coordinates, (2) complete elimination of drift as known from Lagrange multiplier methods, (3) simple integration of collision and friction and (4) real time performance even for complex multibody systems like six legged walking machines. In order to demonstrate the potential of the impulse-based method, we report on numerical experiments. We compare the following dynamic simulation methods: (1) Generalized (or reduced) coordinates, (2) Lagrange multipliers without and with several stabilization methods like Baumgarte, velocity correction and projection method, (3) impulse-based methods of order 2, 4, 6, 8, and 10. We have simulated the mathematical pendulum, the double and the triple pendulum with all of these dynamic simulation methods and report on the attainable accuracy.

First, we will provide a short introduction to the impulse-based method for dynamic simulation. Till now, impulses were frequently used to resolve collisions between rigid bodies. In the last years, we have extended these techniques to simulate constraint forces. Important properties of the new impulse method are: (1) Simulation in Cartesian coordinates, (2) complete elimination of the constraint drift known from Lagrange multiplier methods, (3) simple integration of collision and friction and (4) real-time performance even for complex multibody systems like six-legged walking machines. In order to demonstrate the potential of the impulse-based method, we report on numerical experiments. We compare the following dynamic simulation methods: (1) Generalized (or reduced) coordinates, (2) the Lagrange multiplier method with and without several stabilization methods like Baumgarte, the velocity correction and a projection method, (3) impulse-based methods of integration order 2, 4, 6, 8, and 10. We have simulated the mathematical pendulum, the double and the triple pendulum with all of these dynamic simulation methods and report on the attainable accuracy. It turned out that the impulse methods of higher integration order are all of O(h^3) but have very small factors and are therefore relatively accurate. A Lagrange multiplier method fully stabilized by impulse-based techniques turned out to be the best of the Lagrange multiplier methods tested.

Impulse-based dynamic simulation using the iterative method results in relatively simple algorithms which are easy to implement. However, two important theoretical questions have so far still remained open: (1) In what situations does the iterative procedure converge or diverge, and how can divergence be avoided? (2) Does the impulse-based simulation converge towards the exact solution of the dynamics problem as the step size is reduced? We will completely answer both questions in this paper. First we simplify the argumentation in that we prove that for every multibody system there is a dynamically and kinematically equivalent point mass system. Hence, our results on point mass systems also apply to multibody simulations. Next we show how to replace the iterative procedures by solving systems of linear equations. We prove that the matrices of these equation systems are non-singular if redundant constraints are removed from the point mass system in question. We prove further that the solution generated by the impulse-based procedure converges towards the exact solution of the dynamics problem as the step size is reduced towards zero. The proof is based on a detailed comparison of the impulse-based integration expression and the Taylor series solution. It is well known that the latter converges to the exact solution of the dynamics problem if a Lipschitz condition is satisfied.

Comparison with the standard numerics on the basis of Lagrange multipliers shows significant advantages for the impulse-based method because the latter is completely free of drift problems, and stabilizations in the sense of Baumgarte are unnecessary. Because of the existence of methods of higher order, we can finally conclude that the impulse-based method is superior to the method with Lagrange multipliers.