마우스 클릭 한 번에 일어나는 일
3D 뷰어에서 물체를 클릭하면 "Raycasting"이라는 과정이 실행됩니다. 화면에서 마우스 위치를 기준으로 가상의 광선을 쏘고, 그 광선이 어떤 물체와 부딪히는지를 계산하는 겁니다.
기본 방식의 한계
기본 방식은 메시의 모든 삼각형을 하나씩 확인합니다. 10만 개의 삼각형이 있으면 10만 번 검사합니다. 마우스를 움직일 때마다.
BVH란?
BVH(Bounding Volume Hierarchy)는 3D 공간을 효율적으로 탐색하기 위한 트리 자료구조입니다.
기본 원리
3D 모델은 수만~수십만 개의 삼각형으로 이루어져 있습니다. 광선이 어떤 삼각형과 부딪히는지를 알려면 원래는 모든 삼각형을 하나씩 검사해야 합니다.
BVH는 이 삼각형들을 **바운딩 박스(AABB, Axis-Aligned Bounding Box)**로 감싸서 계층적으로 묶습니다.
[전체 모델] ← 루트 바운딩 박스
/ \
[왼쪽 절반] [오른쪽 절반] ← 공간을 둘로 분할
/ \ / \
[△△△] [△△△] [△△△] [△△△] ← 리프 노드 (실제 삼각형)
광선이 루트 박스에 닿지 않으면 → 전체 모델 검사 종료. 광선이 왼쪽 절반 박스에만 닿으면 → 오른쪽 절반은 통째로 건너뜁니다. 이런 식으로 매 단계마다 검사 범위가 절반으로 줄어듭니다.
분할 전략: SAH (Surface Area Heuristic)
트리의 성능은 "어디서 공간을 나누느냐"에 달려 있습니다. Voxel3D는 SAH(Surface Area Heuristic) 전략을 사용합니다.
SAH는 "자식 노드의 표면적이 작을수록 광선이 그 노드에 닿을 확률이 낮다"는 원리를 활용합니다. 가능한 모든 분할 위치를 비교해서, 전체 탐색 비용이 가장 낮아지는 지점을 찾습니다.
비용 = 왼쪽 표면적/부모 표면적 × 왼쪽 삼각형 수
+ 오른쪽 표면적/부모 표면적 × 오른쪽 삼각형 수
빌드 시간은 더 걸리지만, 이후 광선 탐색이 가장 빠른 트리를 만들어 냅니다. 실시간 인터랙션이 중요한 3D 뷰어에 적합한 전략입니다.
다른 분할 전략
| 전략 | 방식 | 빌드 속도 | 탐색 성능 |
|---|---|---|---|
| SAH | 표면적 기반 최적 분할 | 느림 | 최고 |
| CENTER | 삼각형 중심점 기준 분할 | 빠름 | 보통 |
| AVERAGE | 평균 위치 기준 분할 | 빠름 | 보통 |
어디에 쓰이나
BVH는 3D 분야 전반에서 사용되는 핵심 알고리즘입니다.
- 게임 엔진 (Unreal, Unity): 충돌 감지, 오클루전 컬링
- 광선 추적 렌더러 (NVIDIA RTX): GPU 가속 BVH로 실시간 레이트레이싱
- 물리 시뮬레이션: 충돌 후보 쌍 빠르게 탐색
- 3D 뷰어 (Voxel3D): Raycasting, 단면 계산, 거리 측정
BVH로 해결
Voxel3D는 이 BVH를 Raycasting에 적용합니다. 공간을 트리 구조로 나눠서, 광선이 지나지 않는 영역은 통째로 건너뜁니다.
기본: 10만 삼각형 → 10만 번 검사 (O(n))
BVH: 10만 삼각형 → ~17번 검사 (O(log n))
구현 방식
- three-mesh-bvh 라이브러리를 활용하되, BVHManager로 감싸서 관리
- 기존 코드 수정 없이, 모든 메시의 raycast가 자동으로 가속
- 50만 삼각형 이상의 대형 메시는 메모리 보호를 위해 자동 필터링
- Grid, Gizmo 같은 보조 객체는 BVH 생성 대상에서 제외
BVH 위에서 동작하는 기능들
BVH의 진짜 가치는 클릭 한 번이 빨라지는 것만이 아닙니다.
Selection (물체 선택)
BVH 트리 탐색으로 후보 삼각형을 줄이고, 첫 번째 교차점을 찾으면 즉시 중단합니다. 대형 모델에서도 마우스 클릭이 즉각 반응합니다.
Clipping Edge (단면 윤곽선)
씬의 모든 모델을 하나의 geometry로 병합한 뒤 단일 BVH를 구축합니다. 이 BVH에서 평면과 삼각형의 교차선을 실시간으로 계산하여 단면 윤곽선을 시각화합니다.
Measurement (거리 측정)
BVH 기반 기하 분석으로 두 메시 사이의 정밀 거리를 계산합니다.
BVH (기반)
├── Selection - firstHitOnly + BVH 가속
├── Clipping Edge - merged BVH + shapecast
└── Measurement - BVH 기반 기하 분석
BVH 없이는 이 기능들이 대형 모델에서 실시간으로 작동할 수 없습니다. Voxel3D에서 사용자가 느끼는 모든 반응 속도는 BVH에서 시작됩니다.