플랫랜드 비유
에드윈 애벗의 『플랫랜드』(1884): 2차원 평면의 주민들. 그들은 길이와 너비만 인지한다. 깊이: 그들 위에 있는 제3의 차원은 보이지 않는다. 그들은 이를 인지할 수 없고, 사용할 수 없으며, 이를 이용해 구축할 수 없다. 그들의 세계 기하에는 구조적으로 폐기된 차원이 존재한다.
MOAD-0007도 동일하게 작동한다. 3D 공간의 객체들은 위치, 회전, 경계 체적을 지닌다: 풍부한 기하 구조. 선형 탐색은 이들을 평평한 목록으로 취급한다. 공간 구조는 존재하지만 사용되지 않고 폐기된다. 모든 교차 테스트는 전체 목록을 스캔하며, 객체에 기하나 위치가 없는 것처럼 처리한다.
Three.js 예제
Three.js Raycaster.intersectObjects(): 주어진 광선(3D 공간에서의 위치와 방향)을 사용하여 광선과 교차하는 모든 객체를 찾습니다. 구현 방식: 장면 내 모든 N개의 객체를 순회하며 각 객체에 대해 광선과의 교차 테스트를 수행합니다. 호출당 O(N) 복잡도.
호버 이벤트 핸들러는 초당 60프레임마다 intersectObjects()를 한 번씩 호출합니다. N=100개의 객체일 경우: 초당 6,000회의 교차 테스트. N=10,000개의 객체일 경우: 초당 600,000회의 테스트. 비용은 광선이 실제로 교차하는 객체 수가 아닌 N에 비례합니다.
N=100일 때: 눈에 띄지 않습니다. 60fps 기준 16.7ms의 프레임 예산이 비용을 흡수합니다.
N=10,000일 때: 지배적입니다. 초당 600,000회의 교차 테스트가 메인 스레드를 포화시킵니다. 프레임 속도가 떨어집니다. N=100에서 작동하던 장면이 임계점을 넘으면서 조용히 붕괴합니다.
선형 스캔이 버리는 구조
객체는 공간 내에 위치를 차지합니다. (1000, 0, 0) 위치의 객체는 (0, 0, 0)에서 (-1, 0, 0) 방향으로 향하는 광선과 교차할 수 없습니다: 객체가 반대 방향에 있기 때문입니다. 선형 스캔은 어쨌든 해당 객체를 검사합니다.
객체는 경계 체적(bounding volume)을 가집니다: 객체 전체를 감싸는 구체 또는 상자입니다. 객체의 경계 체적과 교차하지 않는 광선은 해당 객체와 교차할 수 없습니다. 선형 스캔은 어쨌든 전체 교차 테스트를 수행합니다.
지오메트리는 어떤 객체를 건너뛸지 인코딩합니다. 선형 스캔은 이 지오메트리를 무시합니다. 이것이 바로 폐기(discard)입니다.
'구조 버리기'의 의미
Flatland 비유: 애벗의 주민들은 깊이를 인식할 수 없었다. Flatland 결함은 데이터에 존재하지만 알고리즘에 결코 들어오지 않는 기하학적 구조를 버린다.
해시 집합이 MOAD-0007을 해결할 수 없는 이유
MOAD-0001 수정: 순차적 멤버십 테스트를 해시 집합으로 교체. list.contains(x): O(N). set.has(x): O(1). 멤버십 질문: '이 컬렉션에 x가 있는가?' 공간 기하학은 관여하지 않음.
MOAD-0007 수정: 선형 공간 스캔을 공간 인덱스(BVH, octree, k-d tree, R-tree)로 교체. 공간 질문: '이 컬렉션에서 어떤 객체가 이 ray/sphere/frustum과 교차하는가?' 공간적 근접성이 필요함.
해시 집합은 멤버십을 답변: '이 정확한 객체가 존재하는가?' O(1). 근접성을 답변할 수 없음: '이 ray 근처에 어떤 객체가 있는가?' 해시 집합은 거리나 공간적 범위 개념이 없음. 해싱은 선형 스캔만큼 철저히 기하학을 버림.
BVH는 근접성을 답변: '이 공간 쿼리 내에 어떤 객체가 속하는가?' O(log N + k). 객체를 위치별로 정리하므로 근접성 쿼리는 기하학적으로 멀리 떨어진 객체를 건너뜀.
| 질문 | 올바른 구조 | 잘못된 구조 |
|---|---|---|
| 이 집합에 객체 X가 있는가? | HashSet (O(1)) | 선형 리스트 (O(N)) |
| 이 ray와 교차하는 객체는? | BVH/octree/k-d tree (O(log N)) | 선형 스캔 또는 HashSet (O(N) 또는 O(N)) |
MOAD-0001 & MOAD-0007: 둘 다 O(N) 연산이 더 빠른 것으로 대체되었습니다. 질문이 다르기 때문에 다른 구조가 필요합니다.
언제 빌드하고, 언제 건너뛸까
BVH를 빌드하는 데 O(N log N)이 소요됩니다. 쿼리는 O(log N + k) 비용이 듭니다. 손익분기점: 쿼리 횟수가 빌드 횟수를 충분히 초과하여 쿼리 절감이 빌드 비용을 초과할 때입니다.
N=100일 때: 선형 스캔은 마이크로초 단위로 수행됩니다. BVH 빌드는 오버헤드를 추가합니다. BVH를 건너뛰세요.
N=10,000, 60Hz일 때: 선형 스캔이 프레임 예산을 지배합니다. BVH 쿼리는 선형 스캔의 1/1,000 비용이 듭니다. BVH를 한 번 빌드하고 초당 60회 쿼리하세요. 첫 프레임 전에 손익분기점에 도달합니다.
규칙: N * Q > N log N일 때 빌드하세요. 여기서 Q는 재빌드 주기당 쿼리 수입니다. 인터랙티브 3D 장면의 경우: Q = 초당 60, N 임계값 = 수백 개의 객체.
3D 장면 진단 및 수정
3D 시각화 애플리케이션이 5,000개의 기하학적 객체를 렌더링합니다. 호버 핸들러가 초당 60회 발생합니다. 매 호버 이벤트마다 핸들러는 scene.intersectObjects(ray, objects)를 호출하여 5,000개의 객체를 모두 순회하고 각 객체를 레이와 테스트합니다. 프레임 속도가 60fps에서 8fps로 떨어졌습니다.
팀원이 제안합니다: '모든 객체를 Set에 넣어 O(1) 조회를 하자.'