공간 인덱스의 정확성 기준은 빠르게 찾는 것이 아니라 실제로 충돌할 쌍을 후보에서 빠뜨리지 않는 것입니다. 한 tick의 이동 범위와 객체의 생명주기·layer·형상 시점을 먼저 고정한 뒤, 그 보수적 집합을 grid나 tree로 줄이고 마지막에 정밀 판정을 적용합니다.
후보 축소와 실제 충돌 누락의 구분
n개 물체의 모든 쌍은 n(n−1)/2입니다. broad phase는 AABB·원 등 보수 경계로 가능성 있는 쌍을 추리고 narrow phase는 실제 캡슐·박스·mesh·trigger·접촉 규칙을 검사합니다. broad phase false positive는 추가 비용이지만 false negative는 정밀 단계가 복구할 수 없는 누락입니다.
물체가 한 tick 안에 cell A에서 C로 이동하면 시작 cell과 현재 cell만 조회할 때 사이의 cell B를 건너뛸 수 있으므로, 후보 범위가 이동 구간 전체를 덮어야 합니다. 선형 병진에서는 시작·끝 형상을 포함한 swept AABB로 그 tick의 이동을 감쌀 수 있지만, 회전·곡선 운동은 endpoint box를 합친 것만으로 중간 궤적을 포함하지 못할 수 있습니다. 그런 경우에는 중간 궤적까지 포함한 bound나 별도 continuous 검사를 사용합니다.
Cell 크기와 Query·Update 비용의 절충
cell side s, 반경 R이면 각 축에서 [floor((x-R)/s), floor((x+R)/s)] 범위를 조회합니다. 작은 s는 cell당 후보를 줄이지만 조회할 cell·hash lookup·큰 객체 다중 등록·이동 update가 늘어납니다. 큰 s는 등록이 단순해도 hotspot 후보가 늘 수 있습니다.
음수 x=-1,s=16은 floor division으로 cell=-1이어야 합니다. 0 방향 truncate는 cell0에 잘못 넣습니다. hash bucket 충돌은 실제 cell 동일성이 아니므로 bucket 안에서 원래 cell 좌표를 비교합니다.
| 구조 | 유리한 조건 후보 | 비용 |
|---|---|---|
| uniform grid | 비슷한 크기·국소 이동 | hotspot·큰 물체 다중 등록 |
| spatial hash | 큰 희소 공간 | hash lookup·bucket 충돌 |
| dynamic AABB tree | 크기 차이·다양한 질의 | update·회전·pointer·tree 품질 |
| hierarchical grid | 여러 크기 규모 | 관련 level 모두 조회·전환 관리 |
큰 객체와 중심 Cell 등록의 한계
형상이 여러 cell에 걸치면 AABB 전체를 index에 등록하거나, 크기 상한만큼 query를 넓히거나, 큰 객체용 별도 구조를 둡니다. 여러 cell에서 같은 객체를 다시 찾을 수 있으므로 ID+generation 방문 집합에 이미 본 객체를 기록해 dedup하고, 쌍은 canonical ordered pair로 순서를 정해 한 번만 처리합니다. 이 중복 제거가 객체가 실제로 살아 있는지 보장하지는 않으므로, 후보를 조회하고 정밀 검사하는 동안의 객체 lifetime 보호는 별도로 둡니다.
그림을 글로 읽기
- tick snapshot · 위치·형상·layer
- swept bound·grid/tree 후보
- ID·generation·pair dedup
- 정밀 형상·TOI·게임 정책
- 안정 event ID로 효과 확정
- tick snapshot · 위치·형상·layer → swept bound·grid/tree 후보: 보수적 포함
- swept bound·grid/tree 후보 → ID·generation·pair dedup: 중복 후보 허용
- ID·generation·pair dedup → 정밀 형상·TOI·게임 정책: 수명 보호
- 정밀 형상·TOI·게임 정책 → 안정 event ID로 효과 확정: 최종 판정
Layer 변경과 후보 집합 갱신
물체가 움직이지 않아도 collision mask나 활성 상태가 바뀌면, 이전에는 제외했던 쌍이 새 후보가 됩니다. layer별 index/filter를 쓰는 경우에는 그 상태 변경을 index에 반영한 뒤 query가 새 layer를 읽게 해야 합니다. 갱신 중 snapshot이 갈리면 같은 tick의 위치·형상·layer를 함께 읽거나, 옛 후보와 새 후보를 보수적으로 둘 다 유지하고 최종 단계에서 하나의 일관된 정책으로 판정합니다.
삭제·ID 재사용에는 generation, 메모리 접근에는 참조 보호가 필요합니다. version을 읽으려 이미 해제된 pointer에 접근하는 것은 안전하지 않습니다.
진단 시 한 tick의 위치·AABB·layer·활성 상태에 버전을 붙이고, query가 읽은 버전을 기록하면 후보 누락을 분리하기 쉽습니다. 전수 정밀 판정의 쌍이 index 후보에 없으면 cell 계산 오류인지, swept bound 누락인지, layer snapshot 불일치인지, 전환 중 한 level만 조회한 것인지 순서대로 확인합니다.
승격·강등 전환과 후보 누락 방지
큰 객체를 old level에서 제거한 뒤 new level에 넣는 사이에 query가 오면, 잠깐 어느 level에도 없어져 후보를 놓칠 수 있습니다. 그래서 tick snapshot을 통째로 교체하거나 전환 동안 old와 new 양쪽에 등록하고 양쪽을 조회한 뒤 dedup합니다. query는 자기 level만 보지 않고 관련된 모든 크기 level을 보수적으로 포함하며, 셀 크기 전체를 바꿀 때는 index version·이중 조회·전환 cutoff를 함께 둡니다.
임계 주변의 크기/밀도 진동은 hysteresis·최소 유지로 줄이되 query correctness를 바꾸지 않습니다. 최악 hotspot에서는 실제 후보 수 자체가 많아 구조만으로 O(n²) 상호작용을 제거할 수 없을 수 있습니다.
동일 장면의 전수 충돌 쌍과 후보 누락 검사
작은 장면의 전수 정밀 충돌 쌍이 후보 집합의 부분집합인지 확인합니다. 균일·hotspot·최대 크기·긴 sweep·layer 전환·음수 cell·삭제/재생성을 시험하고 update p99·query p99·candidate 수·dedup·memory·narrow CPU를 함께 비교합니다. 이 노트는 공간 index 설계이며 실제 물리 엔진 benchmark 결과는 아닙니다.