---
title: "움직이는 것들에는 트리를 짓지 않는다"
description: "앞의 네 편은 구조를 지어 두고 질의를 던졌습니다. 스윕 앤 프룬(sweep and prune)은 한 축으로 줄만 세워 둡니다. 프레임마다 순서가 거의 안 바뀐다는 성질 하나로 어디까지 갈 수 있는지, 대신 무엇을 내주는지 실측으로 봅니다."
author: "유니얼"
pubDate: 2026-09-20
category: "programming/algorithm/spatial"
tags: ["최적화", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-sweep-and-prune/
---
BVH에서 상자만 고쳐 가며 120프레임을 돌렸더니 레이 비용이 아홉 배가 됐습니다.
쿼드트리는 물체가 칸을 옮길 때마다 쪼개고 합쳐야 했고, KD 트리는 아예 정적 데이터 전용이었습니다.

네 편이 같은 모양입니다. **구조를 먼저 짓고, 질의를 던지고, 움직이면 구조가 상한다.**

그런데 게임에서 충돌 판정은 질의가 아닙니다. 매 프레임 **전부 대 전부**를 물어보는 일입니다.
물체 1000개면 쌍이 499,500개고, 이걸 60번씩 해야 합니다.
질의가 매 프레임 한 번뿐이라면, 구조를 짓는 값을 그 한 번에 다 치르는 셈입니다.

질문을 바꿔 봅니다. 구조를 안 짓고 **줄만 세워 두면** 어떨까요.

## 한 축에 눕히면 구간이 된다

물체의 경계 상자를 x축에만 투영하면 구간 하나가 됩니다. `[왼쪽 끝, 오른쪽 끝]` 입니다.

여기서 쓸 수 있는 사실이 하나 있습니다.
**두 물체가 겹친다면 두 구간도 반드시 겹칩니다.** 뒤집으면 이렇게 됩니다.

> 구간이 안 겹치면 물체도 절대 안 겹친다.

그러면 구간이 겹치는 쌍만 추려 놓고, 그 안에서만 진짜 판정을 하면 됩니다.
구간이 겹치는 쌍을 찾는 방법은 줄을 세우는 것입니다.

모든 물체의 시작점과 끝점을 한 줄에 늘어놓고 왼쪽부터 지나갑니다.
시작점을 만나면 그 물체를 **열린 목록**에 넣고, 끝점을 만나면 뺍니다.
새로 여는 물체는 **그때 열려 있는 것들과만** 짝을 짓습니다.

이것이 **스윕 앤 프룬(sweep and prune)** 입니다. 소트 앤 스윕이라고도 부릅니다.

<x-sweep>
<script type="application/json">
{
  "label": "한 축으로 줄 세워 훑기",
  "size": 16,
  "boxes": [[8.0, 9.7, 1.6, 3.0], [4.8, 12.3, 1.6, 3.0], [8.4, 6.4, 3.6, 2.0], [6.3, 3.4, 3.6, 3.0], [11.3, 11.8, 3.6, 2.4], [2.2, 1.9, 2.0, 3.0], [1.3, 3.5, 3.0, 2.4], [9.5, 10.7, 1.6, 2.0]],
  "note": "아래 막대가 물체를 x축에 눕힌 구간입니다"
}
</script>
</x-sweep>

물체 여덟 개면 모든 쌍이 28개인데 9개만 판정합니다. 물체 1000개로 키워 보면 이렇습니다.

| 방법 | 판정한 쌍 | 전부 대비 |
| --- | --- | --- |
| 전부 다 (n²/2) | 499,500 | 100% |
| 스윕 앤 프룬 (x축) | 13,188 | 2.6% |
| 격자 (칸 25) | 1,396 | 0.3% |
| 격자 (칸 50) | 3,006 | 0.6% |

**진짜로 겹친 쌍은 409개**입니다. 2.6퍼센트까지 줄었지만 여전히 필요한 것의 32배를 판정합니다.
그리고 격자가 더 적습니다. 이 표만 보면 스윕 앤 프룬을 쓸 이유가 없습니다.

## 한 축만으로는 모자라다

13,188과 409 사이의 간격이 어디서 나오는지는 분명합니다.
x 구간이 겹쳐도 y가 멀리 떨어져 있으면 물체는 안 겹칩니다. **한 축만 봤기 때문입니다.**

| 무엇까지 보나 | 남는 쌍 |
| --- | --- |
| 아무것도 안 봄 | 499,500 |
| x 구간만 | 13,188 |
| x 로 추린 뒤 y 까지 | **409** |

y까지 보면 정확히 진짜 겹친 쌍만 남습니다. 축에 나란한 상자라면 두 축이 전부니까요.

그래서 실제 구현은 두 단계입니다. **한 축으로 추리고, 남은 쌍마다 온전한 상자 판정을 한 번 합니다.**
상자 판정은 비교 네 번이라 싸고, 판정할 쌍이 13,188개면 부담이 안 됩니다.

축을 여러 개 유지하는 방법도 있습니다. 뒤에서 다시 보겠습니다.

## 어느 축으로 눕힐까

축을 잘못 고르면 전부 무너집니다. 물체 1000개를 **전부 바닥 근처에 붙여** 놓고 재 봤습니다.
가로로 긴 2.5D 게임이나, 지면 위에 유닛이 늘어선 장면이 이 모양입니다.

| 방법 | 판정한 쌍 | 전부 대비 |
| --- | --- | --- |
| 스윕 앤 프룬 (x축) | 9,457 | 1.9% |
| 스윕 앤 프룬 (y축) | **205,809** | **41.2%** |
| 격자 (칸 25) | 15,759 | 3.2% |
| 격자 (칸 50) | 23,934 | 4.8% |

**스물두 배 차이**입니다. y축으로 눕히면 모든 구간이 서로 겹쳐서, 열린 목록에 거의 전부가 들어앉습니다.
전부 대 전부로 돌아가는 것과 다를 게 없습니다.

고르는 방법은 간단합니다. **물체 중심의 분산이 가장 큰 축**을 씁니다.
위 장면의 분산은 x가 80,275, y가 133입니다. 고민할 것도 없습니다.
분산은 한 번 훑으면 나오니, 몇 초에 한 번씩 다시 재서 축을 갈아타도 됩니다.

여기서는 스윕 앤 프룬이 격자를 이겼습니다. 격자는 칸이 정사각형이라
납작한 장면에서 세로로 텅 빈 칸을 계속 만들지만, 스윕은 축 하나만 잘 고르면 되니까요.

## 진짜 값어치는 다시 정렬하지 않는 데 있다

여기까지는 한 프레임 이야기입니다. 스윕 앤 프룬이 실제로 쓰이는 이유는 다음 프레임에 있습니다.

물체가 한 프레임에 움직이는 거리는 자기 크기에 비하면 아주 작습니다.
그러면 **줄 세운 순서도 거의 그대로**입니다. 천 개를 다시 정렬할 이유가 없습니다.
값만 갱신하고 **삽입 정렬**을 돌리면, 어긋난 자리 몇 개만 고치고 끝납니다.

거의 정렬된 배열에서 삽입 정렬은 자리바꿈 횟수에 비례하는 값만 씁니다. 이것을 **시간적 일관성**이라고 부릅니다.

<x-sweep>
<script type="application/json">
{
  "label": "조금씩 움직일 때",
  "size": 16,
  "mode": 1,
  "frames": 24,
  "boxes": [[8.0, 9.7, 1.6, 3.0], [4.8, 12.3, 1.6, 3.0], [8.4, 6.4, 3.6, 2.0], [6.3, 3.4, 3.6, 3.0], [11.3, 11.8, 3.6, 2.4], [2.2, 1.9, 2.0, 3.0], [1.3, 3.5, 3.0, 2.4], [9.5, 10.7, 1.6, 2.0]],
  "note": "짝이 생기면 진한 색, 사라지면 점선입니다"
}
</script>
</x-sweep>

물체 1000개를 120프레임 동안 움직이면서 프레임당 평균을 재 봤습니다. 한 축만 유지한 경우입니다.

| 프레임당 이동 거리 | 자리바꿈 | 짝 추가 | 짝 삭제 |
| --- | --- | --- | --- |
| 0.5 | 1,133 | 282 | 283 |
| 2.0 | 4,518 | 1,126 | 1,126 |
| 8.0 | 18,132 | 4,522 | 4,521 |

물체가 천천히 움직이면 프레임당 자리바꿈이 **1,133번**입니다.
천 개를 처음부터 정렬하면 비교가 대략 9,965번이고, 후보 쌍을 매 프레임 다시 훑으면 13,188번입니다.

거꾸로 빠르게 움직이면 값어치가 사라집니다. 프레임당 8픽셀이면 자리바꿈이 18,132번으로,
차라리 다시 정렬하는 게 낫습니다. **시간적 일관성은 공짜로 주어지는 게 아니라 장면의 성질입니다.**
순간이동이 잦은 게임이라면 이 구조를 쓸 이유가 없습니다.

## 자리 한 번에 짝 하나

자리바꿈 횟수보다 중요한 것이 있습니다. **자리를 한 번 바꿀 때 무슨 일이 일어나는가** 입니다.

줄에는 시작점과 끝점 두 종류만 있습니다. 이웃한 둘이 자리를 바꾸는 경우는 네 가지인데,
그중 둘은 아무 의미가 없고 둘만 뜻이 있습니다.

- **끝점을 시작점이 앞질렀다**: 저쪽이 끝나기 전에 이쪽이 시작했다는 뜻입니다. **짝이 하나 생깁니다**
- **시작점을 끝점이 앞질렀다**: 저쪽이 시작하기 전에 이쪽이 끝났다는 뜻입니다. **짝이 하나 사라집니다**
- 시작점끼리, 끝점끼리 바뀐 것은 겹침 관계를 바꾸지 않습니다

그래서 목록을 **처음부터 다시 만들 필요가 없습니다.** 자리를 바꿀 때마다 짝 하나를 넣거나 빼면 끝입니다.
위 표의 "짝 추가·삭제" 가 그 횟수입니다.

이것을 두 축에 다 적용하면 재미있는 일이 벌어집니다.
짝마다 **몇 개 축에서 겹쳤는지**를 세어 두고, 그 값이 2가 되는 순간을 잡는 것입니다.

| 프레임당 이동 거리 | 자리바꿈 (두 축 합) | 짝 추가 | 짝 삭제 | 들고 있는 짝 |
| --- | --- | --- | --- | --- |
| 0.5 | 2,277 | 15.4 | 15.5 | 401 |
| 2.0 | 9,082 | 60.1 | 60.3 | 385 |

**들고 있는 짝이 진짜로 겹친 쌍과 정확히 같습니다.** 후보가 아니라 답입니다.
그리고 프레임당 바뀌는 것이 **열다섯 개**뿐입니다.

이게 격자와 갈리는 지점입니다. 격자는 매 프레임 후보 쌍 1,396개를 다시 만듭니다.
그중 무엇이 **새로 겹치기 시작했고** 무엇이 **막 떨어졌는지** 알려면 지난 프레임 목록과 따로 비교해야 합니다.
스윕 앤 프룬은 그 두 사건이 알고리즘 안에서 그냥 나옵니다.

충돌 시스템이 필요로 하는 게 대개 그 두 사건입니다.
"지금 닿아 있다" 보다 "방금 닿기 시작했다" 와 "방금 떨어졌다" 를 알아야
소리를 내고, 데미지를 한 번만 주고, 트리거를 켜고 끕니다.

## 값이 똑같을 때

직접 만들면서 걸린 자리가 하나 있습니다. 끝점 값이 **정확히 같을 때**입니다.

한 물체의 시작이 다른 물체의 끝과 같은 값이면, 정렬에서 둘 중 무엇을 앞에 놓을지가 정해지지 않습니다.
그런데 겹침 판정은 보통 `시작 < 끝` 처럼 등호를 빼고 씁니다. 맞닿기만 한 것은 안 겹친 것으로 봅니다.

이 둘이 어긋나면 **목록이 진실과 조금씩 달라집니다.**
저는 여덟 개짜리 장면에서 이걸 만났습니다. 한 프레임 만에 짝 하나가 빠졌고,
자리바꿈으로는 되살아나지 않았습니다. 이미 순서가 맞아 있어서 바꿀 일이 없었기 때문입니다.

고치는 법은 한 줄입니다. **값이 같으면 끝점을 먼저 놓습니다.**
그러면 맞닿은 것은 "저쪽이 끝난 뒤에 이쪽이 시작" 으로 읽히고, 판정의 등호 규칙과 맞아떨어집니다.

들고 있는 목록이 진실과 어긋나는 버그는 **몇 프레임 뒤에 엉뚱한 자리에서** 터집니다.
그래서 만들 때 **매 프레임 전부 다시 계산한 것과 대조하는 검산**을 켜 두고 돌려 보세요.
위 측정도 전부 그렇게 확인한 값입니다.

## 약점

첫째, **큰 물체 하나가 전부를 망칩니다.**
맵을 가로지르는 물체는 구간도 맵을 가로지르니, 열린 목록에서 내내 안 나갑니다.
그러면 그 뒤에 여는 모든 물체와 짝이 됩니다.

| 맵을 가로지르는 물체 | 판정한 쌍 |
| --- | --- |
| 0개 | 13,188 |
| 1개 | 14,188 |
| 5개 | 18,198 |
| 20개 | 33,378 |

스무 개면 2퍼센트인데 판정할 쌍이 2.5배가 됩니다. 하나당 정확히 1000쌍씩 늘어납니다.
바닥 콜라이더나 벽처럼 크고 안 움직이는 것은 **아예 다른 목록에 두는 편**이 낫습니다.

둘째, **고르게 흩어진 장면에서는 격자에 집니다.** 후보 쌍도 갱신 값도 그렇습니다.

| 프레임당 이동 거리 | 스윕 자리바꿈 (한 축) | 격자 목록 조작 (칸 25) |
| --- | --- | --- |
| 0.5 | 1,133 | 95 |
| 2.0 | 4,518 | 375 |
| 8.0 | 18,132 | 1,418 |

격자는 물체가 칸 경계를 넘을 때만 목록을 건드립니다. 천천히 움직이면 프레임당 62개만 바뀝니다.
숫자만 보면 격자가 모든 줄에서 이깁니다.

그래서 정리하면 이렇습니다.

- **고르게 흩어져 있고 크기가 비슷하면** 격자입니다. 이 시리즈에서 네 번째로 같은 결론입니다
- **한 축으로 납작한 장면**이면 스윕입니다. 격자는 빈 칸을 세로로 계속 만듭니다
- **칸 크기를 정할 수 없거나 세계가 무한**하면 스윕입니다. 고를 값이 축 하나뿐입니다
- **겹치기 시작한 순간과 떨어진 순간이 필요하면** 스윕입니다. 그 두 사건이 공짜로 나옵니다

## 어디에 쓰나

물리 엔진의 **브로드페이즈**가 가장 흔한 자리입니다.
쌍을 추려서 정밀 판정으로 넘기는 단계를 그렇게 부릅니다.
3차원이면 축 세 개로 늘리고, 짝마다 겹친 축 수를 세어 3이 되는 것만 올립니다.

정렬해 두고 시간적 일관성으로 유지한다는 발상 자체는 충돌 밖에서도 씁니다.

- **그리기 순서.** 2D 게임에서 y 값으로 정렬해 앞뒤를 정하는 것도 매 프레임 거의 안 바뀝니다
- **반투명 정렬.** 카메라에서 먼 것부터 그려야 하는데, 카메라가 조금 움직이면 순서도 조금 바뀝니다
- **시야 목록.** 거리순으로 세워 두고 가까운 것부터 갱신하는 구조도 같은 성질을 씁니다

공통점은 **답을 새로 구하지 않고 지난 답을 고친다**는 것입니다.
매 프레임 처음부터 구하는 게 당연해 보이는 자리에서, 지난 프레임의 답이 이미 거의 정답이라면
고치는 쪽이 항상 쌉니다. 얼마나 쌀지는 **얼마나 안 바뀌는지**가 정합니다.

## 정리

스윕 앤 프룬은 **구조를 짓지 않고 줄만 세워 두는** 방법입니다.

- 한 축에 눕히면 구간이 됩니다. **구간이 안 겹치면 물체도 안 겹칩니다**
- 한 축만으로는 13,188쌍이 남고, 두 축을 다 보면 409쌍입니다. 추리고 나서 온전한 판정을 한 번 합니다
- **축을 잘못 고르면 스물두 배**가 나빠집니다. 중심의 분산이 큰 축을 쓰세요
- 프레임마다 다시 정렬하지 않습니다. 삽입 정렬로 어긋난 자리만 고치면 됩니다
- **자리 한 번에 짝 하나**가 생기거나 사라집니다. 두 축을 유지하면 프레임당 바뀌는 게 열다섯 개뿐이었습니다
- 값이 같을 때 **끝점을 먼저** 놓으세요. 아니면 목록이 조용히 진실과 어긋납니다
- 맵을 가로지르는 물체는 따로 빼세요. 하나가 1000쌍씩 늘립니다
- 고르게 흩어진 장면에서는 격자가 더 낫습니다. 스윕의 자리는 **납작한 장면**과 **바뀐 것만 알고 싶을 때**입니다