Invention disclosure draft, Newton physics engine
Compliant augmented-Lagrangian contact on separating-plane constraints with penetrating iterates and a certified committed state (ALM-DAT)
Short form. ALM-DAT: contact forces from multipliers, non-penetration from final truncation.
- He Chen (Anka Chen)NVIDIA
- Donglai XiangNVIDIA
- Ju Myung ChangNVIDIA
- Miles MacklinNVIDIA
Status. Draft of 2026-10-21, not submitted. Internal review copy of the invention submission form, questions Q1 to Q10 as filled in.
Page edits. The background of section 2 is shortened on this page, and the equations are typeset again with the same content. The form keeps the full text.
Code state described. The text describes the design as of October 2026. The implementation has moved since: two detections per substep, the row metric from the pair support, and the row along the stored plane normal. Those changes are not in this text.
0Scope
Scope. Three parts that work together. (1) A separating-plane contact constraint per pair of convex primitives. It bounds all vertices of both primitives with smooth support functions, so one scalar constraint certifies that the whole pair is separated, and the contact force is spread over all vertices by softmax weights. Its structure is that of a support-vector machine with a fixed normal, which is why we call it the SVM-like constraint. (2) A compliant contact row for that constraint: a soft cushion in front of a hard wall, both enforced through one augmented-Lagrangian multiplier with a slack gap, plus Coulomb friction as a capped tangential multiplier and gap-rate damping. (3) A solve scheme that lets the iterates penetrate while the multipliers learn the contact force, and commits only a certified, penetration-free state obtained by truncating the motion against division planes stored at a certified anchor. The description gives the problem, then the three parts, then the differences to earlier work.
1Problem and known approaches
ISF Q1. What is the problem you are trying to solve? If others have tried to solve this problem previously, please summarize what you know of those attempted solutions and their shortcomings.
Problem. A physics engine must simulate cloth, thin shells and soft bodies that touch themselves and each other. The simulation must never let two surfaces pass through each other. At the same time a resting contact must carry its load without a visible gap or a visible overlap, and a stack of layers must come to rest without jitter. The engine of interest, Newton [1], solves each time step with Vertex Block Descent (VBD) [2]: a massively parallel block-coordinate method where every vertex is updated from local information only. A contact method for this engine must be local, must stay well conditioned, and must not need a global linear solve or a global line search.
Known approaches and their shortcomings.
- Barrier methods such as Incremental Potential Contact (IPC) [3] add a logarithmic barrier for every near pair and keep every iterate feasible with a continuous-collision-detection (CCD) line search. The barrier stiffness grows without bound as a pair approaches, which conditions the system badly near contact. One early collision shortens the step for the whole scene (time-of-impact locking). The line search is a global operation.
- Offset Geometric Contact (OGC) [4] and Divide and Truncate (DAT) [5] keep every iterate penetration-free with local operations. They truncate the motion of each vertex against conservative bounds or against division planes, and they take the contact force from a penalty energy. A penalty force needs penetration to exist, while the truncation forbids penetration. Under load the two fight: a weak penalty cannot push through the truncation and the contact freezes, a stiff penalty brings back the conditioning problems of penalties. The truncation margin also acts as a speed cap.
- Augmented-Lagrangian (ALM) contact without barriers [6] keeps a multiplier per pair and lets the primal iterate penetrate. It builds the accepted, intersection-free state by a CCD-filtered interpolation toward the iterate at every outer iteration. Its contact constraint is a signed distance linearized at the last feasible state, so it constrains one witness point per pair. It needs CCD at every accepted update and a global projected-Newton solve with a preconditioned conjugate-gradient solver.
- Compliant ALM rows exist in VBD for rigid-body contacts and joints (Augmented Vertex Block Descent [7], and the compliant ALM path of Newton's rigid solver [1]). Particle contacts, that is cloth and soft-body self-contact, stayed on the penalty path. Compliant constraints with multipliers are also the basis of XPBD [8], which has no non-penetration certificate.
- Witness-based contact constraints (closest point with barycentric weights) are the common building block of all of the above. They certify only the interpolated witness points, not the whole primitives. Their forces load two to four vertices, and the loaded vertices switch abruptly when the closest feature changes. An unsigned distance loses the feasible side once a pair penetrates.
- Support-vector machines (SVM) [9] find the plane of largest margin between two point sets. The margin between two convex hulls is a classical geometric dual of the SVM problem [10]. SVMs are a classification tool and have not been used as a dynamic contact constraint with forces.
In short: barrier and CCD methods are safe but global and badly conditioned. Local truncation methods are fast but their penalty forces fight their own truncation. ALM methods carry the force in a multiplier but still rely on CCD, global solves and single-witness constraints.
2How the invention solves it
ISF Q2. How does your invention solve the problem described in the previous question? Be specific.
Background.
The invention builds on three known parts.
- Solver. Vertex Block Descent (VBD) [2] moves one vertex at a time. Each move is a small Newton step that reads only the elements and the contacts at that vertex. One pass over all vertices is a sweep. The inertial target is where the vertices go under their velocity and gravity alone.
- Multiplier. The augmented Lagrangian method (ALM) [11], [12], [13] keeps one multiplier per constraint. The multiplier is the constraint force. The solver updates it once after each sweep, scaled by a metric .
- Detection and truncation. The collision detector [1] reports every vertex-triangle pair and every edge-edge pair that is closer than a query reach. Divide and Truncate (DAT) [5] builds one division plane per pair at a penetration-free pose. It shortens the motion of each vertex so that the vertex stays on its side of its planes.
The invention keeps the implicit time integration, the VBD local solver and the detector unchanged. It adds three parts.
(a) The separating-plane (SVM-like) contact constraint.
A detected pair has a side A with vertices and a side B with vertices (a vertex against a triangle, or an edge against an edge). A unit normal points from A to B and a required gap is given. With a sharpness we form two smooth support bounds, an upper bound for A and a lower bound for B,
and one scalar constraint per pair,
The constraint certifies the whole pair. Because the sums contain every vertex, is at least the projection of every point of A and is at most the projection of every point of B, including every interior point by convexity. So implies for every point of A and of B, and the plane with offset separates them with margin on each side. The soft gap is always a lower bound of the true support gap , and the two differ by a bounded amount:
where and are the vertex counts of the two sides. The implication is one way: a negative soft gap does not prove intersection.
The constraint loads all vertices with smooth weights. Its gradients are softmax weights,
so with a multiplier the forces are and . The weights sum to one on each side, so the two sides receive equal and opposite total forces at every sweep, by translation invariance of . The weights change continuously with the deformation, so the loaded vertices never switch abruptly. The constraint needs only the normal; it has no plane point, because the plane offset is optimized away inside the support bounds. The plane may slide between the two sides as long as some plane with normal still separates them.
The relation to the SVM is exact for a fixed normal: is the hard-margin feasibility condition, the loaded vertices are the support vectors, the per-vertex forces are the dual variables, and the softmax weights are an entropy-regularized support distribution with temperature . The normal of a pair is taken from the closest-point direction at a certified state. For two separated convex primitives this direction is the maximum-margin direction of the convex-hull dual of the SVM problem [10], so the pair's normal is the SVM optimum and the solver treats every pair as a small SVM whose duals are forces. The sharpness is a model parameter with a default derived from the activation gap and the vertex counts.
Variants. The limit gives the hard min-max support gap. The first implementation uses the witness-gap variant: the signed closest-point gap along the closest-point direction, with the stored normal fixing the sign so that a vertex that crossed its triangle reports a negative gap instead of a flipped direction. The witness variant plugs into the same row and the same truncation.
(b) The compliant contact row: cushion plus hard wall through one multiplier.
The intended force law is zero beyond an activation gap, linear in the gap inside it, and unbounded once the pair reaches the plane. We realize it with one slack gap . The slack carries the cushion energy, and an augmented Lagrangian term enforces the constraint :
with compressive multiplier and metric . The slack solve is closed form,
and selects one of three regimes with a force that is continuous across the switches:
| Regime | Force | Stiffness |
|---|---|---|
| released | none | |
| cushion | ||
| hard wall |
with
In the hard-wall regime a penetration increases the separating force without any penalty stiffness, and the force at the wall is not capped by the cushion. Each VBD local solve reads the persistent and evaluates from the current geometry; the per-vertex Hessian contribution is the regime's stiffness times . After a complete sweep the multiplier is updated once per pair, , evaluated at the trial state. The trial state may penetrate, so the multiplier learns from the attempted motion, not from the committed one; this is what lets a truncated, non-penetrating contact transmit its full load. The metric is the row's inertia scale (the inverse of the pair's effective inverse mass along the normal over the squared time step), with an optional floor relative to . The wall is placed a small offset above the stored division plane, and release uses the raw signed gap so that unsupported multipliers unwind.
Smooth transition from the compliant to the hard regime. The law above is continuous in the force but not in the stiffness: the in-sweep stiffness jumps from to where the slack reaches its bound, and the multiplier ascent factor jumps from to one. A smooth transition removes both jumps (suggested by Miles Macklin; the form below is our proposal). The cushion stiffness becomes a function of the gap: it rises smoothly from at the inner edge of a transition band above the plane to a wall stiffness at the plane, for example
with a smoothstep. The in-sweep stiffness and the ascent factor,
then rise smoothly toward their hard-regime values and one, and the slack bound stays as the backstop for penetrating trial states. is a multiple of the metric , so the hard limit of the row is the bounded metric and never an infinite stiffness; the compliance must not vanish at the plane, because a stiffness that diverges there makes the cushion force diverge and turns the row into a barrier. The cushion force is the integral of this stiffness profile over the slack, so it stays continuous and monotone. At the wall it equals
The slack solve becomes one monotone scalar equation that a few clamped Newton steps solve, and the regime test at the wall stays closed form. Evaluating at the current gap and reusing the quadratic closed form is not equivalent: it multiplies the whole cushion width by the wall stiffness and launches a loaded vertex. An alternative with the same purpose replaces the projection of the slack onto by a smooth projection (a softplus with a small temperature), which is the smoothed-complementarity form and needs a short one-dimensional Newton solve for the slack. The transition band is a model parameter, a fraction of the activation gap. This is safe for the certificate because non-penetration comes from the truncation of part (c), not from the stiffness at the plane.
Friction and damping complete the row. A tangential multiplier lives in the current tangent plane; its trial value adds the metric times the relative tangential slip since the step start, and it is clamped to the Coulomb disk of radius times the row's transmitted normal force, updated after the normal update. Its Jacobian is the metric times the tangent projector inside the disk and the projected form on the rim. The tangential metric is the plain inertia scale without the stiffness floor, because a floored metric saturates every loaded row after microns of slip. Gap-rate damping acts only on the closing motion inside the activation gap, so it is zero before contact and continuous at the gap boundary.
(c) Penetrating iterates, certified commit.
Each step keeps three states: the start state (penetration-free, where detection ran), the trial state (the VBD iterate, allowed to penetrate), and the anchor (certified penetration-free). The scheme is:
- Detect pairs once at with a query reach that covers the motion budgets of both sides. Match the pairs to the previous step's rows and carry their multipliers.
- Build one division plane per pair at the anchor. Truncate the inertial target toward it and move the anchor there.
- Run the VBD sweeps with the contact rows on the trial state. After each sweep update the multipliers at the trial state. At a fixed cadence, truncate the anchor toward the trial state against the stored planes and rebuild the planes at the new anchor.
- After the sweeps, run a fixed number of truncation rounds. Each round truncates every vertex toward the trial state, slides each plane along its normal to give room to the sides that still want to move, and re-picks the normals at the penetration-free anchor.
- Commit the anchor as the new state and take the velocity from the committed motion. Store the multipliers for the next step.
The step in pseudocode (normal multipliers shown; the tangential multipliers follow the same update and matching):
# x_start: penetration-free start state of the step (the detection pose); y: inertial target
# contacts: compact global buffer from the triangle-mesh collision detector, arranged by the
# vertex side's id; each vertex's rows sorted by the three triangle indices (easy matching)
contacts = InitialSphericalQuery(x_start, motion_budgets)
# p, n share the layout of contacts: point and normal of every division plane
p, n = ComputeContactConstraintsAndNormals(contacts, x_start)
# Initial stage
x_anchor = x_start
x_trial = y
x_anchor = DAT_truncate(x_anchor, x_trial, p, n) # motion budget measured from x_start
p, n = ComputeContactConstraintsAndNormals(contacts, x_anchor)
# multipliers: zero, or carried from the previous step by matching the sorted rows
planes_lambdas = zeros(contact_count)
if contacts_history:
planes_lambdas = retrieve_lambda_from_history(contacts, contacts_history, lambda_history)
# Stage 1: ALM/VBD sweeps on the trial state (the trial may penetrate)
for iteration in range(FIXED_ALM_ITERATIONS):
x_trial = ALM_VBDSweep(x_trial, p, n, planes_lambdas)
if iteration % PLANE_UPDATE_INTERVAL == 0:
x_anchor = DAT_truncate(x_anchor, x_trial, p, n)
p, n = ComputeContactConstraintsAndNormals(contacts, x_anchor)
# the multipliers learn from the untruncated trial state
planes_lambdas = UpdateALMMultipliers(x_trial, p, n, planes_lambdas)
# Stage 2: iterative truncation
# x_anchor is penetration-free, x_trial may penetrate; p, n are valid at x_anchor
for iteration in range(FIXED_TRUNCATION_ITERATIONS):
# truncate every particle toward x_trial against its planes (motion budget measured from x_start)
x_anchor = DAT_truncate(x_anchor, x_trial, p, n)
# slide each plane along its normal: sides that still want to move get the room
# (computed from the truncated x_anchor and the remaining displacement x_trial - x_anchor)
p = SlidePlanes(contacts, x_anchor, x_trial, p, n)
# occasionally re-pick the normals, at the penetration-free x_anchor
if iteration % NORMAL_UPDATE_INTERVAL == 0:
p, n = ComputeContactConstraintsAndNormals(contacts, x_anchor, x_trial)
x_out = x_anchor
v_out = (x_out - x_start) / dt
lambda_history, contacts_history = planes_lambdas, contacts
SlidePlanes(contacts, x_anchor, x_trial, p, n), for every pair c:
# heights of the truncated positions, rates from the remaining displacement
h_i = n . x_anchor_i for every vertex i of the pair
r_i = x_trial_i - x_anchor_i
a_i = approach rate toward the plane: max(0, +n . r_i) on side A, max(0, -n . r_i) on side B
# where the plane may be right now (both primitives stay separated with margin m)
b_lo = max over A of h_i + m
b_hi = min over B of h_j - m # m shrunk to half the gap if the gap is thinner than 2m
# who still wants room?
if nobody approaches: b = midpoint(b_lo, b_hi)
elif only B approaches: b = b_lo # A needs nothing: give B everything
elif only A approaches: b = b_hi
else:
# balance the slowest vertex on each side: equal fraction of the remaining motion
# tau_i(b) = (b - m - h_i) / a_i on A, tau_j(b) = (h_j - m - b) / a_j on B
for each approaching pair (i in A, j in B): # 3 pairs for vertex-triangle, 4 for edge-edge
b_ij = (a_j (h_i + m) + a_i (h_j - m)) / (a_i + a_j) # where tau_i == tau_j
clamp b_ij to [b_lo, b_hi]
score_ij = min over all approaching vertices of tau(b_ij)
b = the b_ij with the largest score
p_c = p_c + (b - n . p_c) * n # slide the stored point along the normal
The truncation is per vertex and local. For a plane and a vertex assigned to one side, the allowed fraction of its remaining displacement is the fraction at which its straight path would reach the plane, scaled by a safety factor below one; a vertex that moves away from or parallel to its plane gets no cap. The per-pair caps are combined by an atomic minimum per vertex. Every vertex stays on its side of every plane during its linear motion, so every convex primitive stays on its side too; this is the non-penetration certificate.
Plane placement follows a maximin rule. At the anchor both primitives are separated along . The plane is placed between the highest point of A and the lowest point of B, each side keeping a thickness margin that shrinks to half the gap when the pair is thinner than two margins. Among those offsets the rule picks the one at which the slowest approaching vertex on each side can take the same fraction of its remaining displacement before touching the plane. When only one side approaches, the plane moves to the far side of the gap and that side gets all the room. This is the proportional split of DAT generalized to many approaching vertices and to sliding between rounds.
The committed motion from is bounded by a motion budget of half the detection slack per side, so a pair that was farther than the query reach at detection cannot meet. A buffer overflow in detection sets a coverage flag, because a pair without a stored plane has no certificate.
(d) History. Pairs are stored as canonical sorted rows keyed by the vertex side and the sorted indices of the other side. Matching the sorted rows of two steps is a merge, so the normal multiplier, the tangential multiplier and the stored plane survive re-detection. The normal multiplier is a scalar magnitude that re-attaches along the refreshed normal; the tangential multiplier is projected into the new tangent plane and clamped.
(e) Implementation. The scheme is implemented in Newton's SolverVBD [1] as the alm_dat self-contact method, in Warp kernels [14]: one kernel per pair family for the row forces and Hessians inside the colored VBD sweep, one for the multiplier update, one for plane placement, one for the atomic-minimum truncation and one for the budgeted commit. Every kernel is local and the step records into a CUDA graph. The default penalty path is unchanged.
Variants. Two detections per step, one at the start and one at the truncated inertial target, double the usable motion per step at the cost of a second query and a re-match. A displacement clamp relative to in place of the path-length budget admits corrections that move a vertex back toward its start. A per-vertex motion budget from the vertex's own speed with a matching per-vertex query reach. The same rows and planes apply to rigid-soft and rigid-rigid pairs with one fraction per body.
Evidence so far (limited, internal). Stacked cloth sheets and a dropped elastic block rest on a pinned sheet at the same heights as the engine's penalty path, with friction and damping active. A free-falling stack of sheets keeps its layer spacing exactly, where the penalty path lets the layers drift into each other. A stack with crushed crease geometry exposed the speed cap of the single-detection budget; the two-detection and displacement-clamp variants above address it.
3Technical differences to prior work
ISF Q3. What are the specific technical differences (not benefits) between the solution described in the previous question and prior solutions?
Relative to barrier methods (IPC [3]). The contact force is a multiplier with a compliant cushion, not a barrier energy. Iterates may penetrate; no CCD and no line search run inside the iterations. Non-penetration comes from per-vertex truncation against stored planes at a certified anchor, applied at checkpoints and in final rounds, not from feasibility of every iterate. The contact Hessian is the regime stiffness ( or ), bounded, not a barrier Hessian.
Relative to OGC and DAT [4], [5]. Both truncate every iterate and take the force from a penalty. Here the force comes from a multiplier updated at the untruncated trial state, so a contact at zero violation carries its full load. Truncation runs at checkpoints and after the sweeps, not after every color. The planes are stored and placed by a maximin rule over all approaching vertices, slid between rounds and rebuilt only at certified anchors. Multipliers are carried across steps by sorted-row matching. The constraint of part (a) is a whole-primitive support constraint instead of a closest-point witness.
Relative to barrier-free ALM elastodynamics [6]. That method also lets the primal iterate penetrate and keeps multipliers with slacks. Differences: its accepted state is a CCD-filtered interpolation computed at every outer iteration; here the committed state is the truncation against stored division planes with no CCD. Its constraint is a signed distance linearized at the last feasible state, one witness per pair; here it is a support-bound constraint over all vertices of both primitives with softmax force distribution, or the witness variant with the sign fixed by the stored normal. Its primal solver is a global projected Newton with PCG and its penalty stiffness is estimated from the elasticity Hessian; here the primal solver is local VBD, the metric is the row's inertia scale, and the cushion stiffness is the authored contact stiffness. Its multiplier is a single ALM term; here one slack carries both a compliant cushion and a hard wall, with three closed-form regimes.
Relative to compliant ALM in VBD and XPBD [1], [7], [8]. Those rows are witness constraints with a single compliance. Here the row has a cushion in front of a hard wall through one slack, the compliance can change smoothly with the gap so that the row passes from compliant to hard without a stiffness jump and with the bounded metric as its hard limit, the multiplier update reads the untruncated trial state, the tangential metric has no stiffness floor, and the row is paired with a non-penetration certificate.
Relative to SVM [9], [10]. The SVM optimizes the normal and treats the points as fixed data. Here the normal is frozen per step and taken from the certified closest-point direction, which coincides with the maximum-margin direction; the points move under the forces; the dual variables have units of force and obey the third law; the smoothing is a log-sum-exp support bound with a proven one-sided certificate, not a loss function; and no training takes place.
Known background used as building blocks and not claimed as new. The implicit Euler incremental potential; VBD and its coloring [2]; the augmented Lagrangian method and its slack treatment of inequalities [11], [12], [13]; the division-plane truncation of DAT and the conservative bounds of OGC [4], [5]; the IPC friction smoothing [3]; log-sum-exp smoothing; the SVM margin and the convex-hull duality [9], [10]; Newton's triangle-mesh collision detector, its compact pair buffers and its Warp kernels [1], [14]. The proposed contribution is the combination: a whole-primitive support-bound constraint with softmax force distribution and a separation certificate, a cushion-plus-wall row through one slack and one multiplier updated at the penetrating trial state, and a commit scheme that truncates toward the trial against stored, maximin-placed and sliding division planes at a certified anchor, with history carried by sorted rows.
4Supplementary material
ISF Q4. Please feel free to attach any supplementary documentation (e.g., white papers, .ppts, diagrams) that may be helpful to understand the invention.
On this page the figures of the design note are embedded in section 2. The showcase page with its videos is online at the link below; the attachment folder keeps offline copies.
Attached (folder attachments; every file opens offline, no network access is needed):
alm-contact-design/index.htmlwith its figures: the design note "ALM contact with final-only truncation" (constraint, separation proof, cushion plus wall, friction, normal update, query coverage, final truncation, solver flow). Source:notes/alm-contact-design/design.md.aggregated_separation_row.html: the design document of the separating-plane constraint (requirements, log-sum-exp row, certificate, ALM form, numeric example, SVM correspondence, cushion law). The formulas are rendered into the file.algorithm-reference.md: the step pseudocode of the implemented scheme.vbd-rest-on-contact/index.htmlwith its videos: a local copy of the showcase page (stacked sheets, dropped block, free fall, folded stack), built from the Newton examplevbd_rest_on_contact.
Online: the same showcase page: https://ankachen.com/report/vbd-rest-on-contact/.
5Form answers Q5 to Q10
- Q5Open-source licenseDo you plan to license code employing your invention under an Open Source license?
-
Yes. Code embodying the invention is planned for release under the Apache 2.0 license, the license of the Newton physics engine repository that hosts it.
- Q6Date of conceptionWhat date did you conceive of the idea?
-
2026-09-02 for the core scheme (multipliers learn the contact force from the untruncated trial state while division-plane truncation keeps the committed state penetration-free). This is the date of the earliest record that states the idea: the project issue "ALM-based contact forces for Divide and Truncate" and the tutoring log of the same day. The written design "Force Without Violation" followed on 2026-09-03. The separating-plane (SVM-like) constraint was specified on 2026-09-11 (design consult; document "The Aggregated Separation Row"). The design note with the separation proof was written on 2026-09-14. The first implementation in Newton is dated 2026-10-04. The smooth compliant-to-hard transition of the row was added on 2026-10-14.
- Q7Technology standardDoes the invention involve implementing or improving a technology standard (e.g., OpenGL)?
-
No.
- Q8Disclosure outside NVIDIADoes NVIDIA plan to disclose software or information embodying or describing the invention outside the company without an NDA? If yes, what is the disclosure date?
-
Yes, and parts are already public. Facts for legal review:
- The public GitHub issues newton-physics/newton #4135 and #4136, opened 2026-09-02, describe the core scheme in a few paragraphs (multipliers carry force at zero violation; the dual update measures the violation against the untruncated target; DAT truncation remains the feasibility guarantee).
- The design note with the separation proof has been on the public fork branch
AnkaChan/newton, branchankac/alm-dat-design, since 2026-09-14. - The showcase page https://ankachen.com/report/vbd-rest-on-contact/ has been reachable without authentication since 2026-10-05.
- The DAT and OGC papers [4], [5] are published prior work by the inventor; they do not describe this invention.
Planned release of the code in the Newton repository: 1 November 2026 (expected date, given by the inventor on 2026-10-14).
- Q9ProductsList all NVIDIA product(s) in which the invention is, or will be, incorporated.
-
Newton (the open-source physics engine [1]) and Warp [14].
- Q10Outside contributionsHave any non-NVIDIA employee or entity contributed to this invention or to funding of the underlying research?
-
No.