Tighter broad-phase BVH queries for self-collision

Minkowski-offset sphere (vertex–triangle) & capsule (edge–edge) queries in Warp, wired into Newton's TriMeshCollisionDetector. Phase-1 prototype & validation · NVIDIA L40 · Warp 1.14.0rc2 · 2026-06-28

1. What changed

Two tighter broad-phase queries replace the radius-padded AABB query; the narrow phase is untouched, so the emitted contacts are unchanged — only the candidate set shrinks.

• Vertex–triangle → sphere: bvh_query_sphere(v, r), exact point→AABB distance test (the sphere is inscribed in the old padded AABB).
• Edge–edge → capsule: bvh_query_ray(e0, e1−e0, inflation_radius=r) bounded by max_dist=1.0 — a ray inflated by r and length-clamped to the edge.

Parity holds by construction: true_contacts ⊆ minkowski_candidates ⊆ aabb_candidates.

2. Correctness — the hard gate

Old AABB detector vs. new detector, both under the same Warp build, every frame of all 8 datasets; canonical VT (v,tri) and EE (e,nbr) sets compared by count + hash.

0 differences across ~24M VT + ~162M EE contacts. Independently, an exact false-positive/false-negative audit on real meshes (fp_fn_test.py) confirms the sphere returns exactly the sphere-overlapping triangle AABBs (0 FP, 0 FN), and a GPU discriminator shows the sphere/capsule dropping crafted boxes the AABB query keeps — i.e. the node tests are genuinely live, not falling back to AABB.

3. Speedup & candidate reduction on cloth

The ~16% EE candidate reduction → ~16% fewer closest_point_edge_edge narrow-phase tests → the 1.23× geomean EE speedup. VT is near-neutral on cloth (next section explains why).

4. Why vertex–triangle gains little on cloth

The candidate drop is governed by h/r = (triangle AABB half-size) / (query radius). The naïve "sphere is π/6 ≈ 48% of its cube" only holds for points filling 3-D. Cloth triangles lie on a 2-D surface (ceiling π/4 ≈ 21%), and they are finite AABBs 1–5× the query radius — so a corner triangle still touches the sphere and isn't dropped. Real cloth sits at h/r ≈ 2–5 (bottom of the curve), giving the measured ~4%. Not a defect — there is simply little slack to remove.

5. Theoretical headroom (random 3-D AABBs)

On 3-D-uniform candidates the queries reach their theory: point-like boxes give a 46.8% sphere candidate drop (≈ π/6) and 1.55× speedup; random long diagonal segments give a 51.7% capsule drop and 1.95× speedup. The gain decays smoothly as boxes grow vs. the radius — the same h/r curve, now confirmed with the real GPU queries and showing the candidate drop converting to wall-clock.

6. Margin sensitivity — VT and EE are opposite

VT sphere gain rises with the query radius (h/r shrinks → up to ~17–25% at 8× margin). EE capsule gain falls with the radius (once r ≫ edge length, the node-AABB inflation swamps the segment's tightness). Cloth self-contact margins land in the EE sweet spot (~15%) and the VT poor spot (~4%) — the two queries are complementary across the margin range.

7. Trade-off & conclusion

Both queries are correct and exact-contact-preserving. The EE capsule is the cloth win (free, ~1.23×); the VT sphere is marginal at cloth's tight margins but realizes up to ~1.5× when the margin/resolution ratio grows or candidates are 3-D-spread. Magnitude on any mesh is set by how surface-bound vs. 3-D-spread the candidates are, and by h/r.

Out of scope (future): exact segment–AABB capsule node test, wide-BVH, fused VT+EE, per-edge length-normalized max_dist.