Post Lists

2019년 8월 4일 일요일

GJK 알고리즘 요점 정리

https://github.com/lch32111/GJKPracticeBasedBox2D
여기에 코드와 내가 필요한 내용들을 정리했다.
--------------------------------------------------------------------------------



GJK 알고리즘 요점 정리하기 based on GDC 2010 Erin Catto

이전에 정리했던 Erin Catto의 GJK 발표 내용이 기억나지 않아
다시 기억할 겸, 정리하면서 공부하기

* GJK 알고리즘의 프로세스 (Bottom-up approach)
1. Point - Line segment
2. Point - Triangle
3. Point - Convex Polygon
4. Convex - Convex Polygon

* GJK 알고리즘의 개념과 용어들
- Voronoi regions
     - Closest Feature Region
- Barycentric coordinates
     - Closest Point
- GJK distance algorithm
- Minkowski Difference
     - Simplex
     - Support Point


* Point - Line Segment에서 Closest point 찾기
- Line segment(선분) : vertex A와 vertex B를 가진 한 선분.
- Query Point (탐색점) : Q
- Closest Point : 선분 AB 위에 있는 가장 가까운 점 P
- Q가 선분 AB에 사영되는 영역(region) : region A, regionAB, region B


~~~

* Polygon structure


struct Polygon
{
    Vec2* points;
    int count;
}

Point to Polygon 상황에서 Closest point on Polygon를 찾으려면 이용해야 할 것
- Closest point to point
- Closest point to line segment
- Closest point to triangle
- 0-Simplex : point
- 1-Simplex : line segment
- 2-Simplex : triangle
- 3-Simplex : tetrahedron
- Idea : polygon a simplex를 새겨넣어라. 왜냐하면 simplex에 대해 closest point를 찾을 수 있으니

* Simplex vertex


struct SimplexVertex
{
    Vec2 point; // polygon vertex로 부터 copy된 point
    int index;  // 그 polygon에서의 index
    float u;    // closest point calculations를 위한 barycentric coordinate u
};

* Simplex


struct Simplex
{
    SimplexVertex vertexA;
    SimplexVertex vertexB;
    SimplexVertex vertexC;
    int count;
};
Simplex는 point/line segment/triangle을 나타낼 수 있다.

* GJK 순서도
1) 임의의 정점을 선택하여 시작 (starting simplex, 0-simplex)
2) 해당 Simplex의 Query Point에 대해 Closest point(E)를 찾는다.
3) 그 Closest point에서, Query Point로 가는 벡터를 그린다. (Search Vector, d, E->Q)
4) Search direction에서 가장 멀리 있는 정점을 찾는다 (Support point)


int Support(const Polygon& poly, const Vec2& d)
{
   int index = 0;
   float maxValue = Dot(d, poly.points[index]);
   for (int i = 1; i < poly.count; ++i)
   {
      float value = Dot(d, poly.points[i]);
      if (value > maxValue)
      {
         index = i;
         maxValue = value;
      }
   }
   return index;
} // 이 때 search direction은 normalized 될 필요가 없다. 똑같은 기준(search direction)에 대해
 // 가장 멀리 있는 vertex를 선택하기 때문이다. 

5) Support point를 구했으면, 그 정점과 현재의 simplex를 합친다.
6) 0-simplex와 한 개의 정점이므로 1-simplex인 line segment가 된다.
7) 해당 simplex에 대해 2~5의 프로세스를 반복한다.
8) 반복하던 도중, 찾은 Closest Point에 기여하지 않는 Simplex의 Vertex가 존재한다면
    현재의 Simplex에서 그 기여하지 않는 Vertex를 버린다.
9) Search Direction(d)를 통해 다시 support point를 찾으려 했을 때, 현재 Simplex에 있는     모든 Vertex라면 더 이상 진행할 수 없으므로, 그 simplex의 closest point가 가장 가까운     점인 것으로 끝낸다.

* GJK algorithm pseudo code


Input : polygon and point Q
pick arbitrary initial simplex S
loop
   compute closest point P on S
   cull non-contributing vertices from S
   build vector d pointing from P to Q
   compute support point in direction d
   add support point to S
end

* Numerical Issue
- Numerical 문제는 Search direction / Loop Termination에 영향을 미침

1) Bad Direction
- Barycentric coordinates는 반올림 문제를 겪어서, search direction이 정확하지 않을 수 있다.
- Search Direction이 정확하지 않다면, 정확하지 않는 Support point를 찾게 되고, 더욱 초과하는 iteration과 부정확한 결과를 발생시킨다.

1-1) Bad Direction - Solution
- closest point를 사용하지 않고, closest point가 edge위에 있을 때에는, 그 edge에 수직인 vector를 생성하는 것이 더 좋다.
- 그 edge vector를 plane normal에 외적하여 수직의 벡터를 얻을 수 있다.
edge direction -> e = (x, y)
search direction -> d = (-y x)
dot product -> dot(e,d)= -xy + yx = 0
- 그리고 방향을 맞추기 위해, dot(d, Q-C)가 음수이면 d를 flip (C는 edge위에 있는 정점)

2) Termination condition
- Case 1 : Repeated Support Point. 위에서 말했듯이, 현재 simplex에 속해있다면 우리는 closest point로 loop를 끝내야 한다.
- Case 2 : 2-simplex + all triangular barycentric coordinates positive -> Query Point가 2-simplex인 삼각형 안에 있다.
- Case 3 : 최종 Closest Point가 Polygon Vertex인 경우. search direction d를 구할 때 zero vector이게 된다.
- Case 3b : Query Point가 polygon edge위에 있을 때. 이 때, search direction d는 임의의 sign을 갖게된다. 그래서 두 가지 경우에 검사해야 한다.
     - Case 3b -> d points left : 만약 d가 왼쪽을 가리킨다면, 그러면 우리는 Case 1을
                      얻게된다. 따라서, duplicate support point 형식이 될 것이다.
     - Case 3b -> d points right : 만약 d가 오른쪽을 얻게 된다면, 그러면 우리는 새로운                           support point를 얻게 된다.
                       이 경우에, 우리는 같은 Closest Point를 얻고 같은 d를 얻게된다.
                       곧, 우리는 반복되는 support point를 보거나 containment를 찾게된다.
                        duplicate vertex case(case 1) 또는 containment(Case 2)가 발생한다.
                        round-off error로 인해.
- Case 4 : Query Point가 simplex의 내부 edge에 중첩될 때이다. 이 경우에, 우리의 simplex는 interior line segment이다. 이 때 d를 유일하게 결정할 수 없다.
따라서, Case 3b와 궁극적으로 같다. d가 어느 방향을 선택하는우리는 repeated vertex를 탐지할 수 있을 것이다.

* Termination in 3D
- 새로운/다른 조건들을 요구할지도 모른다.
- dinstance progression을 탐색 (예를들어 P->Q의 distance가 매 iteration 동안 줄어드는지 테스트 할 필요가 있다).

* Non-Convex Polygon
support point로서 항상 나타나지 않을 것이다.

* Collinear vertices
3개의 vertices가 collinear할 때, 2-simplex가 나오는데 degenerate triangular simplex가 나타나게 될 것이다. 즉 그 삼각형의 넓이는 zero이다. 그래서 triangular barycentric coordinates은 무한이 된다. 이 경우에 triangle solver가 vertex or edge region을 고르도록 보장해야만 한다.


Convex Polygon to Convex Polygon

* idea
- polygon to polygon문제를 point to polygon으로 변환 : Minkowski difference
- point to polygon을 해결하기 위해 GJK를 사용

* Minkowski difference
- 두 개의 polygons을 single convex polygon으로 합친다.



Input: polygon X and Y
array points
for all xi in X
   for all yj in Y
      points.push_back(yj - xi)
   end
end

polygon Z = ConvexHull(points)

polygon Y에서 polygon X의 정점을 뺄셈하여, point cloud를 얻고, 거기에서 convex hull를 찾아 polygon을 형성한다.

* Property of Super Polygon generated by Minkowski difference
- Property 1 : distances are equal
Polygon X와 Y 사이의 거리는, Super polygon과 원점 사이의 거리와 같다.

- Property 2 : support points
Z : super polygon

X와 Y의 support points를 합하여 Z의 한 support point를 결정할 수 있다.
이러한 두 개의 support points의 차는 Z에서의 support point와 같다.
그래서 우리는 이제 Z를 explicitly하게 구성하지않고, Z의 support point를 어떻게
연산하는지를 안다.
따라서, convex hull이 필요하지 않다.

*  Minkowski difference를 다루기위해 GJK를 변경
- support function변경
- Simplex vertices가 두 개의 indices를 유지

* Closest point on polygons
- X와 Y에서의 closest points를 연산하기 위해 barycentric coordinates 사용















댓글 없음:

댓글 쓰기