FT_Newton: Narrow Phase / EPA - (6)

이번에는 지난 글에서 다룬 GJK 이후, 충돌 방향과 충돌 깊이를 찾아주는 EPA 알고리즘에 대해 알아보자.

---

EPA란?

EPA(Expanding Polytope Algorithm)는 두 도형 A, B의 Minkowski Difference를 활용해 충돌 해소의 최소 깊이와 충돌 방향을 찾아주는 알고리즘이다.

이 알고리즘은 GJK에서 생성된 4개의 simplex로 이루어진 사면체에서 시작한다.
GJK에서 충돌이 감지된 경우에만 EPA 단계를 진행하기 때문에, 사면체 내부에 원점이 포함된 상태가 확정적이다.
이후, 아래의 과정을 반복하며 충돌 깊이와 충돌 방향 벡터를 계산한다.

---

EPA 알고리즘 과정

1. 원점에서 다면체의 평면까지의 거리 계산
   • 현재 simplex로 이루어진 다면체의 모든 평면에 대해, 원점에서 각 평면까지의 거리를 구한다.
2. 가장 짧은 거리의 평면 선택
   • 원점에서 가장 가까운 평면을 찾고, 해당 평면의 법선 벡터를 구한다.
3. 새로운 simplex 구하기
   • 선택한 평면의 법선 벡터를 dir로 하여, support 함수를 사용해 새로운 simplex를 구한다.
4. 다면체 확장
   • 새로운 simplex를 다면체에 추가하여 더 큰 다면체를 생성한다.
5. 반복 조건 확인
   • 원점에서 선택된 평면까지의 거리의 최솟값이 변경되었는지 확인한다.
   • 최솟값이 변경되었다면 위 과정을 반복한다.

---

결과: 충돌 방향과 깊이

반복 과정이 끝나면, 원점에서 가장 가까운 평면이 확정된다.
이때:

• 해당 평면의 법선 벡터는 충돌 방향을 나타낸다.
• 원점과 평면 사이의 거리는 충돌 깊이를 나타낸다.

이 정보를 활용해, 충돌 방향으로 오브젝트를 최소 깊이만큼 이동시키면 충돌을 해소할 수 있다.

---

참고 자료

2D에서의 EPA 알고리즘을 다룬 자료를 확인해 보면 비슷한 흐름을 이해하는 데 도움이 된다.
2D 사례와 3D 사례의 원리는 동일하므로 한 번 살펴보기를 추천한다.

https://myprogramming.tistory.com/66

GJK-EPA 알고리즘

 

---

 

 

다음 글에서는 EPA에서 구한 충돌 벡터와 충돌 깊이를 통해 충돌점을 구하는 clipping에 대해 알아볼 예정이다.