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 .
Online PDF Version DIKU
Code available from OpenTissue
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.
- Open-Dynamics Engine contact point generation for box-box collisionode box box test
- Improved contact point generation for box-box collisionimproved box box test
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
- 10 iterations box stack i10 wo error correction
- 100 iterations box stack i100 wo error correction
- 10000 iterations box stack i10000 wo error correction
Second we show convergence testing with error correction enabled, the same number of iterations are used for time-stepping and error-correction.
- 100 iterations box stack i100 w error correction
- 200 iterations box stack i200 w error correction
- 400 iterations box stack i400 w error correction
- 600 iterations box stack i600 w error correction
- 800 iterations box stack i800 w error correction
- 1000 iterations box stack i1000 w error correction
- 2000 iterations box stack i2000 w error correction
- 10000 iterations box stack i10000 w 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
- 10 iterations ball grid i10 wo error correction
- 100 iterations ball grid i100 wo error correction
- 100 iterations with error correction ball grid i100 w error correction
In the fourth convergence study we use a 200 brick wall scene
- 10 iterations wall i10 wo error correction
- 100 iterations wall i100 wo error correction
- 100 iterations with error correction wall i100 w error correction
In the fifth study we use a 320 brick tower
- 10 iterations tower i10 wo error correction
- 100 iterations tower i100 wo error correction
- 100 iterations with error correction tower i100 w error correction
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.
- With Shock-Propagation ball grid error correction w shock
- With out Shock-Propagation ball grid error correction wo shock
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.
- 0.0 restitution box stack low restitution
- 0.4 restitution box stack medium restitution
- 1.0 restitution box stack high restitution
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.
Kinematic splines are used to define scripted bodies, interacting with large-scale stacking.
- 125 balls stacked in a grid scripted motion ball grid
- 2000 balls on a table scripted motion ball pile
- 200 brick wall scripted motion wall
- 320 brick tower scripted motion tower
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.