SAT 충돌 후 충돌 지점 찾아내는 과정에 대해서

MTV의 최소축과 깊이를 알아냈다면, 이제 충돌 지점을 알아낼 수 있는데 도형 처리의 순서에 따라 뒤집어지는 경우가 있어 굉장히 골치아프다.

일단 SAT 처리를 하다보면 경계선과 충돌선이 뒤바뀌는 경우가 제법 있다.

예를 들어 위 예시를 보자. 파란색이 경계선이고 보라색이 충돌선 이다. 위와 같이 평행한 경우는 계산 순서나 처리 과정에 따라서 침투축과 경계선이 바뀔 수 있다. MTV 계산 과정에서 A 객체를 먼저 순회하느냐, B 객체를 먼저 순회하느냐에 따라 바뀔 수도 있고, 각도에 따라서 바뀔 수도 있다.

일단 MTV 노말에 대해 제일 맞닿아 있는 엣지를 내적으로 찾아낸다. 모든 엣지를 순회하면서 구해내면 된다.

예를 들어 위 사진을 보자. 빨간색 박스의 보라색 엣지가 충돌 선이고, 파란색 점이 경계선으로 인식된 것을 알 수 있다. 이는 아래 작은 이미지(MTV의 노말)에 대해 제일 맞닿은 (내적시 1이 되는) 엣지를 찾아낸 것이다.

제일 맞닿아 있는 엣지를 찾아내는 방법은 어렵지는 않다. 애초에 2D 좌표 평면상에서 MTV 노말 벡터는 충돌한 경계면의 법선이다. 법선에서 내적해서 제일 수직이 되는 변은 당연히 자기 자신 엣지일 것이다. 그런데 위 화살표로 된 엣지 영역이 검출되지 않는 이유는 객체를 시계방향으로 그렸기 때문이다. 즉 평행해도 시작점이 파란색 엣지와 다르기 때문에 내적시 파란색 엣지와 부호만 다른 값이 나온다.

그런데, 충돌 지점에 따라 다른 문제가 발생하는데,

객체가 옆에서 충돌하는 경우, 또는 특정 방향에서 충돌하는 경우 경계선과 보라 엣지가 바깥으로 탐지된다. 이 상황에서, 여전히 회색 객체에서 경계선을 찾는 과정 중에 이번에는 충돌 방향이 반대 방향이라서, 충돌한 엣지측은 내적시 부호가 반대로 나오기 때문에 시계 방향쪽인 반대편이 칠해진다. 아무튼 이 문제를 해결해주기 위해서, 두 객체 사이의 벡터를 하나 구해서, A 객체에서 B 객체의 방향 벡터를 구하고 MTV 방향이 반대인 경우 -1을 곱해주는 식으로 해결할 수 있었다.

위 예시에서는 좌측 아래 MTV 벡터를 작게 표시해놨는데, MTV 벡터와 객체 중심 방향 (무조건 A->B) 가 같은 경우에는 그대로 내비두고,

반대 일 때는 -1을 곱해주어 무조건 내부 처리를 위한 MTV 방향은 객체 A->B 를 향하도록 수정해준다. 이 때, 객체를 섞지 말고 순회할 때 한 방향으로 순회하도록 해야한다 B, A 자리가 바뀌면 방향이 다시 바뀔 수 있기 때문에 for 시에도 같은 객체가 뒤집어서 계산되지 않도록 해야한다.

그러면 일단 충돌이 발생한 가까운 두 엣지를 검출 해 낼 수 있게 된다. 그런데 아직 한가지 문제가 더 남았는데, 일단 가까운 두 엣지를 검출 해 냈다면, 여기서 MTV 에 수직으로 맞닿은 엣지를 경계 선, 나머지 한 선을 충돌 선으로 지정해야 하는데,

위 예시를 보면 알 수 있다시피, A 객체에서 MTV와 제일 맞닿은 엣지를 하나 구하고, B 객체에 대해서 MTV와 제일 맞닿은 엣지를 하나 구했다. 즉 무조건 A가 B에 비해 제일 맞닿았다고는 볼 수 없는 것이다. 따라서 A와 B도 비교 연산을 해주어 MTV에 더 맞닿아있는 엣지를 경계로, 나머지를 충돌선으로 찾아줘야 한다.

한편, 충돌 점을 구하기 위해서는 직선 교차식을 사용해서 범위로 잘라줘야 하는데, 이 충돌 선의 점이 땅경계션 위에 있는지, 아니면 안에 박혔는지 확인을 해야한다.

위 예시를 보자. 파란색이 경계선일 때, 점이 파란색 밑으로 박혔는지 확인하기 위해 MTV 방향을 확인하면 된다. MTV이 침투 축이므로 해당 축으로 파고 들어갔다는 것이기에 MTV 와 내적해서 양수가 나오면 박혀있다는 것을 알 수 있다. (경계선의 아무런 점에서 충돌 점을 향하는 방향 벡터를 만들면된다.)

문제는 위 사례에서 발생한다.

객체가 회전을 하다보면 방향이 반대가 되기도 한다. MTV 는 왼쪽 아래로 향하고 있는데, 막상 경계선에서 충돌 점에서 향하는 벡터는 반대 방향이다. 이 이유가 A 객체에 충돌선(보라선)이 있고, B 객체에 경계선(파란선)이 있으면 정상 동작하는데, 아까 넣었던 A, B 두 개 중에 더 적합한 경계선과 충돌선을 찾아 바꿔주면서 방향이 바꼈기 때문이다. 객체는 시계 방향인데, 경계선과 충돌선이 처리되는 A, B 의 객체 순서가 바꼈기 때문이다.

물론 내가 시도를 하면서 다양한 경우의 수에 맞춰 작업을 하다 보니 이 게시글의 내용이 정확하지는 않다..

잘 찾아지는 것을 볼 수 있다..

참고로 충돌 점을 찾을 때는 일단 클립핑을 해야 한다. 나 같은 경우 직선과 선분 만나는 교차점을 찾아내고, 잘라내기 위한 직선은 t 범위 제한 안주고, 선분 교차점을 구하기 위한 u는 0~1 제한을 주는식으로 하였다. 제한을 주고 해당 제한된 u로 교차점을 구하면 알아서 잘라진 위치를 알아낼 수 있기 때문이다.

그렇게 구해낸 좌표를 다시 박혀있는지 확인하는 내적식을 통해 박힌지 확인하였다.

위 두 객체가 있고, 경계선, 충돌선(보라)을 구했을 때 경계선의 시작점, 끝점에 대해 각각 외적 벡터를 구해 법선을 구해낸다. 법선 방향은 중요하지 않다. 직선으로 잘라내기 위한 것이기 때문이다. 그리고 보라(충돌)를 잘라내야하므로 보라 선분식과 위 외적하여 나온 2개의 경계선에 대해 각각 교차점을 구한다. 이때 나온 외적에 대한 ratio 는 t, 선분에 대한 ratio 는 u라고 했을 때 t는 중요하지 않다. u로 유도를 할 때, u의 범위를 0~1로 제한하면 선분의 범위로만 제한이 된다.

이렇게 구해진 두 점을 이제 아까 MTV랑 경계->점 내적을 해서 파고 들었는지 확인한다. 그러면 충돌점 하나만 남겨진다.

추가로 위 같은 상황이더라도, 빨간색 원이 구해지지는 않는다. 교차점은 빨간색 점 부분이지만, u를 0~1로 제한했기 때문에 보라 범위 내로만 나온다.