Nonsmooth contact time stepping and projections

Let $d\ge 1$, $T>0$, and let $C\subseteq {\mathbb{R}}^d$ be nonempty, compact, and closed. Let $M\ge 0$. If $u_j:[0,T]\to C$ satisfies $\mathrm{\parallel }{u}_j(t)-u_j(s){\mathrm{\parallel }}_2\le M\mathrm{\mid }t-s\mathrm{\mid }(j\ge 1,s,t\in [0,T]),$ then some subsequence converges uniformly to a map $u:[0,T]\to C$ with the same Lipschitz bound.

Let $d\in \mathbb{N}$, including $d=0$. Let $C\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex, and let $P_C(y)$ denote the unique nearest point in $C$ to $y$. Then $\mathrm{\parallel }{P}_C(u)-P_C(v){\mathrm{\parallel }}_2\le \mathrm{\parallel }u-v{\mathrm{\parallel }}_2(u,v\in {\mathbb{R}}^d)\mathrm{.}$

Input a gap $q\ge 0$, velocity $v\in \mathbb{R}$, constant acceleration $a\in \mathbb{R}$, step horizon $h>0$, mass $m>0$, restitution $e\in [0,1]$, and a candidate-root budget $B\in \mathbb{N}$. Use exact real arithmetic and comparisons. Define $g(s)=q+sv+\frac{1}{2}a{s}^2$ and $w(s)=v+as$ on $[0,h]$. Return impact, free-flight, or unresolved by these instructions.

• If $q=0$ and $v<0$, return impact at $s=0$ with contact gap $0$, $v^{-}=v$, $J=-m(1+e)v^{-}$, and $v^{+}=-e{v}^{-}$.
• Otherwise form the complete candidate set $R$ of real roots of $g$. If $q=v=a=0$, set $R=\mathrm{\varnothing }$. If $a=0$ and $v\mathrm{\ne }0$, set $R=\{-q\mathrm{/}v\}$. If $a=0$, $v=0$, and $q>0$, set $R=\mathrm{\varnothing }$. If $a\mathrm{\ne }0$, put $D=v^2-2aq$: for $D<0$ set $R=\mathrm{\varnothing }$; for $D=0$ set $R=\{-v\mathrm{/}a\}$; and for $D>0$ set $R=\{(-v-\sqrt{D})\mathrm{/}a,(-v+\sqrt{D})\mathrm{/}a\}$, with duplicate values removed. If $\mathrm{\mid }R\mathrm{\mid }>B$, return unresolved. From $R$, retain exactly the values $s$ satisfying $0<s\le h$ and $w(s)<0$, and order them increasingly.
• If the retained list is nonempty, take its least value $s$, set $v^{-}=w(s)$, $J=-m(1+e)v^{-}$, and $v^{+}=-e{v}^{-}$, and return impact with time $s$, contact gap $0$, impulse $J$, and post-impact velocity $v^{+}$.
• If the retained list is empty, compute the minimum of $g$ on $[0,h]$ by evaluating its two endpoints and, when $a>0$ and $-v\mathrm{/}a\in (0,h)$, its vertex $-v\mathrm{/}a$. If this minimum is negative, return unresolved; otherwise return free-flight with endpoint $(g(h),w(h))$ and impulse $0$.

The candidate set contains every root of the nonzero polynomial $g$, so the retained list is complete. The vertex check certifies nonpenetration over the whole step, including a grazing zero. The procedure stops after this first event and returns at the event time; it does not integrate the post-impact mode, sustained contact, or repeated impacts. A numerical implementation that cannot certify an exact comparison returns unresolved.

Let two spheres of radii $r_1,r_2>0$ and masses $m_1,m_2>0$ have centers $q_1,q_2\in {\mathbb{R}}^d$ at contact, so $\mathrm{\parallel }{q}_1-q_2{\mathrm{\parallel }}_2=r_1+r_2$. Let $n=(q_1-q_2)\mathrm{/}(r_1+r_2)$ be the unit normal pointing from center $2$ to center $1$. Suppose the pre-impact relative normal velocity is $v_n=⟨v_1^{-}-v_2^{-},n⟩<0$. For prescribed restitution $e\in [0,1]$, put $\alpha =\frac{1}{m_1}+\frac{1}{m_2},J=-\frac{(1+e)v_n}{\alpha },v_1^{+}=v_1^{-}+\frac{J}{m_1}n,v_2^{+}=v_2^{-}-\frac{J}{m_2}n\mathrm{.}$ Then $J>0$, total linear momentum is conserved, the post-impact relative normal velocity is $-e{v}_n$, each tangential velocity is unchanged, and $K^{+}-K^{-}=-\frac{(1-e^2)v_n^2}{2(1\mathrm{/}{m}_1+1\mathrm{/}{m}_2)}\le 0,$ where $K^{\pm }=\frac{1}{2}{m}_1\mathrm{\parallel }{v}_1^{\pm }{\mathrm{\parallel }}_2^2+\frac{1}{2}{m}_2\mathrm{\parallel }{v}_2^{\pm }{\mathrm{\parallel }}_2^2$. This is a single frictionless binary impulse law; it asserts no existence or uniqueness for simultaneous or frictional multi-contact.

Let $d\in \mathbb{N}$, including $d=0$. Let $C\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex. If $y\in {\mathbb{R}}^d$, $\epsilon \ge 0$, and $p\in C$ satisfy ${\sup }_{z\in C}⟨y-p,z-p⟩\le {\epsilon }^2,$ then $\mathrm{\parallel }p-P_C(y){\mathrm{\parallel }}_2\le \epsilon$.

For any resolved output of First-impact step for a one-dimensional unilateral contact, let $q_{\ast }$ be the reported gap (zero at an impact, the free-flight endpoint gap otherwise), let $J$ be the reported impulse, and let $v_{\ast }$ be the reported endpoint velocity. Then $q_{\ast }\ge 0$, $J\ge 0$, and $q_{\ast }J=0$. On a free-flight branch, $J=0$ and $m{v}_{\ast }=mv+mah$. On an impact branch at time $s$, with incoming velocity $v^{-}=v+as$, the post-impact velocity satisfies $m{v}^{+}=m{v}^{-}+J$ and $\frac{1}{2}m(v^{+}{)}^2-\frac{1}{2}m(v^{-}{)}^2=-\frac{1}{2}m(1-e^2)(v^{-}{)}^2\le 0.$ When $a=0$, the full resolved step has nonincreasing kinetic energy. For $a\mathrm{\ne }0$, the displayed energy statement concerns only the instantaneous impact jump; work during free flight is not covered by it.

Use the Euclidean norm on the full state $z=(q_1,\dots ,q_P,v_1,\dots ,v_P)$ of $P\ge 2$ spheres in ${\mathbb{R}}^d$. Fix a pair $i<j$, positive masses $m_i,m_j$, positive radii $r_i,r_j$, and a fixed restitution coefficient $e\in [0,1]$. Put $d_{ij}=q_i-q_j,n(z)=\frac{d_{ij}}{\mathrm{\parallel }{d}_{ij}{\mathrm{\parallel }}_2},\gamma (z)=\mathrm{\parallel }{d}_{ij}{\mathrm{\parallel }}_2-r_i-r_j,$ $\alpha =m_i^{-1}+m_j^{-1},\kappa =\frac{1+e}{\alpha },\beta =\sqrt{m_i^{-2}+m_j^{-2}}\mathrm{.}$ Extend the binary reset formula of Impulse, momentum, and kinetic-energy laws for an isolated frictionless sphere impact to every state with $d_{ij}\mathrm{\ne }0$ by setting $J(z)=-\kappa ⟨v_i-v_j,n(z)⟩$, replacing $v_i$ by $v_i+J(z)n(z)\mathrm{/}{m}_i$ and $v_j$ by $v_j-J(z)n(z)\mathrm{/}{m}_j$, and leaving all other coordinates unchanged. Denote this time-independent reset extension by $R(z)$.

The functions $\gamma ,n,R$ are $C^1$ on the open set $d_{ij}\mathrm{\ne }0$. For two states $z,z^{\mathrm{\prime }}$ with both pair distances at least $\sigma >0$ and both relative velocity norms at most $V\ge 0$, $\mathrm{\mid }\gamma (z)-\gamma (z^{\mathrm{\prime }})\mathrm{\mid }\le \sqrt{2}\mathrm{\parallel }z-z^{\mathrm{\prime }}{\mathrm{\parallel }}_2,\mathrm{\parallel }n(z)-n(z^{\mathrm{\prime }}){\mathrm{\parallel }}_2\le \frac{2\sqrt{2}}{\sigma }\mathrm{\parallel }z-z^{\mathrm{\prime }}{\mathrm{\parallel }}_2,$ $\mathrm{\parallel }R(z)-R(z^{\mathrm{\prime }}){\mathrm{\parallel }}_2\le L_R\mathrm{\parallel }z-z^{\mathrm{\prime }}{\mathrm{\parallel }}_2,L_R:=1+\sqrt{2}\beta \kappa (1+\frac{4V}{\sigma })\mathrm{.}$ These pairwise bounds do not require a convex collision-free state set. Along a differentiable smooth segment with $q_k^{\mathrm{\prime }}=v_k$, $\frac{d}{dt}\gamma (z(t))=⟨n(z(t)),v_i(t)-v_j(t)⟩\mathrm{.}$ The normal bound $2\mathrm{/}\sigma$ applies to differences of the relative vectors $d_{ij}$; its full-state version includes the factor $\sqrt{2}$. This extension does not assert that an approximate state is exactly at contact or that an event exists.

Inputs. A dimension $d\ge 1$; $P\ge 2$ spheres with centers $q_i$, velocities $v_i$, masses $m_i>0$, radii $r_i>0$ and fixed restitution coefficients $e_{ij}\in [0,1]$; an initial state and horizon $T>0$; a positive time-bracket tolerance ${ϵ}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}$, a separate positive guard-residual tolerance ${ϵ}_{\mathrm{g}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{d}}$, an event-separation bound $\delta >0$, a certified finite event-count bound $N_{\mathrm{e}\mathrm{v}\mathrm{t}}\in \mathbb{N}$, an event budget $B\in \mathbb{N}$, an endpoint policy ${\pi }_T\in \{\mathtt{\text{include}},\mathtt{\text{pre-impact}}\}$, and a finite-budget certificate provider. The exact smooth-mode reference dynamics are $q_i^{\mathrm{\prime }}=v_i,v_i^{\mathrm{\prime }}=F_i(t,q,v),$ where $F=(F_1,\dots ,F_P)$ is a specified $C^1$ force field on an open neighborhood of an admitted compact tube. The exact reference initial state is nonpenetrating: ${\gamma }_{ij}(0):=\mathrm{\parallel }{q}_i(0)-q_j(0){\mathrm{\parallel }}_2-r_i-r_j\ge 0$ for every pair. A completed provider must certify that the exact reference states remain nonpenetrating on each smooth segment and after every exact reset; a failed or undecidable nonpenetration check returns unresolved. Throughout each certified incoming/outgoing tube every pair distance is at least a stated $\sigma >0$. The provider supplies finite relative-velocity bounds $V$ and state/field bounds wherever they are used below.

The provider is an explicit admissible input, not an automatically constructed oracle for arbitrary $C^1$ fields. It must supply the following valid data, with any failed or undecidable certificate test returning unresolved.

1. From the last reported reset time $t_{\ast }$, supply a continuous accumulated dense reconstruction $U$. For a selected event with bracket $[a,b]$, let $X^{-}$ be the exact incoming smooth-mode continuation launched from the aligned reference state at $t_{\ast }$, and let ${\tilde{X}}^{-}$ be the exact solution of the same smooth field launched from the reported state there. Certify both continuations through $b$, including the part after the true event $\tau$. Supply $E\ge \mathrm{\parallel }{\tilde{X}}^{-}(t_{\ast })-X^{-}(t_{\ast }){\mathrm{\parallel }}_2$ (initially $E=0$) and a uniform bound $\mathrm{\parallel }U(t)-{\tilde{X}}^{-}(t){\mathrm{\parallel }}_2\le {\eta }_{\mathrm{l}\mathrm{o}\mathrm{c}}$ for every $t\in [t_{\ast },b]$. With $H=b-t_{\ast }$, supply a state-Lipschitz constant $L$ and the common solution/tube hypotheses of A Lipschitz ODE mode flow is stable to its initial state on a tube on this whole interval, and use ${\eta }_{\mathrm{r}\mathrm{e}\mathrm{f}}={\eta }_{\mathrm{l}\mathrm{o}\mathrm{c}}+e^{LH}E$ as the uniform bound relative to $X^{-}$ through $b$. In a certified no-event branch replace $b$ by $T$. A finite cover of certified convex mode tubes may be used with its propagated bounds. A Jacobian bound on a nonconvex compact set alone is not a substitute. The continuation $X^{-}$ agrees with the incoming reference path up to $\tau$; after $\tau$ it is an auxiliary smooth trajectory, not the reset hybrid path. It need not be nonpenetrating after $\tau$, but must satisfy the stated separation and field/tube bounds.

2. For every pair $i<j$, exact-reference guard enclosures for ${\gamma }_{ij}(t)=\mathrm{\parallel }{q}_i(t)-q_j(t){\mathrm{\parallel }}_2-r_i-r_j$, and a certificate covering the whole physical smooth prefix from $t_{\ast }$ through the next reference event, or through $T$ if there is no next event, that proves ${\gamma }_{ij}\ge 0$ throughout and accounts for every possible zero. Every zero is either the just-processed segment-start root for that pair (which may be ignored once) or a candidate root bracket satisfying item 3; any other possible zero, including a grazing or zero-speed zero, or any possible negative guard value returns unresolved. At the initial simulation time, a zero must be processed as an enabled incoming root or the result is unresolved. Thus a no-event result requires certified nonpenetration and exclusion of every unlisted zero over the whole interval, not merely exclusion of incoming roots. A sufficient explicit sampling assumption may replace a range cover only when its stated variation/domain assumptions justify the same exclusion. Endpoint signs or an unsuccessful sign scan alone do not certify absence. Dense-guard enclosures must include the state-error inflation $\sqrt{2}{\eta }_{\mathrm{r}\mathrm{e}\mathrm{f}}$ as well as guard-evaluation and rounding error; the bound follows from Sphere-contact guards, normals and binary resets have explicit tube bounds. For candidate localization these dense enclosures refer to $X^{-}$ from item 1. The nonpenetration requirement concerns the physical reference hybrid path; it does not prohibit a negative incoming-continuation guard after its first event. Require the selected continuation root to match the earliest unprocessed physical reference event.

3. For each candidate event, a bracket $t_{\ast }\le a\le b\le T$ containing exactly one root $\tau$ of the selected incoming-continuation guard ${\gamma }_{ij}^{-}(t)=\mathrm{\parallel }{q}_i^{-}(t)-q_j^{-}(t){\mathrm{\parallel }}_2-r_i-r_j$, with $b-a\le {ϵ}_{\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}}$ and $b-a<\delta \mathrm{/}3$. On the entire bracket, certify the incoming inequality ${\dot{\gamma }}_{ij}^{-}(t)\le -\nu <0$, not just a derivative value at its root. Supply disjoint ordering certificates identifying the unique earliest event among all pairs. If $b=T$, certify whether the exact root is $\tau =T$; an undecided endpoint equality returns unresolved. A grazing/uncertain derivative, ambiguous overlap or simultaneous multi-contact is unresolved; lexicographic inspection does not settle physical simultaneous impacts.

4. At $\widehat{\tau }=b$, a certified bound ${ϵ}_{\mathrm{o}\mathrm{b}\mathrm{s}}\ge \mathrm{\mid }{\gamma }_{ij}(\widehat{\tau },U(\widehat{\tau }))\mathrm{\mid }$ with ${ϵ}_{\mathrm{o}\mathrm{b}\mathrm{s}}\le {ϵ}_{\mathrm{g}\mathrm{u}\mathrm{a}\mathrm{r}\mathrm{d}}$. The provider includes all evaluation errors in this bound. If $a=b$, the root certificate gives $\tau =a=b$; set the lag bound $\mathrm{\Delta }=0$. If $a<b$, set $\mathrm{\Delta }:=\min \{b-a,\frac{\sqrt{2}{\eta }_{\mathrm{r}\mathrm{e}\mathrm{f}}+{ϵ}_{\mathrm{o}\mathrm{b}\mathrm{s}}}{\nu }\},$ the nonnegative lag bound supplied by A transverse hybrid event time is stable under dense-output and root error using the continuation bound from item 1 on the whole bracket. Require certified bounds $M^{-},M^{+}$ for the incoming/outgoing fields through this lag, and all remaining reset-domain and common outgoing solution/tube hypotheses of Reset and smooth-mode flow propagate a transverse event-time error. Include the incoming continuation through $b$ in these checks. For the selected pair use the state-reset bound $L_R$ from Sphere-contact guards, normals and binary resets have explicit tube bounds, with a velocity bound valid for both compared reset inputs. This reset has no explicit time dependence. If the reset formula is evaluated inexactly, the computed full-state output $\widehat{R}(U(b))$ must come with a separate ${ϵ}_R\ge 0$ satisfying $\mathrm{\parallel }\widehat{R}(U(b))-R(U(b)){\mathrm{\parallel }}_2\le {ϵ}_R$, where the norm is on the full state $(q,v)$; for an exact reset set ${ϵ}_R=0$.

5. A certificate that the matched isolated exact events have separation at least $\delta$ and count at most $N_{\mathrm{e}\mathrm{v}\mathrm{t}}$ under the input endpoint policy. For an exact event at $T$, policy include processes the reset and counts it; policy pre-impact reports the endpoint before reset and excludes that endpoint event from the processed-event count. Process an initial enabled root at most once. Missing endpoint/count/separation bookkeeping is unresolved. In particular $e=0$ does not establish another isolated transverse event after the reset.

Procedure. Initialize the current reported time $t_{\ast }=0$, current state to the input initial state, aligned-start error $E=0$, accepted-event count $j=0$, and an empty output ledger. While $t_{\ast }<T$, request the provider certificates for every unordered pair on the entire remaining horizon $[t_{\ast },T]$, inspecting the pair list in increasing lexicographic order. If the provider certifies no further zero except the permitted just-processed segment-start root, with nonpenetration and no unlisted zero through $T$, append the segment, its error bound and certificates, and return complete. Otherwise select the certified unique earliest pair and its bracket $[a,b]$, with upper endpoint $\widehat{\tau }=b$. If the provider certifies $\tau =T$ and ${\pi }_T=\mathtt{\text{pre-impact}}$, append the incoming segment through $T$ and return complete with the pre-impact endpoint; do not apply a reset or increment $j$. If $j\ge B$ or $j\ge N_{\mathrm{e}\mathrm{v}\mathrm{t}}$, return unresolved with the certified partial trajectory. Otherwise evaluate the binary impulse formula of Impulse, momentum, and kinetic-energy laws for an isolated frictionless sphere impact as the smooth reset extension at $U(b)$; keep positions fixed and update only the selected two velocities. The impulse theorem's exact contact/momentum/restitution/energy laws concern the reference exact incoming contact. A reported approximate state is not asserted to be exactly at contact; its reset error is recorded.

By Reset and smooth-mode flow propagate a transverse event-time error, set the next aligned reset-state error bound to $E\leftarrow L_R{\eta }_{\mathrm{r}\mathrm{e}\mathrm{f}}+(L_R{M}^{-}+M^{+})\mathrm{\Delta }+{ϵ}_R\mathrm{.}$ The outgoing $M^{+}\mathrm{\Delta }$ term accounts for the reference trajectory's flow from its earlier true reset to the reported time. Append the reported reset, set $t_{\ast }\leftarrow b$, update the current reported state and set $j\leftarrow j+1$. Restart the smooth integrator at $b$, discard the previous local reconstruction, and start the next accumulated dense-error ledger. If $t_{\ast }=T$, return complete with the endpoint reset included. Otherwise repeat the loop. These recurrences compare only matched smooth-mode prefixes and post-reset states at aligned times; they make no same-clock state-error assertion between an exact jump and its later reported jump.

Output complete with the certified trajectory, event brackets, error ledger and certificates, or unresolved with the certified prefix. If an endpoint root is included, it is counted under $N_{\mathrm{e}\mathrm{v}\mathrm{t}}$ and must fit within $B$. Any missing continuation/error, enclosure, margin, ordering, separation/count or restart certificate, failed reset domain, or depleted provider budget returns unresolved without an event-absence claim. To allocate a slot for every certified event under the selected endpoint policy, choose $B\ge N_{\mathrm{e}\mathrm{v}\mathrm{t}}$.

Enumerate every unordered pair once per smooth segment. Root-solve guard evaluations, dense reintegration and restart-error calculation are charged separately from one inspection per pair. No neighbor-search acceleration, frictional solver, or simultaneous-contact solver is specified.

The general mode/guard/reset terminology is Smooth hybrid ODE modes, guards, resets, and deterministic event priority. For each pair transition declare crossing orientation ${\sigma }_{ij}=-1$, so the incoming bracket condition ${\dot{\gamma }}_{ij}\le -\nu$ is exactly ${\sigma }_{ij}{\dot{\gamma }}_{ij}\ge \nu$. If one full mode graph is required, use an initial label $m_0$ and one label $m_{ij}$ for each unordered contact pair, all carrying the identical smooth field. From every label, include a transition to each $m_{ij}$ carrying that pair's guard and reset; this includes a self-transition at $m_{ij}$. Start in $m_0$. Simultaneous or ambiguous roots remain unresolved, so the graph imposes no physical priority rule. This avoids assigning many distinct guards to one self-transition. The four general interfaces used here apply to explicitly supplied valid dense/error and interval certificates. The event page's rational residual-checker construction is one sufficient provider branch; this procedure does not import that construction as an evaluator for every $C^1$ force or an irrational reported reset state.

Let $d\ge 1$, let $C\subseteq {\mathbb{R}}^d$ be nonempty, closed, and convex, and let $P_C(y)$ be the unique nearest point in $C$ to $y$, whose existence and uniqueness are Every point has a unique nearest point in a nonempty closed Euclidean convex set. For $x\in C$, set $N_C(x)=\{n\in {\mathbb{R}}^d:⟨n,z-x⟩\le 0\text{ for every }z\in C\};$ for $x\mathrm{\notin }C$, set $N_C(x)=\mathrm{\varnothing }$. On $C$ this is the outward normal cone of Scaled KKT residual and convex normal cone. The projection variational inequality of Metric projection onto a closed convex set satisfies the variational inequality says $P_C(y)=p$ exactly when $p\in C$ and $y-p\in N_C(p)$.