Why does a physics broad phase keep a persistent pair cache, and how does it report pairs that begin and end overlapping?
answer
- most bodies did not move
- only moved bodies query
- ordered id pair as the key
- diff old and new pairs
- overlap events are not touch events
basics
~20 sA persistent pair cache remembers last step's candidate pairs, so only bodies that moved need new queries, and comparing old and new pairs yields begin and end events that create and destroy the narrow phase's per-pair contact data.
solid answer
~50 sRebuilding the pair list every step re-tests pairs that have not changed, and most bodies in a scene are resting or slow. The cache stores each pair once, keyed by the two body ids with the smaller first, in a hash set or sorted array. Each step only bodies whose bounds changed query the structure; a found pair missing from the cache is a **begin**, and a cached pair whose bounds no longer overlap is an **end**, found by re-checking pairs that involve a moved body or reported directly by incremental sweep-and-prune. A begin creates the narrow phase's per-pair record, including the contact data the solver reuses next step; an end destroys it. These are bound-overlap events, not touch events: gameplay enter and exit notifications come from the narrow phase seeing contact points appear or vanish. Sort new pairs by key so their order does not depend on hash layout or threads.
go deeper
Recall that the broad phase remembers its pairs between steps and reports when a pair starts or stops overlapping.
Explain the ordered id key, why only moved bodies query, and how begins and ends are found by comparing cached and new pairs.
Separate bound-overlap events from touch events, and diagnose pair churn, stale entries after destruction and order-dependent results.
Set the rules a team follows for events and determinism: which layer raises gameplay notifications and how pair order is fixed across threads and platforms.
## Why not rebuild the list every step A broad phase could recompute every candidate pair from scratch each step. Two things make that wasteful: - **Most bodies did not move enough to matter.** Resting props, sleeping debris and the static level produce the same pairs step after step. Re-querying them burns time for no new information. - **Downstream state is per pair.** The narrow phase keeps a record for each candidate pair: the contact manifold, contact feature ids, and the accumulated impulses an iterative solver reuses to start the next step close to the answer. Rebuilding the pair list loses the link between this step's pair and last step's record unless something remembers which pairs persist. A **persistent pair cache** is that memory. It holds every current candidate pair and turns the broad phase's output into a stream of changes. ## Storing pairs - **Key:** the two body ids with the smaller first, so (A, B) and (B, A) are the same entry. With 32-bit ids the key can be packed into one 64-bit integer, the smaller id in the high half. - **Container:** a hash set for constant-time lookup, or a sorted array that is merged with the new pairs each step. Each entry points to its narrow-phase record. - **Filtering first:** pairs rejected by collision groups or by both bodies being static are never inserted, so they cost no memory and no events. ## Finding begins and ends 1. **Mark moved bodies.** A body is "moved" when its broad-phase bounds changed this step. With fat bounds in a dynamic AABB tree, that is only when its tight box escaped the fat one. 2. **Query for new pairs.** Each moved body queries the structure with its bounds. For every body found (other than itself) the ordered key is looked up; a key not yet in the cache is inserted and reported as a **begin**. 3. **Detect ends.** Either re-check, each step, the cached pairs that involve a moved body and remove those whose bounds no longer overlap, or let incremental sweep-and-prune report separations directly from its endpoint swaps. Each removal is an **end**. 4. **Handle removals.** When a body is destroyed, every pair it belongs to ends at once, which needs either a per-body list of pairs or a sweep of the cache. 5. **Fix the order.** Sort the step's begins and ends by key before handing them on, so the order does not depend on hash-table layout or on which thread found which pair. That keeps the simulation reproducible run to run. ## Overlap events are not touch events | Event | Comes from | Means | |---|---|---| | Pair begin | broad phase | the two bounding boxes, possibly fattened, now overlap | | Contact begins | narrow phase | the shapes produced at least one contact point | | Contact ends | narrow phase | the last contact point vanished | | Pair end | broad phase | the boxes no longer overlap; the per-pair record is freed | With fattened boxes, a pair can begin many steps before the shapes touch and end many steps after they part. Gameplay notifications such as "started colliding" belong to the narrow-phase rows; reporting broad-phase begins to gameplay would fire them while objects are still visibly apart. ## Costs and traps - **Pair churn.** Two bodies jittering at the edge of overlap can begin and end every step, allocating and freeing a record each time. Ending a pair only when the fat boxes separate, not the tight ones, adds hysteresis that stops it. - **Dense heaps.** Memory grows with the number of overlapping pairs, so a pile of debris whose fattened boxes overlap many neighbours makes a large cache. - **Stale entries.** A body that is destroyed, teleported or moved between structures must have its pairs cleaned up, or the narrow phase works on a pair that no longer exists. - **Thread safety.** Parallel queries need either per-thread pair buffers merged afterwards, or a concurrent set; merging and sorting the buffers is usually simpler and keeps the deterministic order above.
- Why should gameplay collision notifications not be raised from broad-phase pair begins?A broad-phase begin only says the bounding boxes, often enlarged by a margin, overlap. The shapes may still be visibly apart and may never touch. Notifications belong to the narrow phase, which raises a contact-begin when a pair's contact points go from none to some, and a contact-end when they return to none.
- How does the pair cache help keep a simulation deterministic?Hash-set iteration order and multi-threaded queries can produce the same pairs in a different order on different runs, and the solver's result depends on the order it processes contacts. Sorting each step's begins, ends and active pairs by their ordered id key gives every run the same order regardless of threading.
- Says every body must re-query the structure every step even with a pair cache.
- Treats a broad-phase pair begin as proof that the shapes touch.
- Stores (A, B) and (B, A) as separate pairs.
- Forgets to remove a destroyed body's pairs from the cache.
- Relies on hash-set iteration order for a reproducible pair order.