표면적 휴리스틱

컴퓨터 그래픽스 게임 개발 마지막 수정: 2026-08-30 04:39:08

1. 개요[편집]

광선이 어디에 부딪힐지는 모른다. 다만 표면적이 넓은 상자에 더 자주 부딪힌다는 것은 안다. 그 한 줄에 30년치 가속 구조 연구가 얹혀 있다.

표면적 휴리스틱(Surface Area Heuristic, SAH)은 경계 볼륨 계층이나 KD-트리를 지을 때 「여기서 자르면 나중에 광선 순회가 얼마나 비쌀까」를 표면적으로 추정해, 그 기댓값이 최소인 분할을 고르는 비용 모형이다. 중앙값 분할이나 축을 번갈아 자르는 규칙과 달리, SAH는 트리의 균형이 아니라 질의 비용 자체를 목적함수로 놓는다. 골드스미스와 새먼이 1987년에 표면적 기반 비용 추정을 제안했고 맥도널드와 부스가 1990년에 KD-트리 분할 기준으로 정식화한 뒤, 지금까지 이를 범용으로 이긴 휴리스틱이 나오지 않았다.¹

여기서 「휴리스틱」이라는 이름에 속으면 안 된다. 비용식 자체는 몇 개의 명시적 가정 아래 유도되는 기댓값이고, 휴리스틱인 부분은 오직 그 가정들(광선이 균일하다, 조기 종료가 없다, 부분트리가 독립이다)이 실제와 다르다는 데 있다. 가정을 정확히 알아야 SAH가 언제 배신하는지도 알 수 있다.

2. 출발점 — 표면적은 확률이다[편집]

SAH의 뿌리는 렌더링이 아니라 적분기하학이다. 3차원 공간의 직선 전체에 운동 불변 측도(회전·평행이동에 불변인 유일한 측도)를 주면, 볼록체 $K$ 와 만나는 직선들의 측도가 $K$ 의 표면적에 비례한다. 코시의 공식 — 볼록체의 모든 방향 평균 투영 넓이가 $S(K)/4$ 라는 — 이 그 계산의 핵심이다. 여기서 곧바로 따라오는 결론이 SAH의 전부다.

A \subseteq B\ \text{(둘 다 볼록)} \quad\Longrightarrow\quad \Pr\bigl[\text{직선이 } A \text{와 만남} \,\big|\, \text{직선이 } B \text{와 만남}\bigr] \;=\; \frac{S(A)}{S(B)}

2차원이면 표면적 자리에 둘레가 들어간다. 「부피 비」가 아니라는 것이 처음 보면 반직관적인데, 광선은 부피를 채우는 것이 아니라 표면을 뚫고 들어가는 물건이라고 생각하면 납득된다. 얇은 판자는 부피가 0에 가까워도 광선에 자주 맞는다.

이 조건부 확률에 딸린 세부 조건이 둘 있다. 직선의 분포가 균일하고 무한히 뻗어 있어야 하고, $A$ 와 $B$ 가 볼록해야 한다. 실무의 AABB는 볼록하니 두 번째는 공짜이고, 첫 번째가 뒤에서 문제를 일으킨다.

3. 비용식[편집]

노드 $N$ 을 왼쪽 $L$ 과 오른쪽 $R$ 로 나눈다고 하자. 광선이 이미 $N$ 에 맞았다는 조건 아래, 그 광선이 치를 기대 비용은

C(\text{split}) \;=\; C_{\text{trav}} \;+\; \frac{S(L)}{S(N)}\, n_L\, C_{\text{int}} \;+\; \frac{S(R)}{S(N)}\, n_R\, C_{\text{int}}

이다. $C_{\text{trav}}$ 는 내부 노드 하나를 순회하는 비용(상자 두 개와의 교차 판정), $C_{\text{int}}$ 는 프리미티브 하나와의 교차 판정 비용, $n_L, n_R$ 은 각 자식이 품은 프리미티브 수다. 읽는 법은 「어차피 이 노드에는 왔으니 순회 비용 하나는 무조건 내고, 왼쪽 자식에 들어갈 확률 $S(L)/S(N)$ 만큼 $n_L$ 번의 교차 판정을 기대한다」이다.

비교 대상은 잎으로 끝냈을 때의 비용이다.

C(\text{leaf}) \;=\; n\, C_{\text{int}}

그래서 종료 조건이 자동으로 나온다 — 모든 후보 분할의 최소 비용이 $C(\text{leaf})$ 보다 크면 더 쪼개지 말고 잎으로 만든다. 최대 깊이나 「프리미티브 4개 이하면 잎」 같은 임의의 규칙이 필요 없고, 비용 모형이 트리 모양을 통째로 결정한다는 것이 SAH의 미덕이다.

상수 비는 실측으로 정한다. 관례적으로 $C_{\text{trav}} = 1$ 로 두고 $C_{\text{int}}$ 를 1~2 사이에서 잡는데, 이 비를 키우면 트리가 얕아지고(교차가 비싸니 잎을 작게 만들 이유가 줄어든다) 줄이면 깊어진다. 하드웨어가 바뀌면 다시 재야 하는 값이며, GPU에서 SIMD 폭 단위로 프리미티브를 처리한다면 $C_{\text{int}}$ 는 개수가 아니라 묶음 개수에 붙어야 맞다.

여기서 BVH 특유의 함정이 하나 있다. 자식 AABB 둘이 겹칠 수 있어 $S(L) + S(R) \ge S(N)$ 이고, 두 확률의 합이 1을 넘을 수 있다. 확률의 공리를 위반하는 것이 아니라 「왼쪽에도 맞고 오른쪽에도 맞는」 사건이 이중으로 세어질 뿐이지만, 이 겹침이 SAH가 실제 성능을 과소평가하는 주된 통로다. 공간을 자르는 KD-트리에서는 자식 셀이 겹치지 않아 이 문제가 없는 대신, 걸친 프리미티브가 양쪽에 중복 등록되어 $n_L + n_R > n$ 이 된다. 어느 쪽이든 공짜는 없다.

4. 후보를 다 훑는 방법 — 스윕[편집]

이론적으로 좋은 분할 위치를 찾으려면 후보를 다 봐야 한다. 다행히 비용식은 후보 위치 사이에서 조각별로 단조라서, 프리미티브 경계상자의 끝점들만 후보로 보면 충분하다. 축 하나에 대한 절차는 이렇다.

프리미티브를 그 축의 중심 좌표로 정렬한다.
왼쪽에서 오른쪽으로 훑으며 접두 AABB와 개수를 누적해 배열에 적는다.
오른쪽에서 왼쪽으로 훑으며 접미 AABB와 개수를 누적한다.
$n-1$ 개의 분할 위치 각각에서 두 배열을 읽어 비용식을 평가하고 최솟값을 기억한다.

세 축 모두 이렇게 하고 전체 최소를 고른다. 노드 하나의 비용이 정렬을 빼면 $O(n)$ 이고, 정렬을 재귀 전에 축마다 한 번만 해 두고 분할 때 안정적으로 쪼개어 물려주면 전체 구축이 $O(n \log n)$ 이다. 발트와 하브란이 KD-트리에 대해 이 $O(N \log N)$ 구성을 정리했고, 그 전까지 널리 쓰이던 순진한 구현은 $O(n \log^2 n)$ 이었다.

KD-트리에서는 여기에 한 가지가 더 붙는다. 빈 공간 보너스 — 한쪽 자식이 프리미티브를 하나도 안 가지면 비용에 0.8 정도를 곱해 그 분할을 우대한다. 광선이 아무것도 없는 큰 공간을 한 번의 판정으로 통과하는 것이 순회 전체에서 매우 자주 일어나기 때문이고, 이 계수 하나가 이른바 「teapot-in-a-stadium」 장면의 성능을 몇 배 바꾼다.

5. 비닝 — 정확도를 조금 팔아 속도를 산다[편집]

정렬은 캐시에 나쁘고 병렬화가 껄끄럽다. 그래서 실무 빌더는 후보를 고정 개수의 빈으로 이산화한다.

노드 안 프리미티브들의 중심 좌표 범위를 $K$ 개의 등간격 빈으로 나누고, 프리미티브마다 자기 빈에 개수 1과 자기 AABB를 합쳐 넣는다. 그러면 프리미티브를 한 번 훑는 것으로 빈 배열이 채워지고, 이후는 빈 $K$ 개에 대해 접두·접미 누적을 해서 $K-1$ 개의 후보만 평가하면 된다. 노드당 비용이 $O(n + K)$ 로 떨어지고 정렬이 사라진다.

$K$ 는 8~32 사이를 쓰며 16이 사실상 표준이다. 발트의 보고는 $K=16$ 정도면 완전 스윕 대비 트리 품질 손실이 몇 퍼센트 수준이라는 것이었고, 구축 시간이 몇 배 빨라지는 것을 감안하면 거의 언제나 이득이다. 빈이 위쪽 노드에서는 넉넉하고 아래쪽 작은 노드에서는 남아도니, 프리미티브가 몇 개 안 남으면 스윕으로 전환하는 하이브리드가 흔하다.

한 가지 자주 틀리는 지점 — 비닝은 중심 좌표로 하되, 빈의 경계상자는 프리미티브 전체 상자를 합쳐야 한다. 중심만 넣으면 큰 삼각형이 빈 밖으로 삐져나온 만큼 표면적이 과소평가되어 비용이 조용히 틀린다.

6. 공간 분할 BVH — 중간 지점[편집]

BVH의 구조적 약점은 프리미티브를 절대 자르지 않는다는 것이다. 길고 비스듬한 삼각형 하나가 노드 상자를 크게 부풀리면, 그 상자를 물려받은 모든 자손이 넓은 표면적을 떠안는다. KD-트리는 이 문제를 프리미티브를 쪼개어 해결하지만 대신 중복 등록으로 트리가 커진다.

SBVH(스티치 외, 2009)는 각 노드에서 두 종류 후보를 같은 비용식으로 나란히 평가한다 — 프리미티브를 통째로 좌우로 나누는 보통의 객체 분할과, 평면으로 프리미티브 자체를 잘라 양쪽에 참조를 복제하는 공간 분할. 공간 분할이 유의하게 싸면 그쪽을 고르고, 참조 복제 총량에 예산(원본 대비 보통 30% 이내)을 걸어 메모리 폭주를 막는다. 잘라 놓고 보니 한쪽 조각의 상자가 안 줄었으면 다시 합치는 「언스플리팅」 보정도 들어간다. 광선 순회가 보통 BVH 대비 수십 퍼센트 빨라지지만 구축이 느리고 메모리가 늘어, 오프라인 렌더러에서는 표준이고 실시간 빌더에서는 선택지다.

7. SAH를 안 쓰는 빌더와의 거래[편집]

SAH 구축은 아무리 최적화해도 프리미티브를 여러 번 훑는다. 매 프레임 트리를 다시 지어야 하는 실시간 상황에서는 그것조차 비싸서, 품질을 팔아 속도를 사는 빌더들이 따로 있다.

가장 극단이 LBVH다. 프리미티브 중심을 공간 채움 곡선의 모턴 코드로 바꿔 정렬하고, 인접 키의 공통 접두사 길이가 곧 분할 레벨이라는 성질을 써서 트리를 만든다. 비용식을 한 번도 평가하지 않으므로 사실상 정렬 한 번( $O(n)$ 기수 정렬)이 전부고, GPU에서 수백만 삼각형을 밀리초에 짓는다. 대가는 품질이다 — 모턴 순서는 「중심이 가까운 것끼리 묶는다」일 뿐 상자 표면적을 전혀 보지 않아서, 순회 성능이 SAH 트리보다 보통 20~50% 나쁘다.

그래서 현장의 스펙트럼은 이렇게 놓인다.

빌더	구축 비용	순회 성능	쓰는 곳
중앙값·중점 분할	가장 쌈	나쁨	프로토타입, 디버그
LBVH(모턴)	정렬 한 번	보통	완전 동적 장면, GPU 매 프레임 재구축
비닝 SAH	중간	좋음	실시간 렌더러·엔진의 기본값
스윕 SAH	비쌈	아주 좋음	정적 장면, 오프라인
SBVH	가장 비쌈	최고	오프라인 렌더러, 긴 삼각형 많은 장면

중간 지대를 노린 것이 HLBVH류로, 위쪽 몇 레벨만 SAH로 정성껏 짓고 아래는 모턴 정렬에 맡긴다. 순회 시간의 대부분이 상위 노드에서 결정된다는 관찰에 기댄 절충이며, 「비싼 계산은 트리 꼭대기에만 쓴다」는 이 발상은 나중에 부분트리 재배치 후처리로도 이어진다.

8. 가정은 어디서 배신하는가[편집]

SAH의 유도에 깔린 가정은 셋이고, 셋 다 현실에서 틀린다.

광선이 균일하게 분포한다. 실제로는 카메라 한 점에서 나가고, 광원 한 점에서 나가고, 표면에서 반구 방향으로 나간다. 그림자 광선은 특정 방향에 몰려 있다. 국소적으로 광선 분포를 추정해 비용식을 고치려는 시도(광선 분포 휴리스틱)가 있었지만, 구축 시점에 광선을 알 수 없다는 근본 문제 때문에 범용으로는 자리 잡지 못했다.
광선이 노드를 끝까지 통과한다. 비용식은 광선이 조기 종료 없이 두 자식을 다 검사한다고 친다. 실제 레이 트레이싱 순회는 가까운 자식부터 방문하고 교차를 찾으면 먼 쪽을 통째로 버리므로, 가려짐이 심한 장면일수록 SAH는 실제 비용을 과대평가한다. 반대로 자식 상자가 크게 겹치면 두 쪽을 다 봐야 하므로 SAH가 실제를 과소평가한다.
부분트리의 비용이 서로 독립이다. 그래서 매 노드에서 국소 최소를 고르는 탐욕 구축이 정당화되는데, 국소 최적의 연쇄가 전역 최적 트리를 준다는 보장은 없다. 실제로 다 지어 놓은 트리의 부분(treelet)을 뽑아 재배치하며 SAH 비용을 더 낮추는 후처리가 유효하고, GPU에서 이 재배치를 병렬로 도는 기법이 정착해 있다.

가정이 아니라 지표 자체를 의심한 연구도 있다. 아일라·카라스·라이네(2013)는 여러 빌더가 만든 트리들을 놓고 SAH 비용과 실제 순회 시간의 상관이 생각보다 나쁘다는 것을 보이고, 자식 상자의 겹침(EPO)과 캐시 지역성을 추가 지표로 제안했다. 요약하면 SAH 비용이 낮은 트리가 빠른 트리인 것은 같은 빌더 안에서만 대체로 참이고, 서로 다른 방식으로 지은 트리를 SAH 숫자만으로 줄 세우면 틀린다.²

그럼에도 SAH가 표준으로 남은 이유는 단순하다 — 광선을 하나도 안 쏘고, 장면 지오메트리만 보고, 선형 시간에 계산되는 비용 추정 중에 이만한 것이 아직 없다. 도박이 과학이 된 드문 사례라는 말이 괜히 나온 게 아니다.

9. 관련 문서[편집]

Goldsmith & Salmon (1987), IEEE CG&A — 자동 객체 계층 구성. MacDonald & Booth (1990), The Visual Computer — kd-트리 분할 기준으로 정식화. Wald & Havran (2006) — $O(N \log N)$ 구축. Wald (2007) — 비닝. Stich 외 (2009) — SBVH. 40년 가까이 「비용식은 그대로, 구현만 빨라지는」 역사인데, 이 정도로 오래 버틴 휴리스틱이 그래픽스에 흔치 않다. ↩
Aila, Karras, Laine (2013), HPG. 논문의 결론을 실무 언어로 옮기면 “네 빌더가 내 빌더보다 SAH 비용이 3% 낮다고 자랑하는 표는 아무 의미가 없다”에 가깝다. 그 뒤로 좋은 논문들은 SAH 비용과 실측 순회 시간을 둘 다 싣게 됐다. 벤치마크 문화가 논문 한 편으로 바뀐 사례. ↩