SAT (Separating Axis Theorem)

Separating Axis Theorem (SAT, 분리 축 정리)은 충돌 감지 분야에서 많이 사용되는 중요한 이론 중 하나이다. 이 정리는 두 개의 볼록(Convex) 도형이 충돌하지 않으려면 두 도형을 완전히 분리할 수 있는 “축”이 존재해야 한다는 원리에 기반하고 있다. SAT는 주로 임의의 다각형이나 다면체에 대해 적용된다.

기본 개념

SAT의 기본 아이디어는 두 개의 도형이 충돌하지 않으려면, 어느 한 축에 대해서도 도형의 투영이 겹치지 않아야 한다는 것이다. 이 논리에 따라, 다음과 같은 간단한 단계로 충돌 여부를 감지할 수 있다.

1. 모든 가능한 분리 축을 정의한다. 이 축은 두 도형의 면 법선(Normal) 또는 에지 벡터(Edge Vector)를 사용하여 구할 수 있다.

2. 두 도형을 해당 축에 투영한다. 도형의 각 꼭짓점을 정의된 축에 투영하여 최대, 최소 값을 구한다.

3. 투영 구간이 겹치는지 확인한다. 두 구간이 겹치는 경우 해당 축에서는 분리되지 않는 것이다. 모든 축에 대해 이 절차를 수행한 후에도 겹치지 않는 축이 하나라도 있다면, 두 도형은 충돌하지 않은 것이다.

수학적 정식화

SAT를 수학적으로 설명하기 위해 먼저 필요한 몇 가지 정의와 개념을 정리하겠다.

투영

두 도형 $\mathbf{A}$와 $\mathbf{B}$가 존재한다고 가정한다. 각 도형의 꼭짓점들을 벡터로 표현할 수 있다. 도형 $\mathbf{A}$의 꼭짓점들은 다음과 같이 표현할 수 있다:

$$\mathbf{A} = \{ \mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n \}$$

도형 $\mathbf{B}$에 대해서도 동일하게 표현할 수 있다:

$$\mathbf{B} = \{ \mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_m \}$$

각 도형의 꼭짓점들이 주어진 분리 축 $\mathbf{s}$에 투영되었을 때, 투영값 $P(\mathbf{s}, \mathbf{v})$는 다음과 같이 계산된다:

$$P(\mathbf{s}, \mathbf{v}) = \mathbf{s} \cdot \mathbf{v}$$

여기서 $\mathbf{s} \cdot \mathbf{v}$은 벡터 $\mathbf{v}$가 축 $\mathbf{s}$에 투영된 스칼라 값이다.

최소 및 최대 투영 값

축 $\mathbf{s}$에 대한 도형 $\mathbf{A}$의 최소 투영값과 최대 투영값을 각각 $P_{\min}(\mathbf{A})$, $P_{\max}(\mathbf{A})$로 정의한다. 이는 다음과 같이 계산된다:

$$P_{\min}(\mathbf{s}, \mathbf{A}) = \min_{i} (\mathbf{s} \cdot \mathbf{a}_i)$$

$$P_{\max}(\mathbf{s}, \mathbf{A}) = \max_{i} (\mathbf{s} \cdot \mathbf{a}_i)$$

도형 $\mathbf{B}$에 대해서도 동일한 방식으로 정의한다:

$$P_{\min}(\mathbf{s}, \mathbf{B}) = \min_{i} (\mathbf{s} \cdot \mathbf{b}_i)$$

$$P_{\max}(\mathbf{s}, \mathbf{B}) = \max_{i} (\mathbf{s} \cdot \mathbf{b}_i)$$

충돌 여부 판단

도형 $\mathbf{A}$와 도형 $\mathbf{B}$가 충돌하지 않으려면, 어느 한 축에 대해서도 다음 조건을 만족해야 한다:

$$P_{\max}(\mathbf{A}) < P_{\min}(\mathbf{B}) \quad \text{또는} \quad P_{\max}(\mathbf{B}) < P_{\min}(\mathbf{A})$$

만약 어느 축에서도 이 조건이 만족되지 않는다면, 두 도형은 충돌하는 것이다. 이를 실제로 적용하기 위해서는 도형의 모든 가능한 분리 축을 탐색해야 한다.

분리 축의 선택

분리 축의 선택은 알고리즘의 성능과 정확성에 큰 영향을 미친다. n차원에서 두 도형 간 충돌을 판단하려면, 다음과 같은 축들이 주로 사용된다:

• 각 도형의 모든 면의 법선 벡터

• 모든 에지 벡터의 외적

특히 2D의 경우, 각 도형의 모든 에지에 수직인 벡터들을 에지 법선(Normal of Edge)로 사용한다. 3D의 경우, 각 도형의 에지와 다른 도형의 에지 간 외적도 계산하여 분리 축으로 사용한다.

2D SAT 알.고리즘 예제

2D에서 SAT 알고리즘의 간단한 구현 예제를 살펴보겠다. 이 예제는 두 개의 임의의 다각형이 충돌하는지 확인하는 과정이다.

단계 1: 다각형 정의 및 초기화

우선, 두 개의 다각형을 정의해야 한다. 각 다각형은 꼭짓점들의 리스트로 표현된다.

class Polygon:
    def __init__(self, vertices):
        self.vertices = vertices  # 꼭짓점 리스트

    def get_edges(self):
        edges = []
        for i in range(len(self.vertices)):
            start_vertex = self.vertices[i]
            end_vertex = self.vertices[(i + 1) % len(self.vertices)]
            edge = [end_vertex[0] - start_vertex[0], end_vertex[1] - start_vertex[1]]
            edges.append(edge)
        return edges

    def get_normals(self):
        edges = self.get_edges()
        normals = []
        for edge in edges:
            normal = [-edge[1], edge[0]]  # 에지에 수직인 벡터
            normals.append(normal)
        return normals

단계 2: 투영 및 충돌 검사 함수 정의

다각형을 특정 축에 투영하고 충돌 여부를 검사하는 함수를 정의한다.

def dot_product(v1, v2):
    return v1[0] * v2[0] + v1[1] * v2[1]

def project_polygon(vertices, axis):
    min_proj = dot_product(vertices[0], axis)
    max_proj = min_proj
    for vertex in vertices:
        proj = dot_product(vertex, axis)
        if proj < min_proj:
            min_proj = proj
        elif proj > max_proj:
            max_proj = proj
    return min_proj, max_proj

def is_separating_axis(axis, vertices1, vertices2):
    min1, max1 = project_polygon(vertices1, axis)
    min2, max2 = project_polygon(vertices2, axis)
    return max1 < min2 or max2 < min1

def polygons_collide(polygon1, polygon2):
    vertices1 = polygon1.vertices
    vertices2 = polygon2.vertices

    axes = polygon1.get_normals() + polygon2.get_normals()

    for axis in axes:
        if is_separating_axis(axis, vertices1, vertices2):
            return False
    return True

단계 3: 예제 실행

두 다각형이 충돌하는지 여부를 확인하기 위해 위의 함수를 호출한다.

polygon1 = Polygon([(0, 0), (2, 0), (1, 2)])
polygon2 = Polygon([(1, 1), (3, 1), (2, 3)])

collision = polygons_collide(polygon1, polygon2)

if collision:
    print("Polygons are colliding.")
else:
    print("Polygons are not colliding.")

이 예제에서는 두 개의 삼각형 다각형이 충돌하는지 여부를 확인한다. 실시간 물리 엔진에서는 이와 유사한 방식으로 SAT를 활용하여 다각형 및 다면체의 충돌 여부를 계산한다.

3D SAT 알고리즘

3D에서의 SAT는 2D와 개념적으로 유사하지만, 추가적으로 면(Face)과 에지(Edge) 간의 상호작용을 고려해야 한다.

분리 축 선택

3D에서의 분리 축은 다음 세 가지 유형을 포함한다:

1. 각 도형의 모든 면의 법선 벡터

2. 각 도형의 모든 에지 벡터

3. 각 도형의 에지와 다른 도형의 에지의 외적

각 축에 대해 투영값을 계산하고, 각각의 투영 구간이 겹치는지 확인하여 충돌 여부를 판단한다.

---

SAT는 다양한 형태의 도형 간 충돌을 효율적으로 감지할 수 있는 강력한 알고리즘이다. 특히 임의의 다각형이나 다면체와 같은 복잡한 도형에 적합한다. 그러나 SAT는 오직 볼록 다각형에만 적용할 수 있으므로, 비볼록 다각형의 경우 형태를 분해하여 여러 개의 볼록 다각형으로 처리하는 등의 추가적인 작업이 필요할 수 있다.