안 보이는 것을 안 그리는 값도 든다

이 시리즈는 여섯 편 내내 같은 일을 했습니다. 볼 필요 없는 것을 미리 걷어 내기. 격자로, 트리로, 줄 세우기로, 방과 포털로 걷어 냈습니다.

받는 쪽은 전부 CPU 였습니다. 충돌 판정을 줄이고, 가장 가까운 것 찾기를 줄이고, 레이 판정을 줄였습니다.

이번에는 받는 쪽이 다릅니다. GPU 에 무엇을 넘길지를 줄입니다. 그리기는 한 번에 드는 값이 훨씬 큽니다. 정점을 변환하고, 픽셀을 칠하고, 상태를 바꾸는 일이 따라옵니다. 그래서 안 보이는 것을 안 넘기는 것만으로도 프레임이 바뀝니다.

카메라가 보는 범위는 평면 몇 장이다

카메라가 보는 범위는 절두체(frustum) 입니다. 피라미드의 끝을 잘라 낸 모양이라 그런 이름이 붙었습니다.

이 모양을 평면으로 다룹니다. 3차원이면 여섯 장입니다. 옆면 넷(위·아래·왼쪽·오른쪽), 그리고 가까운 면과 먼 면입니다. 2차원이면 넷입니다.

평면 하나는 “이쪽이 안” 이라는 방향과 원점까지의 거리로 적습니다. 어떤 점이 안쪽인지는 내적 한 번이면 압니다. 부호만 보면 됩니다.

그리고 평면 하나라도 완전히 바깥이면 그 물체는 밖입니다. 나머지 평면은 볼 필요가 없습니다. 이 조기 탈출이 실제 성능의 대부분을 만듭니다.

판정 결과는 셋입니다. 완전히 밖, 완전히 안, 경계에 걸침. 둘로 나누지 않고 셋으로 나누는 이유는 뒤에 나옵니다.

상자와 평면을 견줄 때 꼭짓점을 전부 볼 필요는 없습니다. 평면 방향으로 가장 깊은 꼭짓점 하나만 보면 밖인지 알 수 있습니다. 그 꼭짓점이 밖이면 나머지도 전부 밖이니까요. 2차원이면 네 개 중 하나, 3차원이면 여덟 개 중 하나입니다.

구로 먼저 거르면 싸지지만 틀린다

경계 상자 대신 경계 구를 쓰면 더 쌉니다. 중심까지의 부호 있는 거리를 반지름과 견주면 끝이라 평면당 내적 한 번입니다. 상자는 최대 두 번입니다.

물체 5000개에 카메라 500번으로 재 봤습니다.

구가 35퍼센트 쌉니다. 그런데 그리는 물체가 74개 더 많습니다. 구는 상자를 감싸느라 실제보다 커서, 모서리 쪽에서 밖인 것을 안이라고 말합니다. 20퍼센트를 쓸데없이 그리게 됩니다.

그래서 실제로는 둘을 겹쳐 씁니다. 구로 먼저 보고, 완전히 밖이거나 완전히 안이면 거기서 끝냅니다. 애매한 것만 상자로 확인합니다. 결과는 상자만 쓴 것과 똑같은데 값은 28퍼센트 쌉니다.

앞에서 판정을 셋으로 나눈 이유가 이것입니다. “완전히 안” 을 알아야 더 정밀한 판정을 건너뛸 수 있습니다.

컬링 자체가 공짜가 아니다

위 표의 14,157 을 다시 보세요. 프레임마다 내적을 만 번 넘게 합니다. 물체가 8만 개면 21만 번이 됩니다. 걷어 내려고 한 일이 걷어 낸 값을 넘기 시작합니다.

그래서 물체를 하나씩 보지 않고 묶어서 봅니다. BVH 글에서 지은 그 트리입니다.

• 노드 상자가 완전히 밖이면 그 아래 전부를 안 봅니다
• 노드 상자가 완전히 안이면 그 아래 전부를 판정 없이 받습니다
• 걸쳤을 때만 자식으로 내려갑니다

위 요소에서는 묶는 쪽이 집니다. 하나씩이 73번, 묶으면 158번입니다. 물체가 열넷뿐이라 트리를 타고 내려가는 값이 더 큽니다.

뒤집히는 자리를 찾아봤습니다. 밀도를 고정하고 물체 수만 늘렸습니다.

100개와 200개 사이에서 갈립니다. 그 뒤로는 격차가 계속 벌어집니다.

눈여겨볼 것은 오른쪽 열이 거의 안 는다는 점입니다. 1,331 에서 4,434 로, 물체가 80배 느는 동안 3.3배만 늘었습니다. 하나씩은 전체 물체 수에 비례하고, 묶으면 실제로 보이는 것에 비례합니다. 8만 개짜리 장면에서는 48배 차이입니다.

물체가 백 개 안쪽인 장면이라면 트리를 짓지 말고 그냥 하나씩 도세요.

먼 면을 당기는 것이 가장 싸다

평면 여섯 장 중에 먼 면만은 성격이 다릅니다. 나머지 다섯은 카메라가 정하지만 먼 면은 내가 정합니다.

물체 5000개에서 먼 면만 바꿔 봤습니다.

거리를 두 배로 늘리면 그리는 것이 세 배가 됩니다. 2차원이라 넓이가 거리의 제곱에 비례해서 그렇고, 3차원이면 더 심합니다.

그래서 거리를 줄이는 것이 가장 값싼 최적화입니다. 다만 그냥 줄이면 물체가 눈앞에서 사라집니다. 실제로는 이렇게 씁니다.

• 안개를 깔아서 먼 면 근처를 흐리게 만듭니다. 사라지는 순간을 가립니다
• 물체마다 다른 거리를 줍니다. 작은 돌멩이는 50, 건물은 2000 같은 식입니다
• 크기로 정합니다. 화면에서 차지하는 픽셀이 몇 개 아래면 안 그립니다. 거리와 크기를 한꺼번에 보는 방법입니다

LOD 가 덜컹거리는 이유

거리를 아예 안 그리는 데만 쓰지 않고 덜 자세히 그리는 데도 씁니다. 멀면 정점이 적은 모델로 갈아 끼우는 것이 LOD(level of detail) 입니다.

여기에 한 가지 함정이 있습니다. 경계에서 덜컹거립니다.

플레이어가 LOD 경계 근처에 서서 조금씩 움직이기만 해도, 경계에 걸친 물체들이 매 프레임 모델을 갈아 끼웁니다. 눈에는 깜빡임으로 보입니다.

물체 5000개를 놓고, 카메라를 제자리에서 아주 조금씩 흔들면서 600프레임을 돌려 봤습니다.

10퍼센트만 줘도 125배가 줄어듭니다.

고치는 방법은 간단합니다. 경계를 하나가 아니라 둘로 둡니다. 한 단계 내리려면 경계보다 더 멀어져야 하고, 다시 올리려면 경계보다 더 가까워져야 합니다. 사이에 낀 구간에서는 지금 상태를 그대로 둡니다. 히스테리시스라고 부릅니다.

같은 문제가 절두체 컬링 자체에도 있습니다. 카메라가 경계에서 떨릴 때 물체가 들락날락하면, 그때마다 자료를 올렸다 내렸다 하게 됩니다. 그래서 컬링에 쓰는 절두체를 실제보다 조금 넓게 잡아 두기도 합니다.

가려진 것은 어떻게 아나

절두체 안에 있어도 앞의 벽에 가려져 있으면 안 보입니다. 이것을 걸러 내는 것이 차폐 컬링(occlusion culling) 입니다.

절두체와 성격이 완전히 다릅니다. 절두체는 카메라만 보면 되는데, 차폐는 다른 물체를 봐야 알 수 있습니다. 가리는 쪽을 먼저 그려 봐야 가려지는 쪽을 판단할 수 있으니, 순서에 얽힙니다.

• GPU 에 물어보기. “이 상자를 그리면 픽셀이 하나라도 남나” 를 질의합니다. 정확하지만 답이 다음 프레임에나 옵니다. 지금 프레임에 쓰려고 기다리면 GPU 와 CPU 가 서로 기다리게 됩니다. 그래서 지난 프레임의 답으로 이번 프레임을 정합니다. 카메라가 빨리 돌면 한 프레임쯤 틀립니다
• 깊이 버퍼를 작게 만들어 CPU 에서 보기. 큰 물체 몇 개만 낮은 해상도로 미리 그려 두고 거기에 대고 상자를 견줍니다. 기다릴 일이 없는 대신 정확하지 않습니다
• 미리 구워 두기. 방과 포털 글에서 본 방식입니다. 실내에는 여전히 잘 맞습니다

셋 다 공짜가 아니고, 셋 다 틀릴 수 있습니다. 차폐 컬링은 가리는 것이 크고 적을 때 값어치가 있습니다. 실내나 도심처럼 벽이 시야를 통째로 막는 장면입니다. 탁 트인 벌판에서는 가려지는 게 별로 없어서 질의 값만 나갑니다.

정리

컬링은 안 보이는 것을 GPU 에 안 넘기는 일입니다.

• 카메라가 보는 범위는 평면 여섯 장입니다. 한 장이라도 완전히 밖이면 거기서 끝입니다
• 판정은 셋으로 나눕니다. 완전히 안을 알아야 더 정밀한 판정을 건너뜁니다
• 구는 35퍼센트 싸지만 20퍼센트를 더 그리게 만듭니다. 구로 먼저 거르고 애매한 것만 상자로 보세요
• 컬링 자체가 공짜가 아닙니다. 물체 백 개 안쪽이면 하나씩이 낫고, 그 위부터 묶는 쪽이 이깁니다
• 묶으면 전체 수가 아니라 보이는 수에 비례합니다. 8만 개에서 48배 차이였습니다
• 먼 면을 당기는 것이 가장 싼 최적화입니다. 거리를 두 배로 늘리면 그리는 것이 세 배가 됩니다
• LOD 경계는 하나가 아니라 둘로 두세요. 10퍼센트 여유로 덜컹거림이 125배 줄었습니다
• 차폐 컬링은 가리는 것이 크고 적을 때만 값어치가 있습니다. GPU 질의는 답이 한 프레임 늦습니다

이것으로 공간 분할 일곱 편이 끝났습니다. 일곱 편을 관통하는 것이 하나 있습니다. 어느 구조도 항상 이기지 않았습니다. 고르게 흩어져 있으면 격자가 이겼고, 뭉쳐 있으면 트리가 이겼고, 물체가 적으면 아무것도 안 하는 쪽이 이겼습니다. 구조를 고르기 전에 내 장면이 어떻게 생겼는지부터 재세요.