java-topology/docs/tickets/bullet-0002-collisionobject-checkcollide-linear-scan.md

bullet-0002: btCollisionObject::checkCollideWithOverride — O(N) scan per collision pair per frame

Severity: HIGH File: src/BulletCollision/CollisionDispatch/btCollisionObject.h Line: 268 Status: PATCHED

Description

btCollisionObject::checkCollideWithOverride linearly scans m_objectsWithoutCollisionCheck (a btAlignedObjectArray<const btCollisionObject*>) to determine if two objects should be skipped for collision:

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

checkCollideWith is called by btCollisionDispatcher::needsCollision (btCollisionDispatcher.cpp:179) for every pair in processAllOverlappingPairs. With M total pairs and E exclusions per object:

• Per step cost: O(M × E)
• If E grows proportionally to M (ragdoll with N bones, all ignoring each other): O(M²) per step

Root Cause

The exclusion list is btAlignedObjectArray (a dynamic array) with only findLinearSearch for membership queries. There is no hash structure. The m_checkCollideWith integer flag gates the call (fast-path when no exclusions exist) but once any exclusion is added, every pair check pays O(E).

Fix

Replace m_objectsWithoutCollisionCheck with a btHashMap<btHashPtr, bool> or use a parallel std::unordered_set<const btCollisionObject*> for the membership check:

// In btCollisionObject.h
btHashMap<btHashPtr, bool> m_ignoreSet;   // O(1) lookup

virtual bool checkCollideWithOverride(const btCollisionObject* co) const {
    return !m_ignoreSet.find(btHashPtr(co));  // O(1)
}

void setIgnoreCollisionCheck(const btCollisionObject* co, bool ignoreCollisionCheck) {
    if (ignoreCollisionCheck)
        m_ignoreSet.insert(btHashPtr(co), true);
    else
        m_ignoreSet.remove(btHashPtr(co));
    m_checkCollideWith = (m_ignoreSet.size() > 0);
}

The array accessor getObjectWithoutCollision(index) and getNumObjectsWithoutCollision() used in serialization can be satisfied by keeping a separate btAlignedObjectArray in sync or iterating the hash map.

Speedup

Pairs (M)	Exclusions per obj (E)	Before	After
100	5	500 ops	100 ops
1 000	20	20 000 ops	1 000 ops
5 000	50	250 000	5 000

Estimated ~20x speedup for a ragdoll with 20 bones (all ignoring each other) in a 1000-pair scene.