重なりを見つける四つの方法

한국어 원문으로 표시합니다.

목표

AABB, 원, 분리축 정리로 겹침을 판정하고, 넓은 단계로 검사 횟수를 줄이고, 광선과 상자의 교차를 풉니다. 이 실습이 끝나면 물리 엔진의 충돌 감지 층을 직접 만들 수 있게 됩니다.

왜 중요한가

물체가 200개면 쌍이 19,900개입니다. 전부 정밀 판정을 하면 물리 계산이 시작되기도 전에 프레임이 끝납니다. 그런데 실제로 겹치는 쌍은 300개도 되지 않습니다. 그래서 충돌 감지는 두 층으로 나뉩니다 — 겹칠 수도 없는 쌍을 아주 싸게 걸러 내는 넓은 단계와, 남은 쌍을 정확히 보는 좁은 단계입니다.

좁은 단계의 일반해가 분리축 정리입니다. 두 볼록 도형이 떨어져 있다면 그것을 갈라놓는 직선이 반드시 존재하고, 그 방향은 두 도형의 변 중 하나와 나란합니다. 그래서 변 법선 방향으로만 투영해 보면 됩니다. 그리고 겹쳤을 때 가장 작은 겹침을 준 축이 곧 가장 짧게 밀어낼 방향이라, 감지와 반응이 같은 계산에서 나옵니다.

단계

/root/collide 에 도구 상자를 놓습니다.
/root/collide/aabb.py — 축 정렬 경계 상자.
/root/collide/circle.py — 원과 원.
/root/collide/sat.py — 분리축 정리.
/root/collide/out/sat.png — 겹친 도형과 최소 이동 벡터.
/root/collide/boxes.txt 와 /root/collide/out/06-broad.txt — 전수 검사 대 정렬-훑기.
/root/collide/ray.py 와 /root/collide/out/07-ray.txt, ray.png — 광선과 상자.

참고

그림은 nohup python3 -m http.server 8080 -d /root/collide/out & 로 띄우고 웹 미리보기 에서 http://localhost:8080/ 을 엽니다.
함수들은 /root/collide 안에 두십시오. 채점기가 그 폴더를 import 경로에 넣고 직접 불러 봅니다.
흔한 실수 하나: 넓은 단계가 좁은 단계와 다른 답을 내는 것입니다. 넓은 단계는 답을 바꾸는 것이 아니라 같은 답을 싸게 얻는 것이므로, 쌍의 개수가 다르면 break 조건이 틀린 것입니다.
흔한 실수 둘: 광선 판정에서 max(tmin, 0) 의 0 을 빠뜨리는 것입니다. 그러면 광선 뒤에 있는 상자도 맞았다고 나옵니다.

그리기 도구 상자를 놓는다

/root/collide/gfxlib.py 를 예시 그대로 저장하고, /root/collide/check.py 로 시험 무늬를 그려 /root/collide/out/00-check.png 를 만드십시오. 무늬는 64x64 검은 배경에 (0,0)에서 (63,63)까지 흰색(255,255,255) 대각선을 긋고, 그 뒤에 (0,32)에서 (63,32)까지 빨강(255,0,0) 가로선을 겹쳐 그은 것입니다.

이 실습부터는 PNG 인코더를 다시 만들지 않습니다. 첫 실습에서 손으로 만든 것과 같은 코드를 도구로 내려 줍니다 — 여기서 배울 것은 파일 형식이 아니기 때문입니다.

실습 파드에는 볼륨이 없어서 앞 실습에서 만든 파일이 남아 있지 않습니다. 그래서 실습마다 도구 상자를 다시 놓는 것으로 시작합니다.

Canvas(w, h, bg) 를 만들고 line(x0, y0, x1, y1, rgb) 로 두 선을 그은 뒤 write_png(path) 로 저장하십시오. 가로선을 나중에 그어야 교차점 (32,32) 가 빨강이 됩니다.

이 실습에서는 겹친 도형과 최소 이동 벡터를 그리는 데 씁니다.

축 정렬 경계 상자

/root/collide/aabb.py 에 overlap(a, b) 와 penetration(a, b) 를 만드십시오. 상자는 (minx, miny, maxx, maxy) 네 실수이고, 경계가 정확히 맞닿은 경우도 겹침으로 봅니다. penetration 은 겹치면 축별 겹침 폭 (dx, dy) 를, 겹치지 않으면 (0.0, 0.0) 을 돌려줍니다.

겹치지 않는 조건을 먼저 쓰는 편이 훨씬 짧습니다.

not (a[2] < b[0] or b[2] < a[0] or a[3] < b[1] or b[3] < a[1])

부등호에 등호를 넣을지 말지가 곧 '맞닿은 경우' 의 판정입니다. 이 실습은 맞닿음을 겹침으로 보므로 위 식처럼 등호를 뺍니다.

겹침 폭은 min(a[2], b[2]) - max(a[0], b[0]) 입니다. 두 상자의 오른쪽 끝 중 왼쪽에 있는 것에서, 왼쪽 끝 중 오른쪽에 있는 것을 뺀 값입니다.

판정 규칙은 한 곳에만 두십시오. 여러 곳에서 다르게 정하면 상자가 바닥에서 떨렸다 붙었다 합니다.

원과 원

/root/collide/circle.py 에 circle_hit(c1, r1, c2, r2) 를 만드십시오. 중심 사이 거리가 반지름의 합보다 작을 때만 겹친 것으로 보고 (True, 법선, 깊이) 를, 아니면 (False, (0.0, 0.0), 0.0) 을 돌려줍니다. 법선은 1에서 2를 향하는 단위 벡터이고 깊이는 r1 + r2 - 거리 입니다. 두 중심이 정확히 같으면 법선을 (1.0, 0.0) 으로 둡니다.

거리가 0 일 때를 따로 처리하지 않으면 0으로 나누기가 납니다. 물체 두 개가 정확히 같은 자리에서 태어나는 일은 실제로 생각보다 자주 있습니다 — 스포너에서 한꺼번에 만들 때가 그렇습니다.

비교만 할 것이라면 제곱근을 피할 수 있지만, 여기서는 깊이를 구해야 하므로 실제 거리가 필요합니다.

법선의 방향을 1에서 2로 정해 두는 것이 중요합니다. 다음 모듈의 충격량 계산이 이 약속을 그대로 씁니다. 반대로 두면 물체가 서로를 끌어당깁니다.

분리축 정리

/root/collide/sat.py 에 sat_hit(a, b) 를 만드십시오. a, b 는 반시계 방향으로 적은 볼록 다각형(꼭짓점 목록)이고, 겹치면 (True, 축, 깊이) 를, 아니면 (False, (0.0,0.0), 0.0) 을 돌려줍니다. 축은 두 도형의 모든 변 법선 중 겹침이 가장 작은 것이고, a 의 무게중심에서 b 의 무게중심을 향하도록 부호를 맞춥니다.

변 (x0,y0) -> (x1,y1) 의 법선은 (ey, -ex) 를 정규화한 것입니다(ex = x1-x0, ey = y1-y0).

한 축에서의 겹침은 min(a1, b1) - max(a0, b0) 이고, 이 값이 0 이하이면 그 축이 두 도형을 갈라놓는 축이므로 즉시 끝내면 됩니다. 나머지 축을 볼 필요가 없습니다.

마지막에 축의 부호를 맞추는 이유는, 변 법선이 어느 도형의 것이냐에 따라 방향이 반대로 나올 수 있기 때문입니다. dot(축, 무게중심b - 무게중심a) < 0 이면 뒤집으십시오.

정사각형 두 개가 x 방향으로 1.5 만큼 떨어져 있으면 축은 (1,0), 깊이는 0.5 가 나와야 합니다.

겹침과 밀어낼 방향을 그린다

/root/collide/draw.py 로 /root/collide/out/sat.png(256x256, 검은 배경)를 만드십시오. 다각형 A 는 [(-1,-1),(1,-1),(1,1),(-1,1)] 을 흰색(255,255,255) 테두리로, B 는 A 를 (1.5, 0.5) 만큼 옮긴 것을 노랑(255,220,60) 테두리로 그리고, B 의 무게중심에서 축 * 깊이 만큼 뻗는 최소 이동 벡터를 빨강(255,60,60) 선으로 그립니다. 화면 좌표는 sx = 128 + 40*x, sy = 128 - 40*y 입니다.

다각형 테두리는 꼭짓점을 순서대로 잇고 마지막에서 첫 점으로 돌아오는 선분들입니다. gfxlib.Canvas 의 line 을 쓰십시오.

최소 이동 벡터는 sat_hit(A, B) 가 돌려준 축과 깊이를 곱한 것입니다. 이 만큼 B 를 밀면 두 도형이 정확히 떨어집니다 — 그것이 '최소' 라는 말의 뜻입니다.

그리는 순서는 A, B, 화살표입니다. 겹치는 자리에서는 나중에 그린 것이 이깁니다.

그림을 보면 두 사각형이 x 방향으로만 살짝 겹쳐 있고 화살표가 오른쪽을 가리키는 것이 보입니다. y 방향 겹침이 더 깊은데도 x 를 고르는 이유가 '가장 짧게 밀어내는 방향' 이기 때문입니다.

정렬해 놓고 훑는다

/root/collide/gen_boxes.py 를 예시 그대로 저장해 실행하면 /root/collide/boxes.txt 에 상자 200개가 만들어집니다. 그 상자들에 대해 전수 검사와 정렬-훑기를 각각 돌려 /root/collide/out/06-broad.txt 에 pairs_brute=, pairs_sweep=, checks_brute=, checks_sweep= 네 줄을 적으십시오.

전수 검사는 i < j 인 모든 쌍을 보는 것이고 검사 횟수는 200*199/2 = 19,900 입니다.

정렬-훑기는 이렇습니다. 상자를 minx 로 정렬해 두면, 어떤 상자와 겹칠 수 있는 것은 정렬 순서에서 뒤에 이어지는 것 중 minx 가 이 상자의 maxx 를 넘지 않는 것들뿐입니다. 그 지점에서 안쪽 반복문을 break 하십시오.

checks_sweep 은 안쪽 반복문에서 실제로 겹침 판정을 부른 횟수입니다(break 로 빠져나간 것은 세지 않습니다).

두 방법이 찾은 쌍의 개수는 반드시 같아야 합니다. 넓은 단계는 답을 바꾸는 것이 아니라 같은 답을 싸게 얻는 것입니다. 다르다면 break 조건이 틀린 것입니다.

광선과 상자 — 슬랩 방법

/root/collide/ray.py 에 ray_aabb(o, d, box) 를 만들어 광선 다섯 개를 상자 (-1,-1,1,1) 에 쏘고, 결과를 /root/collide/out/07-ray.txt 에 r1=hit,t 또는 r1=miss,0.000000 형식으로 다섯 줄 적으십시오. 그리고 /root/collide/out/ray.png(256x256)에 상자를 흰색으로, 맞은 광선은 초록(60,255,120) 으로 맞은 지점까지, 빗나간 광선은 빨강(255,80,80) 으로 길이 6 만큼 그리십시오. 화면 좌표는 sx = 128 + 30*x, sy = 128 - 30*y 입니다. 광선은 순서대로 o=(-3,0) d=(1,0), o=(-3,3) d=(1,0), o=(0,0) d=(1,0), o=(-3,-3) d=(0.7071067811865476, 0.7071067811865476), o=(3,0) d=(1,0) 입니다.

슬랩 방법은 축마다 광선이 그 축의 두 평면 사이에 있는 구간 [t1, t2] 를 구하고, 모든 축의 구간을 교집합으로 좁혀 나가는 것입니다.

t1 = (box.min - o) / d      # 방향이 음수면 t1 과 t2 가 뒤바뀐다
t2 = (box.max - o) / d
tmin = max(tmin, min(t1, t2))
tmax = min(tmax, max(t1, t2))

방향 성분이 0 이면 나눗셈이 터집니다. 그때는 원점이 그 축의 구간 안에 있는지만 보고, 밖이면 빗나간 것입니다.

마지막 판정은 tmax >= max(tmin, 0) 입니다. 0 을 넣는 이유는 광선이 뒤쪽으로 뻗지 않기 때문입니다. 이걸 빠뜨리면 광선 뒤에 있는 상자도 맞았다고 나옵니다. 다섯 번째 광선이 정확히 그 경우입니다.

광선의 출발점이 상자 안에 있으면 t 가 0 입니다(세 번째 광선).