Post Lists

2018년 8월 31일 금요일

GJK - Distance & Closest Points

http://www.dyn4j.org/2010/04/gjk-distance-closest-points/

GJK - Distance & Closest Points
이전 편은 충돌 탐지에 속하는 GJK 알고리즘에 대해 이야기 했었다. 그 원래 알고리즘은 실제로 두 볼록 도형 사이의 거리와 가장 가까운 점들을 얻기위해 사용된다.


  1. Introduction
  2. Overview
  3. Minkowski Sum
  4. The Distance
  5. Iteration
  6. Closest Points
  7. Convex Combination
Introduction
그 알고리즘은 도형 사이의 거리를 결정하기 위해서 같은 개념 대부분을 사용한다. 그 알고리즘은 반복적이고, Minkowski Sum/Difference를 사용하고, 원점을 찾고, 같은 support 함수를 사용한다.

Overview
우리는 만약 그 도형들이 충돌하고 있지 않다면 그 Minkowski Difference는 원점을 포함하지 않는다는 것을 안다. 그러므로, 원점을 simplex로 반복적으로 감싸려고 하는 댇신에, 우리는 원점에 가장 가까운 simplex를 생성하길 원할 것이다. 그 가장 가까운 simplex는 항상 Minkowski Difference의 edge위에 있을 것이다. 2D에 대해 가장 가까운 simplex는 단일점 또는 한 직선이다.

Minkowski Sum
우리가 이전 글에서 GJK의 충돌 탐지 부분에서 했던 것 처럼, 그 알고리즘은 또한 Minkowski Sum을 알 필요가 있따 (Difference는 내가 그것을 부르는 것이다. GJK 글을 보아라).

GJK 글에서 같은 도형을 취하고 그것들을 분리하는 것 (그림 1) 다소 평행이동만된 같은 Minkowski Difference와 같은 것을 만들어낸다 (그림2). 우리는 원점이 Minkowski Difference내에서 포함되지 않는 것을 유의해야한다. 그러므로, 충돌은 없다.

The Distance
그 거리는 Minkowski Difference에서 원점에 대해 가장 가까운 점을 발견하여 계산되어질 수 있다. 그 거리는 가장 가까운 점의 크기가 된다. 검사에 의해, 우리는 점 (-4, -1)과 (1,3) 점에 의해 만들어지는 변이 그 원점에 가장 가까운 특징이라는 것을 알 수 있다. 자연스럽게, 그 원점에 가장 가까운 점은 이 변 위에 있는 점이고, 이것은 그 원점과 90도를 만든다. 우리는 그 점을 다음과 같이 계산할 수 있다.


A = (-4, -1)
B = (1, 3)
// create the line
AB = (1, 3) - (-4, -1) = (5, 4)
AO = (0, 0) - (-4, -1) = (4, 1)
// project AO onto AB
AO.dot(AB) = 4 * 5 + 1 * 4 = 24
// get the length squared
AB.dot(AB) = 5 * 5 + 4 * 4 = 41
// calculate the distance along AB
t = 24 / 41
// calculate the point
AB.mult(t).add(A) = (120 / 41, 96 / 41) + (-4, -1)
                  = (-44 / 41, 55 / 41)
                  ≈ (-1.07, 1.34)
d = (-1.07, 1.34).magnitude() ≈ 1.71
{
여기에서 한 직선의 원점과의 거리를 왜 이렇게 구하는지 알 필요가 있다.
AO를 AB에 scalar projection을 한다. 그러면 그 삼각형에서 원점과 가장 가까운 거리가 나오는 점까지의 거리를 알게된다.
그리고, AB전체 길이에서, 그 사영시킨 거리의 비율을 구하면(t = 24/41부분, 그러니까 사영시킨 거리/전체 AB의 길이), AB벡터가 A에서 출발하여 얼마만큼 가야 그 가장 가까운 점이 나오는지를 알 수 있게 된다.

그래서 최종적으로 A 점에다가, AB벡터를 t로 스케일링한 것을 더해주면 원하는 점이 나오고. 크기를 구하면 가장 가까운 거리를 구할 수 있다.
}

Iteration
GJK의 충돌 탐지 루틴처럼, 그 거리 루틴은 반복적이다( 그리고 거의 그 문제와 동일하다). 우리는 반복적으로 Minkowski Difference에서 원점으로 가는 가장 가까운 점을 포함하는 simplex를 만들 필요가 있다. 그 점들은 support function을 사용하여 방향을 선택하는 것과 같은 방법을 사용하여 획득될 것이다. 그리고 그 종료 케이스도 검사한다.

몇 가지 슈도 코드를 봐보자:


// exactly like the previoous post, use whatever
// initial direction you want, some are more optimal
d = // choose a direction
// obtain the first Minkowski Difference point using
// the direction and the support function
Simplex.add(support(A,B,d));
// like the previous post just negate the
// the previous direction to get the next point
Simplex.add(support(A,B,-d));
// obtain the point on the current simplex closest
// to the origin (see above example)
// start the loop
d = ClosestPointToOrigin(Simplex.a, Simplex.b);
while(true)
{
    // the direction we get from the closest point is pointing
    // from the origin to the closest point, we need to reverse
    // it so that it points towards the origin
    d.negate();
    // check if d is the zero vector
    if(d.isZero())
    {
        // then the origin is on the Minkowski Difference
        // I consider this touching/collision
        return false;
    }
    // obtain a new Minkowski Difference point along
    // the new direction
    c = support(A, B, d);
    // is the point we obtained making progress
    // toward the goal (to get the closest points
    // to the origin)
    double dc = c.dot(d);
    // you can use a or b here it doesn't matter
    // since they will be equally distant from 
    // the origin
    double da = Simplex.a.dot(d);
    // tolerance is how accurate you want to be
    if(dc - da < tolerance)
    {
        // if we haven't made enough progress,
        // given some tolerance, to the origin,
        // then we can assume that we are done
        
        // NOTE: to get the correct distance we
        // need to normalize d then dot it with
        // a or c
        // OR since we know that d is the closest
        // point to the origin, we can just get
        // its magnitude
        distance = d.magnitude();
        return true;
    }
    // if we are still getting closer then only keep
    // the points in the simplex that are closest to
    // the origin (we already know that is closer
    // than both a and b so we only need to choose
    // between these two)
    p1 = ClosestPointToOrigin(Simplex.a, c);
    p2 = ClosestPointToOrigin(c, Simplex.b);
    // getting the closest point on the edges AC and
    // CB allows us to compare the distance between
    // the origin and edge and choose the closer one
    if(p1.magnitude() < p2.magnitude())
    {
        Simplex.b = c;
        d = p1;
    }
    else
    {
        Simplex.a = c;
        d = p2;
    }
}

처음 몇 가지 라인들이 이전의 GJK 글과 많이 닮아 보인다. 차이점은 우리의 simplex의 구성이다. 우리는 한 simplex의 같은 아이디어를 사용하고있다. 우리는 같은 support function을 사용하고, 대강 같은 로직을 사용한다. 그러나, 우리는 오직 항상 2개의 점만을 유지한다 (3D에서는 3개의 점) 그리고 우리는 원점이 놓여있는 Voronoi region을 찾는 대신에 원점에 가장 가까운 simplex에 있는 점을 찾는다.

우리가 이전 글에서 했던 것처럼, 이것은 예제를 통해서 가장 잘 설명된다. 그림 1에서 위의 예제를 봐보고, 반복을 해보자.

Pre Iteration:
Iteration 1:
이 첫 번째 반복에서, 나는 p를 계산하는 문제를 하지 않았다. 왜냐하면 그것은 명백히 그 끝점 a로 가고있기 때문이다. 만약 너가 코드가 하는 것처럼 그 진짜 계산을 한다면, 너는 같은 결과를 얻을 것이다. 우리는 가장 가까운 점이 그 simplex위에 있는 점일지라도, 우리가 그것을 다음 방향으로 여전히 사용할 수 있다는 것을 유의해야 한다. 우리는 새로운 방향을 사용하여 새로운 점을 얻고 그 두 개의 가장 가까운 점을 유지한다.

Iteraion 2:
우리의 simplex가 원점에 가까워지고 있다는 것에 유의해라,

Iteration 3:
iteration 3에서 d는 원점에 가장 가까운 점이고, 우리가 Distance section에서 찾은 점과 같다는 것에 유의해라.

우리가 종료할 때, 그 사영한 것의 차이는 0이였다는 것의 유의해라. 이것은 오직 두 개의 폴리곤들과 발생할 수 있다. 만약 A또는 B가 곡선을 가진 변이 있는 도형이라면, 사영에서의 차는 0에 다다르지만, 0을 얻지 못할것이다. 그러므로, 우리는 곡선의 도형을 다루기 위해 tolerance를 사용한다. 그 tolerance가 도형들을 위해 작동할 것이기 때문이다.

곡선의 도형들이 만들어내는 또 다른 문제는, 만약 그 선택된 tolerance가 충분히 크지 않다면, 그 알고리즘은 결코 끝나지 않을 것이다. 이 경우에 우리는 maximum iterations termination case를 추가한다.

이 알고리즘이 작동시킬 수 있는 한 가지 이상의 문제는, 그 도형들이 실제로 교차하고 있는지이다. 만약 그것들이 교차하고 있다면, 그 알고리즘은 결코 끝나지 않을 것이다. 이것은 큰 문제는 아니다. 대부분 너는 그 도형들이 처음에 어쨋든 충돌하고 있는지를 결정할 것이기 때문이다. 그렇지 않다면, 우리는 원점을 포함하는 simplex에 대해 while문에서 하나의 체크를 추가해야 한다. 이것은 triangle test(2D)에 있는 한 간단한 점에 의해 처리될 수 있다.

Closest Points
두 도형 사이의 거리 외에도, 우리는 또한 도형들에서 가장 가까운 점들을 결정할 수 있다. 이것을 하기 위해서, 우리는 우리가 그 알고리즘을 진행함에 따라 부가 정보를 저장할 필요가 있다. 만약 우리가 Minkowski Difference 점들을 만들기 위해 사용되는 도형들의 점을 저장한다면, 우리는 가장 가까운 점들을 결정하기 위해 나중에 그것들을 사용할 수 있다.

예를들어, 우리는 위에서 Minkowski Diffrence points A = (1,3) and B = (-4, -1)로 종료했다. 이러한 점들은 그것들의 각각 도형에서 다음의 점에 의해서 만들어진다.

A (9,9)  (8,6) = (1,3)
B (4,5)  (8,6) = (-4, -1)

Minkowski Difference points를 만들기 위해 사용되는 그 점들은 필수적으로 가장 가까운 점이 아니다. 그러나, 이러한 source points를 사용하여 우리는 가장 가까운 점들을 계산할 수 있다.

Convex Combination
우리는 A와 B의 점들이 정확한 가장 가까운 점이 아니라는 것을 안다. 조사에 의해, 우리는 B에서 가장 가까운 점은 (8,6)이고 A에서 가장 가까운 점은 (6.75, 7.25)라는 것을 알 수 있다. 우리는 가장 가까운 점을 얻기위해 몇 가지 계산을 해야만한다. 여기에서 Convex Combination의 정의가 들어온다.






우리는 우리가 찾으려고 시도하는 점들이 simplex위에 있을 것이라는 것을 보장할 수 있다. 왜냐하면 모든 convex combinations는 집합 S의 convex hull내에 있기 때문이다. 람다 계수에 대해 어떤 양수 값은 우리가 simplex의 경계를 넘어가지 않도록 보장한다. 그러나 labmda에 대한 값을 찾기 위해서, 우리는 또 다른 방정식이 필요할 것이다.

우리의 2D 예제는 이것처럼 보일 것이다:



이제, 만약 우리가 Q가 종료 simplex에서 원점에 가장 가까운 점이라고 한다면, 그러고나서 우리는 Q에서 원점으로가는 벡터가 Q에 놓여있는 선분에 수직이여야만 한다는 것을 안다.




만약 우리가 얻은 Q를 바꾼다면:


{
여기에서 L은 B-A을 해서 얻어진 벡터인다. 이 벡터위에 Q가 놓여있다.
그래서 Q와 L은 수직이므로 내적을 하면 0이라는 것을 얻게된다.
근데 Q벡터는 , A B점의 convex combination으로 얻을 수 있게 된다.
https://www.youtube.com/watch?v=6N_caSzNpkc
이 동영상을 보면 정확히 무엇에 대한 건지 이해할 수 있다.
}

우리는 lambda_1과 lambda_2에 대해 풀필요가 있지만, 그렇게 하기 위해서 우리는 두 개의 방정식이 필요하다. 두 번째 방정식은 convex combination의 정의의 다른 부분에서 온다:

lambda_1 + lambda_2 = 1

그 연립방정식을 풀어서 우리는 다음을 얻는다:





















만약 우리가 이 연산을 우리의 위의 예제에 수행한다면, 우리는 다음을 얻는다:

lambda_1과 lambda_2를 계산한 후에, 우리는 convex combination의 정의를 또 다시 사용하여 가장 가까운 점을 계산할 수 있다. 그러나 Minkowski Difference points를 구성한 그 점들을 사용하여:






우리가 볼 수 있듯이, 우리는 가장 가까운 점들을 계산했다!

그러나 여기에서 우리가 해결해야만 하는 두 개의 문제가 있다.

첫 째로, 만약 Minkowski Difference points들 A와 B가 같다면, 그러면 L은 영벡터가 될 것이다. 이것은 나중에 우리가 L의 크기로 나눌 때, 우리가 0으로 나눌 거라는 것을 의미한다: 좋지 않다. 이것이 의미하는 것은, 그 원점에 가장 가까운 점이, Minkowski Difference의 변위에 있지 않고, 한 점에 있다는 것이다. 이 때문에, A와 B 둘 다를 만들었던 support points들은 같다. 그러므로 너는 A 또는 B의 support points를 반환할 수 있다:

if(L.isZero())
{
   Aclosest = A.s1;
   Bclosest = A.s2;
}

두 번째 문제는, lambda_1 또는 lambda_2 둘 중 하나가 음수 일 때 발생한다. convex hull의 정의에 따르면, lambda는 0보다 더 커야만 한다. 만약 labmda가 음수라면, 이것은 우리에게 다른 Minkowski Difference point의 support points가 가장 가까운 점이라는 것을 말해준다:

if(lambda1 < 0)
{
    Aclosest = B.s1;
    Bclosest = B.s2;
}
else if(labmda2 < 0)
{
   Aclosest = A.s1;
   Bclosest = A.d2;
}













시간:
라벨:

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)