Signed-distance fields (SDFs) are a popular shape representation for collision detection. This is due to their query efficiency, and the ability to provide robust inside/outside information. Although it is straightforward to test points for interpenetration with an SDF, it is not clear how to extend this to continuous surfaces, such as triangle meshes. In this paper, we propose a per-element local optimization to find the closest points between the SDF isosurface and mesh elements. This allows us to generate accurate contact points between sharp point-face pairs, and handle smoothly varying edge-edge contact. We compare three numerical methods for solving the local optimization problem: projected gradient descent, Frank-Wolfe, and golden-section search. Finally, we demonstrate the applicability of our method to a wide range of scenarios including the collision of simulated cloth, rigid bodies, and deformable solids.

Inspired by frictional behavior that is observed when sliding matchsticks against one another at different angles, we propose a phenomenological anisotropic friction model for structured surfaces. Our model interpolates isotropic and anisotropic elliptical Coulomb friction parameters for a pair of surfaces with perpendicular and parallel structure directions (e.g. the wood grain direction). We view our model as a special case of an abstract friction model that produces a cone based on state information, specifically the relationship between structure directions. We show how our model can be integrated into LCP and NCP-based simulators using different solvers with both explicit and fully implicit time-integration. The focus of our work is on symmetric friction cones, and we, therefore, demonstrate a variety of simulation scenarios where the friction structure directions play an important part in the resulting motions. Consequently, authoring of friction using our model is intuitive and we demonstrate that our model is compatible with standard authoring practices, such as texture mapping.

Private Copy of Manuscript download

Physics-based animation is becoming increasingly popular due to its use in computer games, for producing special effects in movies, and as part of surgical simulation systems. Over the past decade the field has matured, and today there is a wealth of simulation methods solving many simulation problems. There is a vast amount of examples where physics-based animation is used, e.g., rigid bodies stumbling around (The Hulk, Grand Turismo, Medal of Honor, Half-Life ); skin and muscle deformations (Shrek, The Nutty Professor, Jurassic Park, the Mummy ); water splashing (Shrek, Titanic, Finding Nemo ); jelly blobs dancing around (Flopper); death-like animations (Hitman); hair blowing in the wind or bending due to motion of a character (Monsters Inc ); cloth moving (Monsters Inc ); and melting robots and cyborg parts of characters (Terminator3, Treasure Island ), just to mention a few.

There is an ongoing quest for exploiting physics-based animation. While it was a computationally heavy burden 10–20 years ago to kinetically animate a linked character consisting of no more than a handful of limbs [Wellman, 1993], today this is considered a trivial task due to the large increase of computer power. The increase of computer power allows us to simulate increasingly complex scenarios, in an apparently never-ending spiral, and it appears that there will always be a demand for faster methods, with more details, larger scenes, etc. Nevertheless, a major part of such animations will always be a physical model of the world constructed from the laws of physics and solved numerically. A major part of the physical models and their numerical solutions were developed before the twentieth century. Clever algorithms for solving geometrically-complex systems are less than 40 years old and still part of a very active research field.

The widespread use of physics-based animation, especially in the entertainment industry, has resulted in a strong demand for education in these topics, both from students and industry. Quite a few books on computer animation such as [Watt et al., 1992, Parent, 2001] and computer games such as [Eberly, 2000, Eberly, 2003b] introduce the reader to physics-based animation, but these books often refrain from covering advanced topics, either because they only consider real-time computations, or because of space limitations. The details of the simulation methods used in big commercial productions are usually not accessible by the general public since they are kept as business secrets. Most of the advanced literature on these topics is written as scientific papers addressing specific problems e.g., [Baraff et al., 2003a, Osher et al., 2003, Bergen, 2003a], which requires a broad basic education in physics, mathematics, and computer science to read and understand. Finally, most “tricks of the trade” are not published in scientific papers but learned through experience and word of mouth in the graphics community.

These are the reasons that motivated us to write an advanced textbook on physics-based animation with a focus on the theory. We wanted to create an advanced textbook for computer science graduate students, teaching them the basis while at the same time teaching them the thin red line that separates the different simulation methods. Our pedagogical goal is to prepare readers for a commercial or academic career on the subject of physics-based animation, rather than to produce yet another code-hacker for the gaming industry.

Almost all of the methods described in this book have been tested as the implementation in the open-source project OpenTissue. Major parts of this book and the OpenTissue project have been used in our classes during the last two years, from which we have gotten much feedback, and for which we are very grateful. Special thanks should be given to Andrè Tischer Poulsen, Katrine Hommelhoff Jensen, Anders Holbøll, Micky Kelager Christensen, and Anders Fleron who have served as our student reading committee. Andrè Tischer has also given invaluable help with improving the visual appeal of many of the figures. We would also like to thank our ever-patient publisher Jenifer Niles from Charles River Media, together with her anonymous reviewing panel and technical writers. Finally, we wish to thank our respective families, without whose support, we would not have been able to complete this project.

30th September 2005
Kenny Erleben, Jon Sporring, Knud Henriksen, and Henrik Dohlmann.

We present a framework for the simulation of rigid and deformable bodies in the presence of contact and friction. Our method is based on a non-smooth Newton iteration that solves the underlying nonlinear complementarity problems (NCPs) directly. This approach allows us to support nonlinear dynamics models, including hyperelastic deformable bodies and articulated rigid mechanisms, coupled through a smooth isotropic friction model. The fixed-point nature of our method means it requires only the solution of a symmetric linear system as a building block. We propose a new complementarity preconditioner for NCP functions that improves convergence, and we develop an efficient GPU-based solver based on the conjugate residual (CR) method that is suitable for interactive simulations. We show how to improve robustness using a new geometric stiffness approximation and evaluate our method’s performance on a number of robotics simulation scenarios, including dexterous manipulation and training using reinforcement learning.