Module constraint_graph

A ConstraintGraph with graph coloring for solving constraints in parallel.

The constraint graph implements a greedy edge coloring algorithm that assigns constraints to colors such that no adjacent edges in the graph share the same color. This ensures that each body only appears in a given color once, allowing constraints within the same color to be solved in parallel without race conditions.

See ConstraintGraph for more details on how the graph is structured.

References

• High-Performance Physical Simulations on Next-Generation Architecture with Many Cores
• Box2D - SIMD Matters by Erin Catto

Structs

ConstraintGraph

The constraint graph used for graph coloring to solve constraints in parallel.

ContactConstraintHandle

A handle to a contact constraint in the ConstraintGraph.

ContactManifoldHandle

A handle to a contact manifold in the ContactGraph.

GraphColor

A color in the ConstraintGraph. Each color is a set of bodies and constraints that can be solved in parallel without race conditions.

Constants

COLOR_OVERFLOW_INDEX

The index of the overflow color in the graph, used for constraints that don’t fit the graph color limit. This can happen when a single body is interacting with many other bodies.

DYNAMIC_COLOR_COUNT

The number of colors with constraints involving two non-static bodies. Leaving constraints involving static bodies to later colors gives higher priority to those constraints, reducing tunneling through static geometry.

GRAPH_COLOR_COUNT

The maximum number of GraphColors in the ConstraintGraph. Constraints that cannot find a color are added to the overflow set, which is solved on a single thread.