Parallel local and implicit time stepping for triangulated rigid body dynamics

Abstract

Discrete Element Methods (DEM), i.e. the simulation of many rigid particles, suffer from very stiff differential equations plus multiscale challenges in space and time. The particles move smoothly through space until they interact almost instantaneously due to collisions. Dense and dynamic particle packings require tiny time step sizes, while free and stationary particles can advance with large time steps. The ratio of different admissible time step sizes starts to span multiple orders of magnitude once we encounter quickly moving objects and particles that settle into dense packings before they distribute again. We propose an adaptive local time stepping algorithm which identifies clusters of particles that can advance independently of each other on-the-fly, advances them optimistically in time, determines collision time stamps in space-time such that we maximise the time step sizes used, resolves the momentum exchange in the collisions implicitly, and rolls back particles upon demand.

We also propose a family of novel multiscale collision detection and resolution algorithms that can be applied to triangulated objects within implicit time stepping methods. Inspired by multigrid methods and adaptive mesh refinement, we determine collision points iteratively over a resolution hierarchy. Coarse surrogate geometry representations identify an educated guess which triangle subsets of the next finer level might yield collisions. They prune the search tree and furthermore feed conservative contact force estimates into the iterative solve behind an implicit time stepping. Implicit time stepping and non analytical shapes often yield prohibitive high compute cost for rigid body simulations. Our approach reduces the object-object comparison cost algorithmically by one to two orders of magnitude. It also exhibits high vectorisation efficiency due to its iterative nature. The implicit solve of the actual collision equations avoids particles getting locked into tiny time step sizes, the clustering yields a high concurrency level, and the acceleration techniques in combination with the local time stepping avoid unnecessary computations. This brings a scaling, implicit adaptive time stepping for DEM for real-world challenges into reach.