큐브와 큐브의 충돌 검사 - 소프트웨어 융합

회전된 큐브의 충돌 검사는 축에 정렬된 충돌 검사(AABB)로는 충분하지 않는다. 이를 해결하기 위해서는 SAT(Separating Axis Theorem) 또는 OBB(Oriented Bounding Box)를 사용해야 한다. 이 중 SAT는 두 물체 사이의 충돌 여부를 판단할 때 많이 사용되는 이론이며, 회전된 큐브의 충돌 검사에도 적합한다.

1. SAT(Separating Axis Theorem)의 개념

SAT는 두 물체가 충돌하지 않으려면 적어도 하나의 분리 축(Separating Axis)이 존재해야 한다는 원리이다. 분리 축이 존재하면 두 물체는 해당 축을 따라 투영된 값들이 서로 겹치지 않기 때문에 충돌하지 않는다. 반면, 모든 축에서 투영된 값이 겹치면 충돌이 발생한 것이다.

2. 큐브의 꼭짓점 계산

회전된 큐브는 각 꼭짓점이 회전되어야 하므로 회전 행렬을 적용하여 각 큐브의 꼭짓점을 새로 계산해야 한다. 회전된 큐브의 꼭짓점은 8개이며, 회전된 상태에서 새로운 좌표를 얻기 위해 회전 행렬을 사용한다.

예시: 큐브1의 꼭짓점 좌표가 회전되면 이를 다음과 같이 표현할 수 있다.

$\mathbf{P'} = \mathbf{R} \cdot \mathbf{P}$

여기서: - $\mathbf{P'}$ 는 회전 후의 꼭짓점 좌표이다. - $\mathbf{R}$ 은 회전 행렬이다. - $\mathbf{P}$ 는 원래 꼭짓점 좌표이다.

3. 각 축에 투영 계산

SAT의 핵심은 두 큐브의 각 꼭짓점을 특정 축에 투영하여 비교하는 것이다. 투영된 값을 계산하는 방법은 다음과 같다:

$p = \mathbf{v} \cdot \mathbf{a}$

여기서: - $p$ 는 꼭짓점 $v$ 가 축 $a$ 에 투영된 값이다. - $\mathbf{v}$ 는 큐브 꼭짓점의 좌표 벡터이다. - $\mathbf{a}$ 는 투영할 축의 단위 벡터이다. - $\cdot$ 는 내적 연산이다.

예시: 투영 계산

$p = (x_v, y_v, z_v) \cdot (x_a, y_a, z_a) = x_v x_a + y_v y_a + z_v z_a$

투영된 값은 각 축에 대해 큐브의 꼭짓점이 얼마나 투영되었는지를 나타낸다.

4. 최소/최대 투영 값 계산

두 큐브의 꼭짓점들을 특정 축에 투영한 후, 그 축에 대한 최소값과 최대값을 계산한다. 이 값들은 큐브가 해당 축에 대해 얼마나 퍼져 있는지를 나타낸다.

$\text{min}(p_1, p_2, \dots, p_8), \quad \text{max}(p_1, p_2, \dots, p_8)$

5. 분리 축 검사

두 큐브가 충돌하지 않으려면 투영된 값들이 겹치지 않는 축이 하나라도 존재해야 한다. 이 축을 분리 축이라고 하며, 분리 축이 존재하면 두 큐브는 충돌하지 않는다고 판단할 수 있다. 이를 수학적으로 표현하면:

$\text{max}_1 < \text{min}_2 \quad \text{또는} \quad \text{max}_2 < \text{min}_1$

이 식이 참이면, 두 큐브는 해당 축에서 분리되어 있으며 충돌하지 않는 것이다.

6. 모든 축에 대해 검사

SAT는 가능한 모든 축에 대해 투영된 값이 겹치는지 여부를 검사한다. 회전된 큐브 사이의 충돌을 검사할 때는 15개의 축을 검사해야 한다:

각 큐브의 3개의 축(x, y, z 축).
각 큐브의 면의 법선 벡터.
각 큐브의 모서리 간의 외적(두 큐브 모서리 사이의 벡터).

이 15개의 축에 대해 투영된 값들이 겹치지 않으면 두 큐브는 충돌하지 않는다. 모든 축에서 투영된 값이 겹치면 두 큐브는 충돌한 것이다.

7. 충돌 검사 알고리즘

다음은 두 큐브 간의 충돌 여부를 계산하는 Python 코드 예시이다.

import numpy as np

def project_onto_axis(vertices, axis):
    projections = [np.dot(vertex, axis) for vertex in vertices]
    return min(projections), max(projections)

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

def check_collision(cube1_vertices, cube2_vertices, axes):
    for axis in axes:
        if is_separating_axis(cube1_vertices, cube2_vertices, axis):
            return False  # 분리 축이 있으면 충돌하지 않음
    return True  # 모든 축에서 겹치면 충돌

cube1_vertices = [np.array([1, 1, 1]), np.array([1, 1, -1]), np.array([1, -1, 1]), np.array([1, -1, -1]),
                  np.array([-1, 1, 1]), np.array([-1, 1, -1]), np.array([-1, -1, 1]), np.array([-1, -1, -1])]

cube2_vertices = [np.array([2, 2, 2]), np.array([2, 2, 0]), np.array([2, 0, 2]), np.array([2, 0, 0]),
                  np.array([0, 2, 2]), np.array([0, 2, 0]), np.array([0, 0, 2]), np.array([0, 0, 0])]

axes = [np.array([1, 0, 0]), np.array([0, 1, 0]), np.array([0, 0, 1])]

collision = check_collision(cube1_vertices, cube2_vertices, axes)
print("충돌 여부:", collision)

이 코드는 회전된 큐브 간의 충돌 여부를 SAT를 사용하여 검사한다.