# 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:

```cpp
// 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:

```cpp
// 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.