Mesh BVH

내게는 늘 의문이었다. 레이캐스팅은 정말 triangle을 전부 검사하는 걸까? 그냥 날아가는 레이와
처음 충돌하는 애만 가져오면 되는 거 아닌가. 전부 다 검사해야 된다는 말에 힘들었고, AABB 검사를
알았을 때 환희했다. 그러다 BVH 같은 방법을 통해 메시를 줄일 수 있다는 걸 알고 너무 기뻤고
마침내 복잡한 메시의 수많은 triangle조차 묶어서 처리할 수 있게 되었을 때 놀랐다.

Scene BVH가 어떤 오브젝트를 검사할지를 줄이는 구조라면, Mesh BVH는 선택된 오브젝트 내부에서
어떤 triangle을 검사할지를 줄이는 구조다. 즉 서로 다른 단계다. 먼저 Scene BVH로 오브젝트
후보를 줄이고, 그 다음 복잡한 메시 내부에서는 Mesh BVH로 검사하는 triangle 수를 줄인다.

1. 어떻게 작동하는가

Scene BVH가 잘 동작하더라도, 최종 후보 오브젝트가 고폴리곤 메시라면 마지막 단계에서 여전히
많은 triangle 교차 판정이 남는다. 특히 picking처럼 가장 가까운 triangle 하나를 찾는 작업에서는
오브젝트 후보를 몇 개로 줄였더라도 메시 하나가 수천, 수만 개의 triangle을 가지면 비용이 커질 수 있다.

Mesh BVH는 이 문제를 줄이기 위해 메시 내부 triangle들을 다시 계층적으로 묶는다.
따라서 ray가 닿지 않는 triangle 묶음을 빠르게 후보에서 제외시킬 수 있다. 일종의
가지치기다.

static 메시라면 로딩 시점에 한 번 빌드해 계속 재사용할 수 있다. 반면 스키닝이나 변형처럼
정점 위치가 계속 크게 변하는 메시에서는 유지 비용을 따져 봐야 한다.

2. picking 파이프라인에서의 위치

Mesh BVH는 보통 다음 순서로 사용된다.

Scene BVH로 ray와 관련 없는 오브젝트를 먼저 제거한다.
hit 가능성이 있는 오브젝트에 대해서만 Mesh BVH 순회를 시작한다.
메시 내부 노드의 bound와 ray를 검사하면서 miss인 서브트리를 버린다.
리프 노드에 도달했을 때만 실제 triangle 교차 판정을 수행한다.
최종적으로 가장 가까운 hit triangle을 결과로 선택한다.

핵심은 모든 triangle을 직접 검사한 뒤 가장 가까운 것을 고르는 방식 대신,
triangle 묶음을 먼저 버리면서 내려간다는 점이다.

3. 함께 고려할 수 있는 최적화

Child traversal ordering
- 자식 노드를 ray 진행 방향 기준으로 가까운 순서대로 방문해 early pruning 가능성을 높인다.
SIMD / packetized intersection
- 리프에 도달한 뒤 여러 triangle 교차 판정 자체를 더 빠르게 수행한다.
Proxy mesh
- 매우 정밀한 원본 메시 대신, picking 전용 저해상도 메시를 별도로 두는 방식이다. picking 정확도는 떨어진다.

4. 정리

Scene BVH가 오브젝트 단위 가지치기라면, Mesh BVH는 triangle 단위 가지치기다.
둘을 함께 쓰면 어떤 오브젝트를 볼지와 그 오브젝트 내부에서 어떤 triangle을 볼지를
순차적으로 줄일 수 있다.

Mesh BVH는 오브젝트 수보다 오브젝트 하나당 triangle 수가 큰 경우에 특히 효과가 크다.
예를 들어 scene-level 후보는 적지만, 각 후보가 복잡한 정적 메시인 편집기 picking이나
정밀 충돌 검사에서 유용하다.