Screen Transform (화면 변환)

Screen Transform

투영 변환이 끝난 후의 좌료계는 NDC(Normalized Device Coordinates)로 바뀌게 된다.

이 좌표계는 중심이 (0,0)이고 가장자리 까지 거리가 1인 공간이다.

우리가 보는 화면으로 나타내기 위해서는 이 좌표계에 있는 점들을 화면 좌표계(Screen Coordinates)로 변환하여야 한다.

이때 Viewport정보가 사용 된다.

화면 좌표계는 좌측 상단을 (0,0)으로 가지고 우측 하단을 (Width_screen, Height_screen)으로 가지게 된다.

NDC에서 화면 죄표계로 변환을 y 값 부터 생각해 본다.

NDC에서 y의 범위는 [-1, 1]이므로 화면 좌표계의[0, Height_screen]으로 바꾸어야 한다.

1. y범위가 2배 단위 이므로 절반으로 나누어 1배 단위로 만들고 Height_screen값을 곱하여 늘려준다.

2. NDC의 y 방향과 화면 좌표계의 방향은 반대 이므로 Flip 하여 준다.

3. 화면 좌표계는 좌측 상단(0,0)부터 시작 하므로 Height_screen의 높이의 절반을 더하여 상단으로 이동시켜 준다.

4. x값의 경우, NDC에서의 x 좌표 방향과 화면 좌표계의 x 방향이 같으므로 Flip 과정이 필요 없다.

    그러므로 2번 과정을 제외한 1, 3번 과정을 동일하게 적용하여 값을 구한다.

지금까지 구해진  x_s, y_s 는 화면 좌표계에서 화면의 좌측 상단이 (0, 0)일때를 고려 하였다.

하지만 경우에 따라 좌측 상단이 이 다른 값을 가질 수도 있다.

특정 좌측 상단값을 (x_c, y_c)이라고 할 경우

지금 까지 구해진  x_s, y_s값에 추가로 더하여 주기만 하면 된다. 

마지막으로 z값은 깊이 테스트에 사용하기 위해서

NDC의 범위 [-1, 1]에서  [0, depth_screen]으로 변환해 주어야 한다.

depth_screen값은 보통 1을 사용한다.

x_s 값을 구하는 과정과 똑같이 1, 3번 과정을 거치면 최종 z_s 값은 다음과 같아 진다. 

NDC에서 화면 좌표계로의 변환을 행렬로 나타낼 수 있다.

DirectX 경우  NDC의 z 범위는 [0, 1]을 사용하고 있다. 

따라서 z값을 절반으로 나눌 필요 없이 바로 depth_screen 값을 곱하여 늘려 주며

3번 과정 처럼 추가적으로 z값을 이동 시켜 줄 필요도 없다.

결과적으로 z값은 다음과 같다.

그래서 DirectX에서 사용되는 행렬은 아래와 같이 된다.

참고자료

Essential Mathematics for Games & Interactive Applications Second Edition

Perspective Projection (원근 투영)

설명의 시작은 오른손 좌표계(OpenGL)를 기준으로 시작한다.

투영(Projection)을 하기전에 모든 좌표값은 카메라 공간으로 이동된 상태가 되며

이번에는 원근 투영을 정리할 것이므로 절두체를 이동하여 투영을 계산하게 된다.

이때 투명을 하게 되면 절두체를 정방형공간으로 바꾸는 과정이 이루어 진다.

첫번째로 일단 z의 범위는 생각 하지 않고 x,y를 먼저 투영평면에 투영을 한다.

변환하게 될 정방형 공간의 범위에 따라서 투명평면의 x,y 범위는 [-1, -1] ~ [1, 1]이 된다.

먼저 y를 투명해 보기로 한다.

절두체를 yz폄명으로 잘라서 보자.

절두체에서 y_max의 값을 투영 폄면에 투명하게 되면 

투영평면의 y범위에 따라서 y_p는 1값을 가지게 된다.

그리고 닮은꼴 삼각형에 따라서 

y / -z = y_p / d가 성립하게 되고  y_p = dy /-z가 되어 y_p를 구할 수 있게 된다.

하지만 여기서 원점에서 투명 평면까지 거리인  d를 구해야 한다.

d는 간단한 삼각형 공식을 이용해 구해진다.

tan (Ɵ / 2) =  1 / d

d = 1 / tan (Ɵ / 2), d = cot (Ɵ / 2)

두번째로 x값도 y값을 구하는 과정과 동일하게 구할 수 있지만

투명평면은 정사각형이 아닌 직사각형 형태이다. 

일단 첫번째와 동일 과정을 거치면

x / -z = a x_p / d가 되고 여기서 a값은 직사각형 형태를 만들어 주기 위한 종횡비값을 나타낸다.

a = width / height이고 정리를 하면 

x_p = dx / -za 가 된다.

이제 변환된 새로운 좌표를 동차표현식으로 나타내면 다음과 같아 진다.

x_new = dx / a

y_new = dy

z_new = dz

w = -z

그리고 w로 각 요소를 나누면 투영 변환 후의 좌표를 확인할 수 있다.

x_w = dx / -za

y_w = dy / -z

z_w = -d

w_w = 1

이제 w로 나누기전의 식들을 행렬로 나타내면 아래와 같다.

| d/a 0    0   0 |

| 0     d    0   0 |

| 0     0    d   0 |

| 0     0   -1   0 |

이 행렬에 변환되지 않은 x, y,z를  곱하면  변환된  x, y, z를 확인할 수 있다.

| d/a 0    0   0 |    |   x  |   =    |   dx / a |  

| 0     d    0   0 |    |   y  |   =    |   dy       |  

| 0     0    d   0 |    |   z  |   =    |   dz       |  

| 0     0   -1   0 |    |   1  |   =    |   -z       |

현재까지 z값을 고려하지 않고 행렬을 만들었다.

이제 z값을 [near, far] 범위로 변환해야 한다.

near = 원점 부터 near 평면까지의 거리

far = 원점부터  far 평면까지의 거리

z범위 변환을 위해 위에서 구해진 행렬에 추가 과정를 더 거친다.

1. [ -n, -f]의 범위를 정방형 범위인 [ -1, 1 ]로 Scaling

2. [ -1, 1 ]로 이동

(오른쪽  좌표계 기준이므로 z 방향은 화면 바깥 방향을 가리키고  n, f는

 크기만을 나타내므로 - 부호가 붙어 지게 된다.)

참고로 4x4 Affine 행렬에서 

Scale 인자는 행렬의 대각선분에 

Translation 인자는 마지막 열에 나타내게 된다.

| S_x    0       0         T_x |

| 0        S_y   0         T_y |

| 0        0        S_z    T_z |

| 0        0       0         1      |

이전에 구한 행렬에서 z값에 2가지 과정를 반영하면

| d/a 0    0   0 |      =>      | d/a 0    0   0 |

| 0     d    0   0 |                 | 0     d    0   0 |

| 0     0    d   0 |                 | 0     0    A  B |

| 0     0   -1   0 |                 | 0     0   -1  0 |

이제부터는 변환 과정이 반영된 A, B를 구해본다.

먼저 near 폄면에 대해서 계산해 보자.

| d/a 0    0    0 |    |   0  |   =    |   0             |  

| 0     d    0    0 |    |   0  |   =    |   0             |  

| 0     0    A   B |    |  -n  |   =    |   -nA + B  |  

| 0     0   -1   0 |    |   1  |   =     |   n             |

w값으로 나누어 보면

z_w =  -A + B / n

z_w는 near 평면의 거리이므로 -1이 되고 대입해 보면

-1 = -A + B / n,     B = (A-1) / n

잠시 여기서 멈추고  far 평면에 대해서 계산해 보자.

| d/a 0    0    0 |    |   0  |   =    |   0             |  

| 0     d    0    0 |    |   0  |   =    |   0             |  

| 0     0    A   B |    |  -f   |   =    |   -fA + B  |  

| 0     0   -1   0 |    |   1  |   =     |   f             |

w값으로 나누면 

z_w = -A + B / f

z_w는 far 평면의 거리이므로 1이 되고 대입을 해 보면

1 =  -A + B / f

이 시점에서 위에서 구한  B값을 대입하여  A값을 구한다.

1 =  -A + ( (A-1) / n ) / f 

A에 대하여 정리를 하면

A = n + f / n - f

구해진  A를 처음에 구해진 B식에 대입하여 B를 구한다.

B = (A-1) / n

B = ( ( n + f / n - f ) - 1 ) / n

B에 대하여 정리를 하면

B = 2nf / n - f

최종적으로 구해진 A, B값을 대입하여 원근 투영 행렬은 다음과 같아진다. 

(OpenGL 경우)

| d/a     0    0                  0             |

| 0         d    0                  0             |

| 0         0    n+f / n-f     2nf / n-f |

| 0         0   -1                  0             |

DirectX의 경우

z의 범위는 [0, 1]이 되고

z의 방향도 반대가 된다. (화면 안쪽을 가리킴)

z값을 고려하기 전 행렬은 다음과 같아지고 

| d/a 0    0    0 |

| 0     d    0    0 |

| 0     0    A   B |

| 0     0   1     0 |

z값의 범위를 다시 고려하여 A, B를 구하면

A = f / f - n

B = -nf / f - n

행렬은 다음과 같아진다.

| d/a     0    0                  0             |

| 0         d    0                  0             |

| 0         0    f / f - n     -nf / f - n   |

| 0         0   1                  0              |

마지막으로 DirectX은 행벡터 기준이므로 전치행렬을 만들어 사용한다.

| d/a     0    0                  0     |

| 0         d    0                  0     |

| 0         0    f / f - n        1     |

| 0         0   -nf / f - n     0     |

참고자료

Essential Mathematics for Games & Interactive Applications Second Edtion

광선과 평면 교차 ( Intersecting segment(ray) and plane )

선분 ab는 다음의 식으로 표현할 수 있다.

s(t) = a+ t (b - a) 

a는 선분의 시작점(org)을 나타내다.

(b - a)는 선분의 방향(dir)을 나타내고 크기는 1이 된다.

그리고 t는 선분 상의 위치를 나타내는 변수이고, 0 이상 1이하의 값을 가지게 된다.

여기서 

t 값이 +. -  방향 모두 무한대가 되면 직선, 

t 값이 한쪽 방향으로만 무한대가 되면 반직선이 된다. 

평면과 교차할때 직선의 t 값을  알아내면  교차점을 알아낼 수 있다.

평면의 식을 다음과 같이 나타내고 

n ∙ x + d = 0

특정 t 값 일때의 선분을 위 식에 대입한다.

n ∙ ( a+ t (b - a))  + d = 0

식을 t 에 대하여 정리하게 되면 아래과 같이 된다.

t = ( -n∙ a - d ) / ( n∙(b - a))

계산한 결과 t 값이 0 이상 1 이하라면 해당 평면과 선분을 교차하게 된다.

반직선의 경우는 검사하는 t 값을 범위를 조절하면 

평면과 반직선의 교차 여부를 판단할 수 있다.

-->

 1 bool segment_plane(vector3& org, vector3& dir, plane& p,
 2                 vector3& out_res)
 3 {
 4         float t = (-vec3_dot(p.normal, org) - p.d) /
 5                         vec3_dot(p.normal, dir);
 6 
 7         if(t >= 0.0f && t <= 1.0f)
 8         {
 9                 out_res = org + t * dir;
10                 return true;
11         }
12         return false;
13 }

참고문헌:
Real-Time Rendering 2판
Real-Time Collision Detection

AABB와 구 교차 ( Intersecting AABB and sphere )

AABB의 점들 중에서 구의 중심과 거리가 가장 가까운 점을
찾아서 충돌 확인한다.

AABB이므로 각 축별로 구의 중심과 거리를 확인한다.

구의 중심이 v_min과 v_max 사이에 있을 경우는 서로 교차하므로
따로 검사가 필요 없다.

-->

bool CollisionSphereAABB(Sphere& s, AABB& aabb) {
        float dist = 0.0f;

        for(int i=0; i<3; i++)
        {
                if( s.center[i] < aabb.v_min[i] )
                {
                        d += ((aabb.v_min[i] - s.center[i]) *
                                (aabb.v_min[i] - s.center[i]));
                }
                else if( s.center[i] > aabb.v_max[i] )
                {
                        d += ((s.center - aabb.v_max[i]) *
                                (s.center - aabb.v_max[i]));
                }
        }

        if( dist > s.center * s.center )
                return false;

        return true;
}

참고 문헌
Real-Time Rendering 2판
Real-Time Collision Detection

AABB와 평면 교차 ( Intersecting AABB and plane )

AABB에는 4개의 대각선이 존재
중점 C을 지니고 각 꼭지점을 이어서 나온 대각선들

먼저 충돌 검출할 평면의 n과 가장 평행한 대각선을 찾음
그러면 대각선의 양 끝점 vmin, vmax를 찾게 됨

이 v를 평면 방정식에 대입하여 위치를 판단한다.

n • v + d = 0

1. 두 점의 결과가 양의 영역에 있다면 평면의 바깥쪽에 AABB가 있음

2. 두 점의 결과가 음의 영역에 있다면 평면의 안쪽에 AABB가 있음

3. 두 점의 결과가 다른 경우 평면과 교차함

int CollisionAABBPlane(const D3DXVECTOR3* pMin, const D3DXVECTOR3* pMax, const D3DXPLANE& p)
{
 D3DXVECTOR3 NewMin, NewMax;

 for( int i=0; i<3; ++i)
 {
  if( p[i] >= 0)
  {
   NewMin[i] = pMin[i];
   NewMax[i] = pMax[i];
  }
  else
  {
   NewMin[i] = pMax[i];
   NewMax[i] = pMin[i];
  }
 }

 if( D3DXPlaneDotCoord(&p, &NewMin) > 0 )
 {
  return FRONT; 
 }

 if( D3DXPlaneDotCoord(&p, &NewMax) < 0 )
 {
  return BACK; 
 }

 return INTERSECT;
}

참고 자료: Real- Time Rendering 2판

AABB와 RAY 교차 ( Intersecting AABB and ray )

Slab:

Kay 와  Kajiya가 제안

두 개의 평행한 평면 사이의 무한한 공간

Slab과  Ray의 교차를 이용하여 AABB 교차를 판단

광선(Ray): r(t) = o + td

o: 원점

t: 광선상의 정점들을 생성하는데 사용되는 변수

d: 방향 벡터 ( 일반적으로 편의 위해 정규화 함, ||d|| = 1 )

광선이 Slab의 한 평면과 교차하는 t 값을 구하여 사용

평면:  n + D = 0

평면 위의 한 점 x의 경우 다음을 만족함

n • x + D = 0

그러므로 t 값을 구하기 위해 x를 t값을 가지는 광선의 한점으로 대치함

n • (r(t)) + D = 0

n • ( o + td ) + D = 0

(n • o) + t(n • d) + D = 0

t = ( -(n • o)  - D ) /  (n • d)

여기서  AABB의 특징들을 이용하면 t에 대한 식이 간단히 됨

1. AABB는 표준 기저와 축이 같아서

평면 n의 값이 각 축마다 2개 요소씩 0이 됨

예) x축의 경우: n_x  = (1, 0, 0)

그래서 n_x • o = (1, 0, 0) • (o_x, o_y, o_z) = o_x

 i  ∈ { x, y, z } 이면 위의 t 에 관한 식은 정리 되어서

t = ( -o_i  - D ) /  d_i

2. 추가로 평면이 표준 기저 축과 평행하므로 평면의 D의 값은

AABB의 min[i], max[i]값을 사용할 수 있음 ( i  ∈ { x, y, z } ) 

또한, d_i의 절대값이 아주 작을 경우 해당되는 축과 평행하게 됨

이때는 해당되는 축의 원점 o_i 값이 AABB의 min, max를 

벗어나면 교차 상태가 아니게 됨

광선과 Slab의 평면들과의 교차점을 찾아 t_min, t_max값을 찾는다.

예를 들어 현재 축에 해당되는 Slab 평면과 교차점 찾는 경우

t_min: 광선의 시작점으로 부터 처음 만나는 Slab 평면의 교차점

t_max: 두번째 Slab 평면과 교차점 

이렇게 각 축마다  t값을 구하면서 t_min, t_max가 서로 가까운 거리가 

유지 되도록 한다.

작업 중간에 t_min > t_max 이렇게 값이 서로 바뀌는 경우가 발생하면

AABB는 서로 교차하지 않는 것이 된다.

  

 //o: 광선의 원점

//d: 광선의 방향벡터

//p: 첫번째 교차점

bool AABBtoRay(AABB a, Vector3 o, Vector3 d, Vector3& p)

{

        float t_min = 0;

        float t_max = MAX_FLOAT;

for(int i=0; i<3; i++)

{

if(abs(d[i]) < EPSILON)

{

if( o[i] < a.min[i] ||

  o[i] > a.max[i] )

return false;

}

else 

{

float denom = 1.0f / d[i];

float t1 = (-o[i] - a.min[i]) * denom;

float t2 = (-o[i] - a.max[i]) * denom;

if(t1 > t2)

{

swap(t1, t2);

}

t_min = max(t_min, t1);

t_max = min(t_max, t2);

if(t_min > t_max)

return false;

}

}

p = o + t_min * d;

return true;

}

참고자료:
Real - Time Rendering 2판
Real - Time Collision Detection

Quaternions 정리1

복수수의 확장판

표현

q = ( v, w) = (x, y, z, w) = xi + yj + zk + w 

v: 사원수의 허수부, (  i, j, k는 허수 단위)

w: 사원수의 실수부

혹은

q = v + s 

v: 사원수 허수부

s: 사원수 실수부

허수부들의  곱 성질

i² + j² + k² = -1

i j = -j i = k

j k = -k j = i

k i = -i k = j

허수부에 더하기, 크기, 내적, 외적 등 모든 벡터 연산 사용 가능

두개의 사원수 q, r곱 ( 허수 단위들간의 곱셈을 비가환적)

qr = (iq_x + jq_y + kq_z + q_w) (ir_x + jr_y + kr_z + r_w)

     = i (q_yr_z - q_zr_y + r_wq_x + q_wr_x) + j (q_zr_x - q_xr_z + r_wq_y + q_wr_y) + k (q_xr_y - q_yr_x + r_wq_z + q_wr_z)

         + q_wr_w - q_xr_x - q_yr_y - q_zr_z

     =( q_v x r_v + r_wq_v + q_wr_v, q_wr_w - q_v • r_v)

|  i   j   k |

| q_x q_y q_z |

| r_x r_y r_z    |

외적 공식은 i (q_yr_z - q_zr_y) - j (q_xr_z - q_zr_x ) + k (q_xr_y - q_yr_x) 

덧셈:  q + r = (q_v, q_w) + (r_v, r_w) = (q_v +  r_v, q_w  + r_w)

공액(켤레, conjugate): q* = (q_v, q_w)* = (-q_v, q_w)

놈(norm): ||q||² = n(q) = qq* = q_v .q_v + q_w² = q_x² + q_y² + q_z² + q_w² (실수부만 남음)

항등 사원수: i = (0, 1)

곱셈역(multiplicative inverse): q^-1

q^-1q = qq^-1 = 1이 만족 해야 함, 역도 마찬가지로 만족해야 함

놈의 정의로 부터 유도함

||q||² = qq*   ⇔  1 = qq* / ||q||² , q^-1 = q* / ||q||²

스칼라 곱은 가환적

(가환적: 연산의 순서를 바꾸어도 그 결과가 변하지 않는 일

 실수 전체의 집합에서는 덧셈과 곱셈이 가환적)

sq = (0, s) (q_v, q_w) = (sq_v, sq_w)

qs = (q_v, q_w) (0, s) = (sq_v, sq_w)

공액 규칙:

(q*)* = q

(q + r)* = q* + r*

(qr)* = r* q*

놈의 규칙:

n(q*) = n(q)

n(q r) = n(q) n(r)

곱셈의 법칙

선형성:

p ( sq + tr ) = spq + tpr

( sp + tq ) = spr + tqr

결합법칙:

p(qr) = (pq)r

단위 사원수: q = (q_v, q_w)는 n(q)=1

그러므로  q = (sinøu_q, cosø) = sinøu + cosø 이 

||u_q|| = 1인 3차원 벡터 u_q에 대해 만족됨

이유: u_q • u_q = 1 =||u_q||² 이 만족되는 경우에 다음과 같이 되기 때문

n(q) = n(sinøu_q, cosø) = sin² ø (u_q • u_q) + cos²ø = sin²ø + cos²ø = 1

단위 사원수는 매우 효율적인 방법으로 회전 & 방향 전환 가능

복소수의 2차원 단위 벡터는 cosø + i sin ø = e ^iø

사원수에서 이와 동등한 식은 q = sinøu_q + cosø = e^øuq

단위 사원수에 대한 

로그: log(q) = log(e^øuq) = øu_q

멱함수: q^t = (sinøu_q + cosø)^t  = e^{ø t uq} = sin(øt)u_q + cos(øt)

참고 자료: Real-Time Rendering 2판