· GJK-EPA 알고리즘으로 플레이어를 밀어내는 오브젝트 만들기
· 분리축(SAT)충돌검사를 사용해서 밀어내는 오브젝트 만들기
· OBB충돌검사를 사용해서 밀어내는 오브젝트 만들기
· 원 충돌체크 & AABB충돌체크
· 벡터의 연산과 활용
· 극좌표계의 기본 연산들
· 점이 다각형에 포함되는지 구하기
점이 다각형에 포함되는지의 여부, 그리고 두 선분이 교차하는지의 여부로 두 다각형의 충돌체크를 하는 방법에 대한 글이에요
그리고 저도 수학이나 프로그래밍을 잘 아는게 아니라, 틀리거나 잘못된 내용이 있을수도 있어요
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
1. 두 다각형이 충돌하는 경우의 종류
위에 올려놓은 그림은 두 다각형이 충돌하는 여러 경우에 대한 그림이에요
그리고 그림의 왼쪽의 1.충돌 에서 나와있는것처럼
만약 두 다각형이 충돌한다면, 이때 한 다각형의 꼭짓점이 다른 다각형에 포함되거나
또는 두 다각형의 각각의 모서리중 서로 교차하는 모서리가 있어야 해요
즉, 두 다각형의 모든 꼭짓점들을 조사해서, 한 다각형의 꼭짓점이 다른 다각형에 포함되는지 체크하거나
혹은 두 다각형의 모든 모서리들을 서로 비교해서, 서로 교차하는 모서리가 있는지 체크하면
두 다각형이 충돌하는지를 구할수 있어요, 이게 이번 글에서 이야기하려는 충돌체크 방식이에요
그리고 이런 방식의 충돌체크로는 두 볼록다각형만이 아니라 두 오목다각형에 대해서도 충돌체크를 진행할수 있어요
그리고 위에 올려놓은 그림의 2.포함과 3.관통은 각각 특별한 경우의 충돌을 나타낸거에요
2. 포함은 두 다각형이 충돌하는데, 서로 교차하는 모서리가 없이, 한 다각형의 꼭짓점만 다른 다각형 내부에 포함되어있는 경우에요
즉, 두 다각형의 모서리들을 조사해서 서로 교차하는 모서리가 있는지 체크하는 방식으로는, 이런 경우의 충돌은 체크할수 없어요
그리고 3. 관통은 반대로, 두 다각형이 충돌하지만, 한 다각형의 꼭짓점이 다른 다각형 내부에 포함되지 않고, 두 다각형의 모서리만 서로 교차하는 경우에요
즉, 다각형의 꼭짓점들을 조사해서, 한 다각형의 꼭짓점이 다른 다각형 내부에 포함되는지를 체크하는 방식으로는, 이런 경우의 충돌은 체크할수 없어요
2. 점이 다각형에 포함되는지의 여부를 통한 충돌체크
그리고 여기서 사용하는 한 점이 특정 다각형 내부에 포함되어있는지를 체크하는 함수는, 위의 글의 4번에 나와있는 함수에요
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
def polygon_collision1(p1,p2)
i =0
until p1[i] == nil
x, y = p1[i][0],p1[i][1]
if point_polygon(x,y,p2) == 1
return 1
end
i+=1
end
i =0
until p2[i] == nil
x, y = p2[i][0],p2[i][1]
if point_polygon(x,y,p1) == 1
return 1
end
i+=1
end
return 0
end
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
그리고 여기서 두 선분이 교차하는지를 체크하기 위해서는, ccw알고리즘을 이용한 두 선분의 교차여부를 판별하는 방식이 사용되요
위에 올려놓은 글의 22번과 23번에서 설명되어있는 내용이에요
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
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 ccw(x1,y1,x2,y2,x3,y3)
return (x1*y2+x2*y3+x3*y1)-(y1*x2+y2*x3+y3*x1)
end
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
def line_cross(x1,y1,x2,y2,x3,y3,x4,y4)
if ccw(x1,y1,x2,y2,x3,y3)*ccw(x1,y1,x2,y2,x4,y4) < 0 && ccw(x3,y3,x4,y4,x1,y1)*ccw(x3,y3,x4,y4,x2,y2) < 0
return 1
else
return 0
end
end
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
def polygon_collision2(p1,p2)
p1, p2 = sort(p1), sort(p2)
j =0
until p2[j] == nil
i =0
until p1[i] == nil
x1,y1,x2,y2,x3,y3,x4,y4 = p1[i][0],p1[i][1],p1[i][2],p1[i][3],p2[j][0],p2[j][1],p2[j][2],p2[j][3]
if line_cross(x1,y1,x2,y2,x3,y3,x4,y4) == 1
return 1
end
i +=1
end
j +=1
end
return 0
end
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
그리고 위에 올려놓은 함수들이, 선분의 교차여부를 통한 충돌체크에 사용되는 함수들이에요
첫번째 함수는 다각형의 꼭짓점을 모서리로 변환시켜주는 함수에요,
앞의 점의 포함여부를 통한 충돌체크에서 올려놓은 글의 2번에서 설명하는 함수에요
그리고 두번째와 세번째는 위에 올려놓은 글의 22번과 23번에서 설명하는 내용의 함수에요
두번째가 22번에서 설명하는 ccw알고리즘의 함수고
세번째가 23번에서 설명하는 ccw알고리즘을 사용한 두 선분의 교차판별에 대한 함수에요
그리고 네번째가 앞의 함수들을 이용해서 실제로 두 다각형의 충돌체크를 하는 코드에요
우선 두 다각형의 꼭짓점들을 모서리로 변환하고
그다음 각각의 모서리들을 순서대로 조사하면서 다른 다각형의 모서리와 교차하는지 체크하는거에요
그렇게해서, 만약 다른 다각형의 모서리와 교차하는 모서리가 있다면 충돌했다고 판정하고 1을 출력하고
모든 모서리를 조사해도 다른 다각형의 모서리와 교차하는 모서리가 없다면 충돌하지 않는다고 판정하고 0을 출력해요
역시 p1과 p2에 [ [x1,y1],[x2,y2],[x3,y3] ] 형식으로 충돌체크를 하고자 하는 두 다각형의 꼭짓점들을 배열로 입력하면 되요
시계방향 혹은 반시계방향으로 순서대로 입력해야해요
그리고 위에 올려놓은 영상이 실제로 앞에서 설명한 코드로 인게임에서 충돌체크를 실행하는 영상이에요
파랑색 사각형이 플레이어가 움직이는 오브젝트에요, 그리고 만약 중앙의 연두색 오브젝트와 충돌했다면 둘다 반투명하게 표시되요
여기서는 앞에서 설명한 2번 점의 포함여부를 통한 충돌체크와, 3번 선분의 교차여부를 통한 충돌체크를 둘 다 사용한거에요
즉, 맨 처음 설명한 세 종류의 충돌을 모두 체크할수 있어요
그리고 이런식으로 하면 점의 포함여부와 선분의 교차여부를 이용해서 두 다각형의 충돌체크를 할 수 있어요
댓글 0