# 큐브와 큐브의 충돌 검사

회전된 큐브의 충돌 검사는 축에 정렬된 충돌 검사(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개의 축**을 검사해야 한다:

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

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

#### 7. 충돌 검사 알고리즘

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

```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를 사용하여 검사한다.