Stable contact identifiers

[Jondolf]

trafficstars

Objective

Currently, contact pairs have no stable indentifiers. Contact pairs (i.e. graph edges) are removed with swap_remove, which can invalidate edge indices.

This causes a few problems:

1. When processing contact status changes, we need to first collect removed contact pairs to a separate buffer and perform the actual removal afterwards. Otherwise, the indices of the rest of the status changes might get invalidated while processing them. For the actual pair removal, we also need to use entity pairs and look up the edges manually, which is more costly than indexing edges directly.
2. When writing back constraint impulses to contact data, we need to fetch contact pairs based on the entities, because contact pair removal may have invalidated the original edge indices. This can get expensive with thousands of active contacts.

For both of these cases, we would benefit from stable identifiers that can be used to efficiently fetch or remove contact pairs from the contact graph without invalidating other existing identifiers.

Solution

Rework the UnGraph data structure and ContactGraph to support stable identifiers for graph edge connectivity data.

UnGraph now stores a separate Vec for edges and edge weights. An Edge only contains edge connectivity data and the index of the weight associated with it, or None if the edge is vacant. The order of edges is stable, and a free list is used to track which edges are vacant, but edge weights are still allowed to be moved around by edge removal.

// Before
pub struct UnGraph<N, E> {
    nodes: Vec<Node<N>>,
    edges: Vec<Edge<E>>,
}

// After
pub struct UnGraph<N, E: EdgeWeight> {
    nodes: Vec<Node<N>>,
    edges: Vec<Edge>,
    edge_count: usize,
    free_edge: EdgeId,
    edge_weights: Vec<E>,
}

This is a sort of mix of petgraph's UnGraph and StableUnGraph. For contacts, we need stable edge indices and fast iteration over edge weights, but StableUnGraph only provides the former, as it also stores edge weights for vacant edges. By allowing edge weights to be swap-removed and storing vacant edges for connectivity data to keep their order stable, we (hopefully) get the best of both worlds.

The ContactGraph uses this new graph representation, and stores a stable ContactId in each ContactPair and ContactConstraint. This lets us fix the pair removal problem (1) and improve the performance of writing back impulses from constraints to contacts (2).

I also otherwise cleaned up UnGraph and removed some unused code from it.

Comparison With Box2D

A lot of Avian's narrow phase design (e.g. using bit sets for status changes) is inspired by Box2D v3. The core idea for this PR also came from Box2D.

• b2ContactArray stores b2Contacts, which only contain cold data such as the contact index, the previous and next contact edge, island connectivity information, and more. This is similar to the Nodes and Edges in our UnGraph, and has a stable contact ID.
• b2ContactSimArray stores b2ContactSims, which contain the actual contact pair data, and the ID of the corresponding b2Contact. This is similar to the ContactPair edge weights in our UnGraph, and does not have stable indices, as the items are swap-removed when removing contact pairs.
• A contactIdPool is used to manage IDs and add items to the correct slots in the b2ContactArray. Our UnGraph doesn't store a separate ID pool; instead, it just uses a free list and marks edges as vacant or occupied.

While Box2D keeps these structures separate, we have most of the complexity and logic contained within the UnGraph behind a convenient and flexible API.

Results

Before, "Store Impulses" had a fairly substantial cost in contact-heavy scenarios.

Now, it takes less than half the time:

(note that these profiles were done on a branch with huge solver optimizations; on the main branch, the solver is much more expensive here)

Contact pair removal should also be much more efficient, but that is harder to profile directly. In addition to the performance wins, the new stable identifiers clean up some logic quite nicely.

---

Todo

• [ ] Fix determinism bug