How Box3D Shares Identical Convex Hulls Across Shapes Using a Reference-Counted Database

Box3D stores convex hull geometry in a reference-counted world-level database that deduplicates identical hulls by content hash, allowing multiple collision shapes to share a single memory copy while automatically managing lifetime through reference counting.

The erincatto/box3d physics engine implements a sophisticated hull deduplication system to minimize memory overhead when multiple rigid bodies use identical convex geometry. Instead of storing separate hull copies for every shape, Box3D maintains a global database at the world level that tracks unique convex hulls via content hashing and reference counting.

Reference-Counted Storage Architecture

The world-level database owns all shared hull data through the b3HullData structure. When you create a hull shape using b3CreateHullShape, the library returns a pointer to a world-owned copy rather than adopting the stack-allocated data you provide. The database tracks reference counts for each unique hull, ensuring that the memory remains valid as long as any shape references it.

This architecture prevents memory bloat when thousands of bodies share common geometries like boxes or convex polyhedra. The implementation resides primarily in src/shape.c for the API layer and src/physics_world.c for the database management.

Content-Hash Deduplication

Box3D identifies identical hulls by computing a content hash of the raw hull data, including any deterministic padding bytes. When b3CreateHullShape receives a hull descriptor, the system:

1. Computes a hash of the hull's vertex and face data
2. Checks the world's database for an existing entry matching that hash
3. Returns the existing b3HullData pointer if found, or allocates and stores a new copy if unique

This deduplication occurs even for hulls created on different stack frames. As demonstrated in the test suite, two separate calls to b3MakeBoxHull with identical dimensions will resolve to the same shared database entry.

Creating and Accessing Shared Hulls

The b3CreateHullShape function automatically handles the lookup and sharing logic. When you create shapes from identical geometry, the returned hull pointers compare equal:

b3WorldId world = b3CreateWorld(&worldDef);
b3BoxHull box = b3MakeBoxHull(0.5f, 0.5f, 0.5f);

b3BodyId bodyA = b3CreateBody(world, &bodyDef);
b3BodyId bodyB = b3CreateBody(world, &bodyDef);

b3ShapeId shapeA = b3CreateHullShape(bodyA, &shapeDef, &box.base);
b3ShapeId shapeB = b3CreateHullShape(bodyB, &shapeDef, &box.base);

const b3HullData* gotA = b3Shape_GetHull(shapeA);
const b3HullData* gotB = b3Shape_GetHull(shapeB);

// Both shapes point to the same shared world-owned copy
ENSURE(gotA == gotB);
ENSURE(gotA != &box.base); // Not the original stack variable

According to the test suite in test/test_world.c (lines 973-996), this sharing occurs automatically regardless of whether the source b3BoxHull variables are distinct stack allocations.

Lifetime Management and Safety

The reference counting mechanism ensures safe hull destruction. When shapes are destroyed via b3DestroyShape, the database decrements the reference count for that hull. Only when the last referencing shape is destroyed does the system free the hull memory.

You can safely update a shape's hull using b3Shape_SetHull with its own shared pointer without triggering premature deletion:

const b3HullData* gotD = b3Shape_GetHull(shapeD);
b3Shape_SetHull(shapeD, gotD);
ENSURE(b3Shape_GetHull(shapeD) == gotD);

This operation (demonstrated in test/test_world.c lines 1010-1016) maintains the reference count correctly, preventing use-after-free errors.

Implementation by Source File

The hull database functionality spans several key files in the repository:

• src/shape.c – Implements b3CreateHullShape, b3Shape_GetHull, and b3Shape_SetHull, handling the hash lookup and reference count increment/decrement logic.
• src/physics_world.c – Contains the world-level database storage, hash map implementation for hull lookups, and the assertion that verifies all hulls are freed when the world destroys.
• test/test_world.c – Houses TestHullDatabase, which verifies deduplication, pointer equality, and proper reference counting across shape lifetimes.

Verification via Test Suite

The TestHullDatabase function in test/test_world.c validates the sharing behavior through several specific scenarios:

Cross-frame deduplication ensures that hulls created in separate stack frames resolve to the same database entry:

b3BoxHull box2 = b3MakeBoxHull(0.5f, 0.5f, 0.5f);
b3ShapeId shapeC = b3CreateHullShape(bodyC, &shapeDef, &box2.base);
ENSURE(b3Shape_GetHull(shapeC) == gotA);

(See test/test_world.c lines 1000-1007).

Partial destruction safety confirms that destroying one shape preserves the hull for remaining shapes:

b3DestroyShape(shapeA, true);
const b3HullData* stillB = b3Shape_GetHull(shapeB);
ENSURE(stillB == gotB);

(See test/test_world.c lines 1018-1022).

When the world itself is destroyed, the system asserts that the hull-reference database is empty, confirming that all hulls were properly released after their last referencing shapes were destroyed.

Summary

• World-level database – The b3World maintains a centralized store of unique convex hulls using b3HullData structures.
• Automatic deduplication – b3CreateHullShape hashes hull contents and returns pointers to existing identical hulls rather than creating duplicates.
• Reference counting – The database tracks how many shapes reference each hull, freeing memory only when the final reference is destroyed.
• Safe updates – Functions like b3Shape_SetHull handle reference count management automatically, preventing dangling pointers.
• Verified behavior – The TestHullDatabase suite in test/test_world.c confirms that identical geometries share memory across different stack allocations and body instances.

Frequently Asked Questions

How does Box3D determine if two convex hulls are identical?

Box3D computes a content hash of the raw hull data—including vertices, faces, and deterministic padding—when b3CreateHullShape is called. If the hash matches an existing entry in the world's database, the function returns a pointer to the stored b3HullData rather than allocating a new copy. This hash-based lookup ensures that geometrically identical hulls share the same memory regardless of when or where they were created.

What happens to the shared hull when I destroy a shape?

When b3DestroyShape is called, the hull database decrements the reference count for that shape's associated hull. The hull memory remains valid if other shapes still reference it. Only when the last shape referencing a particular hull is destroyed does the system remove the hull from the database and free its memory. This prevents use-after-free errors while allowing automatic cleanup of unused geometry.

Can I force a shape to use a specific hull from another shape?

Yes. You can retrieve a shared hull pointer using b3Shape_GetHull from one shape and pass it to b3Shape_SetHull on another shape (or the same shape). Because both operations manipulate reference counts, setting a hull to its existing pointer remains safe and does not cause premature deletion. The database ensures the underlying b3HullData persists as long as any shape references it.

Does the hull database work with stack-allocated hull definitions?

Yes. When you pass a stack-allocated b3BoxHull or b3HullData to b3CreateHullShape, the function copies the data into the world's database if no identical hull exists. The shape receives a pointer to this persistent world-owned copy, not the original stack variable. This allows temporary hull definitions to be used for shape creation without worrying about their scope outlasting the physics simulation.

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