pith. sign in

arxiv: 2506.14097 · v2 · submitted 2025-06-17 · 💻 cs.RO · cond-mat.soft· physics.comp-ph

Smooth-Rigid-Body Contact as a ReLCP: A Recursively Generated Linear Complementarity Problem

Bryce Palmer , Hasan Metin Aktulga , Tong Gao This is my paper

Pith reviewed 2026-05-19 09:58 UTC · model grok-4.3

classification 💻 cs.RO cond-mat.softphysics.comp-ph
keywords rigid body contactlinear complementarity problemnonsmooth dynamicssmooth geometrytime steppingnonpenetrationstrict convexityadaptive constraints
0
0 comments X

The pith

Smooth rigid-body contact is recast as a recursively generated linear complementarity problem that adds constraints only when needed to stop penetration.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reformulates frictionless contact between smooth rigid bodies by beginning with one shared-normal signed-distance constraint and then generating additional unilateral constraints only when a trial velocity update would cause the smooth surfaces to interpenetrate. The resulting sequence of linear complementarity problems grows adaptively until nonpenetration is satisfied to a fixed tolerance. For strictly convex bodies and sufficiently small time steps, the process is proved to stop after finitely many steps and to produce a unique velocity. In the limit of vanishing time steps the recursion collapses back to the classical single-constraint formulation, preserving consistency with the underlying differential variational inequality. The approach therefore works directly on smooth geometry and avoids the rapid growth in constraint count that accompanies finer surface tessellations or multi-sphere proxies.

Core claim

Contact between smooth rigid bodies is expressed as a recursively generated linear complementarity problem. An initial single-constraint shared-normal signed-distance LCP is solved; if the resulting discrete-time velocity would violate nonpenetration of the underlying smooth surfaces, an additional unilateral constraint is appended and the LCP is resolved. This augmentation continues until every smooth-surface pair satisfies the overlap tolerance. When the bodies are strictly convex, the initial state is overlap-free, and the time step is small enough, the recursion terminates after a finite number of steps and the velocity update is unique. In the small-time-step limit the procedure reduces

What carries the argument

The recursively generated linear complementarity problem (ReLCP), which starts from a classical single-constraint SNSD LCP and adaptively augments the constraint set with new unilateral conditions whenever a predicted update violates smooth-surface nonpenetration.

If this is right

  • Nonpenetration is enforced directly on the smooth geometry to a user-specified tolerance without introducing discretization-induced surface roughness.
  • Active constraint counts remain far lower than those required by tessellated or multi-sphere proxy models as geometric fidelity increases.
  • Large time steps remain stable for colliding ellipsoids, compacting suspensions, and taut chainmail networks while still respecting the overlap tolerance.
  • In the small-time-step limit the method recovers the classical single-constraint SNSD LCP and its consistency properties with the continuous differential variational inequality.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same adaptive-augmentation idea could be tested on bodies whose curvature changes sign to see where the finite-termination guarantee fails.
  • Because the method works with any smooth surface representation that supplies a signed-distance query, it could be paired with implicit or level-set geometry without retessellation.
  • The reduction to a single LCP for tiny steps suggests that the extra computational work appears only when the time step is large relative to local curvature, offering a natural accuracy-cost tradeoff.

Load-bearing premise

The bodies are strictly convex, the initial configuration is overlap-free, and the time step is small enough that the recursive addition of constraints always stops after finitely many steps.

What would settle it

Execute the recursion on a pair of strictly convex ellipsoids with a deliberately large time step and check whether the number of added constraints grows without bound or whether the final velocity becomes non-unique.

Figures

Figures reproduced from arXiv: 2506.14097 by Bryce Palmer, Hasan Metin Aktulga, Tong Gao.

Figure 1
Figure 1. Figure 1: 2D depictions of collision constraints (solid red lines) generated by three approaches: (a) Single-constraint “deepest-point” method, [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Snapshots from a toy simulation of three spherocylinders capsules, initially overlapping, with their collision constraints shown in red. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Temporal evolution of twp ellipsoids as they collide and subsequently slide past one another due to constant, equal-and-opposite external [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Performance comparison of ReLCP and multi-sphere (LCP–MS) collision resolution for a suspension of 10,000 ellipsoids (aspect ratio [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Growth simulation of a bacterial colony modeled as spherocylinders of length [PITH_FULL_IMAGE:figures/full_fig_p016_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Simulation of a chainmail-like network composed of interlaced rigid rings arranged in a two-dimensional lattice and subject to a smooth [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
read the original abstract

This paper reformulates complementarity-based time-stepping for frictionless nonsmooth contact between smooth rigid bodies as a recursively generated linear complementarity problem (ReLCP), involving a sequence of LCPs of increasing dimension. Starting from a classical single-constraint shared-normal signed-distance (SNSD) LCP, the method adds unilateral constraints only when the discrete-time update predicted by the current contact set would violate nonpenetration of the underlying smooth surfaces. The resulting procedure acts directly on smooth geometry, enforces nonpenetration to a prescribed tolerance, and avoids the oversampling inherent to proxy-surface contact models such as tessellations or multi-sphere decompositions, for which improved geometric fidelity can drive rapid growth in constraint count and cost. For strictly convex bodies, we prove that an initially overlap free configuration with sufficiently small timestep sizes, imply finite termination of the adaptive augmentation, and yield a unique discrete-time velocity update. In the small timestep limit and for any fixed overlap-free discrete state with a fixed geometric overlap tolerance, we prove that the recursion terminates after the initial solve, reducing the method to the classical single-constraint SNSD LCP and retaining the usual consistency of complementarity time-stepping with the underlying differential variational inequality. Numerical tests on colliding ellipsoids, compacting ellipsoid suspensions, growing bacterial colonies, and taut chainmail networks demonstrate stable large-timestep behavior, bounded interpenetration without discretization-induced surface roughness, and substantial reductions in both active constraint counts and runtime relative to representative discrete-surface complementarity formulations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The paper reformulates frictionless nonsmooth contact for smooth rigid bodies as a recursively generated linear complementarity problem (ReLCP). It starts from a single-constraint shared-normal signed-distance (SNSD) LCP and adaptively augments the constraint set only when a predicted discrete-time update would violate nonpenetration of the underlying smooth surfaces. For strictly convex bodies, the authors prove finite termination of the adaptive augmentation and uniqueness of the velocity update when the initial configuration is overlap-free and the timestep is sufficiently small; they further show that the recursion collapses to the classical single-constraint SNSD LCP in the small-timestep limit. Numerical demonstrations on colliding ellipsoids, compacting suspensions, bacterial colonies, and chainmail networks report stable large-timestep behavior, bounded interpenetration, and substantial reductions in active constraint count and runtime relative to discretized-surface baselines.

Significance. If the finite-termination and uniqueness results hold, the work supplies a theoretically grounded route to direct smooth-geometry contact that avoids both the geometric error of coarse proxies and the combinatorial cost of high-resolution tessellations or multi-sphere decompositions. The explicit reduction to standard SNSD LCP in the small-timestep regime preserves consistency with existing differential variational inequality theory, while the reported runtime and constraint-count gains on the four example suites indicate practical utility for robotics and multibody simulation.

major comments (1)
  1. [§3] §3 (Finite termination and uniqueness): the proofs establish finite augmentation and uniqueness only under an unquantified 'sufficiently small' timestep whose dependence on local curvature radii and the fixed geometric overlap tolerance is not made explicit. No scaling relation or computable bound for this threshold is supplied, nor is it verified that the timestep sizes used in the ellipsoid-collision and chainmail experiments lie below the implied dt*. This assumption is load-bearing for the central claims of finite termination and uniqueness.
minor comments (3)
  1. [§2.2] The abstract and §2.2 refer to 'geometric overlap tolerance' as a fixed parameter, yet no sensitivity study or recommended range relative to body size or curvature is provided.
  2. [Figures 4 and 6] Figure 4 (ellipsoid suspension) and Figure 6 (chainmail) would benefit from an additional panel showing the evolution of active constraint count versus time for both ReLCP and the baseline discrete-surface method.
  3. [§2.1] Notation: the distinction between the continuous-time signed-distance function and its discrete-time counterpart is introduced in §2.1 but reused without redefinition in the proof of the small-timestep limit; a brief reminder would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and constructive criticism. We address the single major comment point by point below, with an honest assessment of what can be strengthened in revision.

read point-by-point responses

  1. Referee: [§3] §3 (Finite termination and uniqueness): the proofs establish finite augmentation and uniqueness only under an unquantified 'sufficiently small' timestep whose dependence on local curvature radii and the fixed geometric overlap tolerance is not made explicit. No scaling relation or computable bound for this threshold is supplied, nor is it verified that the timestep sizes used in the ellipsoid-collision and chainmail experiments lie below the implied dt*. This assumption is load-bearing for the central claims of finite termination and uniqueness.

    Authors: We agree that the proofs in §3 rely on a 'sufficiently small' timestep without an explicit quantitative bound or scaling law expressed in terms of local curvature radii and the geometric overlap tolerance. Deriving a sharp, computable threshold is nontrivial because it depends on local Lipschitz constants of the signed-distance functions, which are geometry-specific and not uniformly controlled for arbitrary strictly convex bodies. In the revised manuscript we will insert a clarifying paragraph in §3 that (i) states the qualitative scaling (the admissible timestep shrinks with smaller minimum radius of curvature and with tighter overlap tolerance), (ii) explains why a uniform a-priori bound is difficult to obtain without additional assumptions on the bodies, and (iii) reports that all numerical examples (ellipsoid collisions and chainmail) terminated after a single augmentation step with observed interpenetration strictly below the prescribed tolerance, thereby satisfying the small-timestep hypothesis in practice. We do not claim to supply a closed-form computable dt* for arbitrary geometries. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via new recursive construction and direct proofs.

full rationale

The paper defines the ReLCP as a sequence of LCPs that augments constraints only upon predicted violation of the smooth nonpenetration condition. Finite termination and uniqueness for strictly convex bodies are claimed via direct argument from the recursion, initial overlap-free state, and sufficiently small dt; the small-dt reduction to single-constraint SNSD LCP is shown by explicit termination after the initial solve rather than by re-using the target result. No self-definitional loops, fitted inputs renamed as predictions, or load-bearing self-citations appear in the derivation chain. The central claims rest on the novel adaptive procedure and standard LCP theory applied to the new formulation, remaining independent of the results being proved.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 0 invented entities

The method introduces the ReLCP construction and relies on domain assumptions about convexity and timestep size; no new physical entities are postulated.

free parameters (1)
  • geometric overlap tolerance
    Prescribed tolerance used to decide when to add new unilateral constraints; appears as a user-chosen parameter controlling nonpenetration enforcement.
axioms (2)
  • domain assumption Bodies are strictly convex
    Invoked for the finite-termination and uniqueness proofs stated in the abstract.
  • domain assumption Initial configuration is overlap-free
    Required for the termination guarantee under small timesteps.

pith-pipeline@v0.9.0 · 5813 in / 1454 out tokens · 38133 ms · 2026-05-19T09:58:11.918587+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Pazouki, M

    A. Pazouki, M. Kwarta, K. Williams, W. Likos, R. Serban, P. Jayakumar, D. Negrut, Compliant contact versus rigid contact: A comparison in the context of granular dynamics, Phys. Rev. E 96 (2017) 042905. doi:10.1103/PhysRevE.96.042905. URL https://link.aps.org/doi/10.1103/PhysRevE.96.042905

    work page doi:10.1103/physreve.96.042905 2017

  2. [2]

    Servin, D

    M. Servin, D. Wang, C. Lacoursi `ere, K. Bodin, Examining the smooth and nonsmooth discrete element approaches to granular matter, International Journal for Numerical Methods in Engineering 97 (12) (2014) 878–902. arXiv:https://onlinelibrary.wiley.com/ doi/pdf/10.1002/nme.4612, doi:https://doi.org/10.1002/nme.4612. URL https://onlinelibrary.wiley.com/doi/...

    work page doi:10.1002/nme.4612 2014

  3. [3]

    B. I. Gavrea, M. Anitescu, F. A. Potra, Convergence of a class of semi-implicit time-stepping schemes for nonsmooth rigid multibody dynamics, SIAM Journal on Optimization 19 (2) (2008) 969–1001

    work page 2008

  4. [4]

    Anitescu, Optimization-based simulation of nonsmooth rigid multibody dynamics, Math

    M. Anitescu, Optimization-based simulation of nonsmooth rigid multibody dynamics, Math. Program. 105 (1) (2006) 113–143. doi:10. 1007/s10107-005-0590-7 . URL https://doi.org/10.1007/s10107-005-0590-7 27

    work page doi:10.1007/s10107-005-0590-7 2006

  5. [5]

    Anitescu, G

    M. Anitescu, G. D. Hart, A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction, International Journal for Numerical Methods in Engineering 60 (14) (2004) 2335–2371. arXiv:https://onlinelibrary.wiley.com/ doi/pdf/10.1002/nme.1047, doi:https://doi.org/10.1002/nme.1047. URL https://onlinelibrary.wiley.c...

    work page doi:10.1002/nme.1047 2004

  6. [6]

    Markauskas, R

    D. Markauskas, R. Ka ˇcianauskas, A. Dˇziugys, R. Navakas, Investigation of adequacy of multi-sphere approximation of elliptical particles for dem simulations, Granular Matter 12 (2010) 107–123. doi:10.1007/s10035-009-0158-y

    work page doi:10.1007/s10035-009-0158-y 2010

  7. [7]

    H ¨ohner, S

    D. H ¨ohner, S. Wirtz, H. Kruggel-Emden, V . Scherer, Comparison of the multi-sphere and polyhedral approach to simulate non-spherical particles within the discrete element method: Influence on temporal force evolution for multiple contacts, Powder Technology 208 (3) (2011) 643–656. doi:https://doi.org/10.1016/j.powtec.2011.01.003. URL https://www.science...

    work page doi:10.1016/j.powtec.2011.01.003 2011

  8. [8]

    H ¨ohner, S

    D. H ¨ohner, S. Wirtz, V . Scherer, A numerical study on the influence of particle shape on hopper discharge within the polyhedral and multi- sphere discrete element method, Powder Technology 226 (2012) 16–28. doi:https://doi.org/10.1016/j.powtec.2012.03.041. URL https://www.sciencedirect.com/science/article/pii/S0032591012002094

    work page doi:10.1016/j.powtec.2012.03.041 2012

  9. [9]

    H ¨ohner, S

    D. H ¨ohner, S. Wirtz, V . Scherer, A study on the influence of particle shape on the mechanical interactions of granular media in a hopper using the discrete element method, Powder Technology 278 (07 2015). doi:10.1016/j.powtec.2015.02.046

    work page doi:10.1016/j.powtec.2015.02.046 2015

  10. [10]

    Z. Liu, Y . Zhao, Multi-super-ellipsoid model for non-spherical particles in DEM simulation, Powder Technology 361 (2020) 190–202. doi:https://doi.org/10.1016/j.powtec.2019.09.042. URL https://www.sciencedirect.com/science/article/pii/S0032591019307697

    work page doi:10.1016/j.powtec.2019.09.042 2020

  11. [11]

    Y . You, Y . Zhao, Discrete element modelling of ellipsoidal particles using super-ellipsoids and multi-spheres: A comparative study, Powder Technology 331 (2018) 179–191. doi:https://doi.org/10.1016/j.powtec.2018.03.017. URL https://www.sciencedirect.com/science/article/pii/S0032591018302080

    work page doi:10.1016/j.powtec.2018.03.017 2018

  12. [12]

    Z. Liu, H. Ma, Y . Zhao, Comparative study of discrete element modeling of tablets using multi-spheres, multi-super-ellipsoids, and polyhe- drons, Powder Technology 390 (2021) 34–49. doi:https://doi.org/10.1016/j.powtec.2021.05.065. URL https://www.sciencedirect.com/science/article/pii/S0032591021004721

    work page doi:10.1016/j.powtec.2021.05.065 2021

  13. [13]

    D. E. Stewart, J. C. Trinkle, An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and coulomb friction, International Journal for Numerical Methods in Engineering 39 (15) (1996) 2673–2691

    work page 1996

  14. [14]

    W. Yan, S. Ansari, A. Lamson, M. A. Glaser, R. Blackwell, M. D. Betterton, M. Shelley, Toward the cellular-scale simulation of motor-driven cytoskeletal assemblies, eLife 11 (2022) e74160

    work page 2022

  15. [15]

    D. E. Stewart, Convergence of a time-stepping scheme for rigid-body dynamics and resolution of Painlev ´e’s problem, Archive for Rational Mechanics and Analysis 145 (1998) 215–260

    work page 1998

  16. [16]

    J.-S. Pang, D. E. Stewart, Di fferential variational inequalities, Mathematical Programming 113 (2) (Jun. 2008). doi:10.1007/ s10107-006-0052-x . URL https://hal.science/hal-01366027

    work page 2008

  17. [17]

    K. Erleben, Numerical methods for linear complementarity problems in physics-based animation, in: ACM SIGGRAPH 2013 Courses, SIGGRAPH ’13, Association for Computing Machinery, New York, NY , USA, 2013.doi:10.1145/2504435.2504443. URL https://doi-org.proxy1.cl.msu.edu/10.1145/2504435.2504443

    work page doi:10.1145/2504435.2504443 2013

  18. [18]

    L. Posp ´ıˇsil, Development of algorithms for solving minimizing problems with convex quadratic function on special convex sets and applica- tions, Doctoral theses, dissertations, VˇSB - Technical University of Ostrava, Fakulta elektrotechniky a informatiky Ostrava (2015)

    work page 2015

  19. [19]

    Yan, Simtoolbox, https://github.com/wenyan4work/SimToolbox, accessed: 2025-06-05 (2024)

    W. Yan, Simtoolbox, https://github.com/wenyan4work/SimToolbox, accessed: 2025-06-05 (2024)

    work page 2025

  20. [20]

    W. Yan, H. Zhang, M. J. Shelley, Computing collision stress in assemblies of active spherocylinders: Applications of a fast and generic geometric method, The Journal of Chemical Physics 150 (6) (2019) 064109. arXiv:https://pubs.aip.org/aip/jcp/article-pdf/ doi/10.1063/1.5080433/13569304/064109\_1\_online.pdf, doi:10.1063/1.5080433. URL https://doi.org/10....

    work page doi:10.1063/1.5080433/13569304/064109 2019

  21. [21]

    W. Yan, E. Corona, D. Malhotra, S. Veerapaneni, M. Shelley, A scalable computational platform for particulate Stokes suspensions, Journal of Computational Physics 416 (2020) 109524

    work page 2020

  22. [22]

    Iwasawa, A

    M. Iwasawa, A. Tanikawa, N. Hosono, K. Nitadori, T. Muranushi, J. Makino, Implementation and performance of fdps: A framework developing parallel particle simulation codes, Publications of the Astronomical Society of Japan 68 (01 2016).doi:10.1093/pasj/psw053

    work page doi:10.1093/pasj/psw053 2016

  23. [23]

    L. A. Riesen, E. Boman, K. Devine, S. Rajamanicakam, USDOE, Zoltan2 (July 2012)

    work page 2012

  24. [24]

    Baker, M

    C. Baker, M. Heroux, Tpetra, and the use of generic programming in scientific computing, Scientific Programming 20 (2) (2012) 693861

    work page 2012

  25. [25]

    Bavier, M

    E. Bavier, M. Hoemmen, S. Rajamanickam, H. Thornquist, Amesos2 and Belos: Direct and iterative solvers for large sparse linear systems, Scientific Programming 20 (2012) 241–255

    work page 2012

  26. [26]

    M. Mayr, A. Heinlein, C. Glusa, S. Rajamanickam, M. Arnst, R. Bartlett, L. Berger-Vergiat, E. Boman, K. Devine, G. Harper, M. Heroux, M. Hoemmen, J. Hu, B. Kelley, K. Kim, D. P. Kouri, P. Kuberry, K. Liegeois, C. C. Ober, R. Pawlowski, C. Pearson, M. Perego, E. Phipps, D. Ridzal, N. V . Roberts, C. Siefert, H. Thornquist, R. Tomasetti, C. R. Trott, R. S. ...

    work page arXiv 2025

  27. [27]

    R. W. Cottle, J.-S. Pang, R. E. Stone, The Linear Complementarity Problem, Society for Industrial and Applied Mathematics, 2009. arXiv: https://epubs.siam.org/doi/pdf/10.1137/1.9780898719000, doi:10.1137/1.9780898719000. URL https://epubs.siam.org/doi/abs/10.1137/1.9780898719000

    work page doi:10.1137/1.9780898719000 2009

  28. [28]

    D. E. Stewart, Rigid-body dynamics with friction and impact, SIAM Review 42 (1) (2000) 3–39. doi:10.1137/S0036144599360110. 28

    work page doi:10.1137/s0036144599360110 2000