GJK (Gilbert-Johnson-Keerthi)
오늘 나는 dyn4J 프로젝트에 들어간 다른 충돌 탐지 알고리즘에 대해 말할 것이다. 너는 많은 GJK 문서를 찾을 수 있지만, 그것의 대부분은 대개 기술적이다. 왜냐하면 그것들은 논문이기 때문이다. 나는 강하게 이 비디오 튜토리얼을 추천한다. 솔직히 너는 심지어 보고난 후에 읽을 필요조찿도 없다. 그러나 만약 너가 그 비디오를 본 후에 좀 더 많은 정보가 필요하다고 느끼면, 다음을 읽어라.
- Introduction
- Convexity
- Minkowski Sum
- The Simplex
- The Support Function
- Creating The Simplex
- Determining Collision
- Iteration
- Checking The Simplex
Introduction
SAT와 같이, GJK는 오직 볼록 도형에 대해서만 작동한다. GJK의 좀 더 매력적인 특징 중의 하나는 그것이 "support function"을 (우리는 이것을 나중에 이야기 할 것이다) 구현하는 어떤 도형이든 지원할 수 있다는 것이다. 그러므로, SAT와 다르게, 너는 곡선 도형을 다룰 필요가 없다. 예를들어, 특별한 코드 또는 알고리즘들을 사용해서.
GJK는 iterative method이지만, 매우 빠르게 수렴하고, 만약 마지막 관통/분리 벡터로 준비된다면, 거의 상수 시간에 작동할 수 있다. SAT가 검사해야 하는 축들의 개수 때문에 3D 환경에서 SAT보다 더 좋은 대안이다.
GJK의 원래 의도는 두 볼록 도형 사이의 거리를 결정짓는 것이였다. GJK는 또한 작은 관통에 대한 충돌 정보를 반환하기 위해 사용될 수 있고, 더운 깊은 관통에 대한 다른 알고리즘에 의해 보충되어 질 수 있다.
Convexity
내가 이전에 말했듯이, GJK는 convex shapes와 함께 사용되어질 수 있는 알고리즘이다. convexity에 대한 설명은 SAT에서의 나의 글을 보아라.
Minkowski Sum
GJK 알고리즘은 크게 Minkowski Sum이라고 불리는 한 개념에 의존한다. 그 Minkowski Sum은 개념적으로 이해하기에 매우 쉽다. 너가 두 도형을 가지고 있다고 가정하자, 그러한 도형들의 Minkowski Sum은 shape 1에 있는 모든 점에 shape 2에 있는 모든 점을 더하는 것이다:
만약 두 도형이 볼록하다면, 그 최종 도형은 볼록이다.
너는 아마 "그래, 훌륭하지만, 이게 무슨 상관이 있는데?"라고 생각하는 중일 것이다. 그 중요성은 덧셈이 있지 않지만, 만약 우리가 빼기를 하는 것을 선택한다면:
우리가 계속하기 전에 부가 메모로서, 우리가 "difference(차)" 연산자를 사용하고 있을 지라도, 이것은 Minkowski Difference라고 불려지지 않고, 대신에 여전히 Minkowski Sum이다. 자료의 remainder에 대해, 나는 이것은 명료성을 위해 Minkowski Difference로 언급할 것이다.
계속 나아가서, Minkowski Sum에서 뺄셈 연산을 하는 이유는 :
만약 두 도형이 겹치거나/교차하거 있다면, Minkowski Difference will contain the "origin"
한 예제를 봐보자, 그림 1에서 두 도형을 취하고, 그것들에 대해 Minkowski 차를 수행해라. 그러면 너는 그림 2에서의 도형을 얻을 것이다. 최종 도형이 원점을 포함하는 것에 유의해라. 이것은 그 도형들이 교차하고 있기 때문이다.
이제 이 연산을 수행하는 것은 shape1.vertices.size * shape2.vertices.size * 2 subtractions을 요구했다. 한 도형이 무한 개의 점들로 구성되어있기 때문에 이것은 중요하다. 두 도형들은 볼록이고 바깥의 정점들로 정의되기 때문에, 우리는 오직 그 정점에 대해서만 이 연산을 수행할 필요가 있다. GJK에 대해 훌륭한 것은 너는 실제로 Minkowski Difference를 계산할 필요가 없다는 것이다.
The Simplex
우리는 Minkowski Difference를 연산하길 원하지 않는다. 대신에, 우리는 그냥 Minkowski Difference가 원점을 포함하는지를 알고 싶다. 만약 그렇다면, 그러면 우리는 그 도형들이 교차하고 있는지를 알고, 그렇지 않다면 그것들은 교차하고 있지 않다.
대신에 우리가 할 수 있는 것은 반복적으로 원점을 감싸려고 시도하는 Minkowski Difference안의 도형을 만드는 것이다. 만약 우리가 만든 그 도형이 원점을 포함한다면 (그리고 Minkowski Difference에 포함된다면) 그러면 우리는 Minkowski Difference가 원점을 포함한다고 말할 수 있다. 우리가 구성하고 싶은 이 도형은 Simplex라고 불려진다.
The Support Function
그래서 다음 질문은 우리가 어떻게 Simplex를 구성하는가 이다. 그 Simplex는 소위 Support Function이라고 불리는 것을 사용하여 만들어진다. support function은 두 도형이 주어지면 Minkowski Difference 안의 한 점을 반환해야 한다. 우리는 이미 shape1로부터 한 점을 취할 수 있고 shape2로부터 한 점을 취하고, Minkowski Difference에서 한 점을 얻기 위해 그것들을 뺄 수 있는 것을 알지만, 우리는 그것이 매번 같은 점이 되길 원하지 않는다.
만약 support function이 방향에 의존하게 만든다면, support function에 대한 매번 호출마다 같은 점을 얻지 않도록 보장할 수 있다. 다시 말해서, 만약 그 support function이 어떤 방향의 가장 멀리 있는 점을 반환한다면, 우리는 다른 점을 얻기위해 나중에 다른 방향을 선택할 수 있다.
한 방향에서 가장 멀리 있는 점을 선택하는 것은 중요성을 갖는다. 왜냐하면 그것이 최대 넓이 구역을 포함하는 한 simplex를 만들기 때문이다. 그러므로 알고리즘이 빨리 종료되는 가능성을 증가시킨다. 게다가, 우리는 이 방식으로 반환되는 모든 점들이 Minkowski Difference의 변에 있다는 사실을 사용할 수 있다. 그러므로 만약 우리가 어떤 방향을 따라 원점을 지나는 한 점을 추가할 수 없다면, 우리는 Minkowski Difference가 그 원점을 포함하지 않는다는 것을 안다. 이 것은 교차하지 않는 경우에 그 알고리즘이 빠르게 끝나는 가능성을 증가시킨다.
Point support(Shape shape1, Shape shape2, Vector d) { // d is a vector direction (doesn't have to be normalized) Point p1 = shape1.getFarthestPointInDirection(d); Point p2 = shape2.getFarthestPointInDirection(d.negative()); // perform the Minkowski Difference Point p3 = p1.subtract(p2); // pe is now a point in Minkowski space on the edge of the Minkowski Difference return p3; }
Creating The Simplex
한 예제로 시작해보자. 그림 2에서 도형을 사용하고, support function을 3번 수행하여:
처음에 d = (1,0)을 사용하여 시작해보자
p1 = (9, 9);
p2 = (5, 7);
p3 = p1 - p2 = (4, 2);
다음으로 d = (-1, 0)을 사용하자.
p1 = (4, 5);
p2 = (12, 7);
p3 = p1 - p2 = (-8, -2);
p1이 (4, 5) 또는 (4, 11)을 가질 수 있다는 것을 유의해라. 둘 다 Minkowski Difference의 변에서 한 점을 만들어 낼 것이다.
다음으로 d = (0,1)을 사용하자
p1 = (4, 11);
p2 = (10, 2);
p3 = p1 - p2 = (-6, 9);
우리는 그림 3에서 그려지는 Simplex를 얻는다.
Determining Collision
우리는 이전에 우리가 Minkowski Difference에서의 simplex가 원점을 포함한다면 두 도형들이 교차하고 있다는 것을 ㅇ나다고 말했었다. 그림 3에서, 그 Simplex는 원점을 포함하지 않지만, 우리는 그 두 도형이 교차하고 있다는 것을 안다. 그 문제는 여기에서, 우리의 첫 번 쨰 추측 (방향을 고르는)이 원점을 감싸는 Simplex를 만들지 않았다는 것이다.
만약 대신에 내가 d = (0, -1)을 세 번째 Minkowski Difference direction으로 선택했다면:
p1 = (4, 5);
p2 = (5, 7);
p3 = p1 - p2 = (-1, -2);
이것은 그림 4에서 보여지는 simplex를 만들어낸다. 그리고 이제 우리는 원점을 포함하고 충돌이 있다는 것을 결정할 수 있다.
그래서 우리가 보았듯이, 방향의 선택은 결과에 영향을 미칠 수 있다. 우리는 또한 만약 우리가 원점을 포함하지 않는 Simplex를 포함한다면, 우리가 또 다른 점을 계산할 수 있고, 그것을 대신에 사용할 수 있다는 것을 볼 수 있다.
이것이 알고리즘의 iterative part가 들어오는 지점이다. 우리는 우리가 선택한 처음 세 개의 점들이 원점을 포함하는지 또는 우리가 Minkowski Difference가 원점을 포함하는지를 보장할 수가 없다. 우리는 원점 방향에 있는 점들만을 선택하여 점을 선택하는 방식을 수정할 수 있다. 만약 우리가 세 번째 Minkowski Difference point를 선택하는 방식을 바꾼다면, 우리는 원점을 포함할 수 있다.
d = ...
a = support(. . ., d)
d = ...
b = support(. . ., d)
AB = b - a
AO = ORIGIN - a
d = (AB X AO) X AB
c = support(. . ., d)
c가 사용할 d가 직선을 만드는 a와 b에 의존하기 때문에, 우리는 반대 방향을 사용해서 가능한 멀리 가도록 b를 선택할 수 있다:
d = ...
a = support(. . ., d)
b = support(. . ., -d)
AB = b - a
AO = ORIGIN - a
d = (AB X AO) X AB
c = support(. . ., d)
그래서 이제 우리는 오직 첫 번째 Minkowksi Difference point에 대해 d만을 선택할 필요가 있다. 여기에 많은 옵션들, 임의의 방향, 도형의 중심의 차이에 의해 만들어지는 방향들이 등등이 있다. 어떤 것을 작동할것이지만 어떤 것은 좀 더 최적이다.
NOTE : AB는 점 A에서 점B를 나타낸다. 그리고 이것은 A-B가 아닌 B-A로 찾아진다. 이것은 이 글의 나머지에도 유효하다. AO, AC, 등등. 모든 것이 이 형식을 따른다.
Iteration
우리는 충돌을 결정하기 위해 위에서 바꾸었을지라도, 우리는 여전히 그러한 세 단계에서 원점을 포함하는 Simplex를 얻지 못한다. 우리는 반복적으로 그 심플레스가 원점을 포함하게 가까워지도록 Simplex를 만들어야 한다.우리는 또한 그 방법에 따라 두 조건을 확인할 필요가 있다: 1) 그 현재 simplex는 원점을 포함하는가? 2) 우리가 원점을 감쌀 수 있는가?
iterative algorithm의 골격을 봐보자:
Vector d = // choose a search direction // get the first Minkowski Difference point Simplex.add(support(A, B, d)); // negate d for the next point d.negate(); // start looping while (true) { // add a new point to the simplex because we haven't terminated yet Simplex.add(support(A, B, d)); // makes sure that the last point we added actually passed the origin if (Simplex.getLast().dot(d) <= 0) { // if the point added last was not past the origin in the direction of d // then the Minkowski sum cannot possibly contain the origin since // the last point added is on the edge of the Minkowski Difference return false; } else { // otherwise we need to determine if the origin is in // the current simplex if (Simplex.contains(ORIGIN)) { // if it does then we know there is a collision return true; } else { // otherwise we cannot be certain so find the edge who is // closest to the origin and use its normal (in the direction // of the origin) as the new d and continue the loop d = getDirection(Simplex); } } }
다음으로 그림 1에서의 우리의 예제와 함께 그 골격을 사용해보자. 우리의 초기 방향을 도형 1의 중심에서 도형 2의 중심 방향으로 정하자:
d = c2 - c1 = (1, -1)
p1 = support(A, B, d) = (4, 2)
Simplex.add(p1);
d.negate() = (-1, 1);
그러고나서 루프를 시작한다:
Iteration 1
다음의 triple product expansion이 사용된다:
(A x B) x C = B(C.dot(A)) - A(C.dot(B)) triple product를 평가하기 위해
그림 5는 iteration 1 이후의 최종 simplex를 보여준다. 우리는 원점을 향하고 있고 그 선분에 수직인 다음 방향을 가진 선분 simplex를 가지고 있다. 한 가지 노트, 그 방향을 표준화 될 필요 없다 (iteration 2를 보아라) 그러나 나는 그것을 여기에서 할 것이다. 그래서 우리는 우리의 크기 대로 그 방향을 확인할 수 있다
Iteration 2
두 번의 iteration 후에, 우리는 아직 그 원점을 감싸지 못했지만,여전히 그 도형들이 흥미롭지 않다고 결론지을 수 없다. 두 번째 반복에서, 우리는 (-6, 9) 점을 제거했다. 왜냐하면 우리가 필요한 것은 어떤 시간에서의 3개의 점이기 때문이다. 그리고 우리가 매 반복의 시작에서 새로운 점을 추가했기 때문이다.
Iteration 3
Checking The Simplex
우리는 사진과 직접 검사를 사용하여, 그 알고리즘에서 두 가지 이상의 연산을 대충 보았다. 하나는 어떻게 우리가 현재 simplex가 원점을 포함하는지 아는 방법이고. 다른 하나는 우리가 어떻게 다음 방햑을 선택하는가 이다. 위의 슈도 코드에서, 나는 명확성을 위해서 이러한 연산들을 분리했지만, 실제로 그것들은 함께 있어야만 한다. 왜냐하면 그것들은 같은 정보들을 알 필요가 있기 때문이다.
우리는 그 원점이 simplex와 관련하여 일련의 평면 검사를 수행하여 어디에 놓여있는 지를 결정할 수 있다. 그 평면 검사에서, 각 테스트는 간단한 내적으로 구성된다. 다뤄져야만 하는 첫 번째 케이스는 line segment case이다. 그래서 위의 예제로부터 첫 번째 반복을 봐보자. line 9에서 두 번째 점을 추가한 후에, 그 simplex는 이제 선분이다. 우리가 Voronoi regions을 검사하여 (그림 8 참조) 그 simplex가 원점을 포함하는 지를 결정할 수 있다.
그 선분은 A에서 B로 정의되어있다. 거기에서 A는 그 simplex에 추가된 마지막 점이다. 우리는 A와 B 둘 다 Minkowski Difference의 변 위에 있다는 것을 알고, 그러므로 그 원점은 R1 또는 R4에 있지 않다는 것을 안다. 우리는 이 가정을 할 수가 있는데, line 11에서의 check가 false를 반환헀었기 때문이다. 이것은 우리가 우리의 다음 점을 얻을 때 우리가 원점을 지난다는 것을 가리킨다.
{ Simplex.getLast().dot(d) <= 0 에 대한 구체적 설명
https://en.wikipedia.org/wiki/Scalar_projection
https://en.wikipedia.org/wiki/Vector_projection
(위키피디아에서 잘 설명되어있다. Scalar projection을 이용해서 곧 바로 Vector projection을 할 수가 있다)
여기에서 Scalar projection을 이해할 필요가 있다.
두개의 선분이 있다고 해보자. AB는 (3,0)이고,
AO는 (2,4)라고 해보자. 여기서 O는 원점이 아니라 위의 예제를 이해하기 위해서 임의로 그렇게 설정한 것이다.
좌표계에 저 두 벡터를 그리고, AO 벡터를 AB 벡터에 사영시킨다고 해보자.
사영시킨다는 말은 AO벡터가 AB방향을 향하도록 하고, AO벡터의 길이는 그대로 유지하는 것을 말한다.
그러므로 구하고자 하는 것은 AO벡터가 AB방향을 바라볼 때의 길이 이다.
이 구하고자 하는 것을 x라 칭하겠다.
우리는 두 벡터 사이에 각이 생긴다는 것을 볼 수 있고,
AO벡터의 끝점에서 AB벡터로 수직으로 선분을 그으면 삼각형이 생기고
그 삼각형의 밑변이 우리가 고하고자 하는 x가 된다.
AO벡터를 빗변으로 해서
cosθ를 한다면 ( x / AO벡터의 길이 ) 가 된다는 것을 알 수 있다.
그래서 이 cosθ에 AO벡터의 길이를 곱한다면 x가 된다.
근데 중요한 것은 내적(AB, AO)를 하게 된다면
내적(AB, AO) = |AB| |AO| cosθ 가 된다는 것이다.
그래서 두 벡터가 단위벡터가 아니라면,
(내적(AB, AO) / |AB| |AO|) * |AO| = cosθ * |AO|
좌변의 식으로 계산을 할 수 있다. (여기에다가 AB의 단위벡터를 곱하면, 벡터 사영이 된다.)
그러면 여기에서 식을 좀 더 최적화할 수 있는 것이 생긴다.
만약 AB벡터가 단위벡터라면 |AB|가 1이되고,
단순히 내적을 한 것이,
내적(AB, AO) = |AB| |AO| cosθ = 1 * |AO| cosθ = cosθ * |AO|
가 된다. 그래서 사영시킬 방향 벡터가 단위길이라면,
내적을 취하는 것만으로도 x를 구할 수 있는 것이다.
이제 이 과정을 이해했다면, 우리는 위의 코드에서 왜 내적을 취해서
마지막점이 원점을 지나는지를 확인할 수 있다.
정확히는 사영시켰을 때 원점이 Minkowski Difference 도형안에 있는지를 보는 것이다.
Minkowski Difference를 해서 생기는 선분만을 생각해 보아라.
그리고 그 생긴 선분에서의 마지막점과 원점을 이어라.
그러면 우리가 위에서 scalar projection과 공부했던 것과
똑같은 도형이 생긴다. 그래서 선분의 방향은 단위벡터이기 때문에
내적을 취하는 것만으로도, 그 원점으로 향해있는 벡터가, 그 선분에
사영되는지 확인할 수 있다.
내적을 취해서 양의 값이 나온다면, 그어진 선분위에 사영이 될 수 있다는 것이다.
내적을 취해서 음의 값이 나온다면, 그어진 선분뒤에(그려지지 않은 곳)에 사영이 된다는 것이다.
이것은 위의 예시를 들어서도 설명이 이해가 된다.
(1,0)이 방향벡터라하고,
(-2, -4)라는 방향벡터가 있다고해보자.
그렇다면 (-2, -4)를 (1,0)에 사영시키려고 할 때, 그어진 선분뒤에 (그려지지 않은 곳)에 사영을 시켜야 된다.
그래서 Minkowski Difference를 통해서 내적이 음수값이 나온다면, 그 도형은 원점을 포함할 수 없는 상태가 되는 것이다.
}
그 원점은 오직 R2 또는 R3에서만 놓여 있을 수 있다. 그리고 한 선분은 원점을 포함할 수 없기 때문에, 처리될 필요가 있는 모든 것은 하나의 새로운 방향을 고르는 것이다. 이것은 이전에 명시되었듯이, 원점 방향으로의 AB의 수직화를 사용해서 될 ㅜㅅ 있다.
// the perp of AB in the direction of O can be found by
AB = B - A;
AO = O - A;
perp = (AB x AO) x AB;
(여기에서 중요한 것은 O가 그 선에 있을 때 무엇이 발생하는 가 이다. 만약 그것이 발생한다면, 그 perp는 영벡터가 될 것이고, line 11에서의 실패를 불러올 것이다. 이것은 두 장소들에서 발생할 수 있다: 1) Minkowski Sum 그리고, 2) Minkowski Sum의 edge에서. 후자의 케이스는 관통이라기 보다는 접촉 점을 가리킨다. 그래서 너는 이것이 충돌로 고려되어야 할지 말지를 결정할 필요가 있을 것이다. 둘 중 하나의 경우에, 너는 AB의 왼손 또는 오른손 좌표계 방향을 새로운 방향으로서 사용할 수 있다.)
이제, 두 번째 iteration을 검사해보자. 두 번쨰 iteration은 우리의 simplex를 삼각형으로 바꾼다. (그림 9)
그 하얀색 지역은 검사될 필요가 없다. line 11에서 체크를 통과했기 때문에 각 점이 추가된 이후로 그 원점이 그러한 점들을 지날 수 없기 때문이다. R2는 원점을 포함할 수 없다. 왜냐하면 우리가 선택한 마지막 방향이 반대방향에 있었기 때문이다. 그래서 테스트할 유일한 지역은 R3, R4, 그리고 R5이다. 우리는 AB에 수직한 벡터를 만들어 내기 위해서 (AC x AB) x AB를 수행할 수 있다. 그러고나서 우리는 그 원점이 R4 영역에 있는지 결정하기 위해 ABPerp.dot(AO) 를 수행한다.
그래서 한 번 더 테스트하여, 우리는 원점이 어디에 있는지를 결정할 수 있다.
그래서 우리는 원점이 R3에 있다는 것을 발견했다. 그래서 이제 우리는 우리가 우리의 그 방향으로 다음의 Minkowski Difference 점을 얻을 수 있도록 한 방향을 고를 필요가 있다. 이것은 쉽다. 왜냐하면 우리는 AC가 선분인 것을 아는데, 원점이 그 선분의 Voronoi region에 있다는 것을 알기 때문이다.
(AC x AO) x AC
그리고 우리는 점 A와 C를 사용하기 때문에, 우리는 B를 제거할 수 있다. 그것을 쓰지 않기 때문에. 새로운 코드는..
Vector d = //choose a search direction // get the first Minkowski Difference point Simplex.add(support(A, B,d)); // negate d for the next point d.negate(); // start looping while (true) { // add a new point to the simplex because we haven't terminated yet Simplex.add(support(A,B,d)); // make sure that the last point we added actually passed the origin if (Simplex.getLast().dot(d) <= 0) { // if the point added last was not past the origin in the direction of d // then the Minkowski Sum cannot possibly contain the origin since // the last point added is on the edge of the Minkowski Differnce return false; } else { // otherwise we need to determine if the origin is in // the current simplex if(containOrigin(Simplex, d) { return true; } } } bool containOrigin(Simplex s, Vector d) { // get the last point added to the simplex a = Simplex.getLast(); // compute AO (same thing as - A) ao = a.negate(); if (s.points.size() == 3) { // then its the triangle case // get b and c b = Simplex.getB(); c = Simplex.getC(); // compute the edges ab = b - a; ac = c - a; // compute the normals abPerp = tripleProduct(ac, ab, ab); acPerp = tripleProduct(ab, ac, ac); // is the origin in R4 if(abPerp.dot(ao) > 0) { // remove point c s.remove(c); // set the new direction to abPerp d.set(abPerp); } else { // is the origin in R3 if(acPerp.dot(ao) > 0) { // remove point b s.remove(b); // set the new diretion to acPerp d.set(acPerp); } else { // otherwise we know its in R5 so we can return true return true; } } } else { // then its the line segment case b = Simplex.getB(); // compute AB // get the perp to AB in the direction of the origin abPerp = tripleProduct(ab, ao, ab); // set the direction to abPerp d.set(abPerp); } return false; }
이것이 GJK 충돌 탐지 알고리즘의 튜토리얼을 완료시킨다. 원래의 GJK 알고리즘은 두 볼록 도형 사이의 거리를 연산했었다. 나는 다른 포스트에서 그 알고리즘의 이 부분을 다룰 계획이다. 왜냐하면 이 포스트가 이미 너무 길기 때문이다. 또한, 내가 이전에 말했듯이, 만약 너가 충돌 정보 (normal and depth)가 필요하다면, 너는 GJK 알고리즘을 수정하고, 그것에 다른 알고리즘을 보충할 필요가 있다. EPA는 다른 포스트에서 내가 다룰 계획인 하나의 보충 알고리즘이다.
댓글 없음:
댓글 쓰기