[💬] OBB충돌검사를 사용해서 밀어내는 오브젝트 만들기

[vertex(4321vertex)]

OBB 충돌검사를 사용해서 플레이어를 밀어내는 오브젝트를 만드는 방법에 대한 글이에요,

그리고 저도 수학이랑 프로그래밍을 잘 아는게 아니고 제가 이해한 범위 안에서 쓰는 글이라 틀리거나 잘못된 내용이 있을수도 있어요

그리고 이 글은 위에 올려놓은 시리즈에서 분리축(SAT)충돌검사에서 이어지는 내용의 글이에요,

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. OBB충돌검사의 원리

OBB충돌검사는 분리축(SAT)충돌검사를 두 직사각형의 충돌의 경우로 단순화시켜 놓은 충돌검사에요

이때 두 직사각형은 기울어져 있어도 상관없어요, 

SAT충돌검사는 원래 각 다각형의 모든 모서리에 수직인 벡터에 대해서 도형의 투영영역을 체크했지만

충돌하는 다각형을 두 직사각형으로 제한하면, 사각형은 두 모서리가 평행해서, 결국 위에 올려놓은 그림처럼 평행한 한 쌍의 모서리에 수직인 벡터는 동일하니까

도형의 투영영역을 체크해야 하는 벡터를 총 4개(한 사각형에 2개씩)으로 단순화시킬수 있어요,

그리고 OBB충돌체크에서는, SAT의 경우와 다르게 사각형을 각 꼭짓점의 좌표가 아니라, 중심점의 좌표와, 중심점에서 서로 수직인 2개의 모서리까지의 벡터 2개로(위의 그림에서 파랑색과 주황색 벡터) 저장해놓아요

그리고 이때 두 벡터는, 결국 서로가 서로에 대해서 수직인 벡터니까, 분리축(SAT)충돌검사에서 처럼 따로 꼭짓점의 좌표를 통해서 벡터를 만들지 않고

이 두 벡터를 그대로 가져와서 도형의 투영영역을 검사할 벡터로 사용할수 있어요

그리고 이때 두 도형의 투영영역이 겹치는지를 체크하는 방법도

SAT충돌검사에서처럼 도형의 전체 투영영역을 체크하지 않고

각각의 사각형들의 중심점에서부터, 한쪽 가장자리까지를 투영시킨 길이와

두 사각형의 중심점을 이어서 만든 벡터를 투영시킨 길이를 비교하는걸로 단순화 시킬수 있어요

위의 그림에서 파랑색과 주황색이 각각의 사각형의 중심점부터 한쪽 가장자리까지를 아래의 벡터에 투영시킨 길이에요

그리고 보라색이 두 사각형의 중심점을 이은 벡터를 아래에 투영시킨 길이에요

그리고 첫번째 그림처럼 보라색 길이가 파랑색과 주황색 길이의 합보다 크면, 두 사각형은 충돌하지 않은거에요, 즉 투영영역이 겹치지 않은거에요

그리고 두번째 그림처럼, 보라색 길이가 파랑색과 주황색 길이의 합보다 작으면, 두 사각형은 충돌한거에요, 즉 투영영역이 겹치는거에요

OBB충돌검사에서는 사각형을 중심점의 좌표와, 중심점에서 사각형의 서로 수직인 모서리까지의 2개의 벡터로 저장해요, 위의 그림에서 파랑색과 주황색 벡터에요

그리고 여기서 사각형의 중심점으로부터 한쪽 가장자리까지를 투영한 길이는, 이 두개의 벡터를 아래의 벡터에 투영한 길이의 합으로 구할수 있어요

위의 그림에서 보라색 벡터를 투영한 길이는, 주황색 벡터를 투영시킨 길이와 똑같아요,

그리고 파랑색과 보라색 벡터를 투영한 길이를 합하면, 사각형의 중심점에서 한쪽 가장자리까지를 투영시킨 길이인 초록색 길이가 나와요

그리고 사각형의 두 중심점을 이은 벡터를 투영한 길이는 위의 그림에 나와있는것처럼, 사각형의 두 중심점중 하나를 다른 하나에서 빼서, 두 중심점을 이어주는 벡터를 얻은다음 그 벡터를 아래의 벡터에 투영시켜서 얻을수 있어요, 

2. OBB충돌검사에서의 최소이동벡터(MTV)

OBB충돌검사에서 MTV를 구하기 위해서는, 첫번째로 두 사각형을 투영하는 벡터의 방향을 원하는 방향으로 설정해야해요,

우선 두 사각형의 중심점을 이어주는 벡터를 얻을때, 원하는 방향이 되도록 벡터를 구해요, 여기서는 파랑색 사각형을 주황색 사각형 밖으로 밀어내는 방향의 MTV를 얻기 위해서, 주황색 사각형의 중심점에서 파랑색 사각형의 중심점으로 향하는 방향으로 벡터를 구했어요, 즉 파랑 사각형의 중심점에서 주황 사각형의 중심점을 빼는 방향이에요

그리고 아래의 검정색 벡터, 즉 두 사각형을 투영하는 벡터와 이렇게 얻어진 벡터를 내적해서 방향을 비교한다음, 만약 아래의 벡터의 방향이 위에서 얻은 벡터(초록색)와 방향이 반대라면

아래의 검정색 벡터의 방향을 반대방향으로(x,y라면 -x,-y)바꿔줘요, 이렇게하면 두 사각형을 투영하는 벡터를 원하는 방향으로 설정할수 있어요

위의 그림은 두 벡터의 내적값을 통해서 두 벡터의 방향을 비교하는 그림이에요, 두 벡터를 내적한 값이 0보다 작으면 두 벡터가 서로 반대방향이라는 뜻이에요, 즉 내적값이 0보다 작게 나오면, 해당 벡터의 x,y부호를 바꿔서 반대 방향의 벡터로 만들어주면 되요

그리고 OBB충돌검사에서 최소이동벡터의 길이를 구하기 위해서는, 만약 두 사각형의 투영영역이 겹칠경우, 즉 중심점을 이은 길이가, 양 사각형의 중심점부터 한쪽 가장자리까지의 길이를 합한 길이보다 작을경우에,

두 사각형의 중심점부터 한쪽 가장자리까지의 길이(위의 그림에서 주황색과 파랑색)를 합한 값에서 두 사각형의 중심점 사이의 길이(위의 그림에서 보라색)을 빼면 되요

그러면 두 사각형의 투영영역이 겹치는 길이, 즉 주황색과 파랑색이 겹치는 길이가 나와요, 이게 두 사각형이 충돌했을때의 MTV의 길이에요

즉, 이렇게 구한 투영영역이 겹치는 길이가 제일 작은 때에, 그때 두 사각형을 투영한 벡터(앞에서 설명한대로 원하는 방향으로 설정된 벡터에요)의 방향으로의 해당 길이만큼의 벡터가 두 사각형이 충돌했을때의 MTV가 되는거에요

3. 주어진 벡터에서 두 사각형의 충돌여부 체크하기 : obb1함수

여기서부터는 OBB충돌체크에서, 한 벡터를 기준으로 해서 두 사각형의 충돌여부를 체크하는 과정에 대한 설명이에요

그리고 최종적으로는 이러한 체크를 한 사각형에 2개씩 총 4번 반복하게 되요

#1 과정은 주어진 벡터를 단위벡터로 정규화한 다음에, 해당 벡터의 방향이 구하고자 하는 MTV의 방향(파랑색 사각형을 주황색 사각형 밖으로 밀어내는 방향)과 같은지 체크하는거에요,

그리고 만약 그렇지 않다면 해당 벡터의 방향을 정 반대로 바꿔줘요

#2과정에서는 그렇게 정규화한 단위벡터에 두 사각형의 중심점을 이어주는 벡터를 투영해서 그 절대값인 첫번째 길이를 얻고

총 4개의 각 사각형을 저장했을때의 벡터(중심점에서 서로 수직인 두 모서리까지의 벡터)를 각각 투영해서 그 절대값을 구한다음

그렇게 얻어진 4개의 절대값을 모두 합쳐서 두번째 길이를 얻어요

#3 과정은, 이때 첫번째 길이가 두번째 길이보다 크다면, 즉 중심점 사이의 투영길이가, 각 사각형의 중심점에서 한쪽 가장자리까지의 투영길이를 합한 값보다 길다면

두 사각형은 충돌하지 않았다는거니까 nil을 출력하고 함수를 종료해요

#4 과정은, 이때 만약 첫번째 길이가 두번째 길이보다 짧다면

두 사각형은 충돌했다는거니까, 그때의 두 사각형을 투영한 벡터와, 두 길이가 겹치는 값(두번째 길이에서 첫번째 길이를 뺀 값)을 출력하고 함수를 종료해요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def obb1(vx,vy,p1,p2)

cx1,cy1,x1,y1,x2,y2,cx2,cy2,x3,y3,x4,y4 = p1[0],p1[1],p1[2],p1[3],p1[4],p1[5],p2[0],p2[1],p2[2],p2[3],p2[4],p2[5]

#1

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

if (cx2-cx1)*vx+(cy2-cy1)*vy < 0

vx, vy = -vx, -vy

end

#2

d1 = ((cx2-cx1)*vx+(cy2-cy1)*vy).abs

d2 = (x1*vx+y1*vy).abs+(x2*vx+y2*vy).abs+(x3*vx+y3*vy).abs+(x4*vx+y4*vy).abs

#3

if d1 >= d2

return nil, nil, nil

end

#4

if d1 < d2

return vx, vy, d2-d1

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 위의 함수의 코드에요, ruby프로그래밍 언어로 작성한거에요 초록색 #로 입력해놓은 주석이 위의 설명에서 해당하는 과정이에요

p1과 p2는 [cx,cy,x1,y1,x2,y2] 형식의 배열로 사각형을 입력한거에요 cx, cy가 중심점의 좌표고, x1,y1 x2,y2가 중심점으로부터 서로 수직인 사각형의 각 모서리까지의 벡터에요

그리고 입력값의 vx, vy는 충돌을 검사하고자 하는 벡터에요,

이렇게 입력하면, 만약 해당 벡터에서 두 사각형이 충돌하지 않았다면 nil이 출력되고,

만약 충돌했다면, p1에서 p2로 향하는 방향으로 해당 벡터를 정규화한 단위벡터와, 그때의 두 도형의 투영영역이 겹치는 길이가 출력되요,

4. OBB충돌체크의 작동과정

여기서부터는 방금 설명한 함수를 사용해서, 실제로 OBB충돌체크를 진행하는 과정에 대한 설명이에요

#1과정은 입력된 두 사각형으로부터 사각형의 투영영역이 겹치는지 체크할 4개의 벡터를 얻어요,

그리고 #2 과정은 그중 한가지 벡터에 대해서, 앞에서 설명한 obb1함수로 두 사각형의 투영영역이 겹치는지를 체크해요

#3 과정은 만약 이때 두 사각형의 투영영역이 위의 그림처럼 겹치지 않는다면,

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

#4 과정은 이때 만약 두 사각형의 투영영역이 겹친다면

두 사각형이 충돌한다고 판정하고, 이때의 두 사각형의 투영영역이 겹치는 길이와 해당 벡터를 저장해놓아요

그리고 다음 벡터를 골라서 다시 #2 과정부터 함수를 반복해요

함수를 반복하면서 만약 두 사각형의 투영영역이 겹치지 않는다면 두 사각형은 충돌하지 않았다고 판정하고 함수를 종료하고

두 사각형의 투영영역이 겹친다면, 그 값을 기존에 저장했던 값과 비교해서, 더 값이 작은 길이와 그때의 벡터를 저장해요

그리고 이런식으로 함수를 반복하면, 만약 두 사각형이 충돌하지 않는다면 두 사각형의 투영영역이 겹치지 않는 벡터를 찾아서 도중에 함수가 종료되고

두 사각형이 충돌한다면, 최종적으로 두 사각형의 투영영역이 겹치는 길이가 제일 작은 단위벡터와, 그때의 두 사각형의 투영영역이 겹치는 길이를 얻을수 있어요

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

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def obb_collision(p1,p2)

cx1,cy1,x1,y1,x2,y2,cx2,cy2,x3,y3,x4,y4 = p1[0],p1[1],p1[2],p1[3],p1[4],p1[5],p2[0],p2[1],p2[2],p2[3],p2[4],p2[5]

#1

a = Array.new

a.push([x1,y1])

a.push([x2,y2])

a.push([x3,y3])

a.push([x4,y4])

#2

d2 = nil

i = 0

until a[i] == nil

x, y = a[i][0],a[i][1]

vx, vy, d = obb1(x,y,p1,p2)

#3

if d == nil

return nil, nil

end

#4

if d2 == nil || d < d2

vx2, vy2, d2 = vx, vy, d

end

i+=1

end

return vx2*d2, vy2*d2

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 위의 함수의 코드에요, 초록색 #로 달아놓은 주석이 해당 과정의 설명이에요

입력값의 p1과 p2는 앞에서 설명한대로 [cx,cy,x1,y1,x2,y2] 형식의 배열로 입력한 두 사각형이에요,

그리고 그렇게 입력하면 최종적으로 두 사각형이 충돌하지 않는다면 nil이 출력되고

만약 충돌한다면, p2를 p1밖으로 밀어내는 방향으로의 최소이동벡터(MTV)가 출력되요

그리고 이게 위에서 설명한 OBB충돌체크를 이용해서 플레이어를 밀어내는 오브젝트를 만든거에요, 파랑색 사각형이 방향키로 움직이는 플레이어에요

영상의 첫번째와 두번째는, 오브젝트-플레이어 순서로 충돌체크를 해서, 플레이어를 오브젝트 밖으로 밀어내는 방향의 MTV를 구해서 충돌했을때 플레이어를 해당 벡터만큼 이동시키는거에요

그리고 세번째와 네번째는, 플레이어-오브젝트 순서로 충돌체크를 해서, 오브젝트를 플레이어 밖으로 밀어내는 방향의 MTV를 구한다음, 충돌했을때 오브젝트를 해당 벡터만큼 밀어내는거에요

이렇게 하면 OBB충돌체크로 플레이어를 밀어내는 오브젝트를 만들수 있어요,

[ㅇㅇ 1(125.132)]

매번 감사합니다

[로코복실한(dovecreative)]

초고수