How Graph Coloring in the Box3D Constraint Graph Enables Parallel Joint Solving

Box3D partitions all constraints into independent graph colors where no two constraints share the same bodies, enabling the solver to process entire color groups in parallel without race conditions or data hazards.

Box3D organizes every physics constraint—including joints, contacts, and wide-contact manifolds—into a constraint graph that powers massively parallel simulation. By dividing constraints into a fixed number of graph colors (B3_GRAPH_COLOR_COUNT), the engine ensures that constraints within each color operate on mutually exclusive sets of rigid bodies. This independence allows Box3D to scale joint solving across CPU cores while maintaining deterministic physics results.

The Constraint Graph Architecture

Graph Color Data Structures

In src/constraint_graph.h, Box3D defines the core data structures that enable this parallelism. The b3ConstraintGraph maintains an array of color buckets, where each b3GraphColor stores constraints that are guaranteed not to conflict:

typedef struct b3GraphColor {
    // Joint simulations, contacts, and wide-contact manifolds
    // that don't share bodies with other constraints in this color
} b3GraphColor;

typedef struct b3ConstraintGraph {
    b3GraphColor colors[B3_GRAPH_COLOR_COUNT];
} b3ConstraintGraph;

When a constraint is created, Box3D assigns it to a specific color index. The fundamental invariant is that constraints within the same color never reference the same bodies, making them safe to solve simultaneously.

How Graph Coloring Enables Parallel Execution

The simulation follows a five-stage workflow that transforms the constraint graph into parallel work units:

1. Build the graph

When contacts or joints are created, Box3D adds them to specific colors in b3ConstraintGraph. The assignment algorithm ensures body uniqueness within each color bucket.

2. Partition constraints per color

During the simulation step in b3SolveWorld (see src/solver.c, lines 1460–1501), Box3D computes the active constraint counts for each color. It categorizes them into joint, contact, and wide-contact constraints to prepare for block allocation.

3. Create per-color work blocks

For every active color, the solver assembles contiguous sets of b3SyncBlock structures. These blocks are ordered with joints first, followed by wide-contacts and standard contacts (see src/solver.c, lines 1744–1763):

// Prepare graph work blocks. Each color gets joint blocks followed by contact blocks.

4. Launch parallel tasks

Box3D invokes its task system to run a parallel-for loop over each active color, feeding the prepared blocks to the solver. Because colors are independent, the solver updates body velocities and positions simultaneously without atomic operations. The source code explicitly documents this at line 1364 of solver.c: "parallel simulation with graph coloring."

5. Synchronize results

After each color's work completes, Box3D synchronizes the simulation state before proceeding to the next phase (warm-start, solve, relax, restitution). This synchronization point ensures deterministic ordering while preserving the parallelism benefits.

Solver Implementation Details

The actual parallel execution happens inside b3SolveWorld in src/solver.c. The function analyzes the constraint graph to determine which colors contain active work, then constructs solver blocks that respect the color boundaries.

Key implementation characteristics include:

• Fixed color count: Using B3_GRAPH_COLOR_COUNT (typically 32 or 64) rather than dynamic coloring minimizes allocation overhead and cache misses during the simulation step.
• Overflow handling: When constraints exceed available colors, Box3D uses B3_OVERFLOW_INDEX to group remaining constraints serially.
• Deterministic ordering: Colors are processed in a fixed sequence, with parallel work confined within each color boundary.

Practical Usage and Debugging

Box3D automatically leverages graph coloring during world steps. The standard simulation loop requires no special configuration:

// Create a world
b3World* world = b3CreateWorld();

// ... add bodies, joints, contacts ...

// Advance the simulation (the solver internally uses graph coloring)
b3StepContext context = {0};
b3StepWorld(world, &context);

To inspect how constraints distribute across colors for debugging or profiling:

b3ConstraintGraph* graph = &world->constraintGraph;
for (int i = 0; i < B3_GRAPH_COLOR_COUNT; ++i) {
    printf("Color %d – Joints: %zu, Contacts: %zu\n",
           i,
           graph->colors[i].jointSims.count,
           graph->colors[i].contacts.count);
}

For deterministic testing or single-threaded debugging, you can force all constraints into the overflow color:

// Set the overflow index to be the only active color
graph->colors[B3_OVERFLOW_INDEX].jointSims.count = /* your constraint count */;

Summary

• Box3D uses a constraint graph with fixed-size color buckets (B3_GRAPH_COLOR_COUNT) to organize joints and contacts.
• Each graph color contains only constraints that operate on distinct bodies, eliminating data hazards during parallel execution.
• The solver (src/solver.c) builds per-color work blocks (b3SyncBlock) and launches parallel-for tasks over independent colors.
• Synchronization occurs only between color batches and simulation phases, ensuring deterministic results while maximizing CPU utilization.
• The architecture is transparent to users—b3StepWorld automatically handles graph coloring, requiring no manual configuration.

Frequently Asked Questions

What is graph coloring in the context of physics engines?

Graph coloring is a partitioning strategy where constraints are assigned to "colors" such that no two constraints in the same color share a common rigid body. In Box3D, this transforms the sequential constraint satisfaction problem into a parallelizable one, as each color represents an independent set of work that can be processed simultaneously without synchronization locks.

Why does Box3D use a fixed number of colors instead of computing optimal coloring dynamically?

Box3D uses a fixed array of colors (B3_GRAPH_COLOR_COUNT) to minimize runtime overhead and memory allocation during simulation. Computing an optimal graph coloring (minimum number of colors) is NP-hard and would introduce unacceptable latency in the physics step. The fixed-color approach with overflow handling provides a predictable memory layout and cache-friendly access patterns while still exposing substantial parallelism.

How does graph coloring affect simulation determinism?

Graph coloring preserves determinism because colors are processed in a fixed sequential order, and synchronization points occur at well-defined boundaries (between colors and simulation phases). While constraints within a color execute in parallel, the results are merged deterministically before the next stage begins, ensuring that the same initial conditions always produce identical simulation outcomes.

Can I disable parallel solving for debugging purposes?

Yes. You can force single-threaded execution by directing all constraints into the overflow color (B3_OVERFLOW_INDEX). This bypasses the parallel-for loop in the solver while maintaining the same code path, making it useful for debugging race conditions or comparing single-threaded versus multi-threaded behavior. Alternatively, most task systems allow configuring the thread count to one.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}