Methodology for Assessing Mesh-Based Contact Point Methods

Kenny Erleben

Computation of contact points is a critical sub-component of physics-based animation. The success and correctness of simulation results are very sensitive to the quality of the contact points. Hence, quality plays a critical role when comparing methods, and this is highly relevant for simulating objects with sharp edges. The importance of contact point quality is largely overlooked and lacks rigor and as such may become a bottleneck in moving the research field forward.

We establish a taxonomy of contact point generation methods and lay down an analysis of what normal contact quality implies. The analysis enables us to establish a novel methodology for assessing and studying quality for mesh-based shapes. The core idea is based on a test suite of three complex cases and a small portfolio of simple cases. We apply our methodology to eight local contact point generation methods and conclude that the selected local methods are unable to provide correct information in all cases. The immediate benefit of the proposed methodology is a foundation for others to evaluate and select the best local method for their specific application. In the longer perspective, the presented work suggests future research focusing on semi-local methods.

ACM TOG paper

Authors copy

Slides download


Local Models for Data Driven Inverse Kinematics of Soft Robots

Best Poster Prize: Authors
Fredrik Holsten, Sune Darkner, Morten P. Engell-Nørregård, and Kenny Erleben

Soft robots are attractive because they have the potential of being safer, faster and cheaper than traditional rigid robots. If we can predict the shape of a soft robot for a given set of control parameters, then we can solve the inverse problem: to find an optimal set of control parameters for a given shape. This work takes a data-driven approach to create multiple local inverse models. This has two benefits: (1) We overcome the reality gap and (2) we gain performance and naive parallelism from using local models. Furthermore, we empirically prove that our approach outperforms a higher order global model.

SCA 2018 Meta Data download

SCA Poster Abstract download

Get Open Source code

Chunked Bounding Volume Hierarchies for Fast Digital Prototyping Using Volumetric Meshes

Robert Schmidtke and Kenny Erleben

We present a novel approach to using Bounding Volume Hierarchies (BVHs) for collision detection of volumetric meshes for digital prototyping based on accurate simulation. In general, volumetric meshes contain more primitives than surface meshes, which in turn means larger BVHs. To manage these larger BVHs, we propose an algorithm for splitting meshes into smaller chunks with a limited-size BVH each. Limited-height BVHs make guided, all-pairs testing of two chunked meshes well-suited for GPU implementation. This is because the dynamically generated work during BVH traversal becomes bounded. Chunking is simple to implement compared to dynamic load balancing methods and can result in an overall two orders of magnitude speedup on GPUs. This indicates that dynamic load balancing may not be a well suited scheme for the GPU. The overall application timings showed that data transfers were not the bottleneck. Instead, the conversion to and from OpenCL friendly data structures was causing serious performance impediments. Still, a simple OpenMP acceleration of the conversion allowed the GPU solution to beat the CPU solution by 20 percent. We demonstrate our results using rigid and deformable body scenes of varying complexities on a variety of GPUs.

Authors copy: download
IEEE TVCG: version
Supplementary: code

Jobs: Marie Curie PhD Fellowships Open for Applications

We are searching for two Marie Curie PhD fellows interested in pushing the boundaries of rapid biomechanics simulation for personalized clinical design with us.

Many more possibilities in the RAINBOW network

Join us now and be part of changing the way simulation is used in the clinical process.

OpenTissue Resurrected

Kenny Erleben

OpenTissue has as of February 2018 been relocated to Github. This have been on the agenda for some time, but was greatly promoted by the disappearance of the image server that hosted the project for many years. OpenTissue is a collection of generic algorithms and data structures for rapid development of interactive modeling and simulation. It is the open source library that accompanies the textbook “Physics-based Animation”. The library was created around 2001 by the help and support of a vast number of projects and master thesis students at department of computer science; too many to mention all here. After a decade or so the library grew quite large. It evolved into a pretty high-quality code base. The library has over time influenced many other code bases around the world and is still quite advanced in terms of applying generic programming in C++. The library contains numerical methods for simulating fluids, deformable and rigid bodies as well as many methods for collision detection. Due to lack of resources we no longer provide active support for OpenTissue, but we do maintain a repository for others. The code is provided as it is. No guarantees are given. Use it at your own risk.


A Fast Linear Complementarity Problem Solver for Fluid Animation using High Level Algebra Interfaces for GPU Libraries

Michael Andersen, Sarah Niebe and Kenny Erleben

We address the task of computing solutions for a separating solid wall boundary condition model. We present a parallel, easy to implement, fluid linear complementarity problem solver. All that is needed is the implementation of linear operators, using an existing high-level sparse algebra GPU library. No low-level GPU programming is necessary. This means we can rely on the efficiency of a tried-and-tested library, requiring minimal debugging compared to writing more low level GPU kernels. The solver exploits matrix-vector products as computational building blocks. We block the matrix-vector products in a way that allows us to evaluate the products, without having to assemble the full systems. Our work shows speedup factors ranging up to two orders of magnitudes for larger grid resolutions.

Authors Copy download
Computers and Graphics version

Inverse Kinematics Problems with Exact Hessian Matrices

Kenny Erleben and Sheldon Andrews

Inverse kinematics (IK) is a central component of systems for motion capture, character animation, motion planning, and robotics control. The field of computer graphics has developed fast stationary point solvers methods, such as the Jacobian transpose method and cyclic coordinate descent. Much work with Newton methods focus on avoiding directly computing the Hessian, and instead approximations are sought, such as in the BFGS class of solvers. This paper presents a numerical method for computing the exact Hessian of an IK system with spherical joints. It 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 and supplementary details that allows researchers to plug-in exact Hessians in their own work with little effort.

Authors Copy download
Supplementary Notes download
Source Code download

%d bloggers like this: