02. 충돌 감지 알고리즘
목차
- 충돌 감지 알고리즘 (입력과 출력이 뭔지)
- GJK & EPA 소개
- 벡터 삼중곱
- Simplex란
- Support Point
- 민코프스키 합 / 차
- GJK 설명 (Distance(), Vornoi 공간)
- 접촉점, 접촉 법선, 침투 깊이
- Polytope이란
- EPA 설명
- 실전. GJK - EPA 이후, 접촉점 구하기 (매니폴드, featuredEdge, inc/ref)
충돌 감지 알고리즘
물리 엔진에서 사용되는
충돌 감지 알고리즘에는
크게 2개가 있습니다.
GJK & EPA 와 SAT 입니다.
이 두 알고리즘은 작동 방식이 다르지만
- 입력으로써 볼록 다각형(Convex Polygon) 2개를 받고
- 출력으로써 충돌점과 충돌 벡터를 생성
한다는 점에서 같습니다.
SAT의 경우, 간단한 구현에서는 괜찮지만
복잡한 도형의 경우 수행 시간이 급격히
늘어난다는 단점이 있습니다.
일단 이 글에서는 GJK & EPA만 다루겠습니다.
GJK & EPA 소개
이 두 알고리즘은 물리엔진에서
GJK -> EPA 순서대로 실행되는 세트입니다.
우선 GJK 부터 소개하겠습니다.
GJK (Gilbert-Johnson-Keerthi) 알고리즘은
두 볼록 다각형 사이의 거리를 측정하고,
충돌이 일어났는지를 판별하는 알고리즘입니다.
GJK 알고리즘을 통해
얻은 결과값을 사용하여
EPA 알고리즘을 수행하게 됩니다.
EPA (Expanding Polytope Algorithm) 는
GJK 단에서 충돌 여부 자체를 판별했다면
이 단계에서는
물체가 '어느 방향으로, 얼만큼 침투했는지'
를 계산하게 됩니다.
(정확히 말하면 충돌 깊이(Penetration Depth) 정보와
충돌 법선(Contact Normal) 이며, 추후에 설명합니다)
두 알고리즘 모두,
사전에 알아야 하는 개념들이 여럿 있습니다.
GJK 의 경우,
- Simplex
- Support Point
- Triple Product
- Minkowski Sum / Diff
EPA의 경우,
- Polytope
- Closest Edge
- Barycentric Coordinates
이 정도가 됩니다.
GJK의 구현 방식은 밑에처럼 2가지로 나뉘는데요,
벡터 삼중곱 기반 vs 보르노이 영역 기반
두 구현 모두 차례로 설명하겠습니다.