🔦 Ray casting

🔦 Ray casting

• R(t) = O + t * D 와 삼각형 P(u, v) = V0 + u * (V1- V0) + v * (V2 - V0) 가 있을 때
• R(t) = P(u, v) 를 만족하는 u, v, t 를 구한다
• u ≥ 0, v ≥ 0, u+v ≤ 1 일 때, R(t) 는 삼각형 내의 점이라고 판별할 수 있다.

1. 광선

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

\[r(t) = o + t d\]

(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{min + 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 + t d - c| = r\] \[(o + t d - c) \cdot (o + t d - 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 \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,\quad v \ge 0,\quad u + v \le 1,\quad t > 0\]

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

• 계산 알고리즘

  1. 먼저 P 벡터와 Det를 계산

\[P = D \times E_2\] \[Det = E_1 \cdot (D \times E_2)\]

    - `Det`는 스칼라 삼중곱으로, `E_1`, `E_2`, `D`가 만드는 부피에 해당하는 값으로도 볼 수 있음

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

      ```C++
      if (fabs(Det) < EPSILON) { return false; }
      ```

        - Back-face culling 시, 삼각형의 뒷면은 클릭해도 선택되지 못하게 하려면 `fabs(Det)`대신 그냥 `Det` 사용
    
2. `u` 계산

\[T = O - V_0\] \[u = \frac{T \cdot P}{Det}\]

    - `T`는 삼각형의 기준점 `V_0`에서 광선의 원점 `O`까지 가는 벡터

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

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

3. `v` 계산

\[Q = T \times E_1\] \[v = \frac{D \cdot Q}{Det}\]

    - `v`의 범위나 `u + v`의 범위가 벗어나면 연산을 멈춤

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

4. 마지막으로 `t` 계산

\[t = \frac{E_2 \cdot Q}{Det}\]

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

      ```C++
      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{2 s_x}{width} - 1\] \[y_{\mathrm{NDC}} = 1 - \frac{2 s_y}{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},\quad y' = \frac{y}{w},\quad z' = \frac{z}{w},\quad 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_near^world`, `P_far^world` 두 점을 이용하여 World 공간 내 광선 생성

\[O = P_{\mathrm{near}}^{\mathrm{world}}\] \[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가 아니면 간단한 형태의 지오메트리로 빠르게 검사함

Picking

• Sphere → AABB → Ray-Triangle test 를 순차적으로 수행 (연산 비용 순)