Separating Axis Theorem

Sep. 2011 written by 이주형 (Lee Ju Hyung)

SAT(Separating Axis Theorem) 는 두개의 convex 한 물체가 서로 교차하지 않을 때 두 물체 사이를 분리하는 평면(2d 에서는 라인) 이 반드시 존재한다는 이론이다. 이때 분리 평면에 수직인 축을 분리축 (Separating Axis) 이라고 한다.

OBB (Oriented Bounding Box) Intersection Test

아래는 2차원 박스의 2개의 분리축을 나타낸 그림이다.

SAT

위의 그림처럼 center 사이의 거리와 분리축에 투영한 extent 벡터의 거리를 구해서 비교하면 된다.

2차원과 달리 3차원에서는 로컬 분리축들(6개) 외에 edge 끼리 교차하는 경우가 있으므로 edge 분리축들(9개) 검사까지 추가된다. edge 분리축은 로컬 분리축을 서로 외적하여 구할 수 있다.

아래는 3차원 OBB 교차검사를 수행하는 C++ 코드다.

참고 (References)

  1. Introduction to Linear Algebra 4th Edition
    Gilbert Strang
    http://math.mit.edu/linearalgebra/
  2. Real-Time Collision Detection
    Christer Ericson
    http://realtimecollisiondetection.net/

Leave a Reply

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