하이트맵의 높이 구하기

지형의 높이를 구하는 것은 사각 평면상의 높이를 구하는 것이다.
맵툴에서 하나의 사각형 패치는 2개의 삼각형 메쉬로 이루어 진다.
맵툴에서 별도의 버텍스 편집만 하지 않는다면 대부분의 경우는 사각형 높이를 구하는 것 만으로도
충분하다.

사각형 높이를 구하는 방법 2가지,  선형 보간을 이용한 방식, 평면의 방정식을 이용한 방식 
방법을 알아본후 선형 보간을 이용해서 삼각형 별로 높이를 구하여 본다.

1. 선형 보간을 이용한 방식.

2. 평면의 방정식을 이용한 방식

3. 선형 보간을 응용한 삼각형 별로 높이 구하기

1. 선형 보간을 이용한 방식.

4개의 점으로 된 사각형 평면의 높이를 구할려면 쌍(또는 이중) 선형 보간(Bilinear interpolation)
을 이용한다.

직선의 선형 보간 공식은 다음과 같다.

점 A, B를 지나는 직선이 있다.  AB 사이에 임의의 점 t가 있고, t는 0.0 <= t < 1 단위로 표시한다.
이 때 선형 보간 공식은

          u(t) = Aㆍ( 1 - t ) + Bㆍt   이다.

쌍 선형은 말 그대로 선형 보간을 두 번 하는 것이다.
수평 선형을 u(t), 수직 선형을 v(t)라 한다.

          Col = Aㆍ( 1 - t ) + Bㆍt         (t는 0 <= t < 1 범위이다.)
          Row = Cㆍ( 1 - t ) + Dㆍt        

P(u, v) = Colㆍ( 1 - v ) + Rowㆍv
         = ( Aㆍ( 1ㆍu) + Bㆍ u )ㆍ( 1 - v )   +   ( C ㆍ ( 1 - u ) + D ㆍu ) ㆍv
         = Aㆍ( 1 - u )ㆍ( 1 - v ) + Bㆍuㆍ( 1 - v ) + Cㆍ( 1 - u )ㆍv + Dㆍuㆍv

버텍스간의 간격이 1인 정방형 사각형이라고 가정한다.  
x, y 좌표가 0.3, 0.1이고 A(0, 0, 10), B(1, 0, 100), C(0, 1, 100), D(1, 1, 100일때 값을 구해 보자.

float height(float fx, float fy)

{

    float A, B, C, D, u, v;

    A = C = 10.0f;

    B = D = 100.0f;

 

    u = fx;

    v = fy;

    float fHeight = A*( 1 - u )*( 1 - v ) + B*u*( 1 - v ) + C*( 1 - u )*v + D*u*v;

    return fHeight;

}

 

void main()

{

    printf("Height = %f\n", height(0.3f, 0.1f));

}

결과

Height = 37

2. 평면의 방정식을 이용한 방식

평면의 방정식을 이용하여 구하는 방법도 있다.
절두체 컬링에서 ax + by + cz + d = 0 이면 평면위에 있을때이다.
평면의 노멀 벡터를 구한 후, d 값을 구한다.  
마지막으로 평면위의 z 값을 구하면 높이가 나온다.

#include <stdio.h>

#include <d3d9.h>

#include <d3dx9.h>

#pragma comment (lib, "dxguid.lib")

#pragma comment (lib, "d3d9.lib")

#pragma comment (lib, "d3dx9.lib")

 

 

float height(float fx, float fy)

{

    D3DXVECTOR3 A = D3DXVECTOR3(0.0f, 0.0f, 10.0f);

    D3DXVECTOR3 B = D3DXVECTOR3(1.0f, 0.0f, 100.0f);

    D3DXVECTOR3 C = D3DXVECTOR3(0.0f, 1.0f, 10.0f);

    D3DXVECTOR3 D = D3DXVECTOR3(1.0f, 1.0f, 100.0f);

 

    //평면의 노말을 구한다.

    D3DXVECTOR3 ab = B - A;

    D3DXVECTOR3 ac = C - A;

 

    D3DXVECTOR3 normal, plane;

    float  planeD;

    D3DXVec3Cross(&normal, &ab, &ac);

    D3DXVec3Normalize( &plane, &normal);

 

    //평면의 D값을 구한다.

    planeD = -D3DXVec3Dot(&A, &plane);

 

    float height = ( plane.x * fx + plane.y * fy + planeD ) / -plane.z;

    return height;

}

 

 

void main()

{

    printf("Height = %f\n", height(0.3f, 0.1f));

}

 

3. 선형 보간을 응용한 삼각형 별로 높이 구하기

지형 메쉬를 평평 사각형으로 생각하고 높이를 구해도 큰 차이는 없다.
오차 없이 좀 더 세밀하게 높이를 구하는 방법이 필요하다.

좌표는

A (0.0f, 0.0f, 10.0f)
B (1.0f, 0.0f, 100.0f)
C (0.0f, 1.0f, 10.0f)
D (1.0f, 1.0f, 100.0f)  라고 가정한다.
dx = fx - A.x
dy = fy - A.y

지형 사각형 패치에서 삼각형이 모양은 2가지 종류가 있다.
가, 나에서 위, 아래 삼각형에 포함되는지 조사한다.

(가)의 경우:  
dx >= dy 이면 아래 삼각형 , 아니면 위 삼각형에 포함 된다.
0.3 >= 0.1 이므로 아래 삼각형

(나)의 경우:
dx <= 1 - dy 이면 아래 삼각형 , 아니면 위 삼각형에 포함 된다.
0.3 <= 1 - 0.1 이므로 아래 삼각형이다.

(가)의 경우 아래쪽 삼각형이면 다음과 같이 구한다.

uh = A - B
vh = D - B
fHeight = B + Linear( 0.0f, uh, 1.0f - dx ) + Linear( 0.0f, vh, dy )

점 B와 B에서 A 방향의 1 - dx 까지의 보간거리와 점 B에서 D 방향의 dy 까지의 보간거리를
더하면 높이를 구할 수 있다.

이것을 그림으로 표시하면 다음과 같다.

특별한 경우가 아니라면 삼각형을 구분하여 별도로 계산하는 것 보다는 사각형을 평면으로 계산해도
별 문제가 없을 것이다.

#include <stdio.h>

 

float Linear(float v0, float v1, float t)

{

    return v0 * (1.0f - t) + v1 * t;

}

 

//    *

//   *

// *      모양의 사각형 패치

float heightA(float fx, float fy)

{

    float fHeight, A, B, C, D;

    A = C = 10.0f;

    B = D = 100.0f;

    float dx = fx, dy = fy;

    float uh, vh;   //A와의 거리(이때 ABCD의 최대 거리를 1로 본다.)

 

    if( dx >= dy )  //ABD 삼각형, 아래쪽

    {

        uh = A - B;

        vh = D - B;

        fHeight = B + Linear( 0.0f, uh, 1.0f - dx ) + Linear( 0.0f, vh, dy );

    }

    else //ACD 삼각형, 윗쪽

    {

        uh = D - C;

        vh = A - C;

        fHeight = C + Linear( 0.0f, uh, dx ) + Linear( 0.0f, vh, 1.0f - dy );

    }

 

    return fHeight;

}

 

// *

//   *

//    *    모양의 사각형 패치

float heightB(float fx, float fy)

{

    float fHeight, A, B, C, D;

    A = C = 10.0f;

    B = D = 100.0f;

    float dx = fx, dy = fy;

    float uh, vh;   //A와의 거리(이때 ABCD의 최대 거리를 1로 본다.)

 

    if( dx <= 1.0f - dy )  //BAC 삼각형, 아래쪽

    {

        uh = B - A;

        vh = C - A;

        fHeight = A + Linear( 0.0f, uh, dx ) + Linear( 0.0f, vh, dy );

    }

    else //BDC 삼각형, 윗쪽

    {

        uh = C - D;

        vh = B - D;

        fHeight = D + Linear( 0.0f, uh, 1.0f - dx ) + Linear( 0.0f, vh, 1.0f - dy );

    }

 

    return fHeight;

}

 

void main()

{

    //printf("Height = %f\n", heightB(0.3f, 0.1f));

    printf("Height = %f\n", heightA(0.4f, 0.9f));

    printf("Height = %f\n", heightB(0.4f, 0.9f));

}