[💬] 원과 다각형의 충돌체크

[vertex(4321vertex)]

원과 다각형의 충돌체크를 하는 방법에 대한 글이에요

그리고 저도 잘 아는게 아니고 제가 이해한 범위 안에서 쓰는거라 틀린 내용이 있을수도 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. 원과 다각형의 충돌의 종류

위에 올려놓은 그림은 원과 다각형이 충돌하는 경우에 대한 그림이에요

그리고 그림에서 나와있는것처럼 원과 다각형이 충돌할때의 경우는 두가지가 있어요

1. 겹침은 다각형을 이루고 있는 선분중에서 원과 겹치는 선분이 있는 경우에요

2. 포함은 원이 다각형 내부에 완전히 포함되어 있는 경우에요

https://gall.dcinside.com/m/game_dev/166039

점이 다각형에 포함되는지 구하기

그리고 이중 2. 포함의 경우에는, 원의 중심점이 다각형 내부에 포함되어 있는지를 구하는 방법으로 체크할수 있어요

원의 중심점이 다각형 내부에 포함되어 있는 경우라면 원은 다각형과 충돌하고 있다고 판정하는 거에요

그리고 이때 이용하는 함수는 위에 올려놓은 글의 4번에서 설명한 함수에요

2. 점과 선분의 길이 구하기

그리고 이제부터 설명할 내용은 1. 겹침의 경우를 구하는 방법이에요, 즉 다각형의 선분이 원과 겹치는지를 체크하는 방법이에요

그리고 그러기 위해서 점과 선분의 길이를 구하는 방법을 활용해요, 원의 중심점을 점으로 놓은 다음 구하고자 하는 선분과의 길이를 구하는 거에요

그리고 이때 그 점과 선분의 길이가 원의 반지름보다 작다면, 해당 선분이 원과 겹쳐져 있다고 판정하는 거에요

위에 올려놓은 그림이 점과 선분의 길이를 구하는 방법에 대한 그림이에요

그림에서 녹색 선으로 표시된 길이가 바로 점과 아래의 검은색 선분과의 길이에요,

https://gall.dcinside.com/m/game_dev/162026

벡터의 연산과 활용

그리고 여기서 사용하는 연산은 위의 글에서 설명되어있는 내용들이에요

첫번째와 같이 점이 선분의 시작점보다 더 뒤쪽에 있다면, 이때 점과 선분의 거리는, 점과 선분의 시작점과의 거리가 되요

그리고 이 경우는 벡터의 내적을 통한 방향판별로 구할수 있어요, 선분을 시작점에서 끝점까지의 벡터로 보고, 선분의 시작점에서 구하고자 하는 점까지의 벡터를 가정한다음

두 벡터의 내적이 -값이면 점이 선분의 시작점보다 더 뒤쪽에 있다고 판정하고 첫번째 경우로 여기는거에요

위에 올려놓은 글의 7번에서 설명되어 있는 내용이에요

두번째는 점이 선분의 끝점보다 더 뒤쪽에 있는 경우에요, 이때는 선분의 끝점과 점 사이의 거리가 선분과 점의 거리가 되요

그리고 이 경우는 선분의 시작점에서 점까지의 벡터를, 선분에 투영한 투영벡터의 길이가, 원래의 선분의 길이보다 더 길 경우에 해당되요

투영벡터를 구하는 방법은 위에 올려놓은 글의 14번에서 설명되어 있어요

그리고 세번째는 일반적인 점과 선분의 거리를 구하는 방법을 이용하면 되요

위에 올려놓은 글의 15번에 설명되어 있는 내용이에요

그리고 이렇게 구한 점과 선분 사이의 거리가, 원의 반지름보다 작다면

최종적으로 해당 선분은 원과 겹쳐져 있다고, 즉 충돌하고 있다고 판정하는 거에요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def circle_line(x1,y1,x2,y2,x3,y3,r3)

ax,ay = x2-x1,y2-y1

bx,by = x3-x1,y3-y1

if ax*bx+ay*by < 0 

if ((x3-x1)**2+(y3-y1)**2)**0.5 < r3

return 1

else

return 0

end

end

d = (ax**2+ay**2)**0.5

nx, ny = ax/d, ay/d

c = nx*bx+ny*by

if c > d

if ((x3-x2)**2+(y3-y2)**2)**0.5 < r3

return 1

else

return 0

end

end

tx, ty = nx*c, ny*c

vx, vy = tx-bx, ty-by

if (vx**2+vy**2)**0.5 < r3

return 1

else

return 0

end

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 위에 올려놓은 코드가 이런 방식으로 선분과 원의 충돌을 체크하는 함수의 코드에요, ruby 프로그래밍 언어로 작성한거에요

x1,y1,x2,y2로 선분의 양 끝 점의 좌표를 입력하고, x3,y3,r3으로 원의 중심점과 반지름의 길이를 입력하면

최종적으로 원과 해당 선분이 충돌한다면 1을 그렇지 않으면 0을 출력해요

그리고 최종적으로 다각형의 모든 선분과 원이 충돌하는지를 체크하기 위해서는

이런식의 검사를 다각형을 구성하는 모든 선분들에 적용하면 되요

그러면 다각형의 선분중에서 원과 겹치는 선분이 있는지를 구할수 있어요

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def sort(p)

line = Array.new

i = 0

until p[i] == nil

if p[i+1] == nil

line.push([p[i][0],p[i][1],p[0][0],p[0][1]])

else

line.push([p[i][0],p[i][1],p[i+1][0],p[i+1][1]])

end

i += 1

end

return line

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

def circle_polygon(x,y,r,p)

line = sort(p)

i = 0

until line[i] == nil

x1,y1,x2,y2 = line[i][0],line[i][1],line[i][2],line[i][3]

if circle_line(x1,y1,x2,y2,x,y,r) == 1

return 1

end

i+=1

end

return 0

end

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

그리고 이게 해당 방식으로 다각형의 선분중 원과 겹치는게 있는지를 구하는 함수에요

위에서 두번째가 실제로 사용되는 함수고

첫번째는 처음에 올려놓은 글의 3번에서 설명되어있는 함수에요, 실제로 사용하려면 앞에서 설명한 함수까지 셋 다 정의해놓아야 해요

두번째 함수에서 x,y,r에 구하고자 하는 원의 중심점의 좌표와 반지름의 길이를 입력하고

p에 [[x,y],[x,y],[x,y]] 형식의 배열로 다각형의 각 꼭짓점의 좌표를 입력하면

최종적으로 해당 다각형의 선분 중에서 원과 겹치는게 있는지를 구할수 있어요, 이때 꼭짓점의 좌표는 시계방향 또는 시계반대방향으로 순서대로 입력해야해요

그리고 위에 올려놓은 영상이 앞에서 설명한 방법들을 사용해서 인게임에서 원과 다각형의 충돌체크를 하는 영상이에요,

영상에서 파랑색 원이 플레이어가 방향키로 움직이는거에요, 만약 중앙에서 회전하고 있는 연두색 오브젝트와 충돌했다면 둘 다 불투명하게 표시되요

여기서는 처음에 올려놓은 글에서 설명한 점이 다각형에 포함되는지 구하는 함수와, 위에서 설명한 다각형의 선분중에서 원과 겹치는게 있는지를 구하는 함수 둘 다를 사용해요,

즉 첫번째 함수로 원의 중심점이 다각형 안에 포함되는지를 체크하고, 두번째 함수로 다각형을 구성하는 선분중에서 원과 겹치는게 있는지를 체크하는거에요, 이렇게 하면 맨 처음에 설명한 두 종류의 충돌을 모두 체크할수 있어요

그리고 이런 방법으로는 위의 영상처럼 오목다각형과의 충돌도 체크할수 있어요, 

그리고 이렇게 하면 원과 다각형과의 충돌체크를 할 수 있어요

[불타는키보드(1bnmaker)]

[익명(eager3463)]

내가 진짜 잘 몰라서 물어보는건데...요즘 이런건 그냥 유니티같은데선 딸깍 클릭으로 해주는거지?

[익명(121.168)]

충돌알고리즘이 진짜 바퀴 재발명같은거임 새로 엔진만들거 아니면 엔진에서 알아서 성능이 중요한지(비슷한 모양의 사각형이나 원으로 치환) 정확도가 중요한지(메시상태 그대로 다각형 만들어서 충돌)까지 분류해서 딸깍 해줌

[ㅇㅇ 1(218.49)]

완벽하진 않음. 0~360도까지 지정 가능한 부채꼴 충돌 구현해보면 느낌 올걸?