Ray vs Triangle 교차 테스트

Realtime Collision Detection 책의 Ray vs Triangle Intersection 부분에 나온 내용을 간추려봤습니다.

먼저 삼각형을 정의하겠습니다.

    \[T(u, v, w) = uA + vB + wC\]

(1)   \[\mathrm{s.t.} \quad u + v + w = 1 \; \mathrm{and} \; 0 \le u, v, w \le 1 \]

여기서 u, v, w 는 무게중심(barycentric) 좌표계를 나타냅니다. u = 1 - v - w 이므로 변수를 줄이기 위해 식을 약간 변형하면,

    \[T(v, w) = A + v(B-A) + w(C-A)\]

이제 Ray 를 정의하겠습니다.

    \[R(t) = P + t(Q-P)\]

(2)   \[\mathrm{s.t.} \quad t \ge 0 \]

이제 두 벡터 set 의 intersection 을 구하면 됩니다.

    \[T(v, w) = R(t)\]

    \[A + v(B-A) + w(C-A) = P + t(Q-P)\]

    \[(P-Q)t + (B-A)v + (C-A)w = P-A\]

이것은 결국 선형 방정식으로 풀 수 있습니다.

    \[\begin{bmatrix} (P-Q) & (B-A) & (C-A) \end{bmatrix} \begin{bmatrix} t \\ v \\ w \end{bmatrix} = \begin{bmatrix} (P-A)\end{bmatrix}\]

3×3 행렬의 역행렬을 구하는 대신 Cramer’s rule 에 의해 바로 선형 방정식을 아래와 같이 나타낼 수 있습니다.

    \[t = \frac{det\begin{bmatrix} (P-A) & (B-A) & (C-A) \end{bmatrix}}{det\begin{bmatrix} (P-Q) & (B-A) & (C-A) \end{bmatrix}}\]

    \[u = \frac{det\begin{bmatrix} (P-Q) & (P-A) & (C-A) \end{bmatrix}}{det\begin{bmatrix} (P-Q) & (B-A) & (C-A) \end{bmatrix}}\]

    \[v = \frac{det\begin{bmatrix} (P-Q) & (B-A) & (P-A) \end{bmatrix}}{det\begin{bmatrix} (P-Q) & (B-A) & (C-A) \end{bmatrix}}\]

위의 행렬식을 scalar 삼중곱으로 나타내면,

    \[\begin{aligned} t &= \frac{(P-A) \cdot \mathbf{n}}{d}\\ v &= \frac{(C-A) \cdot \mathbf{e}}{d}\\ w &= -\frac{(B-A) \cdot \mathbf{e}}{d} \end{aligned}\]

여기서,

    \[\begin{aligned} \mathbf{n} &= (B-A) \times (C-A)\\ d &= (P-Q) \cdot \mathbf{n}\\ \mathbf{e} &= (P-Q) \times (P-A) \end{aligned}\]

해를 구한후 처음 조건 (1), (2) 를 만족시키는가만 체크하면 교차 여부와 v, w 로 교차점의 삼각형 내부의 무게중심좌표를 구할 수 있습니다. 한가지 주의할 점은 d < 0 이면 ray 의 시작점의 뒤에 있다는 것이므로 유효한 해가 아니라는 것입니다.

참고로 삼각형 edge 들의 평면의 방정식을 미리 구해 놓았다는 가정하에, 좀 더 적은 연산으로 체크하는 방법이 Realtime Collision Detection 에 나와있습니다.

참고.
Realtime Collision Detection – M.K.

Leave a Reply

Your email address will not be published. Required fields are marked *