[💬] 분리축(SAT)충돌검사를 사용해서 밀어내는 오브젝트 만들기

[vertex(4321vertex)]

분리축(SAT) 충돌검사를 사용해서 플레이어를 밀어내는 오브젝트를 만드는 방법에 대한 글이에요

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 볼록다각형

분리축 충돌검사는 두 볼록다각형의 충돌을 판정하는 방법이에요

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

2. 최소이동벡터(MTV, Minimum Translation Vector)

MTV란 두 도형이 충돌했을때, 도형을 서로 충돌하지 않는 상태로 밀어내기 위한 최소 거리의 벡터를 이야기하는거에요

아래의 그림의 두가지 벡터중 초록색 벡터가 최소이동벡터에 해당되요, 파랑색은 최소길이가 아니기 때문에 최소이동벡터가 아니에요

3. 분리축(SAT)충돌검사의 원리

위의 첫번째 그림은 사각형과 삼각형이 충돌한 상태이고, 두번째 그림은 사각형과 삼각형이 충돌하지 않은 상태에요

그리고 그림의 가장자리의 검은 선들은, 다각형의 각각의 모서리에서 수직인 벡터들이에요, 즉, 그림에서는 일부만 그려져있지만, 사각형4개 삼각형3개 해서 총 7개의 벡터가 있을수 있어요

그리고 가장자리의 벡터 위에 도형과 동일한 색으로 그려진 선들은, 해당 다각형을 그 벡터 위에 투영했을때의 영역을 표시한거에요

위의 그림을 보면, 첫번째 그림처럼 만약 두 도형이 충돌했다면, 두 도형의 각각의 가장자리에 수직인 모든(7개)의 벡터에서, 그림에 그려진것처럼 두 도형의 투영영역은 겹치게 되요

반대로 두번째 그림처럼 만약 두 도형이 충돌하지 않았다면, 모든(7개)의 벡터 중에서 그림에 나와있는것처럼 두 도형의 투영영역이 겹치지 않는 벡터가 있어요,

즉, 다각형의 각각의 가장자리에 수직인 모든 벡터별로, 각 벡터들마다 도형을 투영시켜서, 그 영역이 겹치는지 아닌지를 조사하면, 결국 두 도형이 충돌하지 않는지를 구할수 있어요,

만약 하나라도 투영영역이 겹치지 않는 벡터가 있다면, 두 도형은 충돌하지 않는 것이고, 모든 벡터에서 두 도형의 투영영역이 겹친다면 두 도형은 충돌하는거에요

그리고 이게 분리축(SAT)충돌검사의 원리에요

그리고 이때 앞에서 설명한 최소이동벡터(MTV)를 구하려면, 두 도형의 투영영역이 제일 적게 겹치는 벡터를 찾으면 되요,

그리고 그때 두 도형을 투영시킨 벡터의 방향으로, 두 도형의 투영영역이 겹치는 길이 만큼의 벡터가, MTV가 되는거에요

위의 그림에서 초록색으로 표시한 벡터가 두 도형의 충돌에서의 MTV에요

그리고 MTV의 방향을 결정하기 위해서는(위의 그림에서 삼각형을 사각형 밖으로 밀어낼지, 사각형을 삼각형 밖으로 밀어낼지)

두 투영영역중 어떤 선분을 고정시키고 밀어낼지에 따라 길이의 부호를 +혹은-로 하면 되요

위의 그림은 파랑색이 왼쪽, 주황색이 오른쪽인 상태에서, 파랑색을 주황색 밖으로 밀어내고자 해서

-길이가 나오게 되는거에요

4. 투영벡터의 길이 구하기

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

a벡터와 b벡터를 내적하면 되요, 단 이때 b벡터는 단위벡터(길이가 1인 벡터)여야 되요

그래야 두 벡터를 내적했을때 c벡터의 길이가 나와요, 이게 투영벡터의 길이를 구하는 방법이에요

5. 도형의 투영영역 구하기 : shape_project 함수

그리고 위의 투영벡터의 길이를 구하는 방법을 사용해서, 특정 도형을 특정 벡터에 투영했을때의 영역을 구할수 있어요

위의 그림에서 파랑색으로 표시된 부분, 즉 도형을 아래의 벡터에 투영했을때의 영역을 구하는거에요

최종적으로는 그림에서 min max라고 표시된 최소값과 최대값이 나오게 되요

도형의 각각의 꼭짓점을, 원점으로부터 해당 꼭짓점까지의 벡터로 여긴다음

앞의 투영벡터를 구하는 방법을 사용해서, 모든 꼭짓점(벡터)들을 아래의 벡터에 투영시켰을때의 길이를 구하고

그때의 최소값과 최대값을 구하면 되요,

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def shape_project(vx,vy,p)

len = Array.new

i = 0

until p[i] == nil

len.push(p[i][0]*vx+p[i][1]*vy)

i+=1

end

return len.min, len.max

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 위의 과정의 코드에요, ruby프로그래밍 언어로 작성된 코드에요

입력값에서 vx와 vy는 도형의 투영영역을 구하고자 하는 벡터에요, 단 이때 이 벡터는 단위벡터로 입력해야해요

그리고 p는 [[x1,y1],[x2,y2],[x3,y3]] 형태의 배열로 투영영역을 구하고자 하는 다각형의 각 꼭짓점의 좌표를 입력한거에요

그리고 그렇게 입력하면, 최종적으로 해당 도형을 해당 벡터에 투영했을때의 최소값과 최대값이 출력되요

6. 선분이 겹치는 영역 구하기 : line_overlap 함수

위에 올려놓은 그림은, 두 선분이 주어졌을때, 두 선분이 겹치는지를 체크하는 함수에요

두 선분(주황a 파랑b)의 최대값과 최소값(amn amx bmn bmx)이 주어졌을때, 두 선분이 겹치는지를 체크해서

만약 겹치지 않는다면 nil을 출력하고,

겹친다면, 그때의 길이를, 주황색 선분은 고정시킨채로 파랑색 선분을 주황색 선분 밖으로 밀어내기 위한 최소 이동길이로 출력해줘요

그림에서 왼쪽 위의 선분들을 보면 두 선분이 겹쳐있지 않아요, 이럴때는 nil을 출력해줘요

그리고 그림에서 왼쪽 아래는 두 선분이 일반적으로 겹쳐져있는 상태에요,

위쪽은 파랑색을 오른쪽으로 밀어내야 하기 때문에 + 방향의 길이로 출력되고

아래쪽은 파랑색을 왼쪽으로 밀어내야 하니까 -길이로 출력되요

그리고 그림의 오른쪽 부분들을 보면, 두 선분중 한쪽이 다른한쪽에 포함되어 있는 경우에요

이럴때는 파랑색을 어느쪽(오른쪽 또는 왼쪽)으로 밀어내야 더 이동거리가 적은지를 체크해서

해당 방향으로의 이동거리를 출력해줘요, 역시 파랑색 선분을 오른쪽으로 밀어내야 한다면 +를, 왼쪽이라면 -를 출력해줘요

그리고 이렇게 이동방향에 따라 이동거리의 부호를 + - 로 바꾸는 기능은

두 도형의 충돌에서 MTV의 방향을 구하기 위해 사용해요

두 도형의 투영영역이 겹치는 길이를 토대로 MTV를 구할때

어떤 도형을 고정시키고, 어떤 도형을 밀어낼지에 따라서, 고정시킬 선분과 이동시킬 선분을 구하면

그 길이를 기반으로 해서, 결국 원하는 도형을 밀어내기 위한 MTV를 구할수 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def line_overlap(amn,amx,bmn,bmx)

#1

if amx <= bmn || bmx <= amn

return nil

end

#2

if (amn <= bmn && bmx <= amx) || (bmn <= amn && amx <= bmx)

t1,t2 = amx-bmn, bmx-amn

if (t1).abs < (t2).abs

return t1

else

return -t2

end

end

#3

if amn <= bmn

return amx-bmn

end

if bmn <= amn

return (bmx-amn)*-1

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

이게 위의 함수의 코드에요, 입력값으로 두 선분의 최소값과 최대값을 입력하면, 두 선분이 겹치지 않는다면 nil을,

만약 겹친다면 b를 a밖으로 밀어내기 위한 최소길이를 출력해줘요, +방향으로 밀어내야 한다면 +길이를 출력해주고

-방향으로 밀어내야 최소거리라면 -길이를 출력해줘요

위의 함수의 코드에서 #1 부분은 겹치지 않는다면 nil을 출력해주는 부분이에요

#2 부분은 두 선분중 한쪽이 다른 한쪽에 완전히 포함되는 경우에요, 오른쪽(+방향) 왼쪽(-방향)중 더 거리의 절대값이 적은 방향의 이동거리를 출력해줘요

#3부분은 일반적으로 두 선분이 겹쳐있는 경우에요, a가 왼쪽이고 b가 오른쪽이면 +길이로

b가 왼쪽이고 a가 오른쪽이면 -길이로 출력해줘요

7. 두 다각형을 투영했을때 겹치는 부분 구하기 : sat1함수

그리고 앞의 두 함수를 사용해서, 최종적으로 두 다각형을 투영했을때 겹치는 부분을 구하는 함수를 만들수 있어요

위의 그림은 해당 함수의 그림이에요, 만약 첫번째처럼 두 도형의 투영영역이 겹치지 않는다면 nil을 출력하고

두번째처럼 두 도형의 투영영역이 겹친다면, 이때 파랑색(사각형)을 주황색(삼각형) 밖으로 밀어내기 위한 최소이동거리를 출력해줘요,

즉, 두번째 그림은 +거리가 나오고, 세번째 그림은 -거리가 나오게 되요

이렇게 이동시켜야할 방향에 따라 이동거리의 부호를 다르게 하면, 충돌시에 MTV를 구하는 과정에서 특정 도형을 고정시키고 특정 도형을 밀어내기 위한 최소이동벡터를 구할수 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def sat1(vx,vy,p1,p2)

amn, amx = shape_project(vx,vy,p1)

bmn, bmx = shape_project(vx,vy,p2)

return line_overlap(amn,amx,bmn,bmx)

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 위의 함수의 코드에요, vx와 vy는 투영영역이 겹치는지 확인하고자 하는 벡터를 단위벡터로 입력하면 되요

p1과 p2는 각각 [[x1,y1],[x2,y2],[x3,y3]] 형식으로 입력한 다각형이에요,

그리고 이때 두 도형이 해당 벡터에서 투영영역이 겹치지 않는다면 nil을, 겹친다면 p2를 p1밖으로 밀어내기 위한 최소이동거리를 출력해줘요,

즉 +방향으로 밀어내야한다면 +거리가 나오고, -방향으로 밀어내야한다면 -거리가 나오게 되요

8. 다각형의 꼭짓점을 벡터로 변환하기 : sort함수

위에 올려놓은 그림은, 그림에 표시된것처럼 다각형의 꼭짓점들이 있을때, 해당 꼭짓점들을 벡터로 변환시켜주는 함수에요,

그림처럼 5개의 꼭짓점이 주어져있다면, 1번-2번, 2번-3번, 3번-4번, 4번-5번, 5번-1번 이렇게 총 5개의 모서리(벡터)가 나오게 되요

그리고 이때 중요한건, 꼭짓점들이 순서대로 입력되야 해요, 시계방향이나 반시계방향은 상관없어요

이 함수는 SAT충돌검사에서, 다각형의 꼭짓점의 좌표들로부터 도형을 투영시킬 벡터를 구하기 위해서 사용하는 함수에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def sort(p)

a = Array.new

i = 0

until p[i] == nil

if p[i+1] == nil

x,y = p[0][0]-p[i][0],p[0][1]-p[i][1]

else

x,y = p[i+1][0]-p[i][0],p[i+1][1]-p[i][1]

end

a.push([x,y])

i += 1

end

return a

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

이게 위에 올려놓은 함수의 코드에요, 다각형의 각 꼭짓점들을 [[x1,y1],[x2,y2],[x3,y3]] 형식의 배열로 입력하면 되요, 이때 꼭짓점들을 순서대로 입력해야해요, 시계방향인지 반시계방향인지는 상관없어요

그리고 그 출력값도 동일한 형식의 배열로 나오게 되요 [[x2-x1,y2-y1],[x3-x2,y3-y2],[x1-x3,y1-y3]] 이런식으로요

9. SAT충돌검사의 작동방식

#1 과정은 앞에서 이야기한 sort함수로, 충돌검사를 하고자 하는 두 다각형의 모든 꼭짓점들로부터 벡터를 얻어요,

#2 과정은 그중 한가지의 벡터를 골라서, 해당 벡터에서 수직인 벡터를 구하고(벡터가 x,y라면 -y,x 또는 y,-x)

해당 벡터를 정규화해서 단위벡터로 만들어요, 두 벡터의 각 요소(x,y)를 해당 벡터의 길이로 나눠주면 되요

#3 과정은 앞에서 이야기한 sat1함수를 사용해서

그렇게 얻은 단위벡터에서의 두 다각형의 투영영역을 비교해요,

그렇게해서 만약 위의 그림처럼 두 다각형의 투영영역이 겹치지 않는다면,

두 다각형은 충돌하지 않았다고 판단하고 nil을 출력하고 함수를 종료해요

아래는 두 다각형의 투영영역이 겹치는 경우애요

#4 과정은 만약 두 다각형의 투영영역이 겹친다면, 이때의 투영영역을 체크하는 단위벡터와, 해당 단위벡터에서 겹치는 투영영역의 길이(방향에 따라서 + 또는 -)를 저장해놓고

다음 벡터를 골라서 #2 부터 다시 함수를 반복해요

그렇게 반복하면서 만약 두 도형의 투영영역이 겹치지 않는다면 충돌하지 않았다고 nil을 출력하고 함수를 종료하고

두 도형의 투영영역이 겹친다면, 기존에 저장해놓았던 투영영역과 비교해서, 더 절대값의 길이가 짧은쪽의 단위벡터와 겹치는 길이를 저장해요

그리고 이렇게 반복을 계속한다면

최종적으로는 두 도형이 충돌하지 않는다면, 충돌하지 않는 벡터를 찾아서 nil을 출력하고 함수가 도중에 종료되게 되고

만약 충돌한다면 모든 벡터를 끝까지 반복해서 제일 겹치는 거리가 작은 단위벡터와 그때의 겹치는 길이를 구할수 있어요

그리고 그렇게 두 도형이 충돌해서 제일 겹치는 거리가 작은 단위벡터와 길이를 구했다면,

그 단위벡터에 해당 길이를 곱해서 출력하고 함수를 종료해요, 이게 두 도형이 충돌했을때의 원하는 방향으로의 MTV가 되는거에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def sat_collision(p1,p2)

#1

a = Array.new

a = sort(p1)+sort(p2)

#2

d2 = nil

i = 0

until a[i] == nil

vx, vy = a[i][0], a[i][1]

vx, vy = -vy,vx

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

#3

d = sat1(vx,vy,p1,p2)

if d == nil

return nil,nil

end

#4

if d2 == nil || (d).abs < (d2).abs

vx2, vy2, d2 = vx, vy, d

end

i += 1

end

return vx2*d2, vy2*d2

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

이게 위의 함수의 코드에요,

초록색 #으로 주석을 표시해놓은 부분이 위에서 설명한 해당 과정이에요

p1과 p2로 충돌을 검사하고자 하는 두 다각형의 꼭짓점의 좌표를 [[x1,y1],[x2,y2],[x3,y3]] 형식의 배열로 입력하면 되요,

단 이때 꼭짓점들은 순서대로 입력해야되요, 시계방향인지 반시계방향인지는 상관없어요

그렇게하면 두 도형이 충돌하지 않는다면 nil을 출력하고

만약 충돌한다면, p2로 입력한 다각형을 p1 밖으로 밀어내기 위한 최소이동벡터(MTV)가 출력되요

그리고 이게 앞에서 설명한 SAT충돌검사를 사용해서 만든 플레이어를 밀어내는 오브젝트에요

영상의 첫번째와 네번째는, 오브젝트-플레이어 순서로 충돌체크를 해서, 만약 플레이어와 오브젝트가 충돌한다면 플레이어를 오브젝트 밖으로 밀어내기 위한 MTV를 구한다음, 플레이어를 해당 벡터만큼 밀어내는 방식이에요

그리고 두번째와 세번째는 플레이어-오브젝트 순서로 충돌체크를 해서, 만약 충돌한다면 오브젝트를 플레이어 밖으로 밀어내기 위한 MTV를 구하고 오브젝트를 해당 벡터만큼 밀어내는 방식이에요

이렇게하면 분리축(SAT)충돌검사를 사용해서 플레이어를 밀어내는 오브젝트를 만들수 있어요

[소닉쫄따구테일즈(dcz3xv7zgu14)]

좋은설명 감사. 그럼 mtv구하는 순서가 플레이어 오브젝트 순이 되면 오브젝트가 밀려난다는거지? 그럼 저 회전하는 바가 밀려난다는건데. 그럼 안되지 않나. 그 부분은 어떻게 해소하면 좋음? 보통 물리엔진은 질량계산해서 양쪽다밀어내거나 kinematics나 static인 애들은 안밀리게하거나 그런거같던디

[ㅇㅇ 1(211.200)]

겹친 다음 서로 밀어냄

[소닉쫄따구테일즈(dcz3xv7zgu14)]