FT_Newton: Narrow Phase / SAT vs GJK - (5)

Broad Phase와 Narrow Phase를 살펴보기 전에, Broad Phase에 대해 간단히 상기해보자.

---

Broad Phase

• 모든 물체의 충돌 범위를 AABB(축 방향 정렬된 박스)로 설정한다.
• Integrate 단계 이후, AABB 범위가 겹치는 물체들을 충돌 쌍으로 만들어 Narrow Phase에 전달한다.

---

Narrow Phase

Broad Phase에서 만들어진 충돌 쌍은 AABB의 넓은 범위를 기준으로 설정되었기 때문에, Narrow Phase에서는 더 정밀한 충돌 감지를 진행한다.
이 과정에서 실제 충돌이 확정되면 접촉점, 침투 깊이, 충돌 방향에 대한 정보를 계산하여 Solve 단계로 넘겨준다.

Narrow Phase를 진행하기 위해서는 먼저 실제 충돌인지 여부를 감지하는 알고리즘이 필요하다.
대표적인 충돌 감지 알고리즘으로는 SAT와 GJK가 있다.

---

SAT (Separating Axis Theorem)

SAT는 볼록 다면체의 충돌 감지에 사용된다.
두 볼록 다면체가 충돌하지 않으려면, 두 도형을 분리하는 하나의 축이 존재해야 한다.
SAT는 두 도형 간 충돌이 일어날 수 있는 모든 축을 검사하여, 모든 축에서 투영 범위가 겹친다면 충돌이 발생했다고 판단한다.

Box A와 Box B의 충돌 감지 시 검사 축:

1. Box A와 Box B의 각 평면의 법선 벡터
2. Box A와 Box B의 모서리 간 외적 벡터

---

Box와 Box 충돌 시 축의 수

• Box 하나당 평면 법선 축: 6개
• 두 Box의 법선 축: 6 + 6 =12개
• 모서리 간 외적 축: 12 × 12 = 144개
• 총 검사 축: 12 + 144 = 156개

하지만 Box 간 충돌의 경우 겹치는 축을 제외하면 검사해야 할 축은 15개로 줄어든다.
이는 평면의 법선 축 3개와 모서리 간 교차 축 12개로 구성된다.

SAT 충돌 감지 과정:

1. 모든 점을 검사 축에 투영한다.
2. 두 도형의 투영 범위가 겹치지 않는 축이 하나라도 있다면 충돌이 발생하지 않는다.
3. 모든 축에서 투영 범위가 겹치면 충돌이 발생했다고 판단한다.

SAT는 간단하고 구현하기 쉬운 장점이 있지만, 검사 축의 개수가 많아지면 연산량이 크게 늘어난다.
특히, Box가 아닌 복잡한 다면체에 적용할 경우 SAT의 효율이 떨어질 수 있다.

---

GJK (Gilbert-Johnson-Keerthi Algorithm)

GJK는 SAT와 마찬가지로 볼록 다면체의 충돌 감지에 사용된다.
GJK를 이해하기 위해서는 먼저 Minkowski Difference를 알아야 한다.

Minkowski Difference

Minkowski Difference는 두 도형 A와 B의 모든 점의 차이를 계산하여 새로운 도형을 생성하는 연산이다.
수식으로는 A ⊖ B= { a − b ∣ a ∈ A, b ∈ B } 로 정의된다.
이때 Minkowski Difference에 원점(0, 0, 0)이 포함되면 두 도형은 충돌한 것으로 판단할 수 있다.

(원점은 도형 A와 도형 B의 내부의 점 중 같은 점이 있다는 것이고, 그것은 충돌을 의미하기 때문)

GJK는 이 Minkowski Difference를 효율적으로 계산하여 충돌 여부를 감지한다.

---

GJK 알고리즘 과정

가정 1. 지금 충돌을 감지하려는 도형은 A와 B이다.

가정 2. support 함수란 A와 B가 각각 가지고 있는 함수로, 도형에서 dir 방향으로 가장 멀리 떨어져 있는 점을 반환한다. 

가정 3. simplex란 A와 B에서 support 함수에서 찾은 점으로 생성한 Minkowski Different 점

1. A와 B의 중심을 연결한 방향 벡터 dir 생성
2. A에서는 dir 방향으로, B에서는 -dir 방향으로 support함수에 넣어 첫 번째 simplex인 simplexA 생성
3. 해당 dir을 통해 두 번째 simplex인 simplexB 생성
4. simplexA와 simplexB로 이루어진 직선을 기준으로, 원점이 있는 방향으로의 수직 벡터 dir 생성
5. 해당 dir을 통해 세 번째 simplex인 simplexC 생성
6. simplexA, simplexB, simplexC 로 이루어진 평면을 기준으로, 원점이 있는 방향으로의 수직벡터 dir 생성
7. 해당 dir을 통해 두 번째 simplex인 simplexB 생성
8. simplexA, simplexB, simplexC, simplexD로 이루어진 사면체 내부에 원점이 포함되면 충돌 발생 확정
9. 해당 dir을 통해 네 번째 simplex인 simplexD 생성
10. simplexA, simplexB, simplexC, simplexD로 이루어진 사면체 내부에 원점이 포함되면 충돌 발생 확정

만약 새로운 simplex가 원점을 포함할 수 없으면, 새로운 방향 dir을 통해 반복한다.
충돌 여부는 simplex가 원점을 포함하는지 여부로 판별하며, 포함하지 않는 경우 충돌이 발생하지 않았다고 본다.

 

자세한 내용은 여기에 설명이 잘 되어있으므로 보면 좋다. 

https://www.slideshare.net/slideshow/collision-detection-algorithms/251207941#44

충돌 알고리즘(collision detection algorithms)

 

---

SAT와 GJK의 비교

알고리즘	장점	단점
SAT	구현이 쉬움	연산량이 많아질 수 있음
GJK	모든 볼록 다면체에 적용 가능	구현이 어려움

---

구현 경험과 선택

초기 구현에서는 Sphere와 Box Shape만 사용했기 때문에 SAT 알고리즘으로 충돌 감지를 구현했다.
SAT는 충돌 감지 자체는 쉬웠으나, 충돌 깊이와 충돌 방향을 계산하기 위해 추가 예외 처리가 필요했다.
이 과정에서 SAT의 한계에 의구심이 들었고, 충돌 방향과 깊이를 계산할 수 있는 EPA(Expanding Polytope Algorithm)를 알게 되었다.
EPA를 사용하려면 GJK가 선행되어야 하므로, 최종적으로 GJK를 충돌 감지 알고리즘으로 선택했다.

---

다음 글에서는 EPA 알고리즘에 대해 간단히 알아볼 예정이다.