움직이는 것들에는 트리를 짓지 않는다

BVH에서 상자만 고쳐 가며 120프레임을 돌렸더니 레이 비용이 아홉 배가 됐습니다. 쿼드트리는 물체가 칸을 옮길 때마다 쪼개고 합쳐야 했고, KD 트리는 아예 정적 데이터 전용이었습니다.

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

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

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

한 축에 눕히면 구간이 된다

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

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

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

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

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

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

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

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

한 축만으로는 모자라다

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

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

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

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

어느 축으로 눕힐까

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

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

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

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

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

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

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

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

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

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

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

자리 한 번에 짝 하나

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

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

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

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

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

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

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

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

값이 똑같을 때

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

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

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

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

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

약점

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

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

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

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

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

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

어디에 쓰나

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

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

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

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

정리

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

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