Projects/Physical Collision

GJK 알고리즘

아헿헿헿 2022. 5. 31. 09:15

참고자료 : https://box2d.org/files/ErinCatto_GJK_GDC2010.pdf

 

목적

볼록 다각형 폴리곤들이 있을 때, 이들의 가장 가까운 점을 구하는 방법과 이들이 어떻게 겹쳐졌는지를 판단하는 방법에 대해서 배워나가보겠습니다. 밑에서부터 더 큰 범위의 물체에 대해서 적용하는 식으로 진행해나갈 것입니다.

  • Point to line segment
  • Point to triangle
  • Point to convex polygon
  • Convex polygon to convex polygon

이를 위한 개념으로는 다음과 같은 것을 배울 것입니다

  • Voronoi regions
  • Barycentric coordincates
  • GJK distance algorithm
  • Minkowski difference

Point to line segment

Voronoi regions

점들의 집합을 영역의 집합으로 변환한 것을 voronoi regions라고 합니다. 옆의 그림에서 한 색깔이 의미하는 것은 해당 위치에서 가장 가까운 점들이 같은 경우를 의미합니다.

 

 

 

 

 

 

 

 

Point to Line

점과 선분의 가장 가까운 거리를 구할 때, QA와 AB의 내적을 통해서 구할 수 있습니다. 이를 voronoi regions로 확장시키면 A에 가장 가까운 경우는 region A, B가 가장 가까운 경우는 region B, 그 사이에 있다면 region AB로 구별 가능합니다.

 

Barycentric coordinate

A와 B 사이에 어떠한 점 G가 존재할 때 G는 A와 B의 선형 결합으로 나타낼 수 있기에 좌표로서 나타내질 수 있다는 것입니다. 이를 통해 한 점 Q와 이를 AB에 내린 G의 좌표를 구할 수 있습니다.

선분 AB의 unit vector n과 QA 및 QB를 내적하여 이를 선분 AB에 대해 길이가 얼마나 긴지를 구한다면 barycentric coordinate에서의 u, v를 쉽게 구해낼 수 있습니다.

 

Point to Triangle

먼저 삼각형에 대한 voronoi regions을 정의하면 다음과 같이 됩니다.

이를 구하기 위해서는 한 점 Q에 대해서 Point to line segment와 같이 barycentric coordinate를 구한 후에 이를 통해 voronoi region에 대한 정의를 할 수 있습니다. 이를 통해 Q = uA + vB + wC (u + v + w = 1)로 나타낼 수 있습니다. 이제 Region ABC에 대해서 처리를 해주어야만 합니다. 이때 면적으로 생각한다면, u, v, w는 각각 부분 삼각형의 넓이에 비례하며 이는 전체 삼각형에서 차지하는 비중으로 해석 가능합니다.

삼각형의 면적은 두 선의 외적으로 구할 수 있습니다. 또한 u, v, w의 값을 통해서 삼각형이 어느 위치에 존재하는지 유추해낼 수 있습니다. 따라서, 앞서 구한 voronoi region과 barycentric coordinate를 활용하면 모든 영역을 적절하게 나눌 수 있으며 이를 통해 가장 가까운 위치를 찾을 수 있습니다. vertex region은 한 점에서 가장 가까운 부분에 해당하며 edge region은 어느 한 선분에서 가장 가까운 지역을 해당하며, interior region은 내부에 존재하는 경우입니다. 이를 확인 하는 방법은 

  1. Q로부터 voronoi region을 찾습니다. vertex region인지를 확인합니다.
  2. 그 다음 barycentric coordinate를 통해 edge region인지 interior region인지를 확인 후 가장 가까운 점을 찾습니다.

 

Point to Convex Polygon

  1. 구하고자하는 점 Q(그림에서는 origin)을 위해 임의의 점 A에서 출발하여 simplex를 구성합니다.
  2. A에서 구하고자하는 점까지의 선분에 모든 다른 점을 정사영시키고 가장 먼 점B을 supporting point로 잡아 이를 simplex에 넣습니다. 
  3. 이후 선분 AB에 점 Q를 정사영시켜 점 C를 찾은 뒤, 다시 선분 QC에 다른 점들을 정사영 시켰을 때 가장 먼점 D를 simplex에 넣습니다.
  4. ABD simplex에서 가장 가까운 점은 E가 되고 이때 A는 E와 관계가 없으므로 simplex에서 뻅니다.
  5. 다시 여기서 선분 EQ에 정사영 시킨 뒤 가장 먼점을 찾아 F를 simplex에 넣습니다.
  6. 이번에는 가장 가까운 점이 G가 되면서, 관계없는 B를 simplex에서 제거하고, 선분 GQ에 정사영시켰을 때 양수의 값을 가지는 점이 없으니 이때는 알고리즘이 종료되며 가장 가까운 점은 G가 됩니다.

Convex Polygon to Convex Polygon

Minkowski Sum and Minkowski difference

minkowski sum은 다른 두개의 물체가 존재할 때 이 둘의 좌표의 합을 구한 것입니다.

minkowski difference는 반대로 다른 두개의 물체가 존재할 때 이 둘의 좌표를 뺀 값의 집합을 구한 것입니다.

이렇게 minkowski difference에서 구한 물체와 원점과의 거리는 두 물체의 거리와 동일합니다. 또한 support vector를 구할 때, support(A+(-B), d) = support(Y, d) - support(X, -d)가 성립합니다.