[📚정보] 민코프스키 차이와 볼록껍질을 활용한 충돌체크

[vertex(4321vertex)]

1.민코프스키 합과 민코프스키 차이

위의 그림처럼 xy좌표평면위의 꼭짓점을 가진 다각형은, 결국 해당 꼭짓점들까지의 벡터들로 바라볼수 있어요

즉 한 다각형의 각각의 꼭짓점마다, 다른 다각형의 각각의 꼭짓점들의 벡터를 더해서 새로운 다각형을 만들수 있어요

그리고 그렇게 만들어진 새로운 다각형이 바로 민코프스키 합이에요

위의 그림에서 왼쪽은 사각형+삼각형의 방향으로, 사각형의 각각의 꼭짓점의 벡터에, 삼각형의 각각의 꼭짓점의 벡터를 더해서 새로운 다각형을 만든거에요

그리고 오른쪽은 삼각형+사각형의 방향으로, 삼각형의 각각의 꼭짓점의 벡터에, 사각형의 각각의 꼭짓점의 벡터를 더해서 새로운 다각형을 만든거에요

위의 그림이 벡터의 덧셈의 방향이에요, 벡터 a+b를 하면 a의 끝점에서 b만큼 나아간 벡터인 c가 나오게 되요

그리고 동일한 방식으로, 한 다각형의 각각의 꼭짓점의 벡터에서, 다른 다각형의 각각의 꼭짓점의 벡터를 빼서, 그렇게 나온 벡터들로 새로운 다각형을 만들수 있어요, 그리고 이게 민코프스키 차이(Minkowski Difference)에요

위의 그림에서 왼쪽이 사각형-삼각형 방향의 민코프스키 차이를 구하는 방법이에요, 그리고 오른쪽 위가 그렇게 해서 최종적으로 나온 사각형-삼각형 방향의 민코프스키 차이에요,

그리고 오른쪽 아래는 삼각형-사각형 방향의 민코프스키 차이에요

위의 그림이 벡터의 뺄셈의 방향이에요, 벡터b에서 a를 빼면 a의 끝점에서 b의 끝점까지 나아가는 방향의 벡터c가 나오게 되요,

그리고 그렇게 해서 최종적으로 위의 그림에서 분홍색으로 표시된 벡터가 나오게 되는거에요

2.민코스프키 차이를 통한 충돌체크의 원리

위의 그림에서 연두색 다각형이 사각형-삼각형 순서의 민코스프키 차이에요, 그리고 중앙의 지점이 원점(0,0)이에요

즉 위의 그림처럼 만약 두 다각형이 충돌하지 않았다면, 이때 원점은 민코스프키 차이의 밖에 있어요

그리고 위의 그림처럼 만약 두 다각형이 가장자리에서 만났다면, 원점은 민코스프키 차이의 가장자리에 있어요

그리고 위의 그림처럼 두 다각형이 충돌했다면, 이때 원점은 민코스프키 차이 내부로 들어오게 되요

그리고 이때 원점을 민코스프키 차이 밖으로 밀어내기 위한 최소거리 벡터가 바로 삼각형을 사각형 밖으로 밀어내기 위한 최소거리 벡터가 되는거에요, 위의 그림에서 보라색으로 표시된 벡터에요

사각형-삼각형 순서의 민코스프키 차이니까, 삼각형을 사각형 밖으로 밀어내기 위한 최소거리벡터가 되는거에요

그리고 위의 그림은 반대로 삼각형-사각형 순서의 민코스프키 차이에요

즉 위의 그림에서 원점을 민코스프키 차이 밖으로 밀어내기 위한 최소거리 벡터는, 삼각형-사각형 순서니까 사각형을 삼각형 밖으로 밀어내기 위한 최소거리벡터가 되는거에요

위의 그림은 왜 두 다각형이 충돌하지 않으면, 원점이 민코스프키 차이의 밖에 있게 되고, 두 다각형이 충돌하면 원점이 민코스프키 차이 안에 있게 되는지에 대한 설명이에요,

사각형-삼각형 순서의 민코스프키 차이는, 사각형의 각각의 꼭짓점들로부터 삼각형의 각각의 꼭짓점들까지의 벡터에요, 그리고 위의 첫번째 그림처럼 만약 사각형과 삼각형이 충돌하지 않는다면, 이때 그렇게 나오는 벡터들의 범위는 180도를 넘어가지 않아요, 따라서 원점은 결국 민코스프키 차이 밖에 있게 되는거에요

반면 위의 두번째 그림처럼 만약 사각형과 삼각형이 충돌한다면, 이때 그렇게 나오는 벡터들의 범위는 180도를 넘어가게 되요, 따라서 원점은 결국 민코스프키 차이 안에 있게 되는거에요

그리고 최소이동벡터(Minimum Translation Vector)는 위의 그림처럼 두 다각형이 충돌했을때, 한 다각형을 서로 충돌하지 않는 범위까지 이동시키기 위한 최소거리의 벡터에요, 위의 그림에서는 삼각형을 사각형 밖으로 이동시키기 위한 최소거리의 벡터에요

3. 민코스프키 차이와 볼록껍질 알고리즘을 활용한 충돌체크의 원리

즉, 앞의 설명처럼 두 다각형의 민코스프키 차이를 구한다음 그렇게 구한 민코스프키 차이에 원점이 포함되는지를 체크하면 두 다각형이 충돌하는지를 체크할수 있어요

그리고 만약 두 다각형이 충돌한다면, 그때 원점을 민코스프키 차이 밖으로 밀어내기 위한 최소거리벡터를 구하면 충돌하는 다각형을 충돌하지 않는 거리까지 밀어내기 위한 최소거리벡터를 구할수 있어요, 그리고 이때 어떤 다각형을 밀어내는 최소거리벡터를 구할지는, 어떤 순서로 두 다각형의 민코스프키 차이를 구하는지에 따라서 결정할수 있어요

그리고 이때 두 다각형의 민코스프키 차이를 구해서, 그렇게 구한 민코스프키 차이의 전체 범위의 가장자리를 감싸는 다각형을 만드는대에 볼록껍질 알고리즘이 사용되요, 즉 두 다각형의 민코스프키 차이를 구해서 나온 벡터들에 볼록껍질 알고리즘을 적용해서 해당 벡터 전체를 감싸는 볼록껍질 형태의 다각형을 만든다음, 해당 다각형에 원점이 포함되는지를 체크하는거에요, 그리고 만약 원점이 포함된다면 그때 원점을 해당 다각형 밖으로 밀어내기 위한 최소거리벡터를 구하는 거에요

https://gall.dcinside.com/mgallery/board/view/?id=game_dev&no=214654

볼록 껍질 알고리즘

볼록껍질 알고리즘에 대한 설명은 위의 글에 있어요

[링크]

그리고 전체 충돌체크 알고리즘의 코드는 위의 글에 있어요

[Indie 1(218.155)]

완벽히 이해했어

[익명(remote0709)]

좋아 완벽하게 이해했어

[Indie 2(221.158)]

하 어렵네\

[Indie 3(27.35)]

이게 한국어인건 알았는데

[FLow(1.232)]

이전에 격자점 넣기전에 최적화 고민했었는데 이런 충돌 체크 방법이 있구나 컨벡스 헐은 벡준에서 본 기억이 있었는데 이건 좀 어렵네.. 원점이 어쩌고 한 부분부터 머리가 못버티고 있어 유니티에서 Physics2D.Distance이것도 이 알고리즘 사용하는 건가?

[Indie 4(112.186)]

오케이 분석완료 못해