[💬] GJK-EPA 알고리즘으로 플레이어를 밀어내는 오브젝트 만들기

[vertex(4321vertex)]

GJK-EPA 알고리즘을 이용해서 플레이어를 밀어내는 오브젝트를 만드는 방법에 대한 글이에요

그리고 저도 수학이나 프로그래밍을 잘 아는게 아니고 제가 이해한 범위 안에서 쓰는 내용이라 틀리거나 정확하지 않은 내용이 있을수도 있어요

그리고 이 글은 위에 올려놓은 1편(GJK알고리즘)에서 이어지는 내용이에요

1. 충돌벡터

오브젝트의 충돌감지에는 크게 두가지가 있어요

첫번째는 단순히 on off 방식으로 충돌을 했는지 안했는지를 감지하는거에요

그리고 두번째는 만약 두 오브젝트가 충돌했다면 그때의 충돌벡터를 결과값으로 출력해주는거에요

위의 그림의 왼쪽에서 파랑색으로 표시해놓은 화살표가 충돌벡터에요,

위의 왼쪽 그림처럼 만약 사각형과 삼각형이 충돌했다면,

이때 두 오브젝트가 충돌하지 않도록, 즉 오른쪽처럼 서로 겉면이 만나도록 밀어내기 위한 최소 거리의 벡터가 바로 충돌벡터에요

그리고 충돌벡터는 항상 두 오브젝트가 서로 충돌하지 않는 지점까지 밀어내기 위한 최소 거리의 벡터, 즉 제일 짧은 벡터를 이야기해요

위의 그림에서 첫번째처럼 사각형과 삼각형이 충돌했을때, 충돌벡터는 두번째처럼 파랑색이 아니라, 세번째처럼 초록색이에요

2. GJK-EPA 알고리즘의 원리

GJK-EPA 알고리즘은 1편에서 이야기한 GJK알고리즘에서 이어지는 알고리즘이에요

GJK알고리즘이 단순히 두 다각형이 on off로 충돌했는지 안했는지만을 출력했다면

GJK-EPA 알고리즘은 두 다각형이 충돌했는지 안했는지와 함께, 만약 두 다각형이 충돌했다면 그때의 충돌벡터 또한 출력해주는 알고리즘이에요

위의 그림은 1편에서 설명했던 내용이에요

위의 첫번째 그림에서 나와있는것처럼 만약 두 다각형이 충돌했다면

그때 원점은 두 다각형의 민코스프키 차이 내부에 있고

만약 두 다각형이 충돌하지 않았다면, 그때의 원점은 민코스프키 차이의 외부에 있어요

그리고 위에 나와있는것처럼

만약 두 다각형이 서로 가장자리에서 만난다면

그때의 원점은 민코스프키 차이의 가장자리에 있어요

즉, 두 다각형이 충돌했을때 충돌벡터를 구하려면

두 다각형의 민코스프키 차이 내부에 있는 원점을, 민코스프키 차이의 가장자리까지 옮기기 위한 최소거리(제일 길이가 짧은 벡터)를 구하면 되요

그리고 이렇게 두 다각형의 민코스프키 차이에서, 그 내부에 있는 원점을 가장자리로 옮기기 위한 최소 벡터를 구하는게 바로 GJK-EPA알고리즘의 원리에요

위의 경우에 오른쪽의 다각형은 사각형에서 삼각형을 뺐을때의 민코스프키 차이로 얻어진 다각형이에요, 

즉, 이때의 충돌벡터는, 삼각형을 사각형 밖으로 밀어내기 위한 방향의 벡터에요

반대로 위의 그림처럼 삼각형에서 사각형을 뺀 민코스프키 차이에서 충돌벡터를 구하면

이때 나오는 충돌벡터는 사각형을 삼각형 밖으로 밀어내기 위한 충돌벡터가 나와요

위에 올려놓은 그림이 벡터의 뺄셈의 방향이에요

만약 a벡터에서 b벡터를 뺐다면 위의 그림처럼 b에서 a로 향하는 방향의 벡터가 나와요

즉, 사각형에서 삼각형을 뺀 민코스프키 차이는, 결국 삼각형에서 사각형으로 향하는 벡터들의 집합이니까

이때 나오는 충돌벡터는 삼각형을 사각형 밖으로 이동시키기 위한 벡터가 되는거에요, 

그리고 만약 반대로 삼각형에서 사각형을 뺀 민코스프키 차이라면, 사각형을 삼각형 밖으로 이동시키기 위한 벡터가 나오게 되는거고여

3. 점과 직선 사이의 거리 구하기

다음은 GJK-EPA알고리즘 내부에서 사용되는 함수인

점과 직선과의 거리를 구하는 함수에 대한 설명이에요

첫번째로 위의 그림은 투영벡터의 길이를 구하는 공식이에요

위의 그림에서 a벡터를 b벡터가 있는 방향으로 투영시킨 c벡터의 길이를 구하려면

a벡터를 b벡터와 내적하면 되요, 그러면 c벡터의 길이를 구할수 있어요

그리고 이때 b벡터는 단위벡터(길이가 1인 벡터)여야되요 그래야 두 벡터를 내적했을때 c벡터의 길이가 나와요

그리고 위의 그림이 앞에서 설명한 투영벡터의 길이를 구하는 공식을 사용해서, 점과 직선의 거리를 구하는거에요

위의 그림처럼 a라는 직선과 파랑색 점 사이의 길이인 초록색 c의 길이를 구하려면, 

이때 a직선에서 파랑색 점이 있는 방향으로의 수직벡터(이건 1편에서 설명한 vector_direct함수로 구할수 있어요) 를

정규화(벡터를 길이가 1인 단위벡터로 만드는 과정)한 다음, 그렇게 얻어진 주황색 벡터와

a직선의 한 점에서 파랑색 점까지의 벡터인 b를 내적하면 되요,

그러면 최종적으로 c벡터의 길이를 얻을수 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡ

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

ㅡㅡㅡㅡㅡㅡㅡㅡ

ㅡㅡㅡㅡㅡㅡㅡㅡ

def line_dist(x1,y1,x2,y2)

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

vx, vy = vx/((vx**2+vy**2)**0.5), vy/((vx**2+vy**2)**0.5) 

return vx, vy, x2*vx+y2*vy

end

ㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 위에 올려놓은 두번째 함수가, 이렇게 점과 직선의 거리를 구하는 함수에요, ruby프로그래밍 언어로 작성한거에요,

첫번째 함수는 1편에서 설명했던 수직벡터를 구하는 함수에요

두번째 함수는 위의 그림처럼 벡터 x1,y1과 x2,y2가 있을때 파랑색 벡터를 구해주는 함수에요

우선 첫번째 함수를 사용해서 x1 y1의 x2 y2방향의 수직벡터를 구한다음

그렇게 얻어진 수직벡터를 정규화해서 단위벡터로 만들고

그렇게 얻어진 단위벡터를 x2 y2와 내적해서 파랑색 벡터의 길이를 구해요

그렇게해서 최종적으로는 얻어진 파랑색 벡터의 길이와, 앞서 구해놓은 단위벡터를 함께 출력해주는 함수에요

4. 삼각형의 무게중심 구하기

삼각형의 무게중심도 GJK-EPA알고리즘에서 사용되는 공식이에요,

그리고 삼각형의 무게중심은 위의 그림처럼 구할수 있어요, x y 각각 좌표를 더한다음 3으로 나눠주면 되요

5. GJK-EPA알고리즘의 작동방식

GJK-EPA알고리즘은 1편에서 설명한 GJK알고리즘에서 이어지는 알고리즘이에요

GJK알고리즘에서는, 만약 원점이 삼각형의 내부에 있다면 두 다각형은 충돌했다고 판정하고 함수를 종료해요

그리고 GJK-EPA알고리즘은 이때, 즉 원점이 삼각형 내부에 있을때

함수를 종료하지 않고, 원점으로부터 민코스프키 다각형의 가장자리까지의 최소벡터를 찾아서 출력해주는 거에요

위의 그림이 GJK-EPA알고리즘이 작동하는 순서에요

첫번째 그림이 원점이 삼각형 내부에 있다고 판정한 지점이에요, 즉 GJK알고리즘이 두 다각형이 충돌했다고 출력하고 함수를 종료하는 지점이에요

그리고 두번째 그림은 이때에 원점으로부터 삼각형의 각각의 가장자리까지의 거리를 구하는거에요, 앞에서 이야기한 점과 직선의 거리를 구하는 함수로 구할수 있어요

그리고 세번째는 이때 제일 거리가 짧은 직선(거리가 주황색으로 표시된 직선)에서 삼각형 외부로의 수직방향으로(초록색 벡터) 새로운 민코스프키 차이의 가장자리의 support point를 찾는거에요 이때 얻어진 새로운 support point는 빨강색으로 표시했어요

삼각형 외부로의 수직방향을 찾으려면, vector_dorect함수로 앞에서 이야기한 삼각형의 무게중심에 반대되는 방향의 수직벡터를 찾으면 되요

그리고 해당 방향으로의 민코스프키 차이 다각형의 support poinjt를 찾으려면 역시 1편에서 이야기한 mink_dif함수를 사용하면 되요

네번째 그림은 그렇게 새로운 민코스프키 차이의 support point를 찾은다음, 해당 방향의 삼각형의 모서리를 제거하고, 모서리의 양 꼭짓점에서 새로 찾은 support point와 이어지는 두개의 모서리를 추가한거에요, 즉 삼각형이 사각형이 된 모습이에요

그리고 다섯번째 그림은 다시 이 사각형의 4개의 모서리와 원점간의 거리를 측정해서 제일 거리가 짧은 모서리를 구하는거에요, 역시 앞에서 설명한 직선과 점과의 거리를 구하는 함수를 사용해요

그리고 여섯번째는 이렇게 찾아진 제일 거리가 짧은 모서리(거리가 주황색으로 표시된 모서리)에서 역시 다각형 외부로 수직인 방향으로 새로운 민코스프키 차이의 support point를 찾는거에요,

다각형 외부의 방향으로의 수직벡터를 구하려면 맨 처음에 구해놓은 삼각형의 무게중심에서 반대방향으로 수직벡터를 찾으면 되요

그리고 이때 찾아진 새로운 supprot poin는 기존의 모서리를 구성하는 점들중 하나에 포함되니까(빨강색으로 표시한 지점), 결국 현재의 모서리가 민코스프키 차이로 얻어진 다각형의 가장자리 라는게 되고

따라서 원점에서 현재 직선까지의 벡터가 충돌벡터가 되니까, 해당 벡터를 출력하고 알고리즘을 종료하는거에요

위의 그림은 GJK-EPA 알고리즘이 진행될수 있는 또다른 경우에요, 

위의 그림에서처럼 처음에 최소거리라고 판정되지 않았던 직선이 알고리즘을 진행하면서 최소거리 직선으로 판정될수도 있어요,

아니면 앞의 과정들처럼 사각형까지 확장하지 않고 삼각형 단계에서 종료되거나, 아니면 더 많은 모서리를 가진 다각형까지 확장될수도 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

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

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

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

def gjk_epa_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 nil, nil

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 nil, nil

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

p3 = Array.new

p3.push([x1,y1,x2,y2])

p3.push([x2,y2,x3,y3])

p3.push([x3,y3,x1,y1])

cx, cy = (x1+x2+x3)/3,(y1+y2+y3)/3

return epa(p3,p1,p2,cx,cy)

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위에 올려놓은 코드는 1편에서 설명한 GJK알고리즘의 코드에요,

그리고 위의 코드에서 GJK-EPA알고리즘으로 확장하면서 수정된 부분을 파랑색으로 표시해 놓았어요

코드를 보면 우선 함수의 이름이 달라졌고 

함수의 출력에서 충돌하지 않았을때 0 대신 nil을 출력하도록 변경했고

충돌했을때 1을 출력하는 대신 epa알고리즘을 진행해서 충돌벡터를 출력하도록 변경했어요

위의 함수에서 epa알고리즘을 진행하는 부분을 보면

삼각형의 모서리를 [ [x1,y1,x2,y2], [x2,y2,x3,y3], [x3,y3,x1,y1] ] 형식으로 ruby언어의 배열로 만들고

삼각형의 무게중심을 cx cy 로 구한다음

해당 값을 기반으로 epa 알고리즘을 진행해요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def line_dist(x1,y1,x2,y2)

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

vx, vy = vx/((vx**2+vy**2)**0.5), vy/((vx**2+vy**2)**0.5) 

return vx, vy, x2*vx+y2*vy

end

def side_line(p)

d = nil

i = 0

until p[i] == nil

vx2, vy2 ,d2 = line_dist(p[i][2]-p[i][0],p[i][3]-p[i][1],0-p[i][0],0-p[i][1])

if d == nil || d2 < d

pi, vx, vy, d = i, vx2, vy2, d2

end

i+=1

end

return pi, -vx*d, -vy*d

end 

def epa(p3,p1,p2,cx,cy)

while 1 == 1

pi,x,y = side_line(p3)

vx, vy = vector_direct(p3[pi][2]-p3[pi][0],p3[pi][3]-p3[pi][1],cx-p3[pi][0],cy-p3[pi][1])

mx, my = mink_dif(-vx,-vy,p1,p2)

if ( mx == p3[pi][0] && my == p3[pi][1] ) || ( mx == p3[pi][2] && my == p3[pi][3] )

return x,y

end

p3.push([mx,my,p3[pi][0],p3[pi][1]])

p3.push([mx,my,p3[pi][2],p3[pi][3]])

p3.delete_at(pi)

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위에 올려놓은 코드는 epa알고리즘에서 사용되는 코드에요

첫번째 함수는 앞에서 설명한 점과 직선과의 거리를 구하는 함수에요

그리고 두번째 함수는 위의 GJK-EPA알고리즘의 진행방식에서

원점과 다각형의 각각의 모서리까지의 거리를 비교해서 제일 작은걸 찾는 함수에요

 [ [x1,y1,x2,y2], [x2,y2,x3,y3], [x3,y3,x1,y1] ] 형식의 배열로 모서리들이 주어진 다각형이 있을때

첫번째 함수를 이용해서 모든 모서리와 길이를 비교한다음, 제일 길이가 작은 모서리의 인덱스, 그리고 그때의 원점에서 모서리까지의 벡터를 출력해요

여기서는 원점에서 다각형의 가장자리를 향하는 방향의 벡터로 출력해요, 즉 첫번째 line_dist함수에서 나온것과는 방향이 반대되는 벡터에요

그리고 세번째는 epa알고리즘의 함수에요

1편에서 설명한 충돌을 감지하는 처음 다각형들의 배열인 p1과 p2

그리고 앞에서 설명한것처럼 [ [x1,y1,x2,y2], [x2,y2,x3,y3], [x3,y3,x1,y1] ] 형식의 원점이 포함된 삼각형의 배열인 p3과

처음 삼각형의 무게중심인 cx와 cy를 입력값으로 받아요

그렇게해서 우선 위의 두번째 함수로 p3, 즉 삼각형에서 원점과 가장 거리가 가까운 모서리와, 원점에서 해당 모서리까지의 벡터를 구하고

해당 모서리에서 삼각형의 무게중심에 반대되는 방향의 수직벡터를 구해서

해당 방향의 민코스프키 차이 다각형의 support point를 구한다음

그렇게 구한 점이 해당 모서리의 두 꼭짓점과 같은 점인지를 비교해요

그렇게해서 만약 같은 점이라면, 그때의 원점에서 모서리까지의 벡터를 출력한다음 종료하고

아니라면 해당 모서리의 양 꼭짓점에서 새로 구한 민코스프키 차이 다각형의 support point까지의 두개의 모서리를 p3에 추가한다음

원래의 모서리를 p3에서 제거해서

다시 세번째 함수를 처음부터, 즉 원점과 제일 가까운 모서리를 찾고 그때의 원점에서 해당 모서리까지의 벡터를 구하는 부분부터 반복하는거에요

이렇게 하면 최종적으로 원점과 거리가 제일 짧으면서 민코스프키 차이의 가장자리에 있는 모서리를 찾을수 있고

원점으로부터 해당 모서리까지의 벡터인 충돌벡터를 구해서 출력할수 있어요

 

위에 올려놓은 영상은 앞에서 설명한 GJK-EPA알고리즘을 이용해서 만든 플레이어를 밀어내는 오브젝트의 영상이에요

영상에서 파랑색 사각형이 방향키로 움직이는 사각형이에요

영상의 첫번째와 네번째는 오브젝트가 플레이어를 밀어내는 방식이에요,

즉, 맨 처음에 충돌벡터의 방향 부분에서 설명한것처럼 오브젝트의 다각형에서 플레이어의 다각형을 빼는 방식으로 민코스프키 차이의 충돌벡터를 구한다음

충돌시에 플레이어를 해당 벡터만큼 이동시켜주면 되요

그리고 두번째와 세번째는 플레이어가 오브젝트를 밀어내는 방식이에요

이건 반대로 플레이어의 다각형에서 오브젝트르 빼는 방식으로 민코스프키 차이 다각형의 충돌벡터를 구해서

오브젝트를 해당 벡터만큼 이동시켜주면 되요

그리고 이렇게하면 GJK-EPA알고리즘을 이용해서 플레이어를 밀어내는 오브젝트를 만들수 있어요

[ㅇㅇ 1(125.132)]

진짜 너무 좋은글입니다

[ㅇㅇ 1(125.132)]

혹시 블로그같은건 안하시나요 좋은 자료들은 링크를 모아놓고 있는데 디씨 게시물들은 나중에보면 짤이 없어지거나 하는 일도 좀 있어서.

[익명(125.130)]

와 이런거 알아야 개발할수있는거구나... 나 바로포기해야하는거야...?ㅠ

[디붕쿤(divide6198)]

[디붕쿤(divide6198)]

GJK-EPA알고리즘을 이용한 오브젝트 밀어내기..와드..

[태보미(taebomi)]

컴퓨터대단해..