비디오 게임 물리학 튜토리얼 - 2부: 고체 물체에 대한 충돌 감지

이것은 비디오 게임 물리학에 대한 3부작 시리즈의 2부입니다. 이 시리즈의 나머지 부분은 다음을 참조하세요.

1부: 강체 역학 소개
파트 III: 구속된 강체 시뮬레이션

이 시리즈의 1부에서 우리는 강체와 그 운동을 탐구했습니다. 그러나 해당 토론에서 개체는 서로 상호 작용하지 않았습니다. 몇 가지 추가 작업 없이 시뮬레이션된 강체는 서로를 관통하거나 "상호 침투"할 수 있으며, 이는 대부분의 경우 바람직하지 않습니다.

고체 물체의 거동을 보다 사실적으로 시뮬레이션하려면 물체가 움직일 때마다 충돌하는지 확인해야 하며 충돌할 경우 속도를 변경하는 힘을 가하는 등의 조치를 취해야 합니다. 그들은 반대 방향으로 움직일 것입니다. 여기서 충돌 물리학을 이해하는 것이 게임 개발자에게 특히 중요합니다.

2부에서는 2D 또는 3D 세계에 흩어져 있을 수 있는 많은 수의 몸체 사이에서 충돌하는 몸체 쌍을 찾는 것으로 구성된 충돌 감지 단계를 다룰 것입니다. 다음이자 마지막 기사에서는 이러한 충돌을 "해결"하여 상호 침투를 제거하는 방법에 대해 자세히 설명합니다.

이 기사에서 언급한 선형 대수학 개념의 복습을 위해 1부의 선형 대수 집중 과정을 참조할 수 있습니다.

비디오 게임의 충돌 물리학

강체 시뮬레이션의 맥락에서 충돌은 두 강체의 모양이 교차하거나 이러한 모양 사이의 거리가 작은 허용 오차 아래로 떨어질 때 발생합니다.

시뮬레이션에 n개의 몸체가 있는 경우 쌍별 테스트로 충돌을 감지하는 계산 복잡성은 O ( n 2 ) 이며, 이는 컴퓨터 과학자를 움츠리게 만드는 숫자입니다. pairwise 테스트의 수는 바디의 수에 따라 2차적으로 증가하며 임의의 위치와 방향에서 두 모양이 충돌하는지 확인하는 것은 이미 저렴하지 않습니다. 충돌 감지 프로세스를 최적화하기 위해 일반적으로 넓은 단계 와 좁은 단계 의 두 단계로 나눕니다.

광범위한 단계는 시뮬레이션에 있는 전체 바디 세트 중에서 잠재적으로 충돌할 수 있는 강체 쌍을 찾고 확실히 충돌하지 않는 쌍을 제외하는 역할을 합니다. 이 단계는 O ( n 2 ) 시간 복잡도 아래에서 잘 유지되도록 하기 위해 강체의 수와 함께 정말 잘 확장될 수 있어야 합니다. 이를 달성하기 위해 이 단계에서는 일반적으로 충돌 상한을 설정하는 경계 볼륨 과 결합된 공간 분할 을 사용합니다.

좁은 위상은 충돌할 수 있는 넓은 위상에서 찾은 강체 쌍에서 작동합니다. 충돌이 실제로 발생하고 있는지 확인하는 개선 단계이며, 발견된 각 충돌에 대해 나중에 충돌을 해결하는 데 사용할 접점을 계산합니다.

다음 섹션에서 우리는 넓은 단계와 좁은 단계에서 사용할 수 있는 몇 가지 알고리즘에 대해 이야기할 것입니다.

넓은 단계

비디오 게임에 대한 충돌 물리학의 광범위한 단계에서 충돌 할 수 있는 강체 쌍을 식별해야 합니다. 이러한 몸체는 다각형 및 다면체와 같은 복잡한 모양을 가질 수 있으며 이를 가속화하기 위해 우리가 할 수 있는 것은 물체를 둘러싸기 위해 더 단순한 모양을 사용하는 것입니다. 이러한 경계 볼륨 이 교차하지 않으면 실제 모양도 교차하지 않습니다. 그들이 교차하면 실제 모양 이 교차할 수 있습니다.

경계 체적의 일부 인기 있는 유형은 방향 경계 상자(OBB), 2D의 원, 3D의 구입니다. 가장 단순한 경계 볼륨 중 하나인 축 정렬 경계 상자(AABB) 를 살펴보겠습니다.

AABB는 단순하고 좋은 절충안을 제공하기 때문에 물리학 프로그래머로부터 많은 사랑을 받습니다. 2차원 AABB는 C 언어에서 다음과 같은 구조체로 나타낼 수 있습니다.

 typedef struct { float x; float y; } Vector2; typedef struct { Vector2 min; Vector2 max; } AABB;

min 필드는 상자의 왼쪽 하단 모서리 위치를 나타내고 max 필드는 오른쪽 상단 모서리를 나타냅니다.

두 개의 AABB가 교차하는지 테스트하려면 해당 투영이 모든 좌표축에서 교차하는지 확인하기만 하면 됩니다.

 BOOL TestAABBOverlap(AABB* a, AABB* b) { float d1x = b->min.x - a->max.x; float d1y = b->min.y - a->max.y; float d2x = a->min.x - b->max.x; float d2y = a->min.y - b->max.y; if (d1x > 0.0f || d1y > 0.0f) return FALSE; if (d2x > 0.0f || d2y > 0.0f) return FALSE; return TRUE; }

이 코드는 Box2D 엔진(버전 2.3.0)의 b2TestOverlap 함수와 동일한 논리를 가지고 있습니다. 두 축에서 두 순서로 두 AABB의 min 과 max 의 차이를 계산합니다. 이 값 중 하나라도 0보다 크면 AABB가 교차하지 않습니다.

AABB 중첩 테스트가 저렴하더라도 여전히 바람직하지 않은 O ( n 2 ) 시간 복잡도가 있기 때문에 가능한 모든 쌍에 대해 쌍별 테스트를 수행하면 별로 도움이 되지 않습니다. AABB 중복 테스트의 수를 최소화하기 위해 일종의 공간 분할 을 사용할 수 있습니다. 이는 쿼리 속도를 높이는 데이터베이스 인덱스와 동일한 원칙에 따라 작동합니다. (PostGIS와 같은 지리 데이터베이스는 실제로 공간 인덱스에 대해 유사한 데이터 구조와 알고리즘을 사용합니다.) 하지만 이 경우 AABB는 지속적으로 이동하므로 일반적으로 시뮬레이션의 모든 단계 후에 인덱스를 다시 생성해야 합니다.

균일 격자, 2D의 쿼드트리, 3D의 옥트리, 공간 해싱과 같이 이를 위해 사용할 수 있는 공간 분할 알고리즘 및 데이터 구조가 많이 있습니다. 두 가지 인기 있는 공간 분할 알고리즘인 정렬 및 스윕과 경계 볼륨 계층 구조(BVH)에 대해 자세히 살펴보겠습니다.

정렬 및 스윕 알고리즘

정렬 및 스윕 방법( 스윕 및 정리라고도 함)은 강체 시뮬레이션에 사용하기 위해 물리 프로그래머가 가장 선호하는 방법 중 하나입니다. 예를 들어 Bullet Physics 엔진은 btAxisSweep3 클래스에 이 메서드를 구현합니다.

단일 좌표축에 대한 하나의 AABB 투영은 기본적으로 간격 [ b , e ] (즉, 시작 및 끝)입니다. 시뮬레이션에서 우리는 많은 강체, 따라서 많은 AABB를 가질 것이며, 이는 많은 간격을 의미합니다. 어떤 구간이 교차하는지 알아내고자 합니다.

정렬 및 스윕 알고리즘에서는 모든 b 및 e 값을 단일 목록에 삽입하고 스칼라 값에 따라 오름차순으로 정렬합니다. 그런 다음 목록을 스윕 하거나 탐색합니다. b 값이 발생할 때마다 해당 간격이 별도의 활성 간격 목록에 저장되고 e 값이 발생할 때마다 해당 간격이 활성 간격 목록에서 제거됩니다. 언제든지 모든 활성 간격이 교차합니다. (자세한 내용은 David Baraff의 Ph. D Thesis, p. 52를 확인하십시오. 이 온라인 도구를 사용하여 포스트스크립트 파일을 볼 것을 제안합니다.) 간격 목록은 시뮬레이션의 각 단계에서 재사용할 수 있으므로 효율적으로 재정렬할 수 있습니다. 이 목록은 거의 정렬된 목록을 정렬하는 데 좋은 삽입 정렬을 사용합니다.

2차원 및 3차원에서 위에서 설명한 대로 단일 좌표축에 대해 정렬 및 스윕을 실행하면 수행해야 하는 직접 AABB 교차 테스트의 수가 줄어들지만 결과는 한 좌표축에서 다른 좌표축보다 더 나을 수 있습니다. 따라서 정렬 및 스윕 알고리즘의 보다 정교한 변형이 구현됩니다. Christer Ericson은 저서 Real-Time Collision Detection (336페이지)에서 모든 AABB를 단일 배열에 저장하고 정렬 및 스윕의 각 실행에 대해 하나의 좌표 축이 선택되고 배열이 다음과 같이 정렬되는 효율적인 변형을 제시합니다. 퀵소트를 사용하여 선택한 축에서 AABB의 min . 그런 다음 어레이를 탐색하고 AABB 중첩 테스트를 수행합니다. 정렬에 사용해야 하는 다음 축을 결정하기 위해 AABB 중심의 분산이 계산되고 분산이 더 큰 축이 다음 단계로 선택됩니다.

동적 경계 토량 트리

또 다른 유용한 공간 분할 방법은 Dbvt 라고도 하는 동적 경계 볼륨 트리 입니다. 이것은 경계 볼륨 계층 의 유형입니다.

Dbvt는 각 노드에 자식의 모든 AABB를 묶는 AABB가 있는 이진 트리입니다. 강체 자체의 AABB는 리프 노드에 있습니다. 일반적으로 Dbvt는 교차로를 감지하려는 AABB를 제공하여 "쿼리"됩니다. 이 작업은 쿼리된 AABB와 교차하지 않는 노드의 자식이 겹치는지 테스트할 필요가 없기 때문에 효율적입니다. 이와 같이 AABB 충돌 쿼리는 루트에서 시작하여 쿼리된 AABB와 교차하는 AABB 노드에 대해서만 트리를 통해 재귀적으로 계속됩니다. AVL 트리에서와 같이 트리 회전을 통해 트리의 균형을 맞출 수 있습니다.

Box2D에는 b2DynamicTree 클래스에 Dbvt가 정교하게 구현되어 있습니다. b2BroadPhase 클래스는 광범위한 단계를 수행하는 역할을 하며 b2DynamicTree 의 인스턴스를 사용하여 AABB 쿼리를 수행합니다.

좁은 단계

비디오 게임 충돌 물리학의 광범위한 단계 후에 잠재적으로 충돌할 수 있는 한 쌍의 강체 세트가 있습니다. 따라서 각 쌍에 대해 두 몸체의 모양, 위치 및 방향이 주어지면 실제로 충돌하는지 알아내야 합니다. 교차하거나 거리가 작은 허용 오차 값 아래로 떨어지는 경우. 나중에 충돌을 해결하는 데 필요하기 때문에 충돌하는 물체 사이에 어떤 접촉점이 있는지 알아야 합니다.

볼록 및 오목 모양

비디오 게임 물리학의 일반적인 규칙에 따라 두 개의 임의의 모양이 교차하는지 확인하거나 두 모양 사이의 거리를 계산하는 것은 간단한 일이 아닙니다. 그러나 그것이 얼마나 단단한지를 결정하는 데 결정적으로 중요한 한 가지 속성은 모양의 볼록 함입니다. 모양은 볼록 하거나 오목 할 수 있으며 오목한 모양은 작업하기 더 어렵기 때문에 이를 처리하기 위한 몇 가지 전략이 필요합니다.

볼록 모양에서 모양 내의 두 점 사이의 선분은 항상 모양 안에 완전히 들어갑니다. 그러나 오목한(또는 "볼록하지 않은") 모양의 경우 모양의 점을 연결하는 가능한 모든 선분에 대해 동일한 것은 아닙니다. 모양 외부에 있는 하나 이상의 선분을 찾을 수 있다면 모양이 오목한 것입니다.

계산상 시뮬레이션에서 모든 모양이 볼록한 것이 바람직합니다. 볼록한 모양으로 작동하는 강력한 거리 및 교차 테스트 알고리즘이 많이 있기 때문입니다. 모든 객체가 볼록하지는 않으며 일반적으로 볼록 껍질과 볼록 분해라는 두 가지 방법으로 객체를 해결합니다.

모양의 볼록 껍질 은 해당 모양을 완전히 포함하는 가장 작은 볼록 모양입니다. 2차원의 오목 다각형의 경우 각 정점에 못을 두드리고 모든 못 주위에 고무 밴드를 감는 것과 같습니다. 다각형이나 다면체, 더 일반적으로 점 집합에 대한 볼록 껍질을 계산하려면 평균 시간 복잡도가 O ( n log n ) 인 빠른 껍질 알고리즘을 사용하는 것이 좋습니다.

분명히 볼록 껍질을 사용하여 오목한 개체를 나타내면 오목한 속성을 잃게 됩니다. 객체가 여전히 오목한 그래픽 표현을 갖기 때문에 "고스트" 충돌과 같은 바람직하지 않은 동작이 명백해질 수 있습니다. 예를 들어 자동차는 일반적으로 오목한 모양을 가지고 있으며 볼록 껍질을 사용하여 물리적으로 표현한 다음 그 위에 상자를 놓으면 상자가 위의 공간에 떠 있는 것처럼 보일 수 있습니다.

일반적으로 볼록 껍질은 비현실적인 충돌이 그다지 눈에 띄지 않거나 오목 속성이 시뮬레이션 대상에 필수적이지 않기 때문에 오목한 물체를 표현하기에 충분할 때가 많습니다. 그러나 어떤 경우에는 오목한 개체가 물리적으로 오목한 모양처럼 동작하도록 할 수 있습니다. 예를 들어 볼록 껍질을 사용하여 물리적으로 그릇을 나타내는 경우 그 안에 아무 것도 넣을 수 없습니다. 개체는 그 위에 떠 있을 것입니다. 이 경우 오목 모양의 볼록 분해 를 사용할 수 있습니다.

볼록 분해 알고리즘은 오목 모양을 받고 결합이 원래 오목 모양과 동일한 볼록 모양 세트를 반환합니다. 일부 오목한 모양은 많은 수의 볼록한 모양으로만 나타낼 수 있으며 이러한 모양은 계산 및 사용에 막대한 비용이 소요될 수 있습니다. 그러나 근사치는 종종 충분히 좋기 때문에 V-HACD 와 같은 알고리즘은 오목 다면체에서 볼록 다면체의 작은 집합을 생성합니다.

그러나 많은 충돌 물리학 사례에서 볼록 분해는 아티스트가 손으로 만들 수 있습니다. 이렇게 하면 분해 알고리즘으로 성능에 부담을 줄 필요가 없습니다. 성능은 실시간 시뮬레이션에서 가장 중요한 측면 중 하나이므로 일반적으로 복잡한 그래픽 개체에 대한 매우 간단한 물리적 표현을 만드는 것이 좋습니다. 아래 이미지는 9개의 볼록한 모양을 사용하여 2D 자동차의 가능한 볼록 분해를 보여줍니다.

교차 테스트 - 축 분리 정리

분리 축 정리 (SAT)는 이 축에 있는 모양의 직교 투영이 교차하지 않는 축이 하나 이상 있는 경우에만 두 개의 볼록한 모양이 교차하지 않는다는 것을 나타냅니다.

일반적으로 두 모양을 구분하는 2D의 선이나 3D의 평면을 찾는 것이 시각적으로 더 직관적입니다. 이는 사실상 동일한 원리입니다. 2D에서는 선과 직교하는 벡터 또는 3D에서는 평면의 법선 벡터를 "분리 축"으로 사용할 수 있습니다.

게임 물리 엔진에는 원(3D의 구), 가장자리(단일 선분) 및 볼록 다각형(3D의 다면체)과 같은 다양한 유형의 모양이 있습니다. 모양 유형의 각 쌍에 대해 특정 충돌 감지 알고리즘이 있습니다. 가장 간단한 것은 아마도 circle-circle 알고리즘일 것입니다:

 typedef struct { float centerX; float centerY; float radius; } Circle; bool CollideCircles(Circle *cA, Circle *cB) { float x = cA->centerX - cB->centerX; float y = cA->centerY - cB->centerY; float centerDistanceSq = x * x + y * y; // squared distance float radius = cA->radius + cB->radius; float radiusSq = radius * radius; return centerDistanceSq <= radiusSq; }

SAT는 원에 적용되지만 중심 사이의 거리가 반지름의 합보다 작은지 확인하는 것이 훨씬 간단합니다. 이러한 이유로 SAT는 볼록 다각형 대 볼록 다각형(또는 3D의 다면체)과 같은 특정 쌍의 모양 클래스에 대한 충돌 감지 알고리즘에 사용됩니다.

모든 모양 쌍에 대해 분리를 테스트할 수 있는 축의 수는 무한합니다. 따라서 먼저 테스트할 축을 결정하는 것은 효율적인 SAT 구현에 중요합니다. 다행히 한 쌍의 볼록 다각형이 충돌하는지 테스트할 때 가장자리 법선을 잠재적인 분리 축으로 사용할 수 있습니다. 모서리의 법선 벡터 n 은 모서리 벡터에 수직이고 다각형 외부를 가리킵니다. 각 다각형의 각 모서리에 대해 다른 다각형의 모든 정점이 모서리 앞에 있는지 확인하기만 하면 됩니다.

테스트가 통과하면(즉, 가장자리에 대해 다른 다각형의 모든 정점이 앞에 있는 경우) 다각형이 교차하지 않습니다. 선형 대수는 이 테스트에 대한 쉬운 공식을 제공합니다. 정점 a 와 b 가 있는 첫 번째 모양의 모서리와 다른 모양의 정점 v 가 주어지면 ( v - a ) · n 이 0보다 크면 정점이 앞에 있습니다. 가장자리의.

다면체의 경우 면 법선과 각 모양의 모든 모서리 조합의 외적을 사용할 수 있습니다. 그것은 테스트할 것이 많은 것처럼 들립니다. 그러나 속도를 높이기 위해 마지막으로 사용한 분리 축을 캐시하고 시뮬레이션의 다음 단계에서 다시 사용해 볼 수 있습니다. 캐시된 분리 축이 더 이상 모양을 분리하지 않으면 이전 면이나 가장자리에 인접한 면이나 가장자리에서 시작하여 새 축을 검색할 수 있습니다. 몸이 종종 단계 사이에서 많이 움직이거나 회전하지 않기 때문에 효과가 있습니다.

Box2D는 SAT를 사용하여 b2CollidePolygon.cpp의 폴리곤-폴리곤 충돌 감지 알고리즘에서 두 개의 볼록 폴리곤이 교차하는지 테스트합니다.

거리 계산 - Gilbert-Johnson-Keerthi 알고리즘

많은 충돌 물리학 사례에서 우리는 물체가 실제로 교차하는 경우뿐만 아니라 서로 매우 가까운 경우에도 충돌하는 것으로 간주하기를 원하므로 물체 사이의 거리를 알아야 합니다. Gilbert-Johnson-Keerthi (GJK) 알고리즘은 두 볼록 모양과 가장 가까운 점 사이의 거리를 계산합니다. 아래에 설명된 대로 지원 함수, Minkowski 합 및 심플렉스를 통해 볼록 모양의 암시적 표현과 함께 작동하는 우아한 알고리즘입니다.

지원 기능

지원 함수 s A ( d ) 는 벡터 d 에서 가장 높은 투영을 갖는 모양 A 의 경계에 있는 점을 반환합니다. 수학적으로 d 와 가장 높은 내적을 가집니다. 이것을 지지점 이라고 하며 이 작업을 지지 매핑 이라고도 합니다. 기하학적으로 이 점은 d 방향으로 모양에서 가장 먼 점입니다.

다각형에서 지지점을 찾는 것은 비교적 쉽습니다. 벡터 d 에 대한 지지점의 경우 꼭짓점을 반복하고 다음과 같이 d 와 내적이 가장 높은 것을 찾아야 합니다.

 Vector2 GetSupport(Vector2 *vertices, int count, Vector2 d) { float highest = -FLT_MAX; Vector2 support = (Vector2){0, 0}; for (int i = 0; i < count; ++i) { Vector2 v = vertices[i]; float dot = vx * dx + vy * dy; if (dot > highest) { highest = dot; support = v; } } return support; }

그러나 지원 함수의 진정한 힘은 원뿔, 원통 및 타원과 같은 모양으로 작업하기 쉽게 만드는 것입니다. 그러한 모양 사이의 거리를 직접 계산하는 것은 다소 어렵습니다. GJK와 같은 알고리즘이 없으면 일반적으로 일을 더 단순하게 만들기 위해 이를 다각형이나 다면체로 이산화해야 합니다. 그러나 다면체의 표면이 구체의 표면처럼 매끄럽지 않기 때문에 다면체의 표면이 매우 상세하지 않으면 충돌 감지 시 성능이 저하될 수 있기 때문에 추가 문제가 발생할 수 있습니다. 다른 바람직하지 않은 부작용도 나타날 수 있습니다. 예를 들어 "다면체" 구는 부드럽게 굴러가지 않을 수 있습니다.

원점을 중심으로 하는 구의 지지점을 얻으려면 d 를 정규화하면 됩니다(즉, 여전히 같은 방향을 가리키는 길이 1(단위 길이)의 벡터인 d / || d || 계산 의 d ) 그런 다음 구 반경으로 곱합니다.

Gino van den Bergen의 논문을 확인하여 다른 모양 중에서 원통 및 원뿔에 대한 지원 기능의 더 많은 예를 찾으십시오.

물론 우리의 객체는 시뮬레이션 공간의 원점에서 변위되고 회전되므로 변형된 모양에 대한 지지점을 계산할 수 있어야 합니다. 우리는 아핀 변환 T ( x ) = R x + c 를 사용하여 객체를 변위시키고 회전시킵니다. 여기서 c 는 변위 벡터이고 R 은 회전 행렬 입니다. 이 변환은 먼저 원점을 중심으로 개체를 회전한 다음 변환합니다. 변형된 모양 A 에 대한 지원 함수는 다음과 같습니다.

민코프스키 합계

두 도형 A 와 B 의 Minkowski 합 은 다음과 같이 정의됩니다.

즉, A 와 B 에 포함된 모든 점의 합을 계산합니다. 결과는 A 를 B 로 팽창시키는 것과 같습니다.

마찬가지로 Minkowski 차이 를 다음과 같이 정의합니다.

A 와 -B 의 Minkowski 합으로 쓸 수도 있습니다.

볼록 A 와 B 의 경우 A⊕B 도 볼록합니다.

Minkowski 차이의 유용한 속성 중 하나는 공간의 원점을 포함하는 경우 이전 이미지에서 볼 수 있듯이 모양이 교차한다는 것입니다. 왜 그런 겁니까? 두 모양이 교차하는 경우 공간의 같은 위치에 있는 적어도 하나의 공통점이 있고 그 차이는 실제로 원점인 0 벡터이기 때문입니다.

Minkowski 차이의 또 다른 좋은 기능은 원점을 포함하지 않는 경우 원점과 Minkowski 차이 사이의 최소 거리가 모양 사이의 거리라는 것입니다.

두 모양 사이의 거리는 다음과 같이 정의됩니다.

즉, A 와 B 사이의 거리는 A 에서 B 로 가는 최단 벡터의 길이입니다. 이 벡터는 A⊖B 에 포함되며 길이가 가장 작은 벡터이므로 결과적으로 원점에 가장 가까운 벡터입니다.

일반적으로 두 모양의 Minkowski 합을 명시적으로 작성하는 것은 간단하지 않습니다. 다행히도 다음과 같은 이유로 여기에서도 지원 매핑을 사용할 수 있습니다.

심플렉스

GJK 알고리즘은 원점에 가장 가까운 Minkowski 차이의 점을 반복적으로 검색합니다. 각 반복에서 원점에 더 가까운 일련의 심플렉스 를 구축하여 이를 수행합니다. 심플렉스(또는 보다 구체적으로 정수 k 에 대한 k-심플렉스 )는 k 차원 공간에서 k + 1개의 아핀으로 독립적인 점의 볼록 껍질입니다. 즉, 2개의 점이 일치하지 않아야 하고, 3개의 점에 대해 추가로 같은 선 위에 놓이지 않아야 하며, 4개의 점이 있는 경우에도 같은 평면에 놓이지 않아야 합니다. 따라서 0-심플렉스는 점, 1-심플렉스는 선분, 2-심플렉스는 삼각형, 3-심플렉스는 사면체입니다. 심플렉스에서 한 점을 제거하면 차원이 1 감소하고 심플렉스에 점을 추가하면 차원이 1 증가합니다.

행동하는 GJK

이 모든 것을 종합하여 GJK가 어떻게 작동하는지 봅시다. 두 도형 A 와 B 사이의 거리를 결정하기 위해 먼저 민코프스키 차이 A⊖B 를 취합니다. 이 점까지의 거리는 원래 두 모양 사이의 거리이기 때문에 결과 모양에서 원점에 가장 가까운 점을 찾고 있습니다. 우리는 A⊖B 에서 어떤 점 v 를 선택하는데, 이것은 우리의 거리 근사가 될 것입니다. 또한 현재 테스트 심플렉스의 포인트를 포함할 빈 포인트 세트 W 를 정의합니다.

그런 다음 루프에 들어갑니다. 우리는 지지점 w = s A⊖B ( -v ) , v 에 대한 투영이 원점에 가장 가까운 A⊖B 상의 점을 얻는 것으로 시작합니다.

만약 || 여 || || 와 크게 다르지 않아 v || 그리고 그들 사이의 각도가 많이 변경되지 않았다면(일부 사전 정의된 허용 오차에 따라), 알고리즘이 수렴되었고 우리가 반환할 수 있음을 의미합니다 || v || 거리만큼.

그렇지 않으면 w 를 W 에 추가합니다. W 의 볼록 껍질(심플렉스)이 원점을 포함하면 모양이 교차하며 이는 작업이 완료되었음을 의미하기도 합니다. 그렇지 않으면, 우리는 원점에 가장 가까운 심플렉스에서 점을 찾은 다음 v 를 이 새로운 가장 가까운 근사값으로 재설정합니다. 마지막으로 W 에서 가장 가까운 점 계산에 기여하지 않는 점을 제거합니다. (예를 들어 삼각형이 있고 원점에 가장 가까운 점이 모서리 중 하나에 있는 경우 W 에서 이 모서리의 정점이 아닌 점을 제거할 수 있습니다.) 그런 다음 알고리즘이 완료될 때까지 이러한 동일한 단계를 반복합니다. 수렴합니다.

다음 이미지는 GJK 알고리즘의 4번 반복의 예를 보여줍니다. 파란색 개체는 Minkowski 차이 A⊖B 를 나타내고 녹색 벡터는 v 입니다. 여기서 v 가 원점에 가장 가까운 지점에서 어떻게 연마되는지 볼 수 있습니다.

GJK 알고리즘에 대한 상세하고 심도 있는 설명은 Gino van den Bergen 의 A Fast and Robust GJK Implementation for Collision Detection of Convex Objects 를 참조하십시오. dyn4j 물리 엔진에 대한 블로그에도 GJK에 대한 훌륭한 게시물이 있습니다.

Box2D에는 b2Distance 함수의 b2Distance.cpp에 GJK 알고리즘이 구현되어 있습니다. 연속 충돌 감지를 위한 알고리즘에서 충돌 계산 시간 동안에만 GJK를 사용합니다(아래에서 더 논의할 주제).

Chimpunk 물리 엔진은 모든 충돌 감지에 GJK를 사용하며, 그 구현은 GJK 함수의 cpCollision.c에 있습니다. GJK 알고리즘이 교차를 보고하는 경우에도 침투 깊이와 함께 접점이 무엇인지 알아야 합니다. 이를 위해 확장 폴리토프 알고리즘을 사용합니다. 이 알고리즘은 다음에 살펴보겠습니다.

침투 깊이 결정 - 확장 폴리토프 알고리즘

위에서 언급했듯이 모양 A 와 B 가 교차하는 경우 GJK는 Minkowski 차이 A⊖B 내부에 원점을 포함하는 심플렉스 W 를 생성합니다. 이 단계에서 우리는 모양이 교차한다는 것만 알고 있지만 많은 충돌 감지 시스템의 설계에서 교차가 얼마나 많은지, 접촉점으로 사용할 수 있는 점을 계산할 수 있는 것이 바람직합니다. 우리는 현실적인 방식으로 충돌을 처리합니다. EPA( Expanding Polytope Algorithm )를 사용하면 GJK가 중단한 부분부터 시작하여 해당 정보를 얻을 수 있습니다.

침투 깊이 는 최소 변환 벡터 (MTV)의 길이로, 교차하는 모양을 다른 모양과 분리하기 위해 교차하는 모양을 변환할 수 있는 가장 작은 벡터입니다.

두 도형이 교차할 때 그들의 민코프스키 차이는 원점을 포함하고, 원점에 가장 가까운 민코프스키 차이의 경계 상의 점이 MTV입니다. EPA 알고리즘은 GJK가 우리에게 준 심플렉스를 다각형으로 확장하여 그 점을 찾습니다. 새로운 정점으로 가장자리를 연속적으로 세분화합니다.

먼저 원점에 가장 가까운 심플렉스의 모서리를 찾고 모서리에 수직인 방향(즉, 모서리에 수직이고 다각형 외부를 가리키는 방향)에서 Minkowski 차이의 지지점을 계산합니다. 그런 다음 이 지지점을 추가하여 이 가장자리를 분할합니다. 벡터의 길이와 방향이 많이 변하지 않을 때까지 이 단계를 반복합니다. 알고리즘이 수렴되면 MTV와 침투 깊이가 있습니다.

EPA와 함께 GJK를 사용하면 물체가 이미 교차하거나 충돌로 간주될 만큼 충분히 가깝더라도 충돌에 대한 자세한 설명을 얻을 수 있습니다.

EPA 알고리즘은 Gino van den Bergen이 작성한 Proximity Queries and Penetration Depth Computation on 3D Game Objects 문서에 설명되어 있습니다. dyn4j 블로그에는 EPA에 대한 게시물도 있습니다.

연속 충돌 감지

지금까지 제시된 비디오 게임 물리 기술은 시뮬레이션의 정적 스냅샷에 대한 충돌 감지를 수행합니다. 이것을 이산 충돌 감지 라고 하며 이전 단계와 현재 단계 사이에 일어나는 일을 무시합니다. 이러한 이유로 특히 빠르게 움직이는 물체의 경우 일부 충돌이 감지되지 않을 수 있습니다. 이 문제를 터널링 이라고 합니다.

연속 충돌 감지 기술은 시뮬레이션의 이전 단계와 현재 단계 사이에서 두 물체가 충돌한 시점 을 찾으려고 시도합니다. 충돌 시간을 계산하므로 시간을 거슬러 올라가 그 지점에서 충돌을 처리할 수 있습니다.

충돌 시간(또는 접촉 시간) t c 는 두 물체 사이의 거리가 0인 순간입니다. 시간에 따라 두 물체 사이의 거리에 대한 함수를 작성할 수 있다면 우리가 찾고자 하는 것은 이 함수의 가장 작은 근입니다. 따라서 임팩트 계산 시간은 근을 찾는 문제 입니다.

임팩트 계산 시 t i -1 시점의 이전 스텝과 t i 시점의 현재 스텝에서의 바디 상태(위치 및 방향)를 고려합니다. 일을 더 간단하게 하기 위해 단계 사이의 선형 운동을 가정합니다.

모양이 원이라고 가정하여 문제를 단순화합시다. 반지름이 r 1 과 r 2 인 두 원 C 1 과 C 2 의 경우, 여기서 질량 중심 x 1 및 x 2 는 중심과 일치합니다(즉, 자연적으로 질량 중심을 중심으로 회전함), 우리는 거리 함수를 작성할 수 있습니다. 같이:

단계 간의 선형 운동을 고려하여 t i -1 에서 ti i 까지 C 1 의 위치에 대해 다음 함수를 작성할 수 있습니다.

x 1 ( t i -1 ) 에서 x 1 ( t i ) 까지의 선형 보간입니다. x 2 에 대해서도 마찬가지입니다. 이 간격에 대해 다른 거리 함수를 작성할 수 있습니다.

이 표현식을 0으로 설정하면 t 에 대한 이차 방정식을 얻을 수 있습니다. 근은 이차 공식을 사용하여 직접 찾을 수 있습니다. 원이 교차하지 않으면 이차 공식에 해가 없습니다. 그렇게 하면 하나 또는 두 개의 뿌리가 생길 수 있습니다. 루트가 하나만 있는 경우 해당 값은 영향 시간입니다. 두 개의 루트가 있는 경우 가장 작은 것은 충돌 시간이고 다른 하나는 원이 분리되는 시간입니다. 여기서 충격 시간은 0에서 1 사이의 숫자입니다. 초 단위 시간이 아닙니다. 이것은 충돌이 발생한 정확한 위치로 본체의 상태를 보간하는 데 사용할 수 있는 숫자일 뿐입니다.

비원형에 대한 연속 충돌 감지

다른 종류의 모양에 대한 거리 함수를 작성하는 것은 어렵습니다. 주로 거리가 방향에 따라 달라지기 때문입니다. 이러한 이유로 우리는 일반적으로 객체가 충돌하는 것으로 간주될 만큼 가까워질 때까지 각 반복에서 객체를 점점 더 가깝게 이동하는 반복 알고리즘을 사용합니다.

보수적 발전 알고리즘은 몸체를 앞으로(및 회전) 반복적으로 이동합니다. 각 반복에서 변위의 상한을 계산합니다. 원래 알고리즘은 신체의 탄도 운동을 고려한 Brian Mirtich의 박사 학위 논문(섹션 2.3.2)에 나와 있습니다. Erwin Coumans(Bullet Physics Engine의 저자)의 이 논문은 일정한 선형 및 각속도를 사용하는 더 간단한 버전을 제시합니다.

알고리즘은 모양 A 와 B 사이의 가장 가까운 점을 계산하고 한 점에서 다른 점으로 벡터를 그리고 이 벡터에 속도를 투영하여 동작의 상한을 계산합니다. 이것은 신체의 어떤 점이 이 투영을 넘어서 움직이지 않도록 보장합니다. 그런 다음 이 양만큼 몸체를 앞으로 전진시키고 거리가 작은 허용 오차 값 아래로 떨어질 때까지 반복합니다.

예를 들어 바디 중 하나의 각속도가 너무 높은 경우와 같이 수렴하는 데 너무 많은 반복이 필요할 수 있습니다.

충돌 해결

충돌이 감지되면 충돌하는 물체가 서로 튕겨 나가게 하는 등 현실적인 방식으로 물체의 움직임을 변경해야 합니다. 이 이론의 다음이자 마지막 기사에서는 비디오 게임에서 충돌을 해결하는 몇 가지 인기 있는 방법에 대해 논의할 것입니다.

참고문헌

충돌 감지 알고리즘 및 기술과 같은 충돌 물리학에 대한 더 깊은 이해에 관심이 있다면 Christer Ericson의 Real-Time Collision Detection 이라는 책이 반드시 필요합니다.

충돌 감지는 기하학에 크게 의존하기 때문에 Toptal의 기사 Computational Geometry in Python: From Theory to Application 은 주제에 대한 훌륭한 소개입니다.