java-topology/defects/bullet/bullet-0002.md

bullet-0002: O(M·E) collision exclusion check — findLinearSearch in checkCollideWithOverride

Severity: MEDIUM CWE: CWE-407 (Algorithmic Complexity — Insufficient Control of Quadratic Complexity) Target: bulletphysics/bullet3 File: src/BulletCollision/CollisionDispatch/btCollisionObject.h Lines: 268–273 Status: PATCHED (unit test PASS)

Description

btCollisionObject::checkCollideWithOverride is called by needsCollision() for every overlapping pair during processAllOverlappingPairs. It scans the exclusion list m_objectsWithoutCollisionCheck linearly:

// btCollisionObject.h:268
virtual bool checkCollideWithOverride(const btCollisionObject* co) const
{
    int index = m_objectsWithoutCollisionCheck.findLinearSearch(co);  // O(E)
    if (index < m_objectsWithoutCollisionCheck.size())
    {
        return false;
    }
    return true;
}

With M active collision pairs and E exclusions per object, this is O(M·E) per step. A ragdoll with E=20 self-collision exclusions and M=1000 active pairs incurs 20 000 comparisons per step in this function alone, every frame.

Root Cause

m_objectsWithoutCollisionCheck is a btAlignedObjectArray<const btCollisionObject*> — a plain array. No hash set index is maintained alongside it.

Fix

Add a parallel btHashMap<btHashPtr, bool> m_ignoreSet that mirrors the array. Replace findLinearSearch in checkCollideWithOverride with an O(1) hash lookup. Update setIgnoreCollisionCheck to keep both structures in sync.

Patch: patch/bullet-0002-collisionobject-checkcollide-hashmap.patch

Complexity

Scenario	Before	After
M pairs, E exclusions per object	O(M·E) per step	O(M) per step
M=1000, E=20	20 000 comparisons	1 000 ops
Speedup at M=1000 E=20	—	~20x

Unit Test

unit/BulletAlgorithm.java — see bullet-0002 section. Correctness: identical collision decisions for all inputs. Performance: op-count ratio >= 5x verified at M=1000 E=20 (measured 12x).

Run:

javac -d /tmp/out defects/bullet/unit/BulletAlgorithm.java
java -cp /tmp/out unit.BulletAlgorithm

Output: 6/6 PASS