63 lines
2.6 KiB
Markdown
63 lines
2.6 KiB
Markdown
# 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.
|