프러스텀 컬링

프러스텀 컬링은 카메라에 담기지 않을 물체를 그리기 전에 목록에서 빼는 일입니다. 카메라 뒤에 선 나무와 화면 옆으로 한참 벗어난 건물이 그 대상입니다. 물체마다 씌운 단순한 도형이 카메라가 보는 공간에 닿는지만 따져서 가려냅니다.

쉽고 빠른 이해

프러스텀 컬링은 카메라에 안 담길 물체를 그릴 목록에서 빼 줍니다. 플레이어 등 뒤에 있는 집은 화면에 한 점도 안 나오므로 빼도 화면은 같습니다.

3D 물체는 작은 삼각형을 이어 붙여 만듭니다. 빼지 않으면 GPU(Graphics Processing Unit, 그래픽 처리 장치)가 그 집을 이루는 삼각형을 전부 계산한 뒤에야 화면 밖이라는 것을 압니다. 물체가 수천 개인 장면에서는 이렇게 버리는 계산이 한 화면을 그리는 시간을 늘립니다.

물체마다 공이나 상자 하나를 씌워 둡니다
카메라가 보는 공간을 둘러싼 면 여섯 장과 그 공을 견줍니다
어느 한 면 바깥으로 공이 완전히 나가 있으면 뺍니다. 애매하면 남깁니다

대가도 있습니다. 판정 자체에 시간이 듭니다. 공이 물체보다 커서 안 보이는 물체 일부가 남습니다. 다른 물체 뒤에 가려진 물체는 이 방법으로 못 뺍니다.

물체가 몇 개 없거나 맵 전체가 한 화면에 들어오는 장면에서는 뺄 것이 거의 없어 이득이 작습니다.

상세

이 절은 프러스텀 컬링에 무엇을 넣고 무엇을 받는지부터 봅니다. 그다음 카메라가 보는 공간의 모양을 봅니다. 평면 하나로 안팎을 가르는 계산은 숫자로 따라갑니다. 끝으로 물체가 많을 때 판정을 줄이는 방법과 프러스텀 컬링이 못 하는 일을 짚습니다.

그리기 전에 목록을 줄이는 이유

3D 게임은 화면 한 장을 그리고 끝나지 않습니다. 카메라가 움직일 때마다 화면을 처음부터 다시 그립니다. 이 한 장을 프레임이라고 부릅니다. 한 장을 그리는 데 쓸 수 있는 시간은 정해져 있어서, 그 안에 끝내지 못하면 화면이 끊겨 보입니다.

화면에 그리는 일은 GPU가 맡습니다. 무엇을 그릴지 정해 GPU 에 넘기는 일은 CPU(Central Processing Unit, 중앙 처리 장치)에서 도는 프로그램이 합니다.

CPU 쪽 프로그램은 물체를 하나씩 GPU 에 넘깁니다. 물체 하나를 그려 달라는 이 요청 한 번을 드로 콜이라고 합니다.

3D 물체는 작은 삼각형을 이어 붙여 만듭니다. GPU 는 넘겨받은 물체가 화면 밖이어도 일단 계산합니다. 삼각형마다 화면 위치를 구한 뒤에야 화면 밖이라는 것이 드러납니다. 그 계산은 결과를 버리는 데 쓰인 셈입니다.

프러스텀 컬링은 이 낭비를 CPU 쪽에서 미리 막습니다. 화면에 안 나올 물체를 넘기기 전에 골라내서 드로 콜 자체를 안 보냅니다. 컬링 가운데 가장 먼저, 가장 싸게 도는 단계입니다.

입력과 출력

넣는 것은 둘입니다. 하나는 장면에 놓인 물체 목록입니다. 다른 하나는 이번 프레임의 카메라가 보는 공간입니다. 나오는 것은 그 공간에 조금이라도 닿을 수 있는 물체만 추린 목록입니다.

물체를 삼각형 하나하나로 따지면 판정만으로 시간이 다 갑니다. 그래서 물체를 감싸는 단순한 도형 하나를 미리 씌워 두고 그 도형만 따집니다. 이 도형이 바운딩 볼륨입니다.

바운딩 볼륨으로 가장 흔히 쓰는 것은 구입니다. 중심 한 점과 반지름 하나만 있으면 정해집니다. 이렇게 감싸는 구를 바운딩 스피어라고 부릅니다.

다음으로 흔한 것은 좌표축에 나란히 놓인 직육면체입니다. 이것을 AABB(Axis-Aligned Bounding Box, 축 정렬 경계 상자)라고 부릅니다. 아래 계산은 구로 먼저 보이고, 상자는 뒤에서 따로 짚습니다.

뷰 프러스텀

카메라가 한 번에 담는 공간은 꼭대기를 잘라 낸 피라미드 모양입니다. 카메라 쪽이 좁고 멀어질수록 넓어집니다. 이 입체를 뷰 프러스텀이라고 부릅니다. 우리말로는 절두체, 곧 뿔의 머리를 잘라 낸 입체입니다.

block-beta
columns 3
  far["원평면 · 넓은 끝"]:3
  left["왼쪽 면"] inside["프러스텀 안"] right["오른쪽 면"]
  space near["근평면 · 좁은 끝"] space
  space cam["카메라"] space

위에서 내려다본 모양입니다. 위 · 아래 면은 같은 모양을 옆에서 보면 나타납니다.

프러스텀은 평면 여섯 장으로 둘러싸입니다. 화면의 네 변에서 뻗어 나간 옆면 넷과, 앞뒤를 막는 두 면입니다. 이 문서에서는 이 평면 하나하나를 「면」이라고 부릅니다. 면마다 잘라 내는 물체가 다릅니다.

면	무엇을 잘라 내나
왼쪽 · 오른쪽 면	화면 좌우로 벗어난 물체
위 · 아래 면	화면 위아래로 벗어난 물체
근평면	카메라에 너무 가깝거나 카메라 뒤에 있는 물체
원평면	너무 멀어서 그리지 않기로 한 물체

원평면을 얼마나 멀리 둘지는 그리는 쪽이 정합니다. 멀리 둘수록 먼 산까지 보이지만 프러스텀 안에 드는 물체도 늘어납니다.

평면 하나로 안팎 가르기

평면 하나는 공간을 두 쪽으로 가릅니다. 어느 쪽이 안인지 정하려면 면이 바라보는 방향이 있어야 합니다.

평면이 바라보는 방향은 그 면에 수직인 화살표 하나로 적습니다. 이 화살표가 법선이고, 이 문서에서는 n 으로 씁니다. 프러스텀의 여섯 면은 법선이 모두 프러스텀 안쪽을 향하게 둡니다. 그러면 면마다 「물체가 법선 쪽에 있나」만 물으면 됩니다.

이 물음에 답하는 데 내적이라는 계산을 씁니다. 두 화살표의 x · y · z 값을 짝지어 곱한 뒤 더하는 계산입니다. 예를 들어 (1, 0, 0) 과 (-3, 0, 5) 의 내적은 1×(-3) + 0×0 + 0×5 = -3 입니다.

점 p 가 어느 쪽인지는 n 과 p 의 내적에 숫자 하나 d 를 더한 값으로 봅니다. d 는 면 위의 점을 넣었을 때 이 값이 0 이 되도록 맞춘 수입니다. 그래서 값이 0 이면 점이 면 위에 있고, 양수면 안쪽, 음수면 바깥입니다.

법선의 길이를 1로 맞춰 두면 이 값이 곧 점에서 평면까지의 거리입니다. 안쪽이면 양수, 바깥이면 음수라서 부호 있는 거리라고 부릅니다.

숫자로 따라가 봅니다. 왼쪽 면이 x = -10 에 서서 오른쪽을 바라본다고 둡니다. 그러면 법선은 (1, 0, 0) 입니다. 면 위의 점 (-10, 0, 0) 을 넣으면 1×(-10) + d 가 0 이어야 하므로 d 는 10 입니다.

// 왼쪽 면  n = (1, 0, 0) · d = 10
dist(p) = n.x*p.x + n.y*p.y + n.z*p.z + d;

dist((-3, 0, 5))     // 7 · 안쪽
dist((-15, 0, 5))    // -5 · 바깥

첫 점은 면에서 안쪽으로 7 만큼 들어와 있습니다. 둘째 점은 바깥으로 5 만큼 나가 있습니다.

구 하나를 평면과 견주기

물체는 점이 아니라 덩어리입니다. 구로 감쌌다면 구의 중심 c 까지 거리를 구하고 반지름 r 과 견줍니다. 경우는 셋으로 갈립니다.

중심까지 거리	구의 위치	판정
`-r` 보다 작다	면 바깥으로 완전히 나갔다	버린다
`-r` 과 `r` 사이	면에 걸쳐 있다	남긴다
`r` 보다 크다	이 면 안쪽에 완전히 들어왔다	남긴다

같은 왼쪽 면에 반지름 2 인 구 두 개를 대 봅니다.

r = 2;
dist((-13, 0, 5))    // -3 · 버린다
dist((-11, 0, 5))    // -1 · 남긴다

첫 구는 중심이 바깥으로 3 떨어져 있어 반지름 2 로는 면에 닿지 못합니다. 둘째 구는 중심이 바깥에 있어도 반지름이 면을 넘어 안쪽에 닿으므로 남습니다.

여섯 면을 합치는 규칙

프러스텀 안은 여섯 면의 안쪽이 모두 겹치는 공간입니다. 그래서 한 면이라도 「완전히 바깥」이라고 답하면 그 물체는 프러스텀 밖입니다. 나머지 면은 볼 필요가 없습니다.

flowchart TD
    S["물체 하나와 그 바운딩 볼륨"] --> P["다음 면과 견준다"]
    P --> Q{"이 면 바깥으로 완전히 나갔나"}
    Q -->|예| X["버린다 · 남은 면은 안 본다"]
    Q -->|아니오| R{"아직 안 본 면이 있나"}
    R -->|예| P
    R -->|아니오| K["남긴다"]

그림의 고리는 많아야 여섯 번 돕니다. 버릴 물체는 앞쪽 면에서 걸리면 거기서 끝나므로 여섯 번을 다 돌지 않을 때가 많습니다. 남길 물체만 여섯 면을 전부 거칩니다.

상자로 감쌌을 때

AABB 도 같은 규칙을 씁니다. 구처럼 반지름 하나로 끝나지 않아서 꼭짓점을 봐야 합니다. 그래도 꼭짓점 여덟 개를 다 볼 필요는 없습니다.

면의 법선 방향으로 가장 멀리 나간 꼭짓점 하나만 봅니다. 상자에서 프러스텀 안쪽으로 가장 깊이 들어온 꼭짓점입니다. 그 꼭짓점마저 면 바깥이면 상자 전체가 바깥입니다.

이 꼭짓점은 법선의 x · y · z 값을 하나씩 보고 고릅니다. 법선의 x 값이 양수면 상자의 x 최댓값을, 음수면 최솟값을 고릅니다. y 와 z 도 같은 식으로 고릅니다. 값이 0 이면 어느 쪽을 골라도 거리가 같습니다.

왼쪽 면에 x 가 -14 에서 -11 까지인 상자를 대 봅니다. 법선 (1, 0, 0) 의 x 값이 양수이므로 x 는 최댓값 -11 을 고릅니다. 이 꼭짓점의 거리는 -11 + 10 = -1 로 바깥이라서 상자 전체를 버립니다.

구와 상자는 맞바꿈 관계입니다. 구는 계산이 가장 싸지만 길쭉한 물체를 감싸면 빈 공간이 많이 생깁니다. 상자는 계산이 조금 더 들지만 건물처럼 각진 물체에 더 꼭 맞습니다.

한쪽으로만 틀리는 판정

이 판정은 틀릴 수 있습니다. 다만 틀리는 방향이 한쪽으로 정해져 있습니다.

틀림	결과
안 보이는 물체를 남겼다	쓸데없이 그립니다. 화면은 맞게 나옵니다
보이는 물체를 버렸다	물체가 화면에서 사라집니다

프러스텀 컬링은 표의 첫 줄 틀림만 냅니다. 첫째 이유는 바운딩 볼륨이 물체보다 크다는 것입니다. 볼륨이 프러스텀에 닿아도 물체 자체는 안 닿을 수 있습니다.

둘째 이유는 면 여섯을 하나씩 따로 본다는 것입니다. 왼쪽 면과 위쪽 면이 만나는 모서리 바깥에 구가 놓이면 어느 한 면에서도 완전히 바깥이 아닐 수 있습니다.

숫자로 보입니다. 계산을 쉽게 하려고 왼쪽 면은 앞의 x = -10, 위쪽 면은 y = 10 에 서서 아래를 바라본다고 둡니다. 반지름 5 인 구의 중심을 (-14, 14, 5) 에 놓으면 두 면에서 거리가 모두 -4 입니다. -4 는 -r 인 -5 보다 크므로 두 면 모두 「걸쳐 있다」고 답합니다.

block-beta
columns 2
  corner["두 면 모두 바깥 · 구 중심이 여기"] top["위쪽 면 바깥 · 왼쪽 면 안"]
  side["왼쪽 면 바깥 · 위쪽 면 안"] inside["프러스텀 안"]

카메라에서 앞을 바라보고 자른 단면입니다. 구는 왼쪽 위 칸에서 이웃한 두 칸으로 넘어가지만 오른쪽 아래 칸, 곧 프러스텀 안에는 닿지 않습니다. 두 면이 만나는 모서리까지 거리가 약 5.7 로 반지름 5 보다 멀기 때문입니다. 그래도 어느 면도 버리라고 답하지 않아 구는 남습니다.

남은 물체는 GPU 로 넘어가 뒤 단계에서 다시 걸러집니다. 그래서 프러스텀 컬링은 확실히 밖일 때만 버립니다. 애매하면 남기는 쪽으로 기울어 있습니다.

바운딩 볼륨 계층

물체가 수만 개면 하나씩 여섯 면과 견주는 것도 부담이 됩니다. 그래서 가까운 물체끼리 묶어 큰 볼륨을 하나 더 씌웁니다. 그 묶음을 또 묶어 나무 모양으로 쌓아 둡니다. 이렇게 쌓은 구조가 BVH(Bounding Volume Hierarchy, 바운딩 볼륨 계층)입니다.

물체 하나를 볼 때는 버리느냐 남기느냐 둘이면 됐습니다. 묶음 볼륨은 남기는 쪽을 둘로 더 나눠 판정이 셋입니다.

프러스텀 전체로 본 판정	조건
완전히 밖	어느 한 면에서라도 중심까지 거리가 `-r` 보다 작다
완전히 안	여섯 면 모두에서 중심까지 거리가 `r` 보다 크다
걸침	그 밖의 경우

판정은 나무의 뿌리부터 내려갑니다. 묶음 볼륨이 이 셋 중 어느 판정을 받느냐에 따라 그 아래로 내려갈지가 갈립니다.

flowchart TD
    R["뿌리 묶음 · 걸침"] --> A["묶음 A · 완전히 밖"]
    R --> B["묶음 B · 걸침"]
    R --> C["묶음 C · 완전히 안"]
    A --> A1["물체들 · 판정 없이 버림"]
    C --> C1["물체들 · 판정 없이 남김"]
    B --> D["묶음 D · 완전히 밖"]
    B --> E["묶음 E · 걸침"]
    D --> D1["물체들 · 판정 없이 버림"]
    E --> E1["물체마다 판정"]

완전히 밖인 묶음은 아래를 볼 필요가 없습니다. 완전히 안인 묶음도 아래 물체가 모두 안이니 더 따지지 않습니다. 판정을 되풀이하는 것은 B 와 E 처럼 프러스텀 경계에 걸친 묶음뿐입니다.

복잡도

물체 수를 n 이라 두면, 목록을 하나씩 보는 방식은 물체마다 면을 많아야 여섯 장 봅니다. 판정 횟수가 n 에 비례하므로 O(n) 입니다.

계층을 쓰면 경계에 걸친 묶음만 내려가므로 판정 횟수가 크게 줄어듭니다. 판정이 가장 많이 드는 때는 프러스텀 경계가 수많은 작은 묶음을 가로지를 때입니다. 그러면 거의 모든 묶음을 내려가야 해서 다시 O(n) 이 됩니다.

방식	판정 횟수	추가 메모리
목록을 하나씩	O(n) · 물체마다 면 최대 여섯	거의 없음
바운딩 볼륨 계층 · 보통	경계에 걸친 묶음 수를 따라감	계층을 담는 O(n)
바운딩 볼륨 계층 · 판정이 가장 많을 때	O(n)	계층을 담는 O(n)

계층에는 유지 비용이 따릅니다. 물체가 움직이면 그 물체를 품은 묶음 볼륨도 고쳐야 합니다.

다른 단계와의 순서

프러스텀 컬링은 컬링 가운데 가장 먼저 돕니다. 물체 하나만 보고 판정이 끝나서 가장 싸기 때문입니다. 아래 그림은 물체 목록이 화면의 픽셀이 되기까지 각 단계가 어떤 차례로 도는지 보입니다.

flowchart TD
    A["장면의 물체 전부"] --> B["프러스텀 컬링 · 물체 단위"]
    B --> C["오클루전 컬링 · 물체 단위"]
    C --> D["드로 콜로 GPU 에 넘김"]
    D --> E["클리핑 · 경계에 걸친 삼각형을 자름"]
    E --> F["백페이스 컬링 · 삼각형 단위"]
    F --> G["래스터화"]

다른 물체 뒤에 가려진 물체를 빼는 것은 오클루전 컬링입니다. 다른 물체와의 관계를 봐야 해서 프러스텀 컬링보다 비쌉니다. 프러스텀 컬링이 먼저 개수를 줄여 두면 오클루전 컬링이 따질 물체도 줄어듭니다.

클리핑은 프러스텀 컬링과 헷갈리기 쉽습니다. 클리핑은 프러스텀 경계에 걸친 삼각형을 경계에서 잘라 안쪽 조각만 남기는 GPU 의 단계입니다. 프러스텀 컬링이 물체를 통째로 남기거나 버린다면, 클리핑은 남은 물체의 삼각형을 다듬습니다.

백페이스 컬링은 카메라를 등진 삼각형을 버리는 GPU 의 단계입니다. 물체가 아니라 삼각형 하나하나를 봅니다.

마지막의 래스터화는 남은 삼각형이 화면의 어느 픽셀을 덮는지 찾는 단계입니다. 앞의 단계는 모두 이 단계에 들어가는 양을 줄이려고 있습니다.

이득이 줄어드는 장면

카메라가 장면의 일부만 담을 때 프러스텀 컬링이 아끼는 양이 큽니다. 1인칭 게임처럼 시야 뒤와 옆에 물체가 많이 깔린 장면이 그렇습니다.

반대로 위에서 내려다보며 맵 전체가 한 화면에 들어오는 게임에서는 버릴 물체가 거의 없습니다. 물체가 몇 개 없는 장면도 같습니다. 이럴 때는 판정에 드는 시간만 남습니다.