[카테고리:] Algorithms

많은 스플라인의 종류 중에 하나인 큐빅 스플라인을 1차원의 보간에 적용하는 것에 대해 살펴보겠습니다. Catmull-Rom 스플라인을 구성하는 구분된 부드러운 곡선들을 나타내는 키 프레임 집합을 가지며 모든 키는 곡선 상에 위치합니다. 이 루틴을 사용하기 위해서 4개의 키 프레임 값이 필요합니다. 이 4개의 키 값을 v0, v1, v2, v3라고 하고, 여기에 보간을 위하여 v1에서 v2 사이의 지정된 0~1까지의 범위를 가지는 실수값 x가 존재합니다. 아래의 f(x)의 반환값은 x값에 의해 결정이 됩니다.

여기서 M은 다음처럼 정의됩니다.

아래의 이미지는 v1에서 v2 사이의 곡선의 한 예를 나타난 것입니다. 이 곡선은 위의 수식에서 x 값을 0에서 1.0 사이의 값을 이용해 얻을 수 있습니다.

아래의 코드는 위에서 설명한 내용을 C언어로 구현한 것입니다.

/* Coefficients for Matrix M */
#define M11  0.0 
#define M12  1.0
#define M13  0.0
#define M14  0.0
#define M21 -0.5
#define M22  0.0
#define M23  0.5
#define M24  0.0
#define M31  1.0
#define M32 -2.5
#define M33  2.0
#define M34 -0.5
#define M41 -0.5
#define M42  1.5
#define M43 -1.5
#define M44  0.5

double catmullRomSpline(float x, float v0,float v1, float v2,float v3) {
    double c1,c2,c3,c4;

    c1 = M12*v1;
    c2 = M21*v0 + M23*v2;
    c3 = M31*v0 + M32*v1 + M33*v2 + M34*v3;
    c4 = M41*v0 + M42*v1 + M43*v2 + M44*v3;

    return(((c4*x + c3)*x +c2)*x + c1);
}

이 글의 원문은 http://www.lighthouse3d.com/opengl/maths/index.php?catmullrom 입니다.

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

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

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

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

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

결국… 교차 여부는 세 값(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는 내적과 외적을 구하는 함수입니다.