Separating Axis Theorem
SAT(Separating Axis Theorem)는 볼록 다면체 간 충돌을 감지하는 알고리즘이다.
이안 밀링턴 Game Physics Engine Development 14.3 SAT(Separating Axis Theorem)를 참고하여 작성하였다.
1. SAT 아이디어
두 객체가 분리되는 축이 있다면, 해당 객체들은 충돌하지 않는다.
3D 객체를 1D 축에 투영해서 확인한다. 각 객체는 해당 축을 따라 매핑되고, 이 범위에 겹치지 않으면 객체들이 분리되어 있다는 뜻이다.
볼록 다면체에서 다음 축들만 확인하면 된다:
- 면 법선 축: 두 객체의 모든 면 법선
- 모서리 교차 축: 서로 다른 객체의 모든 모서리 쌍에 수직인 축
예를 들어, 두 박스의 경우 총 15개 축을 테스트한다:
- 면 축: 6개 (각 박스당 3개)
- 모서리 교차 축: 9개 (3×3 조합)
박스는 실제로 6개의 면과 12개의 모서리를 가지고 있지만, 모든 축을 테스트할 필요는 없다. 면 축의 경우 박스는 평행한 면 쌍을 가지므로 (앞면-뒷면, 왼쪽면-오른쪽면, 위면-아래면) 실제로는 3개의 구별되는 법선 방향만 있다. 따라서 각 박스당 3개씩 총 6개면 충분하다.
모서리 교차 축의 경우도 마찬가지다. 박스의 12개 모서리는 4개씩 평행하게 그룹화된다 (X축 방향 4개, Y축 방향 4개, Z축 방향 4개). 평행한 모서리들은 동일한 방향벡터를 가지므로, 실제로는 각 박스당 3개의 구별되는 모서리 방향만 있다. 따라서 3×3 = 9개의 교차축만 테스트하면 된다.
모서리 교차 축이 왜 필요한가? 면 축만으로는 모든 충돌을 감지할 수 없기 때문이다. 두 박스가 비스듬히 교차하는 경우를 생각해보자. 각 박스의 면 법선 방향으로는 겹치지만, 실제로는 모서리끼리만 스쳐 지나가는 상황이 있다. 이런 경우 면 축 테스트로는 “겹침”으로 잘못 판정되지만, 두 모서리에 수직인 교차 축으로 테스트하면 “분리됨”을 올바르게 감지할 수 있다.
예를 들어, 한 박스는 X축으로 길게 놓이고 다른 박스는 Y축으로 길게 놓인 상태에서 Z축 방향으로 살짝 어긋나 있다면, 각각의 면 축으로는 겹침이 감지되지만 실제로는 모서리끼리 스치는 상황이다. 이때 X축과 Y축의 외적인 Z축 방향으로 테스트하면 분리를 정확히 감지할 수 있다.
생각해보면 두 볼록 다면체가 닿는 방법은 면-점 접촉이거나 모서리-모서리 접촉뿐이다. 각각에 대응하는 축을 테스트하면 모든 경우를 계산할 수 있다.
2. Box-Box 충돌 감지 구현
다음 의사코드를 보면서 어떻게 구현되는지 알아보자. 이 의사코드는 cyclone-physics 소스코드의 SAT 코드를 읽기 쉽게 재구성하였다.
2.1 투영 반지름 계산
박스를 특정 축에 투영했을 때의 “반지름”을 계산하는 방법이다:
함수 calculateProjectionRadius(box, axis):
// 박스의 각 축을 테스트 축에 투영
projX = box.halfSize.x * abs(axis · box.xAxis)
projY = box.halfSize.y * abs(axis · box.yAxis)
projZ = box.halfSize.z * abs(axis · box.zAxis)
// 투영된 반지름 = 각 축 투영의 합
return projX + projY + projZ
박스가 회전되어 있어도 상관없다. 각 축 방향의 halfSize를 테스트 축으로 투영하고, 절댓값을 더하면 박스가 그 축에서 차지하는 “폭”이 나온다.
- box: OBB(Oriented Bounding Box) 객체. 중심
center, 로컬 축xAxis,yAxis,zAxis(단위·정규직교), 로컬 반크기halfSize=(hx, hy, hz)를 가진다. 로컬 꼭짓점은(+/-hx, +/-hy, +/-hz). - halfSize: 각 로컬 축 방향의 반폭(길이의 절반). 비음수이며, 투영 반지름 식의 계수로 쓰인다.
- axis(테스트 축): SAT에서 검사할 단위 벡터.
이에 투영 반지름은 다음과 같다: $R = \sum_{i} \mathrm{halfSize}{i} \, \lvert \mathbf{axis} \cdot \mathbf{boxAxis}{i} \rvert$.
2.2 축별 겹침 테스트
함수 checkOverlapOnAxis(box1, box2, axis, centerDistance):
// 각 박스의 투영 반지름 계산
radius1 = calculateProjectionRadius(box1, axis)
radius2 = calculateProjectionRadius(box2, axis)
// 박스 중심 간 거리의 축 방향 성분
distance = abs(centerDistance · axis)
// 겹침 확인: 거리 < 두 반지름의 합
return distance < (radius1 + radius2)
두 박스가 특정 축에서 겹치는지 확인하는 방법이다. 박스 중심 간 거리(centerDistance)가 두 박스의 투영 반지름 합보다 작으면 겹친다.
2.3 15개 축 테스트
함수 boxIntersectionTest(box1, box2):
centerDistance = box2.center - box1.center
// Phase 1: Box1의 면 축 3개 테스트
if not checkOverlapOnAxis(box1, box2, box1.xAxis, centerDistance): return false
if not checkOverlapOnAxis(box1, box2, box1.yAxis, centerDistance): return false
if not checkOverlapOnAxis(box1, box2, box1.zAxis, centerDistance): return false
// Phase 2: Box2의 면 축 3개 테스트
if not checkOverlapOnAxis(box1, box2, box2.xAxis, centerDistance): return false
if not checkOverlapOnAxis(box1, box2, box2.yAxis, centerDistance): return false
if not checkOverlapOnAxis(box1, box2, box2.zAxis, centerDistance): return false
// Phase 3: 모서리 교차 축 9개 테스트
for i in [x, y, z]:
for j in [x, y, z]:
crossAxis = box1.axis[i] × box2.axis[j]
if not checkOverlapOnAxis(box1, box2, crossAxis, centerDistance):
return false
return true // 모든 축에서 겹침 → 충돌
하나라도 분리되는 축을 찾으면 즉시 false를 반환한다. 모든 축에서 겹치면 충돌이다.
3. 접촉 데이터 생성
다른 블로그에선 여기까지만 설명하는 경우가 많으나, 물리 엔진을 위해서는 어디서, 얼마나 깊이 침투했는지 알아야 한다.
3.1 침투 깊이 계산
함수 calculatePenetrationDepth(box1, box2, axis, centerDistance):
// 각 박스의 투영 반지름
radius1 = calculateProjectionRadius(box1, axis)
radius2 = calculateProjectionRadius(box2, axis)
// 박스 중심 간 거리의 축 방향 성분
distance = abs(centerDistance · axis)
// 침투 깊이 = (두 반지름의 합) - (중심 간 거리)
penetration = radius1 + radius2 - distance
// 양수면 겹침, 음수면 분리
return penetration
침투 깊이를 계산하는 방법이다. 두 박스가 겹치는 정도를 스칼라로 나타낸다.
3.2 최소 침투 축 찾기
함수 findMinimumPenetrationAxis(box1, box2):
centerDistance = box2.center - box1.center
minPenetration = 무한대
bestAxis = null
bestAxisIndex = -1
// 15개 축을 모두 테스트
axes = [box1 면축들, box2 면축들, 모서리 교차축들]
for i, axis in enumerate(axes):
// 거의 평행한 축은 무시
if axis.length < 0.0001: continue
axis = normalize(axis)
penetration = calculatePenetrationDepth(box1, box2, axis, centerDistance)
// 분리 축 발견 → 충돌 없음
if penetration < 0: return null
// 최소 침투 깊이 업데이트
if penetration < minPenetration:
minPenetration = penetration
bestAxis = axis
bestAxisIndex = i
return (bestAxis, minPenetration, bestAxisIndex)
모든 축을 테스트해서 가장 작은 침투 깊이를 가진 축을 찾는다. 이 축이 실제 충돌이 일어나는 방향이다. 현실의 연속 시간에서는 두 물체가 실제로 “겹치는” 일이 없다. 이산 시간 시뮬레이션에서는 프레임 사이 이동으로 겹침이 생길 수 있으므로, 최소 침투 축을 법선으로 삼아 가장 작은 이동량으로 두 물체를 분리한다. 이렇게 하면 분리에 필요한 작업이 최소화되어 계산 효율이 높고, 불필요한 에너지 주입과 시각적 튐(진동)을 줄여 안정적인 동작을 얻을 수 있다.
4. 접촉점 계산
최소 침투 축을 찾았으면, 이제 정확한 접촉점을 계산해야 한다. 축의 종류에 따라 다른 방법을 쓴다.
4.1 Face-Vertex 접촉
면 축에서 최소 침투가 발견되면 한 박스의 꼭짓점이 다른 박스의 면에 박힌 상황이다:
함수 createFaceVertexContact(box1, box2, axisIndex, penetration):
// 충돌 면의 법선 벡터 결정
collisionNormal = box1.axis[axisIndex]
// 법선이 box1에서 box2를 향하도록 조정
centerDistance = box2.center - box1.center
// 내적 < 0: 두 벡터가 90° 초과로 벌어져 서로 반대 방향을 보는 상태 → 노말 반전
if collisionNormal · centerDistance < 0:
collisionNormal = -collisionNormal
// Box2에서 가장 깊이 침투한 꼭짓점 찾기
vertex = box2.halfSize // 시작점: (+, +, +) 꼭짓점
// 각 축에서 법선과 반대 방향이면 반전
for i in [x, y, z]:
if box2.axis[i] · collisionNormal < 0:
vertex[i] = -vertex[i]
// 월드 좌표로 변환
contactPoint = box2.transform * vertex
return Contact(
normal: collisionNormal,
point: contactPoint,
penetration: penetration
)
박스의 꼭짓점 중에서 충돌 면에 가장 가까운(깊이 침투한) 점을 찾는다.
- contact normal(접촉 노말)은 충격 임펄스가 작용하는 방향으로, 여기서는 A(box1)가 B(box2)를 밀어내는 방향이다. A가 밀리는 방향은 contact normal과 반대가 된다.
4.2 Edge-Edge 접촉
함수 findClosestPointsBetweenEdges(P1, D1, edgeSize1, P2, D2, edgeSize2):
// P1, P2: 각 모서리 선분의 월드 좌표 중점.
// D1, D2: 각 P1/P2의 방향 벡터.
// edgeSize1, edgeSize2: 모서리 반길이.
D1D1 = D1 · D1
D2D2 = D2 · D2
D1D2 = D1 · D2
// 시작점 간 벡터
P1_to_P2 = P2 - P1
// 2x2 행렬식 계산 (크래머 공식용)
det = D1D1 × D2D2 - D1D2²
// 평행선 처리
if abs(det) < 0.0001:
return P1과 P2 중 적절한 점 선택
// 크래머 공식으로 매개변수 계산
s = ((P1_to_P2 · D1) × D2D2 - D1D2 × (P1_to_P2 · D2)) / det
t = (D1D1 × (P1_to_P2 · D2) - (P1_to_P2 · D1) × D1D2) / det
// 선분 범위 확인
if s < -edgeSize1 or s > edgeSize1 or t < -edgeSize2 or t > edgeSize2:
// 범위 벗어남 → edge-face 접촉
return 적절한 모서리 중점
else:
// 실제 교차 → 두 점의 중점
L1 = P1 + s × D1
L2 = P2 + t × D2
return (L1 + L2) / 2
두 모서리에서 가장 가까운 점들을 찾아서 그 중점을 접촉점으로 쓴다. 이를 위해 두 선분 위의 한 점 $L_{1}(s)=P_{1}+s\times D_{1}$, $L_{2}(t)=P_{2}+t\times D_{2}$를 찾아 그 두 점을 잇는 벡터가 $D_{1}$, $D_{2}$에 모두 수직이 되도록 해야한다. 따라서, 다음과 같이 표현할 수 있다:
\[(L_{1}(s) - L_{2}(t)) \cdot D_{1} = 0\] \[(L_{1}(s) - L_{2}(t)) \cdot D_{2} = 0\]이를 전개하면 다음과 같이 쓸 수 있다:
\[s\,(D_{1}\cdot D_{1}) - t\,(D_{1}\cdot D_{2}) = (P_{2}-P_{1})\cdot D_{1}\] \[s\,(D_{1}\cdot D_{2}) - t\,(D_{2}\cdot D_{2}) = (P_{2}-P_{1})\cdot D_{2}\]이는 연립방정식 $s,t$를 구하는 문제와 같으며 크래머 공식을 사용하여 아래와 같이 전개한다.
\[\mathrm{det}=(D_{1}\cdot D_{1})(D_{2}\cdot D_{2})-(D_{1}\cdot D_{2})^{2}\] \[s = \frac{\big((P_{2}-P_{1})\cdot D_{1}\big)(D_{2}\cdot D_{2}) - (D_{1}\cdot D_{2})\big((P_{2}-P_{1})\cdot D_{2}\big)}{\mathrm{det}}\] \[t = \frac{(D_{1}\cdot D_{1})\big((P_{2}-P_{1})\cdot D_{2}\big) - \big((P_{2}-P_{1})\cdot D_{1}\big)(D_{1}\cdot D_{2})}{\mathrm{det}}\]$s,t$가 각 선분 범위 내라면 중점 $(L_{1}(s)+L_{2}(t))/2$를 접촉점으로 사용한다.
5. Box-Box 충돌 감지 정리
이제 모든 걸 조합한 코드이다:
함수 boxBoxCollisionDetection(box1, box2):
// 1단계: SAT로 충돌 여부 확인 및 최소 침투 축 찾기
result = findMinimumPenetrationAxis(box1, box2)
if result == null:
return null // 충돌 없음
bestAxis, minPenetration, axisIndex = result
// 2단계: 축 타입에 따라 접촉점 계산
if axisIndex < 6: // 면 축 (0-5)
if axisIndex < 3:
// Box1의 면, Box2의 꼭짓점
contact = createFaceVertexContact(box1, box2, axisIndex, minPenetration)
else:
// Box2의 면, Box1의 꼭짓점
contact = createFaceVertexContact(box2, box1, axisIndex-3, minPenetration)
contact.normal = -contact.normal // 방향 뒤집기
else: // 모서리 교차 축 (6-14)
edgeCase = axisIndex - 6
box1EdgeIndex = edgeCase / 3 // 0,1,2 (X,Y,Z)
box2EdgeIndex = edgeCase % 3 // 0,1,2 (X,Y,Z)
// 각 박스에서 충돌하는 모서리 찾기
edge1Center = findEdgeCenter(box1, box1EdgeIndex, bestAxis)
edge2Center = findEdgeCenter(box2, box2EdgeIndex, bestAxis)
// 두 모서리 사이의 접촉점 계산
contactPoint = findClosestPointsBetweenEdges(
edge1Center, box1.axis[box1EdgeIndex], box1.halfSize[box1EdgeIndex],
edge2Center, box2.axis[box2EdgeIndex], box2.halfSize[box2EdgeIndex]
)
contact = Contact(
normal: bestAxis,
point: contactPoint,
penetration: minPenetration
)
return contact
먼저 SAT로 충돌을 확인해서 15개 축을 테스트해 최소 침투 축을 찾는다. 그 다음 접촉 타입을 판별해서 면 축인지 모서리 교차 축인지 확인하고, 마지막으로 접촉점을 계산할 때 타입에 맞는 방법으로 접촉점을 구한다.
6. SAT의 장단점
SAT의 장점은 볼록 다면체에 대해 충돌 감지를 제공하고, 충돌 여부뿐만 아니라 접촉 데이터까지 모두 계산할 수 있다. 단점으론 볼록 다면체에만 적용할 수 있다. 또한 성능 면에서도 15개 축을 모두 테스트해야 하므로 계산 비용이 상당하다.
끝맺으며
이 책의 번역판 품질이 별로라는 평이 있는데, 사실 원서도 그리 친절하진 않다. 다음 글은 SAT외 다른 충돌감지 알고리즘을 소개하고 언리얼엔진에선 어떻게 응용하고 있는지 분석해보고자 한다.