Description

Fix O(W²·S²) memory explosion in CollisionPipeline shape-pair buffer allocation
for NXN and SAP broad phase modes. The buffer capacity shape_pairs_max was computed
as N*(N-1)/2 over the global shape count across all worlds, but shapes in
different worlds can never collide. The fix computes the sum of per-world
n*(n-1)/2 instead, matching the thread layout already used by the broad phase
kernels. At 1024 worlds with ~20 shapes each this reduces shape_pairs_max from
~210 M to ~215 K (~975×), saving 10+ GB of GPU memory across the pipeline's
pair and narrow-phase buffers.

The same fix is applied to the Kamino CollisionPipelineUnifiedKamino.

Checklist

• New or existing tests cover these changes
• The documentation is up to date with these changes
• CHANGELOG.md has been updated (if user-facing change)

Test plan

uv run --extra dev -m newton.tests -k TestShapePairsMaxScaling -v
uv run --extra dev -m newton.tests -k TestContactEstimator -v

Seven new tests in TestShapePairsMaxScaling verify:

• Single-world result matches the original formula
• Multi-world pairs scale linearly (1×/2×/4× with 1/2/4 worlds)
• 256 worlds: result is <1% of the global N² value
• Global shapes (world=-1) are correctly included per world segment
• End-to-end: CollisionPipeline with NXN and SAP on a 64-world model
  has shape_pairs_max equal to the linear per-world sum

Bug fix

Steps to reproduce:

1. Create a model with ≥1024 worlds of a multi-shape robot (e.g. ANYmal)
2. Construct CollisionPipeline(model, broad_phase="nxn") or "sap"
3. Observe GPU OOM or multi-GB allocation for pair buffers that are mostly empty

Minimal reproduction:

import newton

robot = newton.ModelBuilder()
for _ in range(5):
    b = robot.add_body()
    robot.add_shape_box(body=b, hx=0.1, hy=0.1, hz=0.1)

builder = newton.ModelBuilder()
for _ in range(1024):
    builder.add_world(robot)

model = builder.finalize()
# Before fix: shape_pairs_max ≈ 13 M, allocates ~100 MB+ just for pair buffer
# After fix:  shape_pairs_max = 10240, allocates ~80 KB
pipeline = newton.CollisionPipeline(model, broad_phase="nxn")
print(pipeline.shape_pairs_max)

Summary by CodeRabbit

• Bug Fixes

  • Reduced excessive memory use in collision detection for multi-world simulations by computing shape-pair counts per world instead of using a global all-pairs bound, improving scaling from quadratic to linear as worlds increase.

• Tests

  • Added tests validating per-world pair-count scaling, proper handling of global shapes, and prevention of quadratic memory blowup.