# UNDF: UNDF-2026-000000603
# bullet3-0001: btGhostObject::addOverlappingObjectInternal — O(N²) linear dedup

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | bullet3-0001 |
| Severity | HIGH |
| Ecosystem | bullet3 |
| Package | BulletCollision/CollisionDispatch |
| File | `src/BulletCollision/CollisionDispatch/btGhostObject.cpp` |
| Lines | 37–42, 49–54, 75–80, 90–95 |
| Complexity | O(N²) total per broadphase step |
| Hot path | per broadphase overlap pair update (every physics step) |

## Background

`btGhostObject` is used for trigger volumes and character controllers
(`btKinematicCharacterController` uses `btPairCachingGhostObject`).
Every physics step the broadphase calls `addOverlappingObjectInternal` and
`removeOverlappingObjectInternal` for each new/removed pair that involves the
ghost object.

## Defect

`m_overlappingObjects` is a `btAlignedObjectArray<btCollisionObject*>` (a plain
dynamic array). Both add and remove call `findLinearSearch` which scans the
entire array to find duplicates or locate the element to remove.

```cpp
// btGhostObject.cpp line 37 — the code itself contains the admission:
///if this linearSearch becomes too slow (too many overlapping objects) we should add
///a more appropriate data structure
int index = m_overlappingObjects.findLinearSearch(otherObject);
if (index == m_overlappingObjects.size())
{
    //not found
    m_overlappingObjects.push_back(otherObject);
}
```

The same pattern occurs in `btPairCachingGhostObject::addOverlappingObjectInternal`
(line 75) and both `removeOverlappingObjectInternal` variants (lines 49, 90).

With N objects overlapping the ghost, each broadphase update requires O(N) work
per new pair. In a dense scene where G ghost objects each overlap N bodies, the
total cost per step is O(G × N²) in the worst case (N re-insertions checked
against an N-element list).

## Fix

Replace `m_overlappingObjects` with a `btHashSet`-backed structure.  Since
`btCollisionObject*` pointers are unique, pointer value works as the hash key.

**Option A — drop-in O(1) membership check using `btHashMap` as a set:**

```cpp
// btGhostObject.h — add alongside m_overlappingObjects
#include "LinearMath/btHashMap.h"

btAlignedObjectArray<btCollisionObject*> m_overlappingObjects;
btHashMap<btHashPtr, int> m_overlappingIndex;   // ptr → index in array

// addOverlappingObjectInternal
void btGhostObject::addOverlappingObjectInternal(btBroadphaseProxy* otherProxy,
                                                  btBroadphaseProxy* thisProxy)
{
    btCollisionObject* otherObject = (btCollisionObject*)otherProxy->m_clientObject;
    btAssert(otherObject);
    btHashPtr key(otherObject);
    if (m_overlappingIndex.find(key) == nullptr)
    {
        int idx = m_overlappingObjects.size();
        m_overlappingObjects.push_back(otherObject);
        m_overlappingIndex.insert(key, idx);
    }
}

// removeOverlappingObjectInternal
void btGhostObject::removeOverlappingObjectInternal(btBroadphaseProxy* otherProxy,
                                                     btDispatcher* dispatcher,
                                                     btBroadphaseProxy* thisProxy)
{
    btCollisionObject* otherObject = (btCollisionObject*)otherProxy->m_clientObject;
    btAssert(otherObject);
    btHashPtr key(otherObject);
    const int* pIdx = m_overlappingIndex.find(key);
    if (pIdx)
    {
        int index = *pIdx;
        // swap-erase: move last element into freed slot
        int lastIdx = m_overlappingObjects.size() - 1;
        if (index != lastIdx)
        {
            btCollisionObject* last = m_overlappingObjects[lastIdx];
            m_overlappingObjects[index] = last;
            m_overlappingIndex.insert(btHashPtr(last), index);
        }
        m_overlappingObjects.pop_back();
        m_overlappingIndex.remove(key);
    }
}
```

**Option B (minimal change) — keep existing array, guard entry using `btHashSet`:**

```cpp
// Use btHashMap<btHashPtr, bool> as a membership guard alongside the existing
// array to preserve the indexed getOverlappingObject(int) API.
```

The library already provides `btHashedOverlappingPairCache` as a hash-based
alternative to `btSortedOverlappingPairCache`, so the pattern is established.

## Speedup

| N (overlapping objects per ghost) | Before (ops) | After (ops) | Speedup |
|-----------------------------------|--------------|-------------|---------|
| 10 | 100 | 10 | 10× |
| 50 | 2,500 | 50 | 50× |
| 100 | 10,000 | 100 | 100× |
| 500 | 250,000 | 500 | 500× |

Character controllers with large trigger volumes (area-of-effect spells,
AI perception spheres) in complex scenes are the primary beneficiaries.

## Note

`b3SortedOverlappingPairCache::findPair` in
`src/Bullet3Collision/BroadPhaseCollision/b3OverlappingPairCache.cpp` carries
the same pattern with an even more explicit comment:

```cpp
///this findPair becomes really slow. Either sort the list to speedup the query,
///or use a different solution.
b3BroadphasePair* b3SortedOverlappingPairCache::findPair(int proxy0, int proxy1)
{
    int findIndex = m_overlappingPairArray.findLinearSearch(tmpPair);
```

This is the Bullet3 (GPU) broadphase equivalent of the same defect.
