All’s Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid Body Impact

Iterative algorithms are frequently used to resolve simultaneous impacts between rigid bodies in physical simulations. We study the broad class of such algorithms that are conservative and satisfy a minimal set of physical correctness properties, and which encompasses recent methods like Generalized Reflections as well as pairwise schemes. We fully characterize finite termination of these algorithms. The only possible failure cases can be detected, and we describe a procedure for modifying the algorithms to provably ensure termination.