게임 물리 - 충돌 판정

 

물론 

게임 엔진 자체에서.. 충돌판정을 하는 툴을 제공하나

그런 것도 좋지만 원리 자체를 이해해보자.

 

당연하게 생각하는 것에 의문을 품으면 발전할 수 있다.

**꼭 그런 것은 아니다.

 

충돌은 2가지로 판단한다.

1. 그냥 충돌했다.

2. 충돌하지 않는 경우를 제외하면 충돌했다.

 

2가지 접근 방식으로 알아볼 것이다.

 

 

---

 

 

우선 가장 간단한 것은 사각형(2D) 간의 충돌 판정이다.

왜 간단하냐면..

사각형은.. 가로, 세로 길이만 알면

바로 좌표를 정할 수 있어서 그렇다.

물론.. 우리는 직사각형과 같은 것이 제일 좋다.

 

 

충돌도.. 이렇게 하면 조금 귀찮아진다. ㅎ

 

우선 충돌이 일어난다는 것은 

자신의 영역에 다른 무엇인가가 들어왔다는 것이다.

 

아래와 같은 영역을 생각해보자

 

Ractangle 1 

0<x<3, 0<Y<4

 

Ractangle 2

2<x<5, 5<y<6

 

어떤가? 서로의 영역을 침범하는가?

그렇다면 해당 충돌영역을 얼마나 되는가?

를 알아보자

 

우선 X의 영역이 겹치는 것을 보아

충돌 가능성이 있는 것 같다.

하지만 Y의 영역이 겹치지 않아 결국 충돌하지 않은 것으로 판단된다.

 

 

그림을 보면 아래와 같다.

 

 

 

충돌 가능성을 살펴보는 것도 하나씩 살펴보는 것이다.

1번의 가장 오른쪽 영역이 2번의 가장 왼쪽 영역보다 큰가?

크다면 충돌 가능성이 생긴다. 

그렇다면 다시 보자

1번 가장 위쪽 영역이 2번 가장 아래쪽 영역보다 큰가? 

아니다. 그래서 충돌하지 않았다고 판단했다.

 

물론 각 조건에서 엄밀히 비교하자면

1번의 가장 오른쪽 영역이 2번의 가장 왼쪽 영역보다 커서 2번을 넘어가는 경우도 발생할 수 있고

위쪽 영역 역시 더 커서 넘어가버리는 경우도 있다. 

쉽게 표현하기 위해 말한 것이다.

 

그리고 게임에서는 해당 상황만 주고 충돌 판단을 하는 것이 아닌

캐릭터가 움직이면서 충돌 판단을 하는 것이기 때문에

위와 같이 넘어가버린다는 것은 웬만해서는 일어나지 않는 상황이라고 보면 된다.

** 물론 더 좋은 충돌 판단 방법도 있다.

 

---

 

다른 모양은 어떨까?

원형과 원형은??

 

음.. 수학을 열심히는 안해도 수업을 들었다면

우리는 두 원과 중심 거리 간의 관계란 것을 중학교 때인가? 배웠다.

 

 

배웠다면 훨씬 수월해진다.

닿아있는 것도 충돌로 치자면

 

2,3번만 고려해주면 되겠다.

즉, 2개의 원의 원점과 반지름을 계속 조사해주면 될 것이다. 

2개의 중심 사이의 거리가 반지름의 합과 같거나 작아질 때 충돌한다고 생각하면 된다.

 

 

---

 

그렇다면.. 원형과 사각형의 충돌은??

 

조금 더 복잡해진다.

 

원의 반지름이 r이라고 했을 때

사각형의 4부분을 r만큼 확장시킨다.

 

음.. 아래 그림을 보면 사각형을 각 방향만큼 r만큼 확장시킨 것이다.

(파란부분)

 

즉, 원은 저 범위에 들어오지 않는 이상 충돌할 가능성이 전혀 없다.

 

**쉽게 생각한다면 길이 r인 원을 사각형의 둘레를 따라 굴려보자

원의 중심 자취를 그려보면 상상이 갈 것이다.

 

하지만 아래 빨간 부분은 조금 다르다.

 

빨간 부분의 영역에서는 원의 중심이 있더라도 충돌하지 않는 경우가 있기 때문이다.

왜냐하면 대각선으로는 r*(root 2)라는 r보다 긴 길이를 가지기 때문이다.

 

즉, 추가 판정이 필요해진다.

여기서는 충돌하지 않는 경우를 제외하는 것으로 판단한다.

아래 그림을 보자.

 

빨간색이 원의 중심이고

검은색이 사각형이다.

 

사각형 중 원에 중심에 가장 가까운 정점

즉, 파란부분이

원에 포함되어 있지 않다면 충돌하지 않을 것이다.

 

다시 말해서

첫번째 조건에서 먼저 판별이 되고 그 후에는 충돌하지 않는지를 판단해야 할 것이다.

 

두 번으로 나누는 이유는..

처음부터 2번의 계산을 하지 않기 위해서이다.

 

---

 

다음으로는 선분과 같은 막대기와 원의 충돌이다.

 

이건 원과 직선과의 거리에서 배운 것 같은데..

원에대해서 직선에 수선을 내리고 해당 수선의 길이가 반지름보다 작거나 같다면 맞닿아있다고...?

 

하지만 조금 다르다.

직선이 아닐뿐더러.. 선분은 넓이가 없지만 우리의 물체는 선분이 아니라 그냥 가느다란 물체다.

 

즉, 우리가 배웠던 것을 응용은 하겠지만 다르다는 이야기다.

 

우리는 직선의 방정식을 매개변수로 표현하는 방법을 배웠다.

벡터 표현이기도 하다.

p = bt + a와 같다.

**t의 범위에 제한을 두어 직선을 선분으로 만들 수 있다.

 

아래의 그림에선 A->P 벡터가 b로 표현되어있다.

즉, t의 범위에 따라 A를 지나는 선분이 될 것이다.

 

일반적으로 0<= t <= 1의 범위를 가지므로

양 끝이 A,P인 선분을 생각할 수 있게 된다.

 

선분이 만들어졌다.

그렇다면 직선의 방정식처럼 최단거리는 어떻게 구할 수 있을까?

 

 

선분 상의 점과 임의의 점과의 거리를 t의 함수로 나타내고 

해당 함수를 미분에 최솟값을 찾아내면 그것이 거리가 될 것이다.

 

아니면

해당 선분을 직선으로 만들어 수선을 내리고 벡터의 내적을 이용해서 최소값이 나오는 t를 구한다.

미분은 알아서 구하면 되겠다.

 

---

 

다음으로는

부채꼴 물체와의 충돌이다.

 

왜 부채꼴이냐??

칼을 휘두르면

뭐냐이거다.

 

칼을 휘둘렀을 때, 무엇인가 막대기 긴 것을 휘둘렀을 때 쓸 수 있다.

 

그러나 얘도 엄청난 경우의 수가 많다.

원은 원인데 잘린 원인.. 부채꼴이라서 그렇다.

 

일단 원을 생각해보자.

 

1. 부채꼴의 중심에 해당하는 점이. 해당 원의 내부에 있으면 충돌.

2. 해당 원의 좌표가 부채꼴의 내부에 있으면 충돌

 

위 2가지 상황은 당연하다.

하지만 위 상황이 아니어도 충돌 가능성이 생기는 경우가 있다.

ㅋㅋㅋㅋ 내가 그리고도 한숨나오네 ㅋㅋㅋㅋ

 

 

즉, 원의 중심이 바깥에 있어도 충돌 가능성이 생기는 경우가 당연히 생긴다.

위의 상황을 다시 표현하자면

 

 

먼저 원의 중심 좌표가 부채꼴을 형성하는 두 벡터 사이에 있고

부채꼴과 원의 중심 사이간의 거리가 반지름의 합보다 작다면 충돌할 것이다.

 

그 다음에는

부채꼴을 형성하는 두 벡터에 의해 생긴 호가 아닌 외주에서 선분과 원이 교점을 가진다면 충돌한다.

 

 

먼저 두 벡터 사이에 있다는 것을 어떻게 알 수 있을까??

쉽게 말하면서로 평행하지 않은 두 벡터가 있다면 해당 벡터들이 기저벡터가 되어 다른 벡터를 표현할 수 있다.

또한 좌표평면에서의 사분면을 표현하는 것과 같다.

 

즉, 1사분면을 표현하는 것과 같이 부채꼴의 중심에서 물체의 중심에 해당하는 벡터가 양의 기저벡터로 표현된다면

해당 벡터, 다시 말해서 물체의 중심을 부채꼴을 만드는 두 벡터 사이에 있다고 볼 수 있다.

 

다음으로는

호가 아닌 외주를 구성하는.. 다시 말해서 두 벡터에 대해서, 두 선분에 대해서 교점을 가지면 충돌이다.

해당 선분은 벡터로 표현이 가능하고 교점을 구하면 된다.

 

 

---

 

 

지금까지는 2D에 대해서만 충돌 판정을 했다.

원의 방정식이 아닌 구의 방정식이 되겠고사각형이 아니라 직육면체가 되겠다.

 

즉, 차원이 하나가 증가한다.물체의 상태를 표현하기 위해서 필요한 성분이 하나가 증가하는 것이다.

 

뭐 엄청나게 복잡도가 증가하거나 그렇지는 않다.

왜냐하면 그래도 현실에서의 영역이기 때문이다.

 

하지만 정말로.. 게임에서직육면체만 사용되고 구만 사용될까?

복잡도가 증가하는 이유는..사각형이라고 해봐야 어떻게든 4개의 식으로 표현할 수 있지만3차원에서는 하나가 달라지면 신경써야할 부분이 너무 많아지는 탓이다.그래서 2D와 3D를 따로 보는 경향도 생긴다.

 

그러나 수학은 변하지 않는다.3D가 복잡하더라도 2D에서 응용한 것에 불과하다.3D 충돌 검출에 대해서는 나중에 다뤄보겠다.