Skip to main content

Über dieses Buch

This book introduces the techniques needed to produce realistic simulations and animations of particle and rigid-body systems. The text focuses on both the theoretical and practical aspects of developing and implementing physically based dynamic-simulation engines. Each chapter examines numerous algorithms, describing their design and analysis in an accessible manner, without sacrificing depth of coverage or mathematical rigor. Features: examines the problem of computing an hierarchical representation of the geometric description of each simulated object, as well as the simulated world; discusses the use of discrete and continuous collision detection to handle thin or fast-moving objects; describes the computational techniques needed for determining all impulsive and contact forces between bodies with multiple simultaneous collisions and contacts; presents techniques that can be used to dynamically simulate articulated rigid bodies; concludes each chapter with exercises.



Dynamic Simulation


1. Dynamic Simulations

This chapter presents an overview of how all techniques covered in this book fit together as independent modules constituting a simulation engine. It discusses in detail a possible architectural design of a computationally efficient implementation of a dynamic-simulation engine for non-penetrating particle and rigid-body systems. In doing so, we are mostly interested in studying algorithms that can produce real-time or near real-time performance. The actual description of the algorithms used in each step of the simulation engine proposed in this book, as well as reference software implementations of several modules that make up the entire simulation, are provided in the remaining chapters and appendices. The main goal of this chapter is to justify the book’s organization, and describe the high-level steps necessary to implement an efficient dynamic-simulation engine.

Murilo G. Coutinho

2. Hierarchical Representation of 3D Polyhedra

This chapter focuses on the problem of computing a hierarchical representation of the geometric description of each simulated object, as well as the simulated world. This representation is used to speed collision-detection checks by taking advantage of the geometric arrangement of the objects in the simulated world, such that collision tests are only carried out on objects that are “close enough” to collide. The hierarchical decomposition of the colliding objects is used to prune unnecessary intersection tests and quickly specify the collision points, or discard the collision if no intersections are found. The types of hierarchical representations discussed in this book include axis-aligned bounding boxes, oriented bounding boxes, bounding spheres, convex hulls and spatial grids, both static and continuous (i.e., taking time into account when checking for collisions).

Murilo G. Coutinho

3. Particle Systems

This chapter covers the design and implementation of particle systems as a collection of point mass objects that can collide with each other and other rigid-body objects in the simulation. Even though this is one of the simplest models of particle systems that can be used, the computational efficiency and degree of realism that can be attained with these systems is highly attractive. This chapter also discusses in details the use of spatially dependent interaction forces to model particle-based fluid simulations including a detailed overview of Smoothed Particle Hydrodynamics (SPH).

Murilo G. Coutinho

4. Rigid-Body Systems

This chapter presents the theoretical and practical aspects of designing and implementing dynamic-simulation engines for rigid-body systems. It covers both generic and specialized algorithms for non-convex and convex objects, respectively, including the special cases of thin and fast moving objects. Special attention is given to one of the most difficult and least understood topics in physically based modeling, namely, the computational techniques needed for determining all impulsive and contact forces between bodies with multiple simultaneous collisions and contacts.

Murilo G. Coutinho

5. Articulated Rigid-Body Systems

This chapter extends the techniques for rigid bodies to include articulated rigid bodies. Here, we shall focus on linking rigid bodies with joints that constraint their motion. Position-based, velocity-based and force-based constraints systems are explained and a framework is presented to derive the appropriate constraint equations based on the number of degree of freedoms associated with a joint. This framework is applied to spherical, universal, revolute, cylindrical, prismatic and rigid joints. However, these techniques can be easily applied to include other types of joints suitable to the reader’s interests.

Murilo G. Coutinho

Mathematical Toolset


6. Appendix A: Useful 3D Geometric Constructions

This Appendix briefly covers some of the geometric constructions used as building blocks to implement the several intersection tests that are part of the particle–particle, particle–rigid body and rigid body–rigid body collision-detection algorithms. It also discusses how the tangent plane of a collision or contact can be determined given the collision or contact point and normal vector.

Murilo G. Coutinho

7. Appendix B: Numerical Solution of Ordinary Differential Equations of Motion

This Appendix discusses some of the most common methods used to integrate the differential equations of motion in dynamic simulations. These methods range from simple explicit-Euler, to more sophisticated Runge–Kutta methods, with adaptive time step sizing.

Murilo G. Coutinho

8. Appendix C: Quaternions

This Appendix presents an alternate representation of rotation matrices using quaternions. This representation is extremely useful in reducing rounding-error problems found when combining rotation matrices. Also, the interpolation between two quaternions representing the orientation of an object is easier than using rotation matrices. This is especially useful when backtracking in time the object’s motion to determine the instant just before a collision.

Murilo G. Coutinho

9. Appendix D: Rigid-Body Mass Properties

This Appendix shows an efficient algorithm to compute the mass properties of 3D polyhedra. The mass properties include the total volume, total mass, center of mass, and inertia tensor. These quantities are used in the physically based modeling of the dynamics and interactions of objects in the simulated world.

Murilo G. Coutinho

10. Appendix E: Useful Time Derivatives

This Appendix presents a detailed description of how the time derivatives of a normal vector, a rotation matrix and a quaternion are computed. These time derivatives are extensively used in Chaps.




to describe the dynamics of a rigid-body system.

Murilo G. Coutinho

11. Appendix F: Convex Decomposition of 3D Polyhedra

This Appendix addresses the technical barriers to using non-convex polyhedra in a dynamic simulation. Most interesting objects to be simulated are usually non-convex. However, most of the more efficient algorithms presented in this book are especially tailored for convex objects. Therefore, it is often necessary to pre-process all objects in the simulation with a convex decomposition module that decomposes the objects into a set of non-overlapping convex parts. The specialized dynamic simulation algorithms can then be applied to the convex parts of each object.

Murilo G. Coutinho

12. Appendix G: Constructing Signed Distance Fields for 3D Polyhedra

This Appendix describes the use of signed distance fields to create a simplified, lower-resolution version of the objects registered with the simulation engine. The memory efficient algorithm presented in this book is capable of handling grid-resolutions for the signed fields on the order of thousands of cells along each coordinate axis. A collision detection and response algorithm based on signed distance fields is also discussed.

Murilo G. Coutinho

13. Appendix H: Conservative Time Advancement for Convex Objects

This Appendix discusses the Conservative Time Advancement (CTA) algorithm used to compute the exact collision time between convex objects. This algorithm can be applied to both standard and continuous collision detection.

Murilo G. Coutinho

14. Appendix I: The Linear-Complementarity Problem

This Appendix presents the Linear Complementarity Problem (LCP) in the context of impulse and contact-force computation of multiple simultaneous collisions. This Appendix also presents an extension of the original algorithm to cope with static and dynamic friction at the collision or contact point.

Murilo G. Coutinho


Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!