[💬] GJK알고리즘을 사용한 다양한 도형의 충돌판정 구하기

[vertex(4321vertex)]

GJK충돌판정 알고리즘을 이용해서 다양한 형태의 도형들의 충돌판정을 구현하는 방법에 대한 글이에요

그리고 저도 수학이랑 프로그래밍을 잘 아는게 아니고, 제가 이해한 범위 안에서만 쓰는 내용들이라

틀리거나 정확하지 않은 내용들이 있을수도 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 목차

이번 글에서 다룰 내용은 다음과 같아요

첫번째로 오브젝트의 충돌의 종류에 대해 살펴보고, 여러 충돌판정 방법들을 간략하게 살펴볼 거에요

두번째로 GJK충돌 알고리즘에 대해 이야기할 거에요

그리고 세번째로 곡선으로 이루어진 도형을 다각형으로 간략화하는 방법, 기울어진 다면체의 좌표를 구하는 방법을 살펴본 다음

마지막으로 충돌감지의 최적화 방법에 대해서 이야기할 거에요

2. 도형들의 충돌의 여러 형태

위에 올려놓은 그림은 다각형들의 다양한 충돌방식에 대해 설명하는 그림이에요

1. 충돌은 한 다각형의 한개 혹은 여러개의 꼭짓점이 다른 다각형 내부에 포함되는거에요

2. 포함은 한 다각형의 모든 꼭짓점이 다른 다각형 내부에 포함된 경우에요

3. 관통은 두 다각형이 충돌했지만 꼭짓점이 서로의 내부에 포함되어있지 않은 경우에요

3. 원과 원의 충돌

다양한 충돌감지 방법중 첫번째로 살펴볼건 원과 원의 충돌이에요

첫번째 원의 중점이 (x1,y1) 이고 반지름이 r1 두번째 원의 중점이 (x2,y2)고 반지름이 r2일때

두 원의 중점 사이의 거리 ( (x2-x1)^2+(y2-y1)^2 )^0.5 가 두 원의 반지름의 합 r1+r2보다 작으면 충돌했다고 판정해요

그리고 이 공식은 최적화를 위해서 루트를 제거한 방식으로 (x2-x1)^2+(y2-y1)^2 = d^2 의 형태로 사용되기도 해요

4. 사각형과 사각형의 충돌

두번째는 기울어지지 않은 사각형 사이의 충돌이에요

만약 충돌했다면 오른쪽처럼 xy축에서의 두 사각형의 모든 영역이 겹쳐질 것이니까

xy축중 하나라도 겹쳐지지 않는 영역이 있다면 충돌하지 않았다고 판정해요

즉, a의 x좌표중 최대값이 b의 x좌표중 최소값보다 작거나, 혹은 그 반대로 b의 최대가 a의 최소보다 작거나

a의 y좌표중 최대값이 b의 y좌표중 최소값보다 작거나, 역시 그 반대로 b의 최대가 a의 최소보다 작으면 충돌하지 않았다고 판정해요

5. 분리축(SAT) 충돌검사

세번째는 분리축(SAT)충돌감지 방법이에요

두개의 다각형의 모서리를 각각 벡터로 바라본다음 해당 벡터들에 수직인 벡터를 구해서

그렇게 구한 수직벡터들로의 두 다각형의 투영영역을 구해서 만약 겹치지 않는 수직벡터 영역이 한군데라도 있으면

충돌하지 않았다고 판정하는거에요,

위의 그림을 보면 첫번째는 두 도형이 충돌했기 때문에 모든 수직벡터에서(그림에서는 3개만 나와있지만 사각형 4개 + 삼각형 3개로 총 7개에서 검사해요) 두 도형의 투영 영역이 겹치지만

두번째 그림에서는 두 도형이 충돌하지 않았기 때문에, 두 도형의 충돌영역이 겹치지 않는 수직벡터가 있어요

그리고 이런 분리축 충돌검사는 직사각형과 직사각형의 충돌로 단순화시킨 OBB 충돌검사를 사용하기도 해요

6. 볼록다각형

그리고 다음으로 GJK충돌판정 알고리즘의 설명으로 들어가면

 

우선 GJK충돌판정 알고리즘은 두 볼록다각형의 충돌을 검사하는 방법이에요,

위의 그림에서 첫번째 두번째는 볼록다각형이지만, 세번째는 볼록다각형이 아니에요

7. 민코프스키 합

위의 첫번째 그림처럼 두 다각형이 있을때, 두 다각형의 각각의 꼭짓점을 원점에서 해당 꼭짓점을 향하는 벡터로 바라본다음

두번째 그림처럼 한 다각형의 각각의 벡터(꼭짓점)에 다른 다각형의 각각의 벡터(꼭짓점)을 더하면 새로운 벡터(꼭짓점)들을 얻을수 있어요,

그리고 이렇게 얻어진 벡터들을 두 다각형의 민코프스키 합이라고 해요

그리고 위의 그림에서 갈색으로 테두리를 그려놓은것처럼, 이렇게 얻어진 민코프스키 합은 가장자리를 따라서 다각형으로 바라볼수 있어요

8. 민코프스키 차이

위의 그림에서 보이는것처럼, 민코프스키 합과 비슷한 방식으로 한 다각형의 모든 꼭짓점(벡터)들 각각에 다른 다각형의 모든 꼭짓점(벡터)들을 빼서, 새로운 벡터들을 얻을수 있어요, 

 

앞의 그림에서 두 꼭짓점들(벡터들)간의 차이로 얻어진 벡터들을, 원점을 중심으로 정리하면 위의 그림이 나와요,

그리고 이렇게 어떤 다각형에서 다른 다각형의 모든 벡터들을 빼서 얻어진 벡터들을 두 다각형의 민코프스키 차이라고 해요 

역시 민코프스키 합과 마찬가지로 민코프스키 차이도 위의 그림에서 갈색으로 그려놓은것처럼, 가장자리를 따라서 다각형으로 바라볼수 있어요

9. GJK충돌판정 알고리즘의 원리

그리고 만약 두 다각형이 충돌했다면 두 다각형의 민코프스키 차이는 원점(0,0)을 포함하고 있어요

즉, 두 다각형의 민코프스키 차이를 구한다음 그렇게 얻어진 민코프스키 차이에 원점이 포함되는지를 검사하면

두 다각형이 충돌했는지 안했는지를 알 수 있어요, 이게 GJK충돌판정 알고리즘의 원리에요

위에 올려놓은 그림은 왜 두 다각형이 충돌했을때 두 다각형의 민코프스키 차이가 원점을 포함하는지에 대한 이유에요

위의 그림의 왼쪽처럼 만약 원점(0,0)이 어떤 다각형의 외부에 있다면, 원점으로부터 그 다각형의 모든 꼭짓점까지의 벡터들은 180도 범위를 넘어가지 않아요

그리고 오른쪽 그림처럼 원점이 어떤 다각형의 내부에 있다면, 원점으로부터 그 다각형의 모든 꼭짓점까지의 벡터들은 180도 범위를 넘어가요

그리고 위의 그림은 두 다각형간의 민코프스키 차이들중 일부를 표시해놓은 거에요, 여기서는 사각형에서 삼각형을 빼는 방식이에요

첫번째 그림에서처럼 두 다각형이 충돌하지 않았다면 두 다각형의 민코프스키 차이들의 범위는 180도 범위를 벗어나지 않아요

그렇지만 두번째 그림처럼 두 다각형이 충돌했다면 그림에서 보이는것처럼 두 다각형간의 민코프스키 차이들은 180도 범위를 넘어가요

즉, 저렇게 얻어진 모든 민코프스키 차이들을 원점을 중심으로 모아서 새로운 다각형을 만들었을때, 벡터들의 범위가 180도를 넘어가니까, 원점은 그 다각형의 내부에 있게되는거에요

10. Support Point

Support Point는 어떤 다각형의 모든 꼭짓점중, 특정 방향에서 가장 멀리있는 꼭짓점을 이야기해요

즉, 특정한 다각형과 특정한 벡터가 주어졌을때, 그 다각형을 구성하는 꼭짓점들중 그 벡터의 방향으로 가장 멀리있는 꼭짓점을 이야기하는거에요

위의 그림에서 왼쪽과 오른쪽에서 각각 표시해놓은 꼭짓점들이 해당 벡터에서의 support point에요

그리고 이 support point는 벡터의 내적으로 구할수 있어요

역시 다각형의 각각의 꼭짓점들을, 원점으로부터 해당 꼭짓점까지의 벡터로 바라보면

다각형의 모든 꼭짓점(벡터)들을 주어진 방향벡터와 내적했을때, 그 길이가 최대로 나오는 꼭짓점(벡터)가

그 방향벡터에서 그 다각형의 support point에요, 위의 그림에서는 파랑색으로 표시해놓은 꼭짓점이 아래의 파랑색 벡터에 대한 삼각형의 support point에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def support_point(x,y,p)

rx,ry,d = nil,nil,nil

i = 0

until p[i] == nil

b = p[i][0]*x+p[i][1]*y

if d == nil || b > d

rx,ry,d = p[i][0], p[i][1], b

end

i+=1

end

return rx,ry

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위에 올려놓은 함수는 support point를 구하는 함수에요, ruby프로그래밍 언어로 작성했어요

함수의 입력값에서 x,y는 방향벡터고, p는 다각형이에요 ruby의 배열로 [ [x1,y1],[x2,y2],[x3,y3], ] 형식의 값으로 입력되요

위의 예시는 세 꼭짓점 (x1,y1) (x2,y2) (x3,y3) 을 가진 삼각형의 경우일때에요

각각의 꼭직점들을 주어진 방향벡터와 모두 내적한다음, 그중에서 내적값이 최대로 나온 꼭짓점을 return값으로 출력해요

11. 민코프스키 차이의 support point

앞에서 민코프스키 차이들로 얻어진 벡터들의 가장자리를 따라서, 민코프스키 차이를 다각형으로 바라볼수 있다고 이야기했어요

그리고 그렇게 민코프스키 차이를 다각형으로 바라봤을때, 마찬가지로 민코프스키 차이에 대해서도 support point를 구할수 있어요

위의 그림에서 아래의 사각형과 삼각형의 민코프스키 차이로 얻어진 도형이 위의 다각형이고, 이때 파랑색 벡터 방향의 해당 민코프스키 차이의 support point가 그림에 표시해놓은것처럼 a일때

이 a는 사각형의 동일한 방향으로의(파랑색 벡터) support point인 b에서 삼각형의 반대방향으로의(주황색 벡터) support point인 c를 빼면 얻을수 있어요, 즉 a=b-c에요

ㅡㅡㅡㅡㅡㅡ

def mink_dif(vx,vy,p1,p2)

x1,y1 = support_point(vx,vy,p1)

x2,y2 = support_point(-vx,-vy,p2)

return x1-x2,y1-y2

end

ㅡㅡㅡㅡㅡㅡ

그리고 이게 특정 방향으로의 민코프스키 차이의 support point를 구하는 함수에요, 앞에서 정의한 support point 함수가 사용되요

입력값은 벡터 vx,vy가 주어졌을때, 다각형 p1과 p2의 민코프스키 차이의 주어진 방향(vx,vy)으로의 support point를 구해주는 함수에요

역시 p1과 p2는 앞의 함수처럼 ruby의 배열을 사용해서 [ [x1,y1],[x2,y2],[x3,y3], ] 과 같은 방식으로 입력되요

12. 특정 방향으로 수직인 벡터 구하기

어떤 벡터에서 특정 방향의 수직벡터를 구하는 함수는 GJK알고리즘에서 사용되는 함수에요,

위에 올려놓은것처럼 x,y의 벡터가 있을때 그 x,y에 수직인 벡터는 -y,x y,-x이렇게 두개가 있어요

그리고 그 두가지중 어떤 벡터가 특정 방향으로의 수직벡터인지를 구하는거에요

그리고 이건 벡터의 내적으로 구할수 있어요

위의 그림에서 초록색이 주어진 벡터일때, 파랑색 벡터의 두가지 수직벡터(두개의 주황색 벡터)중, 어떤게 초록색 방향의 수직벡터인지를 구하려면

두개의 주황색 벡터를 각각 초록색 벡터에 내적을 해보면 되요, 그러면 그 값이 +로 나오는 방향의 벡터가 초록색 방향의 수직벡터에요

왼쪽 그림에서는 -y,x가 초록색과의 내적값이 +로 나오기 때문에 구하고자 하는 방향의 수직벡터이고

오른쪽에서는 y,-x가 초록색과의 내적값이 +로 나오기 때문에 구하고자 하는 방향의 수직벡터에요

ㅡㅡㅡㅡㅡㅡㅡㅡ

def vector_direct(x1,y1,x2,y2)

if -y1*x2+x1*y2 >= 0

return -y1,x1

end

if y1*x2+-x1*y2 >= 0

return y1,-x1

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 위의 과정을 함수로 정리한거에요

위의 함수는 입력값에서 x1,y1벡터의 x2,y2벡터 방향으로의 수직인 벡터를 구해주는 함수에요,

즉 최종적으로는 x1,y1과 수직인 두 벡터중에서 x2,y2방향으로의 벡터가 출력되요

13. GJK알고리즘의 작동방식

GJK알고리즘의 작동방식은, 우선 첫째로 앞서 설명한 mink_dif 함수를 이용해서, 충돌판정을 하고자 하는 두 다각형의 임의의 방향(벡터)으로의 민코프스키 차이의 support point를 하나 구해요

이때의 방향(벡터)은 아무거나 지정해도 상관없어요,

위의 그림에서 검정색 다각형이 충돌판정을 하고자 하는 두 다각형의 민코프스키 차이로 얻어진 다각형이고, 이때 파랑색이 임의의 방향으로의 해당 다각형의 support point에요

두번째로 그렇게 얻은 임의의 지점(파랑색)에서 원점(0,0)방향으로의 support point를 구해요, 역시 mink_dif 함수를 사용해요

그렇게해서 얻어진게 초록색 점이에요, 첫번째 그림이에요

그리고 두번째 그림은 그렇게 해서 얻어진 파랑색점 > 초록색점 까지의 벡터(초록색 벡터)와

원점 > 초록색점 까지의 벡터(검정색 벡터)를 내적해서 둘의 방향을 비교해요

초록점은 민코프스키 차이로 얻어진 다각형에서, 원점 방향으로 제일 멀리 있는 점인데

만약 두 벡터의 내적값이 0보다 작다면, 즉 두 벡터가 서로 다른 방향이라면

원점은 결국 민코프스키 차이 다각형 내부에 존재하지 않는다는게 되니까

충돌하지 않는다고 판정하고 함수를 종료해요

다음의 과정은 여기서 내적했을때 +가 나온 경우, 즉 두 벡터가 같은 방향에 있는 경우에요

14. GJK알고리즘의 반복부분 

그리고 세번째로는 우선 앞에서 얻은 두 점을 이은 직선에서(위의 그림의 초록색 직선), 원점까지의 방향으로 수직인 벡터를 구해요

여기에는 앞에서 설명한 vector_direct 함수가 사용되요

그리고 mink_dif함수를 사용해서 그렇게 얻은 수직벡터 방향으로의 민코프스키 차이 다각형에서의 support point를 구해요

왼쪽의 그림에서 주황색 벡터가 원점 방향의 수직벡터고, 주황색 점이 해당 방향으로의 민코프스키 차이 다각형의 support point에요

그리고 오른쪽의 그림처럼 이때의 직선에서 support point까지의 수직벡터(주황벡터) 와 원점에서 support point까지의 검정색 벡터를 내적해서

만약 값이 0보다 작게 나온다면, 즉 두 벡터의 방향이 다르다면 원점은 민코프스키 차이 다각형 밖에 있는거니까, 충돌하지 않았다고 처리하고 함수를 종료해요

여기서의 주황점은 직선에서 원점방향으로 최대로 멀리 있는 민코프스키 다각형의 support point인데, 원점이 이것보다 더 멀리있다면(두 벡터의 방향이 반대라면) 원점은 결국 민코프스키 차이 다각형 밖에 있는게 되는거에요

그리고 다음의 과정은 여기서 두 벡터의 내적값이 +가 나왔을때에요

15. 원점의 범위 제한

위의 그림 가운데의 삼각형은 앞의 과정에서 얻은 세번째 점과, 기존의 직선의 양 끝점을 이어서 그린 삼각형이에요

그리고 이때에 원점은 위의 그림에 표시된 영역에서 e f g 의 영역에밖에 있을수 없어요

우선 첫번째 초록색 직선은 한 점에서 원점 방향으로의 support point를 찾아서 그린 직선이기 때문에

그 직선의 시작점 뒷쪽인 a영역에는 원점이 있을수 없고, 앞에서 그 직선의 도착점인 support point가 원점과의 내적에서 +가 나왔기 때문에

그 직선의 도착점 너머의 영역인 b에도 원점이 존재할수 없어요

그리고 삼각형의 세번째 꼭짓점은 위의 초록색 직선에서 원점 방향으로의 support point니까, 이 직선의 뒤쪽 반대편인 d 영역에는 원점이 있을수 없고

역시 그렇게 구한 support point도 원점과의 내적에서 +가 나왔기 때문에 그 세번째 꼭짓점 너머의 영역인 c에도 원점은 있을수 없어요

즉, 그렇게 소거하면 최종적으로 e f g 영역에만 원점이 있을수 있다는 결론이 나와요

그리고 최종적으로 이때에 원점이 삼각형 내부인 g 영역에 있어야만 원점이 민코프스키 차이 다각형 내부에 있다고 판별해서 충돌했다고 처리하고 함수를 종료해요

16. 삼각형 내부의 원점 판별

 

그래서 다음의 과정은 우선 원점이 삼각형 내부(위의 과정의 g영역)에 있는지 판별하는거에요

그리고 이걸 판별하기 위해, 우선 삼각형의 두 모서리(위의 그림의 주황과 파랑)에서, vector_direct 함수로 삼각형의 다른 꼭짓점 방향으로 수직인 벡터를 구해요

그렇게 하면 그림 아래쪽의 두개의 벡터가 나와요

그리고 그 벡터들을 원점으로부터 두 모서리의 한 꼭짓점까지의 벡터(위의 그림의 보라색 벡터)와 내적해서 그 값을 비교해요

그래서 최종적으로 오른쪽 그림처럼 두 내적값이 모두 0보다 크면 원점은 삼각형 내부에 있는거니까 충돌했다고 처리하고 함수를 종료해요

17. 다음 직선을 구해서 알고리즘을 반복하기

그리고 만약 앞의 과정에서 두 내적값이 0보다 크게 나오지 않으면, 즉 원점이 삼각형 내부(g영역)에 있지 않으면

다음 과정은 원점이 e f 영역중 어디에 있는지를 찾는거에요,

그리고 두 벡터를 내적했을때 그 값이 위의 첫번째 그림과 같으면, 즉 오른쪽이 -고 왼쪽이 +면 

원점은 f영역에 있는거니까 첫번째 그림의 오른쪽처럼 삼각형의 오른쪽 모서리를 직선으로 해서 

14. GJK알고리즘의 반복부분 

여기서부터 과정을 다시 시작해요

그리고 두 벡터의 내적값이 위의 두번째 그림처럼 왼쪽이 -고 오른쪽이 +면

원점은 e 영역에 있는거니까, 역시 그림의 오른쪽처럼 삼각형의 왼쪽 모서리를 직선으로 해서, 역시 14번 과정부터 함수를 다시 반복해요

그리고 이러한 과정을 계속 반복하면

최종적으로 원점이 민코프스키 차이 다각형 속에 있는지 없는지를 판별할수 있어요

이게 GJK충돌검사 알고리즘의 작동방식이에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def gjk_collision(p1,p2)

#1

x1,y1 = mink_dif(1,0,p1,p2)

x2,y2 = mink_dif(0-x1,0-y1,p1,p2)

#2

if (x2-x1)*x2+(y2-y1)*y2 <= 0

return 0

end

#3

while 1== 1

vx,vy = vector_direct(x2-x1,y2-y1,0-x1,0-y1)

x3,y3 = mink_dif(vx,vy,p1,p2)

#4

if vx*x3+vy*y3 <= 0

return 0

end

#5

tx,ty=vector_direct(x3-x1,y3-y1,x2-x1,y2-y1)

d1 =  (0-x1)*tx+(0-y1)*ty 

tx,ty=vector_direct(x3-x2,y3-y2,x1-x2,y1-y2)

d2 =  (0-x2)*tx+(0-y2)*ty 

#6

if d1 >= 0 && d2 >= 0

return 1

end

#7

if d1 <= 0

x1,y1,x2,y2 = x1,y1,x3,y3

end

#8

if d2 <= 0

x1,y1,x2,y2 = x2,y2,x3,y3

end

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 위에 올려놓은 코드가 이러한 GJK알고리즘의 코드에요,

입력값인 p1 p2는 충돌을 판별하고자 하는 두 다각형이에요, 역시 [ [x1,y1],[x2,y2],[x3,y3], ] 와 같은 ruby 언어의 배열 방식으로 입력되요

위의 코드에서 초록색으로 표시된 주석에서 #1 #2가 앞의 설명의 13번 부분이고

#3 #4가 14번 부분

#5 #6이 16번 부분

#7 #8이 17번 부분이에요

그리고 이게 실제로 위의 gjk충돌판정 알고리즘을 이용해서 충돌판정을 처리해보는 영상이에요

파랑색이 방향키로 움직이는 사각형이에요, 만약 중앙에서 회전하는 분홍색 직사각형과 충돌했다면 둘다 반투명하게 표시되요

18. 곡선 도형의 다각형 근사

다음 설명은 앞에서 구한 충돌판정 알고리즘으로 실제로 여러 도형들의 충돌판정을 구해보는 방식에 대한 설명이에요

첫번째 설명은 가장자리가 곡선인 도형들의 충돌판정을 구하는 방법이에요,

그리고 여기서는 곡선 도형의 충돌판정을 구하기 위해서 해당 도형을 다각형으로 근사하는 방법을 사용했어요,

즉, 곡선인 도형과의 충돌판정을 구하는게 아니라 곡선 도형과 상당히 유사한 다각형과의 충돌판정을 구하는거에요

우선 원은 위의 오른쪽 그림처럼 팔각형으로 근사시켰어요,

즉, 원과의 충돌판정을 구하는게 아니라, 실제로는 원에 가까운 팔각형과의 충돌판정을 구하는 거에요,

다음으로 타원 역시 위의 그림처럼 팔각형으로 근사시켰어요,

마찬가지로 타원과의 충돌판정을 구한다고 해도, 실제로는 타원이 아닌 오른쪽 그림의 팔각형과의 충돌판정을 구하는거에요

19. 기울어진 다각형의 꼭짓점 구하기

두번째 설명은 기울어진 다각형의 꼭짓점을 구하는 방법이에요

그리고 위의 그림은 벡터의 회전 공식이에요

그림에 나온것처럼 벡터 x1,y1이 원점을 기준으로 a각도만큼 회전해서 나온 벡터가 x2,y2일때

x2 = x1*cos(a)-y1*sin(a)

y2 = x1*sin(a)+y1*cos(a)

가 되는 방식이에요

그리고 이 벡터의 회전 공식으로 기울어진 다각형의 꼭짓점의 좌표를 구할수 있어요

다각형의 중심점이 원점(0,0)에 놓인 방식으로 다각형의 각각의 꼭짓점들의 좌표값이 주어졌을때

만약 다각형이 원점을 중심으로 a각도만큼 기울어졌다면, 역시 그 다각형의 꼭짓점들도 원점을 중심으로 a각도만큼 기울어진게 되는거니까

원래의 다각형의 꼭짓점에 위의 벡터의 회전공식을 사용하면 기울어진 각도에서의 다각형의 꼭짓점의 좌표를 구할수 있어요

ㅡㅡㅡㅡㅡㅡ

def vector_turn(x,y,a)

return x*Math.cos(a)-y*Math.sin(a),x*Math.sin(a)+y*Math.cos(a)

end

ㅡㅡㅡㅡㅡㅡ

그리고 위의 함수는 위의 그림에 나온 공식을 함수화시킨거에요

입력값의 x,y가 회전시킬 벡터고 a가 회전각도에요

그리고 다각형의 회전에서 실제로 모든 꼭짓점을 회전시키지 않아도 되요

예를들어 위의 마름모를 보면 왼쪽 그림에서처럼 마름모의 꼭짓점은 4개지만

실제로는 오른쪽 그림에 표시한것처럼 2개의 꼭짓점만 회전시키면 되요

다각형의 꼭짓점들의 좌표는, 다각형의 중심점이 원점에 놓였을때를 기준으로 주어졌으니까

나머지 2개는 해당 꼭짓점들에 정 반대방향인 벡터(-x,-y)가 되고, 결국 회전공식을 사용하지 않고 벡터의 부호를 바꾸는것 만으로 구할수 있어요

위의 그림처럼 크리스탈 형태의 다각형도

왼쪽 그림처럼 꼭짓점은 여섯개가 있지만 실제로는 오른쪽 그림처럼 두개의 꼭짓점만 회전시키면 되요

중앙의 4개의 꼭짓점은 중앙의 원점을 기준으로 서로 수직(90도)이니까, 한 꼭짓점의 부호를 바꾸는것 만으로 구할수 있고

가장자리의 2개의 꼭짓점은 역시 서로 반대방향이니까, 하나만 회전시키고 다른 하나는 한 꼭짓점의 부호를 바꾸는것으로 구할수 있어요

20. 오목 다면체의 충돌판정 구하기

세번째는 위의 그림처럼 볼록 다각형이 아닌 다각형의 충돌판정을 구하는 방법이에요

그리고 이건 그림의 오른쪽처럼 해당 오목 다각형을 여러 볼록 다각형으로 나눠서 각각의 다각형과의 충돌판정을 구하는 방식으로 구할수 있어요

오른쪽 그림을 보면 수리검 모양을 두개의 마름모로 나누어놓은걸 볼 수 있어요

즉, 실제로는 수리검 모양과의 충돌판정을 구하는게 아니라, 저렇게 두개의 마름모 모양과의 충돌판정을 각각 구하는거에요,

 

21. 충돌판정의 최적화

마지막은 게임에서 충돌검사를 실행할때 최적화를 하는 방법에 대한 설명이에요

여기서는 충돌판정 방법으로 GJK알고리즘을 사용하지만, 실제로 인게임에서 해당 알고리즘으로 모든 오브젝트와의 충돌을 검사할 필요는 없어요

위의 그림의 오른쪽에서 마름모 주위에 마름모를 포함하는 원을 그려놓은것처럼

각각의 오브젝트별로 오브젝트를 모두 포함하는 원으로 1차 충돌 영역을 설정해놓고

기본적인 오브젝트간의 충돌검사는 글의 맨 처음에서 설명한 원과 원(두 점 사이의 거리를 비교하는 방식)으로 

그렇게 설정해놓은 1차 충돌영역이 서로 충돌하는지를 검사하는거에요

만약 두 오브젝트의 1차 충돌 영역이 만나지 않는다면

두 오브젝트가 충돌하지 않는건 확실하니까

굳이 알고리즘을 사용해서 복잡한 충돌검사를 실행할 필요는 없어요

즉, 기본적인 거리비교로 오브젝트간의 1차 충돌영역의 충돌여부들만 판별하고

만약 두 오브젝트가 1차 충돌영역이 서로 충돌한다면, 그때에만 알고리즘을 사용해서 세부적인 충돌판정을 검사하면 되요

이렇게 하면 복잡한 충돌판정 알고리즘을 사용하면서도 연산량을 상당히 줄일수 있어요

그리고 이게 실제로 인게임에서 충돌판정 알고리즘을 적용한 영상이에요

이런식으로 하면 GJK충돌판정 알고리즘을 이용해서 다양한 도형간의 충돌판정을 구할수 있어요

[ㅇㅇ 1(175.192)]

선생님... 오늘 진도 거기 아닌데요? 너무 어려워요..

[익명(fujiwara1)]

우우 뜌땨아

[ㅇㅇ 2(125.132)]

rpg 쯔꾸르로만든 인갤겜 = 민코프스키 gjk 머시기로 다각형충돌 구현함 언리얼로 만든 내게임 = 구형충돌로 거리계산만함

[모가(sevyhong)]

저한테 왜 이러시는거죠? 이유가 있을꺼 아니예요?! 네?!

[ㅆㅇㅆ(124.216)]

와우

[MAYONEZU(organ2644)]

서..선생님 진도가 너무 빨라요

[흉황(smk4397)]

고봉밥추 - dc App

[ㅇㅇ 3(180.68)]

음 이해했어! (이해 못함)

[ㅇㅇ 4(211.226)]

흠.. 저도 동의합니다.

[로코복실한(dovecreative)]

오오 신기하다 자세한 원리는 이하 못했지만 에셋같은 거 있으면 커스텀 충돌 필요할 때 효과적으로 쓸 수 있을듯?

[ㅇㅇ 5(211.209)]

처음 보는 알고리즘인데 쏙쏙 들어온다! 너 되게 설명 잘하는구나ㅎㅎ 정성담긴 글 고마워, 잘 읽었어! 근데 읽으면서 의문이 들었던 부분이 있어서 질문 하나만 할게!

[ㅇㅇ 5(211.209)]

14번까지 진행하고 15번에서 남은 영역이 e, f, g라고 했는데 내가 이해하기로는 e, f영역의 윗 부분이 좀 더 지워져야 하는 것 같아서 질문해봐. (삼각형 g에서, 초록선의 대각인 점에서 초록선과 평행하게 그은 e, f의 윗부분, 대충 선 추가한 사진 링크야
https://ibb.co/vdWSmFB)

[익명(aa1604)]

해석기하추