EPA (Expanding Polytope Algorithm)

http://www.dyn4j.org/2010/05/epa-expanding-polytope-algorithm/

EPA (Expanding Polytope Algorithm)
지난 몇 개의 글에서, 우리는 충돌 탐지, 도형간의 거리, 그리고 가장 가까운 점을 찾기 위해 GJK를 사용하는 것에 대해 배웠다. 충돌 깊이와 그 벡터 같은 충돌 정보를 알아내기 위해서, 또다른 알고리즘과 함께 GJK가 증강되어야 한다는 것이 명시되었었다. 그러한 한 알고리즘은 EPA이다.

나는 EPA 알고리즘을 다루고 하나의 대안을 언급할 계획이다.

1. Introduction
2. Overview
3. Starting Point
4. Expansion
5. Example
6. Winding and Triple Product
7. Augmenting
8. Alternatives

Introduction

GJK처럼, EPA는 Minkowski Sum의 같은 개념을 사용한다. 이것은 덧셈 대신에 뺄셈 연산을 수행한다. 이전의 포스트처러, 나는 이것은 Minkowski Difference로 언급할 것이다.

처음의 GJK 글에서, 우리는 두 볼록 도형들이 교차하고있는지를 어떻게 결정할지에 대해서 이야기 했었다. 우리가 이제 하길 원하는 것은 충돌이 있은 후에, 충돌 정보를 찾는 것이다: depth and vector.

Overview

GJK 글에서, 우리는 Minkowski Difference가 원점을 포함하면 볼록 도형들이 교차하고 있다는 것을 명시했었다. 이것 외에도, Minkowski Difference에서의 가장 가까운점에서 원점으로 가는 거리가 충돌 깊이이다. 마찬가지로, 가장 가까운 점에서 원점으로 가는 벡터가 충돌 벡터이다.

GJK처럼, EPA는 반복 알고리즘이다. EPA는 Expanding Polytope Algorithm을 나타내고, 그거 그대로 의미한다. 우리는 Minkowski Difference의 내부에 하나의 polytope (or polygon)을 만들고 싶고, 반복적으로 Minkowski Difference의 변에 닿을 때 까지 그것을 팽창시킬 것이다. 중요한 것은 polytope의 원점에 대해 가장 가까운 특징을 팽창시키는 것이다. 만약 우리가 이것을 반복적으로 수행한다면, 우리는 하나의 polytope를 만들 것인데, 거기에서 가장 가까운 특징이 Minkowski Difference위에 놓여있게 된다. 그것으로 인해, 충돌 깊이와 벡터를 만들게 된다.

EPA는 이 작업을 다른 알고리즘과 simplex의 같은 개념에서 사용된 같은 support function을 사용해서 수행한다. GJK와의 한 차이점은 EPA의 simplex는 어떤 개수의 점이든 가질 수 있다는 것이다.

Starting Point

EPA는 팽창시킬 초기의 simplex가 필요하다. GJK collision detection routine의 termination simplex가 훌륭한 시작이다.

EPA는 full simplex가 필요하다 : 2D에서는 삼각형, 그리고 3D에서는 사면체. 

GJK 충돌 탐지 routine은 그것이 위의 경우에 항상 끝나도록 수정되어질 수 있다.

이 글에서 GJK는 한 삼각형이 만들어지고 나서야 그 도형이 교차하고 있는 것을 반환하고 끝낼 것이다.

Expansion

만약 우리가 EPA에 그 termination simplex를 넘긴다면, 우리는 즉시 expansion process를 시작할 수 있다:

Simplex s = //termination simplex from GJK
// loop to find the collision information
while (true)
{
    // obtain the feature (edge for 2D) closest to the
    // origin on the Minkowski Difference
    Edge e = findClosestEdge(s);
    // obtain a new support point in the direction of the edge normal
    Vector p = support(A, B, e.normal);
    // check the distance from origin to the edge against the
    // distance p is along e.normal
    double d = p.dot(e.normal);
    if(d - e.distnace < TOLERANCE)
    {
        // the tolerance should be something positive close to zero (ex. 0.00001)
    
        // if the difference is less than the tolerance then we can
        // assume that we cannot expand the simplex any further and
        // we have our solution
        normal = e.normal;
        depth = d;
    }
    else
    {
        // we haven't reached the edge of the Minkowski Difference
        // so continue expanding by adding the new point to the simplex
        // in between the points that made the closest edge
        simplex.insert(p, e.index);
    }
}

여기에서 findClosestEdge는 이렇게 보인다:

Edge closest = new Edge();
// prime the distance of the edge to the max
closest.distance = Double.MAX_VALUE;
// s is the passed in simplex
for (int i = 0; i < s.length; ++i)
{
   // compute the next points index
   int j = i + 1 == s.length ? 0 : i + 1;
   // get the current point and the next one
   Vector a = s.get(i);
   Vector b = s.get(j);
   // create the edge vector
   Vector e = b.subtract(a); // o a.to(b);
   Vector oa = a; // or a - ORIGIN
   // get the vector from the edge towards the origin
   Vector n = Vector.tripleProduct(e, oa, e);
   // normalize the vector
   n.normalize();
   // calculate the distance from the origin to the edge
   double d = n.dot(a); // could use b or a here
   // check the distance against the other distances
   if (d < closest.distance) 
   {
      // if this edge is closer then use it
      closest.distance = d;
      closest.normal = n;
      closest.index = j;
   }
}
// return the closest edge we found
return closest;

{
여기에서, n과 a(or b)의 내적을 통해서 어떻게 그 변에 가까운지를 구하는 것에 대한 설명이 필요하다. 현재 edge에 대해 수직인 벡터 n을 구했다. 그 벡터 n은 표준화 되어있다. 그래서 내적(n, a)하는 것은 우리가 이전에 명시했던 scalar projection과 같게 되는 것이다. 여기에서 표준화 된 것은 n이므로, n방향으로 a의 벡터를 사영시키는 것이다.

그렇다면 원점에 가장 정확히 가까운 것을 구하려면 이전 글에서 했던
AO를 AB edge에 사영시켜서, A에서 그 만큼의 비율로 움직여서 가장 가까운 점을 구한 후
원점과의 거리를 구할 수가 있다. 하지만, 그것은 더 많은 operation을 요구하기 때문에

a 또는 b와의 내적을 해서 구할 수가 있는 것이다.

따라서, 가장 가까운 점과의 거리를 구하지 않고,
변에서의 한 점을 잡아서 사영시킨 거리를 통해 구하기 때문에,
근사시켜서 편하게 원점과의 거리를 구해서
비교하는 것이다.

https://www.youtube.com/watch?v=l-_DbsFjz_s
원점과 가장 가까운 벡터위의 점을 구하는 것이 여기에 아주 간결하게 설명되어 있다.
}

Example
항상 그럿듯이, 예제로 보여주면 이해가 더 쉽다고 생각한다. 우리는 GJK 글의 예제를 사용할 것이고, EPA를 사용하여 충돌 정보를 결정할 거싱다.

우리는 GJK termination simplex를 EPA에 주어서 시작한다:

Iteration 1
우리가 다른 점을 추가하여 simplex를 팽창시키고 있다는 것을 유의해라. 우리가 추가했던 점이 Minkowski Difference의 변 위에 있다는 것을 지적하는 것이 중요하다. simplex를 구성하는 모든 점들은 Minkowski Difference edge위에 있기 때문에, 그 심플레스가 convex하다는 것을 보장할 수 있다. Minkowski Difference가 convex하기 때문이다. 만약 그 simplex가 볼록하지 않다면, 우리는 많은 연산들을 건너 뛸 수 없을 것이다.

지적되어야 할 또 다른 중요한 것은 우리가 새로운 점을 simplex에 추가하는 방식이다. 우리는 가장 가까운 변을 만드는 두 점 사이에 있는 새로운 점을 추가한다. 이 방식으로 그 도형은 convex를 유지한다. 이 예제에서, 그 점의 winding (감기는 방향)은 중요하지 않다. 그러나 우리가 했듯이, 새로운 점을 넣는 것이 현재의 winding direction을 보존하는 것을 유의하는게 중요하다. simplex의 winding direction은 나중에 더 볼 것이다...

Iteration 2
두 번째 반복에서, simplex의 가장 가까운 변이 Minkowski Difference위에 실제로 놓여있다는 것을 본다. 우리는 검사에 의해, Edge 4의 normal이 충돌 normal인 것으 ㄹ알 수 있고, 그 edge에서 원점으로 가는 수직 거리가 penetration depth라는 것을 안다. 이것은 마지막 iteration에서 확인된다.

우리는 두 번째 iteration에서 종료했다. 왜냐하면 새로운 simplex point에 대한 거리가 더 이상 우리가 우리의 simplex를 더 이상 팽창시킬 수 없다고 알려주는 가장 가까운 변과의 거리보다 더 크지 않기 때문이다. 만약 더 높은 precision numbers가 사용된다면, 우리는 그 거리 변수의 값이 좀 더 0에 가깝다는 것을 볼 것이다. 그리고 이것은 새로운 support point가 가장 가까운 변 위에 놓여있기 때문에 그렇게 된다.

우리는 여전히 곡선 도형과 finite precision math 때문에 tolerance를 가질 필요가 있다. 곡선의 Minkowski Difference에 대해, 그 simplex는 curvature(굽음)에 순응하기 위해 더 작고 작은 변들을 만들 것이다. 너는 그림 5에서 이것을 볼 수 있다. 그러나, 그 증가된 precision 때문에 그것은 더 많은 edges들일 것이다.

Winding and Triple Product
이전에 나는 simplex의 winding이 보존되는 것에 대해 어떤 것을 언급했었다. 이것은 충돌의 특별한 경우를 다루는데 중요하다.

작은 또는 touching collisions(접촉 충돌)은 EPA 문제를 야기시킨다. 이 문제는 triple product를 사용하는 것이 원인이 된다. 만약 그 원점이 정말 그 가장 가까운 변과 가깝게 놓여있다면, 그 triple product는 영벡터를 반환할지도 모른다 (유한 precision 때문에). 우리가 그 벡터를 표준화할 떄, 우리는 0으로 나눌 것이다: 좋지 않은 것이다.

만약 우리가 triple product를 사용하는 이유를 본다면, 우리는 이 문제를 고치는 다른 방법을 생각해낸다. 그 triple product는 원점의 반대방향에 있는 한 edge의 normal vector를 얻기 위해 사용된다. 우리는 그 edge의 per-product를 사용하여 같은 것을 할 수 있다.

그 per-product는 다음과 같이 정의된다:

if A = (x, y)
A.perproduct() = (-y, x) or (y, -x) depending on the
handedness of the coordinate system (right or left respectively)

이 예시에서, 그 왼손 또는 오른손 방향은 실제로 그 simplex의 winding에 의해 결정된다. 만약 그 simplex의 winding이 시계 반대방향이라면, 그러면 우리는 right per-product를 사용하길 원한다. 마찬가지로, 만약 그 simplex winding이 clockwise라면, 그러면 우리는 left per-product를 사용하길 원한다. 우리는 이것을 가정할 수 있다. 왜냐하면 우리가 이미 그 원점이 그 simplex에 포함되어있다고 보장했기 때문이다.

그래서 triple product를 사용하는 대신에, 우리는 edge의 normal을 얻기위해 per-product를 사용할 수 있다. 그 원점이 가장 가까운 변과 아무리 가까울지라도. 그 새로운 코드는 이것처럼 보인다:

// we change this
// Vector n = Vector.tripleProduct(e, oa, e);
// to this
if (winding == CLOCKWISE)
{
    n = e.left(); // (y, -x)
}
else
{
    n = e.right(); // (-y, x)
}

simplex의 winding이 보존되는 것을 주목하는 것이 중요하다. 왜냐하면 새로운 코드를 좀 더 효율적이고 튼튼하기 만든다면 우리가 simplex의 winding을 결정할 수 있다는 것을 의미하기 때문이다.

Augmenting
EPA는 종종 연산 비용 때문에 작은 penetrations에 대해서는 사용하지 않는다. 그러므로 너는 GJK penetration detection algorithm으로 보충된 EPA를 볼 지도 모른다. 충돌 정보를 위해서 GJK를 사용하는 것은 충돌하는 도형의 (core shapes라고 불려지는) 더 작은 버전을 사용하고 GJK distance check을 수행하는 것을 포함한다. 그 core shapes사이의 거리가 발견된다면, 도형에 적용된 radial sinkage의 합계로부터 그것을 빼라.

Alternatives
GJK가 충돌을 탐지한 후에 충돌 정보를 결정하기 위해 EPA 사용하는 것에 대한 대안이 있다. 나는 여기에서 하나를 언급할 것이다: sampling for the smallest penetration.

방향들의 한 sample을 생성해라. 각 방향을 따라서 원점에서 그 Minkowski Difference의 표면으로 가는 거리를 찾아라 (우리가 EPA에서 하는 것 처럼). 가장 작은 거리를 갖는 것을 사용해라.

이것은 명백히 정확한 답 대신에 추정이다. 그러나, 그것은 방향의 지능적인 선택으로 개선되어질 수 있다.

• 고르게 단위 원/구에 따라 방향을 분산시켜라
• 좀 더 많은 방향을 사용해라
• 각 도형의 edge normals를 사용해라
• 도형들의 중심끼리로 가는 벡터를 사용해라
• 등

낮은 vertex count polygons들에 대해, 이것은 좀 더 많은 작업처럼 보일지 모르지만, 많은 vertex count polyhedrons에 대해, 그것이 EPA보다 더 빠르고, 여전히 수용할만한 결과를 만들어낼 수 있다.

위의 EPA 구현은 새로운 simplex가 추가 될 때 마다 22개의 연산을 추가한다. Minkowski Difference가 많은 정점을 가지거나 곡선의 변을 가질 때 이것은 중요하다.