김형준 GIS 연구소 (for Developers) -

이 글은 http://www.lighthouse3d.com/opengl/maths/index.php?raytriint의 글을 통해 재구성한 글로, 변역하면서 쉽게 이해할 수 있도록 내용을 약간 수정했습니다.

매개변수방정식의 형태로 편선(시작점에서 어떤 방향으로 무한하게 진행하는 선, Ray)과 삼각형의 폴리곤이 주어질때.. 이 둘이 교차하는가를 판단하는 방법에 대해 증명은 생략하고 그 방법에 대해서 알아 보겠습니다.

삼각형을 구성하는 점은 다음처럼 정의할 수 있습니다.

삼각형의 구성 점(u,v) = (1-u-v)*p0 + u*p1 + v*p2
여기서, p0, p1, p2는 삼각형 위의 이미 알고 있는 점, u >= 0, v >= 0, u + v <= 1.0

그리고 편선에 대한 매개변수방정식을 다음처럼 정의할 수 있습니다.

편선의 구성 점(t) = p + t * d
여기서, p는 편선의 시작점으로 이미 알고 있는 점, d는 편선의 방향 벡터

이제 편선과 삼각형의 교점은 삼각형의 구성 점(u,v) = 편선의 구성 점(t) 로부터 다음과 같습니다.

p + t * d = (1-u-v) * p0 + u*p1 + v*p2

결국... 교차 여부는 세 값(t, u, v)가 위의 공식을 만족하고 u와 v가 앞서 정의한 조건을 만족하면 교차하는 경우이다. 이런 수학적인 논의는 다음으로 미루기로 하고.... 여러분이 원하는 C 코드로 대신합니다.

/* a = b - c */
#define vector(a,b,c) \
        (a)[0] = (b)[0] - (c)[0]; \
        (a)[1] = (b)[1] - (c)[1]; \
        (a)[2] = (b)[2] - (c)[2];

int rayIntersectsTriangle(float *p, float *d, float *v0, float *v1, float *v2) {
    float e1[3],e2[3],h[3],s[3],q[3];
    float a,f,u,v;
 
    vector(e1,v1,v0);
    vector(e2,v2,v0);
    crossProduct(h,d,e2);
    a = innerProduct(e1,h);
 
    if (a > -0.00001 && a < 0.00001) return(false);
 
    f = 1/a;
    vector(s,p,v0);
    u = f * (innerProduct(s,h));
 
    if (u < 0.0 || u > 1.0) return (false);
 
    crossProduct(q,s,e1);
    v = f * innerProduct(d,q);
    if (v < 0.0 || u + v > 1.0) return (false);

    // at this stage we can compute t to find out where 
    // the intersection point is on the line
    t = f * innerProduct(e2,q);
    if (t > 0.00001) // ray intersection
        return (true);
    else // this means that there is line intersection but not ray intersection
        return (false);
}

vector 함수는 두개의 좌표로부터 백터를 만드는 함수이고 innerProduct와 crossProduct는 내적과 외적을 구하는 함수입니다.

Tag : Algorithm

posted at 2009/02/11 21:09 | 프로그래밍/Algorithms | Comment(6)

Track this back : http://www.gisdeveloper.co.kr/trackback/467

Commented by 김영민 at 2009/02/11 22:35 r x

감사합니다. 많은 도움 되었습니다.

Commented by 김형준(Dip2K) at 2009/02/16 20:38 r x

네, 댓글 감사드립니다~

Commented by 강면구 at 2009/04/09 13:06 r x

좋은 정보 감사드립니다.^^

Commented by 김형준 at 2009/04/10 10:27 r x

강면구님, 댓글 또 한번 감사드립니다.. ^^

Commented by 수아 at 2009/06/17 10:02 r x

감사합니다. 간단한 프로젝트를 하고있는데 많은 도움이 되었습니다.

Commented by 김형준 at 2009/06/18 13:09 r x

수아님, 도움이 되셨다니 저도 좋습니다~ 댓글 감사드리구요~ ^^

name password homepage

hidden