# OBB (Oriented Bounding Box)

OBB는 물체의 회전 및 스케일 변환을 고려하는 충돌 감지 알고리즘이다. 이는 AABB (Axis-Aligned Bounding Box)와 달리, 물체의 실제 회전 상태를 반영하는 박스를 사용한다. OBB의 주요 특징과 계산 방법에 대해 알아보겠다.

#### OBB의 기본 개념

* **정의**: OBB는 임의의 회전을 허용하는 최소한의 경계 박스이다. 각 객체에 맞춰진 경계 박스로, 객체의 회전을 고려한다.
* **구성 요소**: OBB는 중심점, 3개의 축(오브젝트의 로컬 축), 그리고 각 축에 대한 반경으로 구성된다.

#### OBB의 수학적 표현

OBB는 중심 $\mathbf{c}$, 축 $\mathbf{u}\_i$, 그리고 반경 $r\_i$로 정의된다. 각 축 $\mathbf{u}\_i$는 정규화된 기준 벡터이다:

$$
OBB = (\mathbf{c}, \mathbf{u}\_1, \mathbf{u}\_2, \mathbf{u}\_3, r\_1, r\_2, r\_3)
$$

* $\mathbf{c}$ : OBB의 중심
* $\mathbf{u}\_i$ : OBB의 축 (정규화된 벡터)
* $r\_i$ : 각 축에 대한 반경 (스케일 값)

#### 충돌 감지 알고리즘

**Separating Axis Theorem (SAT)**

SAT는 두 물체가 충돌하지 않음을 증명할 수 있는 방법을 제시한다. SAT에 따르면, 두 물체가 충돌하지 않으려면 충돌하지 않는 간격을 갖는 축이 적어도 하나 존재해야 한다.

OBB 간의 충돌 감지에서는 총 15개의 축을 검토한다:

1. 각 OBB의 3개의 축 ($\mathbf{u}*{A1}, \mathbf{u}*{A2}, \mathbf{u}\_{A3}$)
2. 각 OBB의 3개의 축 ($\mathbf{u}*{B1}, \mathbf{u}*{B2}, \mathbf{u}\_{B3}$)
3. 각 OBB의 모든 축과 다른 OBB의 각 축의 외적 ($\mathbf{u}*{A\_i} \times \mathbf{u}*{B\_j}$)

**SAT 적용**

구체적으로, SAT를 적용하여 두 OBB의 충돌을 체크하려면 다음 단계를 따른다:

1. **축과 변환 계산**:

   1.1. 각 OBB의 축 벡터를 획득한다. 1.2. 두 OBB의 중심 간의 벡터 $\mathbf{t} = \mathbf{c}\_B - \mathbf{c}\_A$를 계산한다. 1.3. $\mathbf{t}$를 OBB-A의 로컬 좌표계로 변환한다.
2. **축 투영**:

   2.1. 모든 15개의 축에 대해 해당 OBB의 반경을 각 축에 투영시켜 간격을 계산한다. 2.2. 다른 OBB에 대해서도 동일한 계산을 수행한다.

   각 축 $\mathbf{a}\_i$에 투영된 OBB의 반경은 다음과 같다:

$$
R\_A = r\_{A1} |\mathbf{u}*{A1} \cdot \mathbf{a}*i| + r*{A2} |\mathbf{u}*{A2} \cdot \mathbf{a}*i| + r*{A3} |\mathbf{u}\_{A3} \cdot \mathbf{a}\_i|
$$

```
반대로, OBB-B의 반경 투영 값은:
```

​

$$
R\_B = r\_{B1} |\mathbf{u}*{B1} \cdot \mathbf{a}*i| + r*{B2} |\mathbf{u}*{B2} \cdot \mathbf{a}*i| + r*{B3} |\mathbf{u}\_{B3} \cdot \mathbf{a}\_i|
$$

3. **충돌 여부 결정**:

   충돌 여부를 다음 조건을 통해 판단한다:

$$
|\mathbf{t} \cdot \mathbf{a}\_i| > R\_A + R\_B
$$

```
위의 조건을 만족하는 축이 하나라도 있다면, 두 OBB는 충돌하지 않는다.
```

#### OBB 충돌 감지의 계산 효율성

OBB 충돌 감지는 정확하지만 연산량이 많기 때문에 최적화가 필요하다. 이 과정에서 고려할 수 있는 최적화 방법에는 다음이 포함된다.

1. **단순화된 충돌 사전 체크**: AABB 또는 구체와 같은 더 단순한 경계 박스를 사용해 빠른 사전 체크를 수행할 수 있다. 두 개의 더 단순한 경계가 충돌하는 경우에만 세부적인 OBB 충돌 체크를 수행한다.
2. **축의 최소화**: 15개 축 모두를 검사하는 대신, 특정 상황에서는 일부 축을 생략할 수 있다. 예를 들어, 평행한 축에 대한 검사를 생략할 수 있다.
3. **연산 집약도 경감**: 벡터의 내적 및 절댓값 계산을 가능한 한 최소화하는 방안을 모색한다. 공통 연산을 도출해 캐싱하는 것도 하나의 방법이다.

#### 예제 코드

다음은 Python을 사용해 두 OBB 사이의 충돌을 감지하는 간단한 예제 코드이다:

```python
import numpy as np

def test_OBB_collision(cA, uA, eA, cB, uB, eB):
    # cA, cB: 중심점
    # uA, uB: 축벡터 (3x3 matrix)
    # eA, eB: 반경 (1x3 vector)
    
    # Compute rotation matrix expressing B in A’s coordinate frame
    R = np.dot(uA, uB.T)
    R_abs = np.abs(R) + np.finfo(float).eps  # Add small epsilon to avoid divide by zero
    
    # Vector from A center to B center
    t = np.dot(cB - cA, uA)
    
    # Test axes L = uA[i]
    for i in range(3):
        ra = eA[i]
        rb = eB[0] * R_abs[i, 0] + eB[1] * R_abs[i, 1] + eB[2] * R_abs[i, 2]
        if np.abs(t[i]) > ra + rb:
            return False
    
    # Test axes L = uB[i]
    for i in range(3):
        ra = eA[0] * R_abs[0, i] + eA[1] * R_abs[1, i] + eA[2] * R_abs[2, i]
        rb = eB[i]
        if np.abs(np.dot(t, R[:, i])) > ra + rb:
            return False

    # Test axis L = uA[i] x uB[j]
    for i in range(3):
        for j in range(3):
            ra = eA[(i + 1) % 3] * R_abs[(i + 2) % 3, j] + eA[(i + 2) % 3] * R_abs[(i + 1) % 3, j]
            rb = eB[(j + 1) % 3] * R_abs[i, (j + 2) % 3] + eB[(j + 2) % 3] * R_abs[i, (j + 1) % 3]
            if np.abs(t[(i + 2) % 3] * R[(i + 1) % 3, j] - t[(i + 1) % 3] * R[(i + 2) % 3, j]) > ra + rb:
                return False

    return True

center_A = np.array([0, 0, 0])
axis_A = np.eye(3)
extent_A = np.array([1, 1, 1])

center_B = np.array([1.5, 0, 0])
axis_B = np.eye(3)
extent_B = np.array([1, 1, 1])

is_collision = test_OBB_collision(center_A, axis_A, extent_A, center_B, axis_B, extent_B)
print("Collision:", is_collision)
```

***

OBB는 더 정밀한 충돌 감지를 제공하는 강력한 방법이다. SAT 기반의 기법을 이용해 OBB 충돌 감지를 효율적으로 수행할 수 있지만, 연산량을 줄이기 위한 최적화가 필요하다. 실시간 그래픽스나 물리 엔진에서 주로 사용되며, 정확도를 높이기 위해 다양한 최적화 기법이 함께 사용된다.