겹침을 찾는 네 가지 방법

목표

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

왜 중요한가

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

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

단계

1. /root/collide 에 도구 상자를 놓습니다.
2. /root/collide/aabb.py — 축 정렬 경계 상자.
3. /root/collide/circle.py — 원과 원.
4. /root/collide/sat.py — 분리축 정리.
5. /root/collide/out/sat.png — 겹친 도형과 최소 이동 벡터.
6. /root/collide/boxes.txt 와 /root/collide/out/06-broad.txt — 전수 검사 대 정렬-훑기.
7. /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 을 빠뜨리는 것입니다. 그러면 광선 뒤에 있는 상자도 맞았다고 나옵니다.

단계 7개

1. 그리기 도구 상자를 놓는다
2. 축 정렬 경계 상자
3. 원과 원
4. 분리축 정리
5. 겹침과 밀어낼 방향을 그린다
6. 정렬해 놓고 훑는다
7. 광선과 상자 — 슬랩 방법