Author Kenny Erleben ( 2004 )

Abstract This dissertation is concerned with the theory and difficulties of stable, robust, and versatile multibody dynamics simulation for the purpose of computer animation. The subjects covered touch many aspects in simulation and animation including convergence rate, numerical errors, time-stepping, error-correction et cetera.
From an algorithmic viewpoint, the most novel contributions are considered to be a velocity-based shock-propagation time-stepping scheme, and a method for computing general scripted motion. A formal presentation of contact graphs and their usage is given. Also discussed is insight into speed-up methods, object oriented design of constraints, and optimized and easy implementation of iterative linear complementarity problem (LCP) solvers. Contributions to the subject of collision detection include improvements of using signed distance maps for collision detection and contact point generation for box-box primitives.
The focus of the dissertation is technical and theoretical. Great effort has been made to show clearly how one should approach an implementation of the presented material. An implementation of all the presented algorithms and data structures has been made publicly available in [113].

Online PDF Version DIKU

Code available from OpenTissue

Supplementary Media
Contact Point Generation for Box-Box Collision
Successful contact point generation is vital for stable and robust simulation, here a comparison between the contact point generation algorithm used in Open Dynamics Engine, and the improved version from the PhD thesis.

Notice that the improved algorithm suffers less from flickering contact points. Next we use a 200 Brick Wall for comparison on larger scenes. Following two animations clearly demonstrate the importance of good contact point generation.

  • Open-Dynamics Engine contact point generation for box-box collisionode wall
  • Improved contact point generation for box-box collisionimproved wall

Convergence Testing of Gauss-Seidel with out Shock-Propagation
Time-stepping without shock-propagation using iterative Gauss-Seidel solver. First we show convergence testing witout error correction using a 25 box stack

Second we show convergence testing with error correction enabled, the same number of iterations are used for time-stepping and error-correction.

Notice that the box-stack appears more and more rigid when using more iterations, however it is clear, that this configuration suffers from a slow convergence rate. Third we use a 125 Ball Grid for comparison

In the fourth convergence study we use a 200 brick wall scene

In the fifth study we use a 320 brick tower

Using Shock Propagation with and with-out Error Correction
Here a 125 ball grid scene is used for comparing between using error correction with and without shock-propagation. In both cases 5 iterations are used in the iterative Gauss-Seidel solver.

Notice that without shock-propagation the grid structure is lost, making it impossible to simulate nicely structured stacking, such as brick walls or towers. Also notice that with shock-propagation it takes a few frames before all errors are corrected. This is because we do not re-evaluate contact points when proceeding to the next stack-layer.
Using a Sleepy Policy
Simulations showing how sleepy policy work together with velocity-based shock-propagation, and dependency on restitution and f-weight. Blue color corresponds to sleepy bodies. First we study a 640 brick tower scene. Notice how sleepy state changes on impact and is propagated to nearby objects.

Next we study the influence of restitution. All simulations were done with f-weight equal to 0.125, notice that high restitution causes blow-up, this is because simulation errors are propagated due to the high restitution, and the weight of the dynamics step adds a substantial error for each step, causing errors to grow and accumulate. Lowering the f-weight will result in a perfect box-stack simulation even when using high restitution values.

Now we will study the influence of the f-weight factor on the sleepy policy. Setting the f-weight too low, makes sleepy policy over-efficient.

Using Signed Distance Maps For Collision Detection and Contact Point Generation
These simulations were done without the last smoothing error-correction, notice how the the diku configuration suffers from cyclic dependency problems of the shock-propagation.

Scripted Motion
Kinematic splines are used to define scripted bodies, interacting with large-scale stacking.

Performance Study Cases
Following simulations were used for performance measurements

Try to compare diku2 with diku, notice how the problems of cyclic dependency have vanished.