물리 엔진에서의 충돌 처리

물리 엔진에서의 충돌 처리는 3 가지 정보를 필요로 합니다.

1. Contact point : 충돌점입니다.
2. Contact normal : 충돌해서 튕겨나올 방향을 결정합니다.
3. Penetration depth : 얼마나 침투했는지를 나타냅니다.

제가 생각하는 간단하고, brute force 한 방법은 SAT (Separating Axis Theorem) 로 충돌여부를 판정하고, 최소 분리 edge (3d 에선 plane) 를 구해서 penetration vector 를 구하고, 폴리곤과 상대 폴리곤의 각각의 정점 포함여부를 검사해서 contact point 를 계산하는 방식입니다. 실제로 제가 만든 2D 물리엔진인 physicsRus (http://juhlnet.egloos.com/3820233) 는 이렇게 구현했습니다.

2d-collision-box1

좀 더 효율적인 방법은 GJK (Gilbert–Johnson–Keerthi) 로 충돌여부를 검사하고, 충돌했을 경우 EPA (Expanding Polytope Algorithm) 로 penetration vector 를 구하고, edge clipping 으로 contact point 와 penetration depth 를 구하는 방식입니다. 대다수의 물리엔진들이 SAT 보다는 GJK/EPA 같은 효율적인 알고리즘들을 사용합니다. GJK 알고리즘은 빠르게 충돌여부를 판단할 때도 쓸 수 있을 뿐만 아니라 두 convex 폴리곤의 가장 가까운 거리를 구할때에도 사용할 수 있습니다.

2d-collision-box2

GJK/EPA 알고리즘을 바탕으로 데모를 만들어 봤습니다.
http://juhl.github.com/collision-detection-2d/

참고:
GDC 2010: Computing Distance with GJK by Erin Catto
http://code.google.com/p/box2d/downloads/detail?name=GDC2010_ErinCatto.zip&can=2&q=

Leave a Reply

Your email address will not be published. Required fields are marked *