1. 광선

  • 광선 위의 한 점에 대한 표현

    $$ r(t) = o + t d \text{(o는 원점, d는 방향벡터)} $$

  • 방향벡터가 항상 단위 벡터임이 보장되지는 않지만, 관련 연산 대부분에서 방향벡터를 정규화하여 사용함

2. 표면

  • Ray - Object 교차의 기본이 되는 표면은 크게 음함수 표면과 명시적 표면으로 구분됨

명시적 표면

  • 한 변수를 다른 변수들의 함수로 직접 표현하는 방식

    $$ z = f(x, y) $$

  • 예시: 포물선의 표면

    $$ z = x^2 + y^2 $$

  • 명시적 표면과 Ray 간 교차를 검사할 때, 함수에 \(x\), \(y\) 값을 대입해보고 그 값을 z값과 비교하여 표면에 있는 점인지, 표면을 지난 점인지, 표면에 닿지 못한 점인지 결정

  • 구의 경우 처럼 \(x\), \(y\) 값을 대입하면 \(z\)가 두 개의 값이 가능한 경우는 명시적 표현으로 표현하지 못함

    $$ x^2 + y^2 + z^2 = r^2 $$
    • 기하학적으로 이해하면, 특정 \(x\), \(y\)에 대해 위쪽 반구의 \(z\) 지점과 아래쪽 반구의 \(z\) 지점 총 두 개가 생기기 때문에 표현 불가

음함수 표면

  • 함수값이 0이되는 점들의 집합이 표면

    $$ F(x, y, z) = 0 $$

  • 예시: 구의 표면

    $$ F(x, y, z) = x^2 + y^2 + z^2 - r^2 $$

  • 함수에 \(x\), \(y\), \(z\) 값을 대입해보고 그 값이 0인지 검사하여 표면에 있는 점인지, 표면을 지난 점인지, 표면에 닿지 못한 점인지 결정

  • 음함수 표면은 어떤 형태든 표현이 가능하다는 장점이 있음

    • 명시적 표면 또한 음함수 표면으로 바꿀 수 있으며, 때문에 명시적 표면은 음함수 표현의 특별한 경우로 볼 수 있음

      $$ F(x, y, z) = z - f(x, y) $$

    • 그래픽스에서는 주로 음함수 표면을 교차 검사에 사용

3. 바운딩 볼륨

  • 삼각형 교차 검사나 Mesh 간 충돌 검사는 게임 엔진에서 가장 비싼 연산 중 하나임

  • 정교하게 충돌을 검사하기 전에 Naive하게 싼 연산으로 교차될 가능성이 없는 물체들을 먼저 걸러낸 뒤, 교차 후보가 되는 물체들만 정교하게 검사하기 위해 Naive한 교차 검사 대상으로 바운딩 볼륨을 사용함

    • 일반적으로 Local BV와 World BV를 모두 관리하며, World BV로 1차, Local BV로 2차로 검사함

  • 일반적으로 구나 박스 형태를 사용하며, Unreal Engine에서는 그 둘을 합친 BoxSphereBounds라는 구조를 사용함

AABB(Axis-Alinged Bounding Box)

  • 객체를 감싸는 축 정렬 직육면체 경계 박스

  • 박스의 면이 좌표축과 항상 평행함

  • 계산이 단순하고 축 비교만 하면 되어서 거의 모든 엔진에서 기본으로 사용됨

  • 단, 객체가 회전하여도 AABB는 축 정렬이기 때문에 함께 회전하지 않으므로 회전이 끝날 때마다 다시 계산해야 함

  • 일반적인 구성

    struct AABB
{
    FVector Min;
    FVector Max;
}

  • 박스 내부 판정

    bool Inside =
    P.x >= Min.x && P.x <= Max.x &&
    P.y >= Min.y && P.y <= Max.y &&
    P.z >= Min.z && P.z <= Max.z;

AABB 생성과 변형

  • AABB 생성 자체는 전체 정점 집합을 돌아다니며 각 축의 최소, 최대 지점을 찾으면 되지만, 이 연산도 물체의 변형이 발생할 때마다 수행하면 연산이 부담될 수 있음

  • Unreal Engine에서는 물체의 Local AABB를 물체 생성 시 먼저 계산하고, 물체가 변형됨에 따라서 함께 변형함

    • UStaticMeshComponent 등에서 생성 시 Local AABB를 저장

      • AABB를 생성한 후 Origin 저장

        $$ c = \frac{\mathrm{min} + \mathrm{max}}{2} $$

    • USceneComponent에서 Transform 변경 발생 시 BV 업데이트

  • 변형 방법

    • Unreal Engine의 TBoxSphereBounds는 원점 벡터 Origin과 각 축 방향으로의 BoxExtents(벡터)를 가지고 있음

    • 물체에 가해진 변환 행렬을 \(M\)으로 가정

    • Origin은 단순히 \(M\)의 이동 연산 부분만 활용하여 물체와 함께 이동만 시켜주면 됨

    • 변환 행렬의 선형 변환 부분을 \(A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\\\ a_{21} & a_{22} & a_{23} \\\\ a_{31} & a_{32} & a_{33} \end{bmatrix}\), BoxExtents 벡터를 \(e\)라 하면, BoxExtents는 \(e' = e|A|\)로 계산할 수 있음

      $$ e_x^{'} = |a_{11}|e_x + |a_{21}|e_y + |a_{31}|e_z $$$$ e_y^{'} = |a_{12}|e_x + |a_{22}|e_y + |a_{32}|e_z $$$$ e_z^{'} = |a_{13}|e_x + |a_{23}|e_y + |a_{33}|e_z $$

Bounding Sphere 생성과 변형

  • Bounding Sphere는 오히려 AABB보다 간단하다고 볼 수 있음

  • Unreal Engine에서 Bounding Sphere를 생성할 때는, AABB와 유사하게 전체 정점 집합에서 AABB로부터 계산된 Origin으로부터 가장 멀리 떨어진 정점 정보를 통해 반지름 정보 SphereRadius를 계산

  • 변형할 때는 원점은 그대로 이동만 시키고, 회전에는 영향을 받지 않음

  • 변형에서 고려해야하는 부분은 스케일

    • 균일 스케일의 경우에는 간단히 반지름에 스케일 계수를 곱하여 변형

    • 비균일 스케일의 경우에는 각 방향으로 가장 큰 스케일 값을 반지름에 곱하여 변형

4. 교차

광선 - 구

  • 기본적으로 구의 음함수 표면 검사

    $$ f(p) = |p - c| - r = 0 $$

  • 광선을 대입하여 정리

    $$ f(r(t)) = |r(t) - c| - r = 0; $$$$ |o + td - c| = r $$$$ (o + td - c) \cdot (o + td - c) = r^2 $$$$ t^2(d \cdot d) + 2t(d \cdot (o - c)) + (o - c) \cdot (o - c) - r^2 = 0 $$

  • 만약 광선의 \(d\)가 단위 벡터이고, \(b = d \cdot (o - c), c = (o - c) \cdot (o - c) - r^2\)라고 가정하면, \(t\)에 대해 아래 식으로 정리됨

    $$ t = -b^2 \pm \sqrt{b^2 - c} $$

  • 즉, \(b^2 - c\)에 따라 광선이 구에 맞는지 맞지 않는지를 검사할 수 있음

광선 - 상자

  • OBB까지 가능한 방법은 아니고, AABB에 특화된 조금 더 빠른 알고리즘

    • ‘슬래브 방법’이라고 부름

  • \(x\), \(y\), \(z\)에 해당하는 축을 크게 \(A\)라고 표현

  • 광선이 출발점에서 끝점(광선은 원래 끝이 없지만 물리 연산 한계상 약 시작점 + 100,000 정도를 끝점을 잡음)까지 도착할 때 시간을 1로 두고, 광선이 출발점에서 처음 AABB에 닿는 시간을 \(t\)로 둠

  • \(t\)의 각 축을 다음과 같이 정의

    $$ t.A = \frac{Box.Min.A - Start.A}{End.A - Start.A} $$

    • 단, 계산 시 광선의 시작점과 끝점이 모두 AABB를 지나지 않는다면 연산 자체를 하지 않음

    • 시작점이 애초에 AABB 안에 있어도 연산을 따로 수행하지 않음

  • \(t\)의 각 축 값 중 가장 큰 값이 실제로 광선이 AABB에 닿는 시점

  • Unreal Engine 소스코드에서는 마지막에 부동 소수점 오차를 고려하는 임계값을 추가함

광선 - 삼각형

  • 상용 엔진에서는 Ray Casting을 여러 phase를 통해 사용하는데, 가장 낮은 narrow phase에서는 거의 반드시 광선 - 삼각형 검사를 수행하게 됨

    • 광선 - 폴리곤 검사 방법이 연구되기도 하지만, GPU는 결국 Mesh를 삼각형 기반으로 렌더링하고, CPU에서 처리 또한 삼각형 단위로 하기 때문에 광선 - 삼각형 교차 검사는 그래픽스에서 절대적인 표준 검사임

  • 아래에서 다루는 방법은 광선 - 삼각형 교차의 가장 표준적인 알고리즘인 Möller–Trumbore 교차 알고리즘이라고 부름

  • ‘삼각형이 놓인 평면과 광선의 교차점을 계산해서, 해당 교차점이 삼각형 내에 있는지 검사하면 되지 않나?‘하고 생각할 수도 있지만, 두 단계로 분리하여 구현하면 각종 분기 처리가 늘어나고 수치적으로 계산이 번거로워지는 부분이 생김

    • Möller–Trumbore 교차 알고리즘은 이런 연산을 한 번에 처리함

  • 삼각형 내부의 한 점에 대한 표현(\(V_{0, 1, 2}\)는 삼각형의 각 정점, \(u\), \(v\)는 삼각형 무게중심 좌표계 내 임의의 스칼라)

    $$ P = V_0 + u E_1 + v E_2 $$$$ E_1 = V_1 - V_0 $$$$ E_2 = V_2 - V_0 $$

  • 광선과 삼각형이 만날 때의 식

    $$ O + t D = V_0 + u E_1 + v E_2 $$

    정리하면,

    $$ O - V_0 = u E_1 + v E_2 - t D $$

    • 각 변수의 조건은 다음과 같음

      $$ u \ge 0, v \ge 0, u + v \le 1, t \gt 0 $$

  • 광선의 방향 벡터 \(D\)는 필수는 아니지만 정규화해두는 편이 좋음(숫자가 깔끔해짐)

  • 계산 알고리즘

    1. 먼저 \(P\) 벡터와 \(\mathrm{Det}\)를 계산

      $$ P = D \times E_2 $$$$ \mathrm{Det} = E_1 \cdot P = E_1 \cdot (D \times E_2) $$

      • \(\mathrm{Det}\)는 스칼라 삼중곱으로, \(E_1\), \(E_2\), \(D\)가 만드는 부피에 해당하는 값으로도 볼 수 있음

      • \(\mathrm{Det}\)가 0에 가깝다는 것은 광선의 방향 벡터 \(D\)가 삼각형 평면과 거의 평행하거나, 삼각형의 형태가 의미없을 정도로 찌그러져 있다는 뜻이므로 안정적으로 풀 수 없다는 뜻이기에 EPSILON(일반적으로 1e-6f)등과 비교하여 연산을 멈춤

        if (fabs(Det) < EPSILON) { return false; }
        • Back-face culling 시, 삼각형의 뒷면은 클릭해도 선택되지 못하게 하려면 fabs(Det)대신 그냥 Det 사용

    2. \(u\) 계산

      $$ T = O - v $$$$ u = \frac{T \cdot P}{\mathrm{Det}} $$

      • \(T\)는 삼각형의 기준점 \(V_0\)에서 광선의 원점 \(O\)까지 가는 벡터

      • 대부분의 게임 엔진에서는 \(u\)가 범위를 벗어나면 연산을 멈춤

        if (u < 0.0f || u > 1.0f) { return false; }

    3. \(v\) 계산

      $$ Q = T \cdot E_1 $$$$ v = \frac{D \cdot Q}{\mathrm{Det}} $$

      • \(v\)의 범위나 \(u + v\)의 범위가 벗어나면 연산을 멈춤

        if (v < 0.0f || u + v > 1.0f) { return false; }

    4. 마지막으로 \(t\) 계산

      $$ t = \frac{E_2 \cdot Q}{\mathrm{Det}} $$

      • 만약 \(t < 0\)이라면 광선이 삼각형의 지나친 곳에서 발사되었다는 뜻이므로 교차 부정

        if (t < 0.0f) { return false; }

    5. 여기까지 모든 조건 검사를 통과하면 삼각형과 광선이 교차하는 것이며, 그 교차점은 \(O + t D\)임

5. Ray Casting을 위한 Inverse Projection / View

  • Ray casting은 결국 World 공간에서 일어나지만, 마우스 선택 자체는 Screen 공간에서 일어나기 때문에 렌더링 파이프라인의 공간 좌표계 변환 과정을 역으로 수행할 필요가 있음

  • 화면의 마우스 좌표\((s_x, s_y)\)에 대한 공간 좌표계 역변환

    1. Screen 공간 -> NDC 공간: 화면 위의 마우스 위치를 정규화된 좌표로 변환

      $$ x_{\mathrm{NDC}} = \frac{2s_x}{\mathrm{width}} - 1 $$$$ y_{\mathrm{NDC}} = 1 - \frac{2s_y}{\mathrm{height}} $$

    2. Near / Far 점 만들기: 같은 \((x, y)\)에 \(z\)만 다르게 하여 두 점을 생성

      • Graphics 라이브러리 API 규약에 따라 \(z\) 범위가 다름

        • OpenGL: \([-1, 1]\), DirectX: \([0, 1]\)

      • \(z\) 뿐 아니라, 4차원 동차 좌표(homogeneous coordinate)로 마지막 원소 1도 추가해줌

    3. Inverse Projection: NDC 공간 -> View 공간

      $$ P_{\mathrm{view}} = P_{\mathrm{clip}} \cdot M_{\mathrm{projection}}^{-1} $$

      • 역변환의 결과는 보통 \((x, y, z, w)\)의 형태로 나오는데, 이를 실제 3D 점처럼 쓰기위해 \(w\)로 나누어주는 homogeneous divide를 수행함

        $$ (x' = \frac{x}{w}, y' = \frac{y}{w}, z' = \frac{z}{w}, 1) $$

    4. Inverse View: View 공간 -> World 공간

      $$ P_{\mathrm{world}} = P_{\mathrm{view}} \cdot M_{\mathrm{view}}^{-1} $$
      • 사실 View 공간에서도 이미 광선은 View 공간의 원점에서 출발하는 광선으로써 사용할 수 있기 때문에 View 공간에서 연산을 수행해도 되지만, 보통 최종적으로 Inverse View까지 수행함

    5. World Ray 생성: \(P_{\mathrm{near}^{\mathrm{world}}}\), \(P_{\mathrm{far}^{\mathrm{world}}}\) 두 점을 이용하여 World 공간 내 광선 생성

      $$ O = P_{\mathrm{near}^{\mathrm{world}}} = \mathrm{CameraPosition} $$$$ D = \mathrm{normalize}(P_{\mathrm{far}^{\mathrm{world}}} - O) $$

6. 상용 엔진에서 Ray Casting을 활용하는 방법

  • 엔진 개발자의 입장에서는 Ray Casting으로 제일 먼저 떠올릴 수 있는 것이 편집기 화면 내에서의 객체 선택임

  • 하지만 실제로 상용 엔진에서는 편집기 내 객체 선택에 주로 색 기반 방식을 사용함(Unreal Engine의 Hit Proxy 등)

  • 게임 내 물리 충돌 검사 등에서 Ray Casting을 주로 활용하게 되는데, 정확한 검사를 위해서는 게임 내 모든 객체의 정점들을 이용하여 일일히 광선-삼각형 연산을 수행해야 하지만, 이는 매우 심각한 성능 손실을 가져옴

    • 객체의 형태가 조금만 복잡해져도 객체 하나에 수많은 정점과 삼각형 프리미티브들이 존재하게 됨

  • 이 성능 손실을 감쇠하기 위해 상용 엔진에서는 Ray Casting 검사를 여러 페이즈로 나누어서 계산함

  • 일반적인 phase 구성

    1. Broad Phase: BV를 활용하여 광선과 충돌할 가능성이 있는 객체들만 추리기

    2. Mid Phase: 객체와 관련된 각종 필터(Visibility, 충돌 무시 플래그 등)를 이용하여 객체 추리기

    3. Narrow Phase: 후보 객체들 중에서 광선이 어떤 객체를 맞추었는지 정확히 계산

      • 여기서도 간단한 형태의 지오메트리를 활용하여 근사적 처리를 할 수 있음(정확도 감소, 속도 증가)

        • Unreal Engine에서는 trace_complex 옵션이 true가 아니면 간단한 형태의 지오메트리로 빠르게 검사함