Collision detection · LavenderSim

Spend detailed geometry only on plausible pairs

Collision detection is usually split into two stages. The broad phase cheaply rejects pairs that cannot touch. The narrow phase runs shape-specific or general convex queries on the survivors.

\text{all pairs}\;\longrightarrow\;\text{filters}\;\longrightarrow\;\text{AABB overlaps}\;\longrightarrow\;\text{narrow phase}\;\longrightarrow\;\text{manifold}

Filters encode intent: collision-disabled bodies, connected pairs, static–static pairs, or actor self-collision rules. Geometry should not spend time rediscovering a pair the model already forbids.

Experiment 1: solve spheres analytically

For sphere centers $c_A,c_B$ and radii $r_A,r_B$ , let $d=c_B-c_A$ . The signed surface distance and A-to-B normal are:

\phi=\lVert d\rVert-r_A-r_B,\qquad n=\frac{d}{\lVert d\rVert}

$\phi>0$ is separation, zero is touching, and $\phi<0$ is penetration. Witness points are $p_A=c_A+r_An$ and $p_B=c_B-r_Bn$ .

Experiment 01verified

Compute sphere–sphere and sphere–plane queries

Can one sign convention determine separation, normal, penetration, and contact points consistently?

Overlapping sphere queries with normals and penetration — Both documented queries have signed distance −0.15 or −0.20 m. Normals point from A toward B, or outward from the plane.

Failure modes: reverse the normal without swapping bodies, normalize coincident centers, mix penetration depth with signed distance, or report a center as a surface witness.

Expected result: The command exits successfully and reproduces the numerical or visual relationship described in this card.
Failure modes: Non-finite values, a reversed trend, a failed assertion, or a materially different plot means the assumptions, seed, timestep, build, or backend should be inspected before continuing.

python examples/tutorials/simulation/ch08_collision_detection/collision_detection.py --quickView source ↗

Experiment 2: reject with axis-aligned boxes

An axis-aligned bounding box stores minimum and maximum coordinates. Two boxes overlap only if their intervals overlap on every axis:

a_{min,k}\le b_{max,k}\quad\land\quad b_{min,k}\le a_{max,k}\qquad\forall k

AABB overlap is conservative: it may admit separated rotated shapes, but it must not reject a real collision.

Experiment 02verified

Move forty AABBs

How much narrow-phase work can a simple conservative test avoid?

All candidate pairs versus AABB overlaps across moving objects — Forty objects create 780 unordered pairs per frame. Seeded AABBs reject more than 98% before any detailed shape query.

Failure modes: forget rotation when building an enclosing AABB, use strict inequalities and lose touching contacts, or update bounds after rather than before collision detection.

Expected result: The command exits successfully and reproduces the numerical or visual relationship described in this card.
Failure modes: Non-finite values, a reversed trend, a failed assertion, or a materially different plot means the assumptions, seed, timestep, build, or backend should be inspected before continuing.

python docs-site/scripts/render_tutorial_ch08.pyView source ↗

Boxes reveal the separating-axis idea

The Separating Axis Theorem says two convex bodies are disjoint if some axis produces disjoint projection intervals. Oriented boxes in 3D require face normals from both boxes plus non-degenerate cross products of their edge axes—up to fifteen tests.

\max_{a\in A}n\cdot a < \min_{b\in B}n\cdot b\quad\Longrightarrow\quad\text{separated on }n

If no tested axis separates the boxes, the smallest interval overlap suggests a contact normal and penetration depth. LavenderSim then collects contained vertices to create up to four spatially distinct manifold points.

Experiment 3: search the Minkowski difference

A support mapping returns the furthest point in direction $d$ :

s_A(d)=\operatorname*{argmax}_{a\in A}a\cdot d

The support point of the Minkowski difference is $s_{A-B}(d)=s_A(d)-s_B(-d)$ . Convex bodies intersect exactly when $A-B$ contains the origin. GJK builds a line, triangle, or tetrahedron simplex toward that origin.

Experiment 03verified

Step through 2D GJK

Can support points prove intersection without enumerating every feature pair?

Minkowski difference support points directions origin and final GJK simplex — The final triangle encloses the orange origin, proving overlap after two new support queries.

If a new support point fails to pass the origin along the search direction, a separating plane exists and GJK returns no collision.

Failure modes: use the same direction for both shapes, retain the wrong simplex vertex, mishandle a zero search direction, or apply GJK directly to a concave mesh.

Expected result: The command exits successfully and reproduces the numerical or visual relationship described in this card.
Failure modes: Non-finite values, a reversed trend, a failed assertion, or a materially different plot means the assumptions, seed, timestep, build, or backend should be inspected before continuing.

pytest -q tests/tutorials/test_ch08_collision_detection.pyView source ↗

EPA turns overlap into depth; manifolds stabilize contact

Intersection alone is insufficient for response. The Expanding Polytope Algorithm starts from GJK's enclosing simplex, repeatedly selects the face nearest the origin, and adds a support point along its normal. Convergence returns an approximate penetration normal, depth, and witness point.

A single point can let a box wobble on a face. A contact manifold preserves several well-separated points sharing the collision normal, giving the solver enough geometric leverage to resist rotation.

Experiment 4: trace LavenderSim's pipeline

Experiment 04verified

Compare analytic, SAT, and GJK/EPA contacts

Which pipeline stages ran, and how many contacts did each shape pair produce?

Native manifold points for spheres boxes and convex GJK EPA shapes — The analytic sphere pair produces one point, aligned boxes produce four SAT manifold points, and overlapping convex hulls invoke GJK/EPA before building two points.

1 → 0far pair: broad test → narrow call

1 GJK + 1 EPAconvex overlap

4 pointsbox face manifold

The trace record contains body IDs, point, normal, and penetration. Python can turn those records into browser vector overlays; counters report candidates, filters, broad overlaps, narrow calls, contacts, GJK calls, and EPA calls.

python

collision = observation["collision"]
print(collision["stats"])
for contact in collision["contacts"]:
    body_a, body_b = contact[:2].astype(int)
    point, normal, depth = contact[2:5], contact[5:8], contact[8]

Implemented by LavenderSim: detect_contacts() records filtering and broad/narrow counts. The same C++ buffers are verified semantically through native Python and the rebuilt WebAssembly module.

Failure modes: treat a manifold point count as a collision count, expect GJK counters for analytic sphere pairs, or assume a broad-phase overlap guarantees contact.

Expected result: The command exits successfully and reproduces the numerical or visual relationship described in this card.
Failure modes: Non-finite values, a reversed trend, a failed assertion, or a materially different plot means the assumptions, seed, timestep, build, or backend should be inspected before continuing.

python examples/tutorials/simulation/ch08_collision_detection/lavendersim_collision_trace.pyView source ↗

Paw-check: make geometry explain itself

Separate the two reference spheres by 0.05 m and predict both witness points.
Implement swept AABBs using velocity and timestep.
Add a triangle–triangle SAT query in 2D.
Animate every GJK search direction and simplex.
Rotate one native box and inspect how its manifold changes.
Disable a colliding pair and verify filtering occurs before broad phase.

What should I be able to say now?

Collision detection is a staged geometric query. Filters and AABBs cheaply reject pairs; analytic tests handle simple primitives; SAT finds separating axes for boxes; GJK searches the Minkowski difference of general convex bodies; EPA estimates penetration after overlap; and manifolds provide stable solver points. Counters and traces reveal which path actually ran instead of asking a rendered image to prove it.

By the end, you can…