SAT 충돌 검출 방법

최근들어 물리 처리를 공부하고 있는데, 그 중 제일 기본이 되는 충돌 검출 방식에 대해 기록한다. 대표적으로 SAT가 있는데, Convex 한 물체들에 대해서 어떤 구조를 가지든지 충돌을 검사할 수 있다는 장점이 있다.

다만 퍼포먼스 이슈가 있으므로 광역 검사 후에 지역 검사 시에 사용하는 것이 좋다.

아이디어는 물체를 비출 수 있는 모든 투영 축에 대해 투영하고 모두 겹치는 경우에 물체가 충돌한다고 볼 수 있다는 것이 주요 아이디어이다.

아주 쉬운 예시가 있다. 회전되지 않은 사각형 두 개가 있다고 가정할 때, 아래가 겹쳤는지 확인하려면?

위 두 객체에 대해서,

위와 같이 x 축, y 축으로 투영해서 겹치는 영역이 있는지 확인하면 된다. 한 개의 축이라도 겹치지 않는다면, 그 물체는 충돌하지 않는 것이다.

위 객체 예시를 보자. x축으로는 겹치는데, y축으로는 겹치지 않는다. 하나의 축에라도 겹치지 않으면 그 객체는 충돌하지 않는 것이다.

이를 2D 좌표 평면 공간에서 일반화해보면 다음과 같다.

각 엣지의 노말에 대해 투영했을 때 모두 겹쳐야 충돌 한 것이다.

왜 엣지의 노말이라고 했을까, 아래 이미지를 보자.

각각 노말을 표시해보았다. 파란색 선분은 y축을 나타내고 빨간색 선은 x축을 나타내는 것을 볼 수 있다. 즉 축을 모른다고 가정했을 때(위 상황에서는 말이 안되지만) 각 엣지의 노말의 직선 상에 투영해서 겹치는지만 확인하면 된다. 원점, 시작 점은 중요하지 않다. 어느정도 겹치는지만 파악하면 된다.

이는 객체가 회전 되어있을 때 강점을 드러낸다. 객체가 회전된 상태에서는 단순히 x 축 y 축이 겹치는지만으로는 확인할 수 없다. 이럴 때 회전된 객체와 원 객체에서 모든 엣지의 노말을 추출하고 해당 노말에 대해 투영한 선분이 겹치는지 확인하면 된다.

회전된 객체에 대해서 노말을 하나씩 추출해서 검사하면 위와 같은 모습이 된다. a, c, d 에는 겹치는 라인이 있지만, b 라인에는 겹치는 라인이 없다. 즉 충돌하지 않은 것으로 볼 수 있다.

한편 3D 좌표 공간 상에서 검출을 할 때에는 축이 더 늘어나는데, 엣지 하나의 노말을 알 수가 없기 때문에, 일단 존재하는 엣지 목록에 대해서 외적을 해야 한다. 엣지에 대해서 외적해서 같지 않은 노말이 나올 때 까지 수행해야 하는데, 이 때 서로 다른 두 객체의 각각 엣지에 대해서도 외적을 취해야 한다는 것이다.

즉 두 객체의 모든 엣지에 대해서 외적을 취하면서 노말을 얻어내면 된다. 아무튼 여기서는 2D 공간에서 진행하므로 건너뛴다.

일단 객체의 모든 노말을 수집하고

각 노말을 순회하면서 내적한다. 엣지를 노말에 대해 투영하는 과정인데, 이 부분이 헷갈릴 수 있다. 노말에 대해 내적하는 것이므로 좌표계 원점을 기준으로 노말이 그려진다고 가정하자.

위 방향 벡터 (4,4) 을 노말라이즈 하면 (0.7, 0.7) 정도가 된다.

8,0 점이 있다고 할 때 우리가 대충 눈대중으로 투영하면 어떻게 되는가? 최대한 수직인 지점을 찾아서 당겨주면 될 것이다.

대충 눈 대중으로 맞춘 투영 정점의 길이를 구해보자. 투영된 좌표 정점 (4,4) 는 5.6569 의 길이를 가진다.

이제 다시 돌아가서 dot 내적식으로 계산해보자. 4*8 + 4*0 = 32이고, 32를 sqrt 해주면, 5.6568 이 나온다. 즉 dot을 하면 투영하는 노말 벡터 위에 투영된 정점의 길이를 알 수 있다. 이 길이 정보로 해당 축 위의 어디에 존재하는지 알 수 있고 겹치는지도 알 수 있다.

이제 이렇게 구해진 각 축에 대해 max, min을 비교해서 겹치는지 확인하면 된다. 하나라도 안 겹치면 더 이상 다른 축을 확인할 필요가 없다. 한편 겹쳐지는 경우 각 축에서 겹쳐진 정도를 기록하며 최솟값을 찾아내면 된다.

그러다가 최소의 길이를 가지는 지점이 최소 축 침투 노말이 된다.

위 두 객체의 최소 침투 축은 x축이고, 1만큼 침투했다고 볼 수 있다 .이는 나중에 충돌 지점을 알아내는 데 사용할 수 있다. 침투 지점을 추출할 때는 이제 침투축과 내적을 수행해서 맞닿은 지점을 찾아내는 방법을 활용하는데, 이 부분은 다음 게시글에서 설명한다.