Local Optimization for Robust Signed Distance Field Collision

Authors

Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Zach Corse

Abstract

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.

Paper download

The Matchstick Model for Anisotropic Friction Cones

erleben.ea19

Authors

Kenny Erleben, Miles Macklin, Sheldon Andrews, and Paul G. Kry.

Abstract

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.

Paper download
Get code from  github

Free textbook: Physics-Based Animation

Private Copy of Manuscript download

Authors

Kenny Erleben, Jon Sporring, Knud Henriksen, and Henrik Dohlmann.

Preface

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.

Non-Smooth Newton Methods for Deformable Multi-Body Dynamics

Teaser

Authors

Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Viktor Makoviychuk.

Abstract

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.

Paper download
ArXiv download

High fidelity simulation of corotational linear FEM for incompressible materials

Teaser

Authors

Mihai Frâncu, Arni Asgeirsson, and Kenny Erleben.

Abstract
We present a novel method of simulating incompressible materials undergoing large deformation without locking artifacts. We apply it for simulating silicone soft robots with a Poisson ratio close to 0.5. The new approach is based on the mixed finite element method (FEM) using a pressure-displacement formulation; the deviatoric deformation is still handled in a traditional fashion. We support large deformations without volume increase using the corotational formulation of linear elasticity. Stability is ensured by an implicit integration scheme which always reduces to a sparse linear system. For even more deformation accuracy we support higher-order simulation through the use of Bernstein-Bézier polynomials.

Paper download

A Validated Physical Model For Real-Time Simulation of Soft Robotic Snakes

Authors
Renato Gasoto, Miles Macklin, Xuan Liu, Yinan Sun, Kenny Erleben, Cagdas Onal1, and Jie Fu

Abstract
In this work we present a framework that is capable of accurately representing soft robotic actuators in a multiphysics environment in real-time. We propose a constraint-based dynamics model of a 1-dimensional pneumatic soft actuator that accounts for internal pressure forces, as well as the effect of actuator latency and damping under inflation and deflation and demonstrate its accuracy a full soft robotic snake with the composition of multiple 1D actuators. We verify our model’s accuracy in static deformation and dynamic locomotion open-loop control experiments. To achieve real-time performance we leverage the parallel computation power of GPUs to allow interactive control and feedback.

Author Copy download

GRIT: General Robust Interface Tracking

Open Source Software for General Robust Interface Tracking by H2020 MSCA-ITN RAINBOW



https://h2020-msca-itn-rainbow.github.io/

Data Driven Inverse Kinematics of Soft Robots using Local Models

Author Fredrik Holsten, Morten Pol Engell-Nørregård, Sune Darkner, and Kenny Erleben

Abstract
Soft robots are advantageous in terms of flexibility, safety and adaptability. It is challenging to find efficient computational approaches for planning and controlling their motion. This work takes a direct data-driven approach to learn the kinematics of the three-dimensional shape of a soft robot, by using visual markers. No prior information about the robot at hand is required. The model is oblivious to the design of the robot and type of actuation system. This allows adaptation to erroneous manufacturing. We present a highly versatile and inexpensive learning cube environment for collecting and analysing data. We prove that using multiple, lower order models of data opposed to one global, higher order model, will reduce the required data quantity, time complexity and memory complexity significantly without compromising accuracy. Further, our approach allows for embarrassingly parallelism. Yielding an overall much more simple and efficient approach.

ICRA 2019 Authors copy

Code Github

Automated Acquisition of Anisotropic Friction

AuthorKeno Dreßel, Kenny Erleben, Paul Kry and Sheldon Andrews

Abstract
Automated acquisition of friction data is an interesting approach to more successfully bridge the reality gap in simulation than conventional mathematical models. To advance this area of research, we present a novel inexpensive computer vision platform as a solution for collecting and processing friction data, and we make available the open source software and data sets collected with our vision robotic approach. This paper is focused on gathering data on anisotropic static friction behavior as this is ideal for inexpensive vision approach we propose. The data set and experimental setup provide a solid foundation for a wider robotics simulation community to conduct their own experiments.

CRV 2019Authors copy

Code github

Solving inverse kinematics using exact Hessian matrices

Author
Kenny Erleben and Sheldon Andrews

Abstract
Inverse kinematics (IK) is a central component of systems for motion capture, character animation, robotics motion planning and control. The field of computer graphics has developed fast stationary point methods, such as the Jacobian Transpose method and cyclic coordinate descent. Most of the work that uses Newton’s method and its variants avoids directly computing the Hessian, and instead approximations are sought, such as in the BFGS class of solvers.

In this work, we present a numerical method for computing the exact Hessian of an IK system with prismatic, revolute, and spherical joints. For the latter, formulations are presented for joints parameterized by Euler angles which can be represented for instance by using quaternions. Our method is applicable to human skeletons in computer animation applications and some, but not all, robots. Our results show that using exact Hessians can give performance advantages and higher accuracy compared to standard numerical methods used for solving IK problems. Furthermore, we provide code that allows other researchers to plug-in exact Hessians in their own work with little effort.

CaG paper

Code github