Physics simulation

Uniform grid stored in a hash table: bucket objects by cell, test only neighbouring cells; O(n) neighbour search for many similar-sized objects such as particles.

Binary tree of nested bounding boxes; prunes overlap and ray queries to O(log n) for any size distribution, and supports cheap insert/remove for moving objects.

Sort box endpoints along an axis and sweep: only intervals that overlap on that axis are tested; near-linear per frame thanks to temporal coherence.

Convex shapes are disjoint iff some axis separates their projections; testing face normals and edge crosses gives overlap, depth and contact normal.

GJK decides whether (and how far apart) two convex shapes are from their support functions alone; EPA expands its simplex into penetration depth and normal.

Iterative contact solver applying impulses one constraint at a time with accumulated clamping and warm starting; the standard solver for stacking and friction in real-time physics engines.

Advance one 3D rigid body per step from force and torque: semi-implicit Euler for position, an inertia tensor in the body frame, and quaternion orientation updated by the exponential map.