ReLCP: Scalable Complementarity-Based Collision Resolution for Smooth Rigid Bodies

We present a complementarity-based collision resolution algorithm for smooth, non-spherical, rigid bodies. Unlike discrete surface representation approaches, which approximate surfaces using discrete elements (e.g., tessellations or sub-spheres) with constraints between nearby faces, edges, nodes, or sub-objects, our algorithm solves a recursively generated linear complementarity problem (ReLCP) to adaptively identify potential collision locations during the collision resolution procedure. Despite adaptively and in contrast to Newton-esque schemes, we prove conditions under which the resulting solution exists and the center of mass translational and rotational dynamics are unique. Because increasing the surface resolution in discrete representation methods necessitates subdividing geometry into finer elements--leading to a super-linear increase in the number of collision constraints--these approaches scale poorly with increased surface resolution. In contrast, our adaptive ReLCP framework begins with a single constraint per pair of nearby bodies and introduces new constraints only when unconstrained motion would lead to overlap, circumventing the oversampling required by discrete methods. By requiring one to two orders of magnitude fewer collision constraints to achieve the same surface resolution, we observe 10-100x speedup in densely packed applications. We validate our ReLCP method against multisphere and single-constraint methods, comparing convergence in a two-ellipsoid collision test, scalability and performance in a compacting ellipsoid suspension and growing bacterial colony, and stability in a taut chainmail network, highlighting our ability to achieve high-fidelity surface representations without su ff ering from poor scalability or artificial surface roughness. Keywords: Rigid body dynamics, Nonsmooth dynamics, Linear complementarity problem, Collision resolution, ReLCP 1. Introduction The simulation of collision and contact dynamics in rigid and flexible body systems has a rich and extensive history in scientific computing, engineering, and computer graphics. Methods for managing frictional contact and resolving collisions can be broadly categorized into three types: piecewise-smooth, smooth (penalty-based), and nonsmooth (complementarity-based) methods. Piecewise-smooth approaches focus on identifying the precise times and locations of collision events, applying instantaneous impulses to uphold the conservation of momentum. While these methods are conceptually straightforward and lend themselves well to analytical treatment, they are rarely employed in large-scale simulations.