[태그:] Algorithm

많은 스플라인의 종류 중에 하나인 큐빅 스플라인을 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는 내적과 외적을 구하는 함수입니다.

시작점에서 어떤 방향으로 무한히 뻗어 나가는 선을 편선(Ray)이라고하자.  시작점 p와 방향벡터 d로 정의된 편선이 있을때, 이 편선이 구(Sphere)와 교차하는지 확인하는 방법에 대해 생각해보자. 교차한다면 교차점은 하나 인가, 아니면 두개인가? 아래의 그림은 여개의 상황을 보여준다.

첫번째 질문은 편선과 구가 교차하는지의 여부인데, 이를 위해서 구의 중심점에서 편선까지의 거리를 구해야만 한다. 만약 그 거리가 구의 반지름보다 크다면 교차하지 않는다고 할 수 있다.

거리를 구하기 위해, 2가지 경우를 고려해야 하는데… 구의 중심점이 편선에 투영되는지 투영되지 않는지이다. 이는 내적을 통해 알 수 있다.

구의 중심점을 c라고 하고, p에서 c까지 가는 벡터를 v라고 하자.  그렇다면 만약…….

• d ∙ v > 0 이면 투영되므로 거리를 구할 수 있다는 것이고
• d ∙ v <= 0 이면 편선 뒤에 구가 있어 투영되지 않아 거리를 구할 수 없다는 것이다.

위의 두 경에 대해서 편선과 구와의 교차에 대해 살펴보도록 하자.

구의 중심점이 편선에 투영될 경우

아래의 그림은 투영될 경우에 대해서 가능한 3가지 경우이다. 구A는 교차하지 않는 것이고, 구B는 한 점에서만 교차하고 구C는 2점에서 교차한다.

편선 위에 구의 중심점의 투영을 계산해보자. pc를 투영된 점이라고 하면, 구A에 대한 편선 위의 투영점은 pcA이고 구B에 대한 것은 pcB, 구C에 대한 것은 pcC가 된다. pc에서 구의 중심점까지의 거리가 구의 반지름보다 크다면 교차하지 않는 것이고 구A가 그렇다. pc에서 구의 중심점까지의 거리가 구의 반지름과 같다면 한점에서 만나는 것이고 구B가 그 경우이고 교차점은 점 pc이다.

구C에 대한 경우는 반지름보다 그 거리가 작은 경우이고 2개의 교차점이 존재하며 이 2개의 교차점을 구하기 위해서는 좀더 생각을 해야 하는데… 다음과 같다.

먼저 점 pc는 내적을 이용한 투영을 통해 구할 수 있다. 투영법은 이 블로그의 투영에 관한 글을 참조하기 바란다. 그리고 두개의 교차점을 i1, i2라고 하자. 다음의 과정을 통해 i1을 얻을 수 있다.

p에서 i1까지 거리를 알고 있다고 가정하면, 이 거리를 di1이라고 하고 i1은 다음 공식을 통해 구할 수 있다.

위의 공식에서 p와 d는 이미 알고 있으므로, di1을 구하는 것만 남게 된다. 점i1, pc, c로 구성된 삼각형이 직각삼각형이므로, 피타고라스(Pythagorean) 공식을 적용해보면, 삼각형의 변의 길이를 a,b,c라고 할때…

• a = |c – i1| = 구의 반지름값
• b = |pc – c|
• c = |pc – i1|

위에서 오직 길이 c만이 미지수이며, 길이 c는 다음처럼 계산할 수 있다.

 

그림을 통해 di1은 다음과 같음을 알수있다.

앞서 계산한 di1은 편선의 시작점(p)가 구의 내부에 있지 않다고 가정한 것이다. 만약 p가 구 안쪽에 있다면 di1에 대한 계산은 아래처럼 달라진다.

구의 중심점이 편선에 투영되지 않는 경우

구의 중심점이 편선에 투영되지 않는 경우, 편선의 시작점이 구의 외부에 위치한다면 편선과 구가 교차하지 않는다는 것이다. 반면에… 편선의 시작점 p와 구의 중심점 c까지의 거리가 구의 반지름과 작거나 같다면 교차점이 존재한다. 같다면 p 자체가 교차점이다.

편선의 시작점이 구의 내부에 위치한다면, 앞의 구의 중섬점이 편선에 투영되는 경우와 같은 방법을 적용하여 교차점을 구할 수 있다. 아래 그림을 살펴면…

pc에서 i1까지의 거리 계산은 앞에서 본 것과 동일하다. 거리를 dist로 놓고.. di1은 다음처럼 계산할 수 있다.

 

이 글의 원문은 http://www.lighthouse3d.com/opengl/maths/index.php?planes

원문의 내용을 그대로 번역한 것이 아닌, 제가 이해하고 이해한 내용에 대해 내용을 추가하였으며 좀 더 쉽게 풀어서 다시 작성한 글입니다.

3차원 상에서 평면은 많은 방법으로 표현할 수 있습니다. 그러나 이 모든 방법들은 모두 평면 상에 존재하는 세개의 점을 알고 있다는 가정 아래서 표현이 됩니다. 여하튼….. 가장 일반적인 평면을 기술하는 수학적인 공식은 다음과 같습니다.

평면 상에 존재하는 점을 p0, p1, p2라고 하면, 계수 A, B, C와 D는 다음과 같은 절차로 계산됩니다.

1. 벡터 v와 u를 구하며, 벡터 v = p1 – p0, u = p2 – p0이다.
2. 벡터 n = v x u (v와 u의 외적)
3. 벡터 n을 정규화(크기가 1인 단위벡터화)
4. 벡터 n=(xn, yn, zn)이라고 한다면 계수 A=xn, B=yn, C=zn 임
5. 계수 D를 구하기 위해 앞에서 제시한 평면의 공식을 D에 대해 전개. 즉, -D = Ax + By + Cz
6. 평면 상의 점(예를 들어 p0)에 대해 위의 공식의 x, y, z에 값을 대입하여 D를 구함(이 값은 내적을 이용해 쉽게 구할 수 있음. 즉, D = -n ∙ p0)

어떤 점에서 평면까지의 거리와 그 의미

이 블로그의 포스팅된 글에 중에 이와 관련된 글이 있지만, 평면에 대한 공식을 알아보니.. 복습 차원에서 다시 한번 정리해 보겠습니다.

앞에서 평면 방정식의 계수를 구하는 방법을 이용해 얻은 평면의 공식 Ax + By + Cz + D = 0 이 있다고 할때, 이 평면과 어떤 점 r 사이의 거리는… 만약 r이 (xr, yr, zr)이라면 이 좌표를 위의 평면의 방정식에 대입하여 D에 대해 전개하여 구한 값에 대해 절대값을 취하면 됩니다. 즉, D = |Axr + Byr + Czr|이며 이는 내적의 공식을 이용해서 다음처럼 표현할 수 있습니다.

거리값이므로 D에 대해서 절대값을 취했는데, 그렇다면 이 부호의 의미는 무엇일까요? 먼저 D 값이 0이라면 r은 평면 상에 존재하는 점입니다. r이 양수라면 평면을 기준으로 벡터 n의 방향에 있는 공간상에 r이 존재하고 음수라면 그 반대 방향에 존재합니다.

평면상에 어떤 점을 투영

점 q를 평면 Ax + By + Cz + D = 0에 투영한 점은 q에서 가장 가까운 평면상의 점입니다. q에서 평면까지의 부호있는 거리(계수 D)를 dist라고 한다면… 평면상에 가장 가까운 점 p는 다음과 같습니다.