---
title: "벽은 막고 문은 통과시킨다"
description: "앞의 다섯 편은 물체를 추렸습니다. 포털 컬링은 보이는 영역 자체를 잘라 나갑니다. 문을 지날 때마다 시야가 얼마나 좁아지는지, BSP(binary space partitioning)가 왜 축에 갇히지 않는지 실측으로 봅니다."
author: "유니얼"
pubDate: 2026-09-20
category: "programming/algorithm/spatial"
tags: ["최적화", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-bsp-portal/
---
먼저 이름부터 갈라 둬야 합니다. 이 블로그에서 **포털**이 두 번째 나오는데 같은 것이 아닙니다.

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

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

## 지금까지는 물체를 추렸다

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

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

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

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

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

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

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

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

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

<x-portal>
<script type="application/json">
{
  "label": "문을 지날 때마다",
  "levels": [
    { "name": "미로", "rooms": [[0,0],[1,0],[2,0],[3,0],[0,1],[1,1],[2,1],[3,1],[0,2],[1,2],[2,2],[3,2],[0,3],[1,3],[2,3],[3,3]], "doors": [[0,0,0,1],[0,1,0,2],[0,2,0,3],[0,2,1,2],[0,3,1,3],[1,0,1,1],[1,0,2,0],[1,1,2,1],[1,2,1,3],[1,3,2,3],[2,0,3,0],[2,1,2,2],[2,2,2,3],[2,3,3,3],[3,0,3,1],[3,1,3,2],[3,2,3,3]], "eye": [3,0], "facing": 135 },
    { "name": "곧은 복도", "rooms": [[0,0],[1,0],[2,0],[3,0],[4,0],[5,0],[6,0],[7,0]], "doors": [[0,0,1,0],[1,0,2,0],[2,0,3,0],[3,0,4,0],[4,0,5,0],[5,0,6,0],[6,0,7,0]], "eye": [0,0], "facing": 0 },
    { "name": "꺾인 복도", "rooms": [[0,0],[1,0],[1,1],[2,1],[2,2],[3,2],[3,3],[4,3]], "doors": [[0,0,1,0],[1,0,1,1],[1,1,2,1],[2,1,2,2],[2,2,3,2],[3,2,3,3],[3,3,4,3]], "eye": [0,0], "facing": 45 }
  ],
  "note": "쐐기가 문이 차지하는 각도만큼으로 잘립니다. 잘려서 비면 그 너머는 열어 보지 않습니다"
}
</script>
</x-portal>

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

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

| 방법 | 그리는 방 | 전부 대비 |
| --- | --- | --- |
| 전부 그리기 | 64.0 | 100% |
| 문 두 개 이내 | 5.8 | 9.1% |
| 문 세 개 이내 | 8.8 | 13.8% |
| 문 네 개 이내 | 12.2 | 19.1% |
| **포털 컬링** | **2.2** | **3.5%** |

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

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

| 지난 문 개수 | 남은 시야각 (평균) |
| --- | --- |
| 0 | 90.0도 |
| 1 | 24.7도 |
| 2 | 7.2도 |
| 3 | 4.7도 |
| 4 | 3.8도 |

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

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

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

| 복도 모양 | 보이는 방 | 마지막에 남은 시야각 |
| --- | --- | --- |
| 곧은 복도 | **8개 전부** | 2.6도 |
| 꺾인 복도 | **2개** | 16.7도 |

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

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

## 방은 누가 나누나

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

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

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

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

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

| 벽 방향 | 벽면을 자르는 면으로 (BSP) | 축에 나란한 면만 (KD 식) |
| --- | --- | --- |
| 전부 축에 나란함 | 410조각 | **367조각** |
| 전부 비스듬함 | **411조각** | 494조각 |
| 아무 방향이나 | **397조각** | 453조각 |

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

## 자를 면을 고르는 규칙

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

| 고르는 규칙 | 잘린 횟수 | 최종 조각 | 깊이 |
| --- | --- | --- | --- |
| 맨 앞의 것을 그냥 | 302 | 422 | 18 |
| 양쪽 개수가 맞는 쪽 | 334 | 454 | 10 |
| **조각이 적게 나는 쪽** | **278** | **398** | 15 |

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

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

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

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

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

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

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

## 지금도 쓰나

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

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

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

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

## 정리

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

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