Chunked Bounding Volume Hierarchies for Fast Digital Prototyping Using Volumetric Meshes


Author
Robert Schmidtke and Kenny Erleben

Abstract
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

Advertisements

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.

http://www.diku.dk/ominstituttet/ledige_stillinger/marie-curie-phd-fellows/

Many more possibilities in the RAINBOW network

http://rainbow.ku.dk/open-positions/

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

OpenTissue Resurrected

Author
Kenny Erleben

Abstract
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


Author
Michael Andersen, Sarah Niebe and Kenny Erleben

Abstract
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


Author
Kenny Erleben and Sheldon Andrews

Abstract
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

Constraint Reordering for Iterative Multi-Body Simulation with Contact


Author
Sheldon Andrews, Kenny Erleben, Paul G. Kry, Marek Teichmann
Paper download

A Fast Linear Complementarity Problem (LCP) Solver for Separating Fluid-Solid Wall Boundary Conditions


AuthorsĀ Michael Andersen, Sarah Niebe and Kenny Erleben
Abstract
We address the task of computing solutions for a separating fluid-solid wall boundary condition model. We present an embarrassingly parallel, easy to implement, fluid LCP solver. We are able to use greater domain sizes than previous works have shown, due to our new solver. 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. Any iterative sub-solver can be used. Our work shows speedup factors ranging up to 500 for larger grid sizes.

Paper download

%d bloggers like this: