공간이 아니라 물체를 나눈다

지금까지 세 번 같은 자리에서 걸렸습니다.

균일 격자에서는 물체가 칸 경계에 걸치면 양쪽에 다 넣어야 했습니다. 쿼드트리에서는 부모에 남길지, 걸친 자식마다 중복해서 넣을지, 칸을 느슨하게 잡을지를 골라야 했습니다. KD 트리는 아예 점만 담을 수 있어서 크기가 있는 것은 넣지 못했습니다.

공통점이 있습니다. 셋 다 공간을 먼저 자르고 물체를 그 칸에 끼워 넣습니다. 자르는 선이 물체를 관통하는 것은 막을 방법이 없습니다. 물체에게 물어보고 자른 게 아니니까요.

물체 하나가 몇 칸에 들어가나

얼마나 심각한지부터 재 봤습니다. 1000 × 1000 맵에 크기가 제각각인 물체 1000개를 뿌리고, 격자에 담을 때 물체 하나가 몇 칸에 등록되는지 셌습니다.

칸을 잘게 잡을수록 나빠집니다. 칸 10이면 물체 하나가 평균 10칸에 들어가고, 가장 큰 물체는 72칸에 등록됩니다.

이건 메모리만의 문제가 아닙니다.

• 그 물체가 한 칸 움직이면 72개 목록에서 빼고 새 칸들에 다시 넣어야 합니다
• 질의 한 번에 같은 물체가 여러 번 나오니 중복 제거를 해야 합니다
• 칸을 키워서 중복을 줄이면 이번엔 한 칸에 담기는 물체가 늘어납니다

칸 크기를 어디에 맞춰도 한쪽이 나빠집니다. 1편에서 본 것과 같은 모양의 딜레마입니다.

물체를 둘로 가른다

발상을 뒤집습니다. 공간을 자르지 말고 물체를 나눕니다.

물체 전부를 감싸는 상자 하나로 시작합니다. 그 물체들을 두 무리로 가르고, 각 무리를 감싸는 상자를 하나씩 만듭니다. 각 무리 안에서 같은 일을 반복합니다. 무리에 몇 개 안 남으면 거기서 멈춥니다.

이것이 BVH(bounding volume hierarchy, 경계 볼륨 계층) 입니다. 감싸는 도형으로는 축에 나란한 상자(AABB)를 가장 많이 쓰고, 구나 기울어진 상자를 쓰기도 합니다.

앞의 셋과 다른 점이 눈에 보입니다.

• 상자가 물체에 딱 붙어 있습니다. 빈 공간을 감싸는 칸이 없습니다
• 물체는 정확히 한 잎에만 들어갑니다. 쪼개지도, 중복되지도 않습니다
• 대신 형제 상자끼리 겹칩니다

겹쳐도 되는 이유

공간 분할에서 칸이 겹치면 그건 버그입니다. “이 점이 어느 칸인가” 에 답이 둘이 되어 버리니까요.

BVH는 그 질문을 하지 않습니다. 묻는 것은 “이 상자를 지나가는가” 하나뿐입니다. 지나가면 들어가 보고, 안 지나가면 그 아래를 통째로 건너뜁니다. 답이 둘이어도 아무 문제가 없습니다. 양쪽 다 들어가 보면 그만입니다.

그래서 겹침은 틀린 게 아니라 낭비입니다. 겹친 만큼 양쪽을 다 들어가 보게 되니 느려질 뿐입니다. 그리고 낭비라서, 줄이려고 애쓸 대상이 됩니다.

어떻게 가를까

두 무리로 가르는 방법이 성능을 정합니다. 세 가지를 같은 장면, 같은 레이로 재 봤습니다.

• 가운데 자르기: 상자의 한가운데를 기준으로 물체 중심이 어느 쪽인지 본다
• 중앙값 자르기: 물체 중심으로 줄 세워 딱 절반씩 가른다 (KD 트리와 같은 발상)
• 넓이로 고르기: 자를 자리 후보를 여럿 놓고, 각각에 대해 양쪽 상자 겉넓이 × 그 안의 물체 수 를 재서 가장 작은 것을 고른다

중앙값 자르기는 트리가 가장 얕고 예쁘게 균형이 잡히는데 가장 느립니다. KD 트리에서 값어치였던 균형이 여기서는 값어치가 아닙니다. 개수를 반씩 맞추느라 상자가 커지고, 커진 상자에 레이가 더 자주 걸립니다.

중요한 건 개수가 아니라 넓이입니다. 레이가 상자를 맞힐 확률이 넓이에 비례하니까요. 세 번째 규칙이 그것을 직접 계산합니다. 표면적 휴리스틱(SAH, surface area heuristic) 이라고 부릅니다. 이름 그대로 겉넓이를 씁니다. 2차원이면 둘레가 그 자리를 대신합니다.

SAH는 짓는 값이 비쌉니다. 자를 자리 후보마다 양쪽 상자를 다시 계산해야 하니까요. 그래서 보통 축마다 열두 칸쯤으로 나눠 그 경계에서만 재 보는 식으로 후보를 줄입니다. 위 측정도 그렇게 했습니다.

레이를 쏜다

BVH가 가장 잘하는 일이 이것입니다.

각 노드에서 하는 일은 상자와 선이 만나는지 보는 것뿐입니다. 축에 나란한 상자라면 x 구간과 y 구간을 각각 잘라서 겹치는 구간이 남는지만 보면 됩니다. 나눗셈 몇 번이면 끝나는 슬랩 판정(slab test) 입니다.

• 상자를 안 맞히면 그 아래 물체는 하나도 안 재봅니다
• 맞히면 가까운 자식부터 들어갑니다
• 들어가기 전에 그 상자까지의 거리가 이미 맞힌 것보다 멀면 건너뜁니다

마지막 줄이 핵심입니다. 가까운 쪽을 먼저 봐서 답을 일찍 쥐면, 그 뒤로는 거의 다 걷어 낼 수 있습니다.

12개 중 4개만 실제로 재봅니다. 큰 장면에서는 차이가 훨씬 벌어집니다. 물체 1000개에 레이 2000개를 쏘면 물체 판정이 7,649번입니다. 전부 다 재보면 2,000,000번이니 0.4퍼센트입니다.

잎에 몇 개를 담을까

KD 트리에서는 2에서 4 사이가 가장 좋았습니다. BVH에서 같은 것을 재 봤습니다.

여기서는 잎 1이 가장 낫게 나옵니다. KD 트리와 다릅니다. 이유는 셈법에 있습니다. 이 표는 상자 판정과 물체 판정을 그냥 한 번씩으로 세었는데, BVH의 물체는 그 자체가 상자라서 두 판정의 값이 거의 같습니다. 그러면 잎을 키울 이유가 없습니다.

실제 엔진에서는 잎에 든 것이 삼각형이고, 삼각형 판정이 상자 판정보다 몇 배 비쌉니다. 그러면 곡선이 KD 트리 때처럼 U 자로 돌아오고, 최적점도 2에서 8 사이로 옮겨 갑니다. 표를 그대로 믿지 말고 자기 잎에 든 것이 얼마나 비싼지로 다시 재세요.

격자와 붙여 보면

같은 레이 2000개를 격자에도 쏴 봤습니다. 격자 쪽은 DDA로 칸을 하나씩 밟아 가면서, 지금까지 맞힌 것보다 다음 칸이 멀면 멈추는 방식입니다.

또 갈립니다. 고르게 흩어져 있으면 격자가 두 배 넘게 빠르고, 뭉쳐 있으면 BVH가 네 배 가까이 빠릅니다. 성긴 장면에서는 비슷합니다.

그런데 표에서 더 중요한 것은 굵은 글씨의 자리입니다. 격자가 이기는 칸 크기가 장면마다 25, 50, 100으로 옮겨 다닙니다. 장면이 바뀌면 그 값을 다시 찾아야 하고, 틀리면 두 배씩 손해를 봅니다.

BVH에는 고를 값이 없습니다. 물체가 어떻게 놓여 있든 자기가 알아서 그 모양을 따라갑니다. 성능의 최고점이 아니라 최악을 얕게 만드는 쪽이 BVH의 자리입니다.

움직이면 상자만 키울까, 다시 지을까

물체가 움직이면 상자가 안 맞습니다. 두 가지 길이 있습니다.

• 상자만 다시 맞춘다(refit). 잎부터 뿌리까지 올라오며 상자 크기만 고칩니다. 트리 구조는 그대로입니다. 빠릅니다
• 처음부터 다시 짓는다. 느리지만 품질이 돌아옵니다

refit만 계속하면 어떻게 되는지 재 봤습니다. 물체 1000개를 전부 조금씩 움직이면서, 20프레임마다 형제 상자 겹침과 레이 비용을 봤습니다.

120프레임 만에 아홉 배가 됩니다. 같은 자리에서 처음부터 다시 지으면 겹침 2.3%, 비용 15,380으로 돌아옵니다.

구조가 안 바뀌니까요. 처음에 가까이 있어서 한 무리로 묶인 물체들이 서로 반대 방향으로 흩어져도 계속 같은 상자 안에 있습니다. 상자는 그만큼 커지고, 겹침이 늘고, 레이가 양쪽을 다 들어가게 됩니다.

그래서 실제로는 이렇게 씁니다.

• 매 프레임 refit, 가끔 다시 짓기. 위 표라면 20~40프레임마다 한 번이 타협점입니다
• 안 움직이는 것과 움직이는 것을 나눠서 트리를 둘로 둡니다. 지형은 한 번 짓고 손대지 않고, 움직이는 것만 작은 트리에 담아 매 프레임 다시 짓습니다. 질의는 두 트리에 각각 던집니다
• 겹침 비율을 직접 재서 임계값을 넘으면 그때 다시 짓는 방법도 씁니다. 위 표가 바로 그 계기판입니다

어디에 쓰나

BVH가 가장 잘 맞는 자리는 선이나 원뿔을 쏘는 일입니다.

• 레이캐스트. 총알 판정, 바닥 감지, 마우스로 물체 집기, 시야 확인
• 절두체 컬링. 카메라 절두체가 상자를 안 맞히면 그 아래 전부 안 그립니다. 상자 하나로 수백 개를 걷어 냅니다
• 충돌 브로드페이즈. “겹칠 가능성이 있는 쌍” 만 추려서 정밀 판정으로 넘깁니다
• 오프라인 렌더링. 레이 트레이싱에서는 사실상 BVH밖에 안 씁니다. 지금 GPU의 레이 트레이싱 전용 회로도 BVH를 타고 내려가는 일을 합니다

반대로 “내 주변 반경 5미터 안” 같은 질의는 BVH가 잘하는 일이 아닙니다. 그건 1편의 격자가 훨씬 낫습니다. 상자 판정이 아무리 싸도 칸 아홉 개 훑는 것보다 쌀 수는 없습니다.

정리

BVH는 공간이 아니라 물체를 나누는 구조입니다.

• 물체를 두 무리로 갈라 각 무리를 상자로 감쌉니다. 물체는 정확히 한 잎에만 들어갑니다
• 격자에서는 물체 하나가 평균 열 칸, 최악 일흔두 칸에 등록됐습니다. BVH는 1.00입니다
• 형제 상자가 겹칩니다. 묻는 것이 “어느 칸인가” 가 아니라 “지나가는가” 라서 틀린 게 아니라 낭비일 뿐입니다
• 가르는 규칙은 개수가 아니라 넓이로 골라야 합니다. 개수를 반씩 맞추는 규칙이 가장 느렸습니다
• 레이를 쏘면 물체 판정이 전체의 0.4퍼센트까지 줄었습니다
• 고른 분포에서는 격자가 두 배 빠릅니다. BVH의 자리는 최고점이 아니라 얕은 최악입니다
• 상자만 고치면 120프레임 만에 아홉 배 느려집니다. 주기적으로 다시 짓거나, 정적과 동적을 나눠 담으세요