직선과 삼각형의 교차점 검사

공간에서 직선과 삼각형의 교차 여부를 조사하는 알고리즘을 이해하기 위해서는 먼저 무게 중심(barycentric coordicate)을 이해해야 한다. 즉, 삼각형이 3개의 버텍스 $r_{1}, r_{2}, r_{3}$ 로 구성되어 있을 때, 내부의 점 $r$ 은 $\lambda_{1}{r_{1}}+\lambda_{2}{r_{2}}+\lambda_{3}{r_{3}}$ 으로 표현할 수 있으며, $\lambda_{123}$ 은 $r$ 의 좌표에 미치는 $r_{123}$ 의 가중치를 나타낸다. $\lambda_{1} + \lambda_{2} + \lambda_{3} = 1$ 을 만족해야 한다. 따라서, 다음과 같이 정리할 수 있다.

$\lambda_{3} = 1 - \lambda_{1} - \lambda_{2}$

$\therefore t(\lambda_{1}, \lambda_{2}) = \lambda_{1}{r_{1} + \lambda_{2}{r_{2} + (1 - \lambda_{1} - \lambda_{2})r_{3}$

여기서 $\lambda_{1}, \lambda_{2}$ 는 $u, v$ 로 바꿔 쓸 수 있으며, 광선 $r(t)=o + td$ 와 삼각형의 교차점을 구하는 것은 방정식 $r(t) = t(u, v)$ 의 해를 구하는 것과 같다. 즉, 다음의 방정식으로 표현할 수 있다.

$o + td = (1 - u - v)r_{1} + ur_{2} + vr_{3}$

$\left(\begin{array}{rcl}\-d,$\; r_{2} - r_{1},$\; r_{3} - r_{1}\\\end{array}\right)\left(\begin{array}{rcl}t\\ u\\ v\\\end{array}\right) = o - r_{1}$

여기서 $e_{1} = r_{2} - r_{1},\: e_{2} = r_{3} - r_{1},\: s = o - v_{1}$ 로 정의하면, $t, u, v$ 는 크라머(Cramer)의 공식에 의해 구할 수 있다.

$\left(\begin{array}{rcl}t\\ u\\ v\\\end{array}\right) = \frac{1}{det(-d, e_{1}_, e_{2})}\left(\begin{array}{rcl}det(s, e_{1}, e_{2})\\ det(-d, s, e_{2})\\ det(-d, e_{1}, s)\end{array}\right)$

위의 식은 다음과 같이 다시 정리할 수 있다.

$\left(\begin{array}{rcl}t\\ u\\ v\\\end{array}\right) = \frac{1}{(d \times e_{2}) \cdot e_{1}} \left(\begin{array}{rcl}(s \times e_{1}) \cdot e_{2}\\ (d \times e_{2}) \cdot s\\ (s \times e_{1}) \cdot d\\ \end{array}\right) = \frac{1}{p \cdot e_{1}} \left(\begin{array}{rcl}q \cdot e_{2}\\ p \cdot s\\ q \cdot d\\ \end{array}\right)$

$\because p = d \times e_{2},\; q = s \times e_{1}$

최종적으로, 이것을 의사코드로 표현하면 다음과 같다.

// o is ray's original, d is direction, v1, v2, v3 is triangle coordinate
RayTriangle_Intersect(o, d, v1, v2, v3)
    Vertex e1 = v2 - v1
    Vertex e2 = v3 - v1
    Vertex p = d cross e2
    Scalar a = e1 dot p
    if(a > -epsilon and a < epsilon)
        return NO_INTERSECTION<br/>

    Scalar f = 1 / a
    Vertex s = o - v1
    Scalar u = f * (s dot p)
    if(u < 0 or u > 1)
        return NO_INTERSECTION

    Vertex q = s cross e1
    Scalar v = f * (d dot q)
    if(v < 0 or u + v > 1)
        return NO_INTERSECTION

Scalar t = f * (e2 dot q)
return INTERSECTION // u, v, t is solved

여기서 스칼라(scalar) 타입의 변수는 부동소수점 타입이며, Vertex는 x, y, z 3개의 공간좌표를 가진다. 여기서 입실론(epsilon)이 의아할텐데, 사실 컴퓨터에서 부동소수점 연산은 정확하지 않다. 즉, 방정식에서 정수로 표현되지 않는 유리수 사이에서의 연산 결과가 0이라고 하더라도, 컴퓨터에서는 0이 아닐 수 있다. 입실론은 이 오차 범위를 나타내는데, 이 입실론 값은 $\epsilon = 1.0^{-5}$ 인 경우 만족할만한 정확도를 보인다고 알려져 있다.

날개의 기억

직선과 삼각형의 교차점 검사

티스토리툴바

직선과 삼각형의 교차점 검사

'Library/Computer Graphics' Related Articles

티스토리툴바