벽은 막고 문은 통과시킨다

먼저 이름부터 갈라 둬야 합니다. 이 블로그에서 포털이 두 번째 나오는데 같은 것이 아닙니다.

길찾기 시리즈의 경로 다듬기 글에서 포털은 내비메시 폴리곤 사이의 통로였습니다. 삼각형을 이어 붙인 경로에서 이웃한 두 삼각형이 공유하는 변이고, 쓰는 목적은 팽팽한 길을 뽑는 것이었습니다.

여기서 말하는 포털은 방과 방 사이의 구멍입니다. 문, 창, 복도 입구 같은 것입니다. 쓰는 목적도 다릅니다. 저 방이 지금 보이는가를 판단하는 데 씁니다.

지금까지는 물체를 추렸다

앞의 다섯 편이 전부 같은 모양이었습니다. 물체를 구조에 담아 두고, 질의를 던져서 볼 필요 없는 물체를 걷어 냈습니다. 격자든 트리든 줄 세우기든 추리는 대상은 물체였습니다.

그런데 실내 장면에는 더 센 사실이 하나 있습니다. 벽은 시야를 완전히 막습니다. 옆방에 물체가 몇 개 있든, 벽 너머면 하나도 안 보입니다. 물체를 하나씩 걸러 낼 게 아니라 방 단위로 통째로 잘라 낼 수 있다는 뜻입니다.

그래서 질문이 바뀝니다. “어느 물체가 보이나” 가 아니라 “어느 방이 보이나” 입니다.

문을 지날 때마다 시야가 잘린다

방을 볼록한 덩어리로 나누고, 방 사이의 구멍을 포털로 표시해 둡니다. 그러면 눈에 보이는 것은 내가 선 방과, 포털을 통해 보이는 방들뿐입니다.

그리고 포털은 구멍이라서 크기가 있습니다. 문 너머를 보려면 문틀 사이로 봐야 합니다. 문이 차지하는 각도보다 넓게는 못 봅니다.

그래서 알고리즘이 이렇게 됩니다.

1. 내가 선 방에서 시작합니다. 시야 쐐기는 카메라의 시야각 전체입니다
2. 이 방의 포털마다, 그 포털이 눈에서 차지하는 각도를 잽니다
3. 그 각도와 지금 쐐기를 교집합합니다. 비면 그 너머는 안 봅니다
4. 안 비면 옆방으로 넘어가되, 쐐기를 교집합으로 좁힌 채로 갑니다

이것이 포털 컬링(portal culling) 입니다. 쐐기는 절대 넓어지지 않고 문을 지날 때마다 좁아지기만 합니다. 좁아지다 비면 거기서 멈춥니다.

첫 문 하나가 가장 많이 자른다

방 64개짜리 미로를 만들고 아무 데나 400번 서서 시야각 90도로 재 봤습니다.

거리로 자르는 것과 비교해도 네 배 차이입니다. 그리고 거리로 자르는 것은 틀릴 수 있습니다. 문 두 개 거리에 있어도 벽 뒤면 안 보이고, 곧은 복도라면 문 열 개 너머도 보입니다. 포털 컬링은 실제로 보이는 것만 남깁니다.

왜 이렇게 빨리 줄어드는지는 쐐기의 폭을 보면 됩니다.

첫 문 하나에서 90도가 24.7도가 됩니다. 4분의 1 토막입니다. 두 번째 문에서 다시 3분의 1이 되고, 그다음부터는 이미 바늘구멍이라 어지간한 문은 다 빗나갑니다. 평균 깊이가 얕은 게 그래서입니다.

복도를 꺾으면 시야가 죽는다

복도 여덟 칸을 두 가지로 놓고, 첫 방 한가운데서 복도 쪽을 봤습니다.

똑같이 방 여덟 개인데 하나는 전부 보이고 하나는 둘만 보입니다. 곧은 복도에서는 문이 한 줄로 늘어서 있어서, 쐐기가 아무리 좁아져도 다음 문이 그 안에 들어옵니다. 컬링이 아무것도 못 걷어 냅니다.

이건 알고리즘 문제가 아니라 레벨 디자인 문제입니다. 실내 게임의 복도가 자주 꺾여 있고, 문이 벽 한가운데가 아니라 구석에 붙어 있고, 방과 방 사이에 짧은 꺾인 통로가 끼어 있는 데에는 이런 이유가 있습니다. 한 번만 꺾어도 그 너머가 통째로 사라집니다.

방은 누가 나누나

여기까지는 “방이 이미 나뉘어 있다” 를 전제했습니다. 그 나누는 일을 하는 게 BSP 입니다.

BSP(binary space partitioning, 이진 공간 분할) 는 면 하나로 공간을 둘로 자르고, 양쪽에서 같은 일을 반복합니다. 더 자를 게 없으면 멈추고, 그 조각 하나가 방이 됩니다.

KD 트리와 발상이 같습니다. 다른 점이 하나 있는데 그게 전부를 바꿉니다. KD 트리는 축에 나란한 면만 씁니다. BSP는 아무 방향이나 씁니다.

그래서 BSP는 레벨의 벽을 그대로 자르는 면으로 쓸 수 있습니다. 벽이 45도로 기울어져 있으면 45도짜리 면으로 자르면 됩니다. 축에 갇혀 있으면 그 벽을 계단처럼 여러 번 잘라 근사해야 합니다.

기울어진 벽이 섞인 장면에서 선분 120개로 재 봤습니다. 자르는 면이 선분을 관통하면 그 선분은 두 조각으로 쪼개지고, 조각이 늘수록 손해입니다.

축에 나란한 벽만 있으면 축에 갇힌 쪽이 낫습니다. 굳이 자유를 줄 이유가 없으니까요. 비스듬한 벽이 섞이는 순간 뒤집힙니다. 17퍼센트 차이입니다. KD 트리 글에서 “3차원을 넘어가면 선택지가 없다” 고 했는데, 여기서는 반대 방향의 제약이 문제가 됩니다.

자를 면을 고르는 규칙

같은 장면에서 면 고르는 규칙만 바꿔 봤습니다.

KD 트리에서는 균형이 값어치였습니다. 여기서는 균형을 맞추려 들면 손해입니다. 개수를 맞추느라 벽을 관통하는 면을 고르게 되고, 조각이 늘어납니다.

BSP는 대개 미리 굽는 구조라서 짓는 시간은 신경을 덜 써도 됩니다. 그래서 실제로는 후보 면을 여럿 놓고 조각 수 × 가중치 + 불균형 같은 점수를 매겨 고릅니다. 위 표의 세 번째가 그것입니다.

뒤에서 앞으로 그리는 순서가 공짜로 나온다

BSP에는 컬링과 별개인 성질이 하나 더 있습니다.

트리의 각 노드에는 자르는 면이 하나 있습니다. 눈이 그 면의 어느 쪽에 있는지는 부호 하나로 압니다. 먼 쪽 → 이 면 → 가까운 쪽 순서로 훑으면, 나오는 순서가 그대로 뒤에서 앞으로 입니다.

정렬이 필요 없습니다. 트리를 한 번 훑으면 순서가 나옵니다. 깊이 버퍼가 비싸던 시절에는 이게 결정적이었습니다. 뒤엣것부터 덮어 그리면 앞엣것이 자연히 위에 옵니다. 화가 알고리즘(painter’s algorithm) 이 제대로 도는 순서를 BSP가 공짜로 만들어 줍니다.

지금은 깊이 버퍼가 하드웨어에 있어서 불투명한 것은 순서를 안 따져도 됩니다. 하지만 반투명은 여전히 뒤에서 앞으로 그려야 합니다. 스윕 앤 프룬 글에서 반투명 정렬을 언급했는데, BSP는 그 순서를 정렬 없이 주는 쪽입니다.

지금도 쓰나

솔직하게 적자면, BSP를 굽는 방식은 예전만큼 쓰이지 않습니다.

• 실내가 방으로 깔끔하게 안 나뉘는 게임이 많습니다. 야외나 개방형 지형에는 벽이라는 개념이 약합니다
• 레벨을 바꿀 때마다 다시 구워야 합니다. 5편에서 본 문제와 같습니다
• 하드웨어 차폐 질의가 생겼습니다. GPU에 “이 상자가 지금 화면에 한 픽셀이라도 그려지나” 를 물어볼 수 있습니다

반대로 지금도 남아 있는 것들이 있습니다.

• 실내 게임의 방·포털 구조는 여전히 유효합니다. 문을 꺾어 두면 그 너머가 통째로 사라진다는 것은 하드웨어와 무관합니다
• 로딩 단위로 씁니다. 포털 너머에 있는 방의 리소스만 미리 올려 두는 식입니다
• 소리도 같은 구조를 씁니다. 벽은 소리를 막고 문은 통과시키니, 포털 그래프를 그대로 재활용합니다
• BSP 던전 생성은 지금도 흔합니다. 자르는 쪽이 아니라 만드는 쪽으로 쓰는 것인데, 결이 다른 이야기입니다

정리

포털 컬링은 보이는 영역 자체를 잘라 나가는 방법입니다.

• 앞의 다섯 편이 물체를 추렸다면 여기는 방을 통째로 걷어 냅니다
• 쐐기는 문이 차지하는 각도만큼으로 잘리고 절대 넓어지지 않습니다
• 미로에서 64개 중 평균 2.2개만 그렸습니다. 문 세 개 이내로 자르는 것보다 네 배 적습니다
• 첫 문 하나가 90도를 24.7도로 만듭니다. 그래서 깊이 들어가지를 못합니다
• 복도를 한 번만 꺾어도 보이는 방이 8개에서 2개가 됩니다. 알고리즘이 아니라 레벨 디자인 문제입니다
• BSP는 KD 트리와 달리 아무 방향의 면이나 쓸 수 있습니다. 비스듬한 벽이 섞이면 17퍼센트 이득입니다
• 면을 고를 때 균형을 맞추려 들면 손해입니다. 조각이 적게 나는 쪽을 고르세요
• 트리를 먼 쪽부터 훑으면 뒤에서 앞으로 그리는 순서가 정렬 없이 나옵니다