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개의 축을 검토한다:

각 OBB의 3개의 축 ( $\mathbf{u}_{A1}, \mathbf{u}_{A2}, \mathbf{u}_{A3}$ )
각 OBB의 3개의 축 ( $\mathbf{u}_{B1}, \mathbf{u}_{B2}, \mathbf{u}_{B3}$ )
각 OBB의 모든 축과 다른 OBB의 각 축의 외적 ( $\mathbf{u}_{A_i} \times \mathbf{u}_{B_j}$ )

SAT 적용

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

축과 변환 계산:

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

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| $$

충돌 여부 결정:

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

$|\mathbf{t} \cdot \mathbf{a}_i| > R_A + R_B$

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

OBB 충돌 감지의 계산 효율성

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

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

예제 코드

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

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 충돌 감지를 효율적으로 수행할 수 있지만, 연산량을 줄이기 위한 최적화가 필요하다. 실시간 그래픽스나 물리 엔진에서 주로 사용되며, 정확도를 높이기 위해 다양한 최적화 기법이 함께 사용된다.