라린의 개발창고

-프러스텀 컬링이란?

 3차원의 월드 공간에서 대단히 많은 폴리곤과 오브젝트가 있지만, 이들 중에서 실제로 카메라의 시야범위에 포함되는 것들만 렌더링하고, 나머지 것들은 렌더링하지 않는 기법을 말한다.

절두체는 총 6개의 평면으로 이루어져 있는데, 이들의 구성은 다음과 같다

- 근평면(near plane) : 카메라와 수직하며 제일 가까운 곳의 시야 범위를 나타내는 평면

- 원평면(far plane) : 카메라와 수직하며 제일 먼 곳의 시야 범위를 나타내는 평면

- 좌평면(left plane) : 카메라 좌측 시야 범위를 나타내는 평면

- 우평면(right plane) : 카메라 우측 시야 범위를 나타내는 평면

- 상평면(top plane) : 카메라 상단 시야 범위를 나타내는 평면

- 하평면(bottom plane) : 카메라 하단 시야 범위를 나타내는 평면

-프러스텀 컬링의 원리

 절두체 내부에 점이 포함되는지 판단하기 위해서 6개의 평면 방정식에 점의 좌표를 대입해서 모든 평면 방정식의 결과값이 양수(+)면 이 점은 절두체 내부에 포함되어 있는 것.

-좌표계(Coordinate System)란?

좌표계는 크게 2D 좌표계와 3D 좌표계로 나눌 수 있다.

2D 좌표계는 화면 좌표계와 동일하며 xy 평면위에서 좌표체계를 가진다.

3D 좌표계는 공간상의 한 점을 나타내기 위해 xy평면, yz평면, zx평면을 가지는 좌표체계를 가진다.

-왼손 좌표계(Left-handed coordinate system)와 오른손 좌표계(Right-handed coordinate sytstem)

왼손 좌표계와 오른손 좌표계의 큰 차이점은 Z축의 진행방향이다. 왼손 좌표계에서 +z의 방향은 화면 안쪽으로 향하며, 오른손 좌표계는 화면 바깥쪽으로 향한다. 이러한 차이로 각각의 좌표계에서 구성하는 행렬은 서로 전치된다. 대표적으로 왼손 좌표계는 Direct3D에서 사용하고, 오른손 좌표계는 3Ds Max, OpenGL에서 사용된다.

 왼손 좌표계에서 회전 방향은 각 축에 대해 시계방향으로 회전한다. 왼손의 검지로 축의 방향을 가르키고, 엄지를 폈을때, 엄지가 향하는 방향으로 회전을 한다. 마찬가지로 오른손 좌표계에서 회전 방향은 각 축에 대해 반시계방향으로 회전한다. 왼손과 마찬가지로 오른손의 검지로 축의 방향을 가르키고, 엄지를 폈을때, 엄지가 향하는 방향으로 회전을 하게된다.

브레젠험(Bresenham's algorithm) 알고리즘이란?

 두 점 사이 의 직선에 가까운 근사를 형성하기 위해 선택해야 하는 n차원 래스터의 점을 결정하는 알고리즘입니다. 비트 맵 이미지 (예 : 컴퓨터 화면)에서 선 프리미티브를 그릴 때 주로 사용되며, 정수 추가, 빼기 및 비트 쉬프트 만 사용하므로 표준 컴퓨터 아키텍처에서 매우 저렴한 작업입니다. 증분 오류 알고리즘입니다. 컴퓨터 그래픽 분야에서 개발된 최초의 알고리즘 중 하나입니다. 원 알고리즘을 확장하면 원 그리기에 사용될 수 있습니다.

Wu의 알고리즘과 같은 알고리즘 은 안티 앨리어싱을 지원할 수 있기 때문에 최신 컴퓨터 그래픽에서 자주 사용되지만 Bresenham의 회선 알고리즘의 속도와 단순성은 여전히 ​​중요하다는 것을 의미합니다. 알고리즘은 플로터 및 최신 그래픽 카드의 그래픽 칩과 같은 하드웨어에서 사용됩니다. 또한 많은 소프트웨어 그래픽 라이브러리에서 찾을 수 있습니다. 이 알고리즘은 매우 간단하기 때문에 현대 그래픽 카드의 펌웨어 또는 그래픽 하드웨어에서 구현되는 경우가 많습니다.

"Bresenham"이라는 레이블은 오늘날 Bresenham의 원래 알고리즘을 확장하거나 수정하는 알고리즘 계열에 사용됩니다.

브레젠험 알고리즘의 원리

실수 연산이 필요 없고 정수 연산만으로 처리되는 속도가 매우 빠른 래스터 방식 컴퓨터 그래픽에서 선을 긋는 알고리즘으로, 가로나 세로의 어느 한쪽 좌표를 시작점으로 하여 종료점까지 1씩 가산하여 좌표를 증가시킬 것 인가 또는 그대로 유지할 것인가를 판단합니다. 

1. 기울기가 0과 1 사이인 직선을 가정해줍니다.

2. 현재 좌표에서 다음 찍어야 할 좌표값을 구해야 되는데 x는 항상 1만큼 증가하고, y는 Yk, Yk+1 둘 중 하나를 선택합니다. y좌표 선택 판단기준은 중단점 M으로 판별합니다.

3. 중단점 M을 통해 직선보다 위에 존재하면 아래쪽의 칸을 선택하고, 직선보다 아래에 존재하면 위쪽의 칸을 선택합니다.

4. 즉, 중단점 M이 직선의 위에 있냐 아래에 있냐로 다음 점의 위치를 판단한다는 것인데, 그 판별식은 다음과 같은 방법으로 구합니다.

① 그리는 선분의 양 끝점을 입력받습니다. Pa(Xa, Ya), Pb(Xb, Yb)

② 두 점을 이용해서 W값과 H값을 구합니다.

③ 직선의 방정식의 기울기에 대입합니다.

④ 두 점을 이용하여 직선의 방정식을 구합니다.

⑤ 식을 한편으로 정리를 합니다.

5. 도출된 식으로 중단점을 대입하고, 값의 크기를 0과 비교합니다.

 이때, 중단점 M은 다음과 같습니다.

 이 값을 위의 식에 대입합니다.

이 값을 판별하여, 0보다 크면, 중단점이 직선보다 위에 있으므로, 다음 점의 위치는 다음과 같습니다.

0보다 작으면, 중단점이 직선보다 아래에 있으므로, 다음 점의 위치는 다음과 같습니다.

정리를 하면, 다음과 같은 결과가 됩니다.

일반화를 하면 함수는 다음과 같이 정의됩니다.

삼각형에 색상을 채우는 방법은 3가지가 있습니다.

1. Flat Shading(플랫 셰이딩)
 삼각형을 단색으로 채우는 방법으로 채우기 속도는 가장 빠르다.

2. Gouraud Shading(고라우드 셰이딩)

 삼각형의 각 점에 대해 색상을 부여하여 색상을 보간하여 채우는 방법입니다. OpenGL, DirectX 등 3D API에서 보통 쓰는 방식입니다. 속도는 Flat Shading 보다 떨어진다.

3. Phong Shading(퐁 셰이딩)

 삼각형에 채워지는 각각의 픽셀에 대해 색상계산하여 채우는 방법입니다. 실제 퐁쉐이딩의 정의는 법선 벡터를 보간하여 각각 픽셀의 법선벡터를 이용하여 채우는 방법입니다.

 위와 같이 내부가 칠해지지 않은 삼각형이 있습니다. 그림의 삼각형에서 가장 상단에 있는 점에서 출발해, 삼각형의 나머지 2개의 점 중 X값이 작은 쪽의 점이 시작점, 큰 쪽의 점이 끝점인 수평선을 그려줍니다.

 그림과 같은 삼각형을 채우기 위해서는

1. 시작점에서 나머지 삼각형의 정점을 잇는 직선의 기울기를 구합니다.

2. 시작점에서 y값을 1씩 증가했을때의 각각의 직선의 방정식을 통해 x값을 구합니다.

3. 구하여진 x값 2개와 y값으로 수평선을 긋습니다.

4. 끝점의 y값 - 시작점의 y값 만큼 반복합니다.

 렌더 파이프 라인에서 Vertex Shader 단계의 마지막에, 지정된 좌표를 받아들이고 이 범위에서 벗어난 모든 좌표는 자르게됩니다. 이때, Clip 된 좌표들은 모두 폐기되고, 남은 좌표들은 최종적으로 파편화되어 화면에 보이게 됩니다. 이때, 눈에 보이는 모든 좌표들이 -1.0과 1.0 범위 안에 지정하는 것은 직관적이지 않기 때문에, 우리가 원하는 화면에 표현하기 위한 공간으로 다시 변환하게 됩니다. 이때 사용되는 것이 NDC(Noramlize Device Coordinate)이며, 이 공간은 투영(Projection) 행렬에 정의됩니다.

앞서 유도한 투영 행렬이 정의하는 Viewing Box는 절두체(Frustrum)라고 불립니다. 이 절두체 내부에 있는 좌표들은 화면에 나타나게 됩니다. 지정한 범위 내에서 NDC로 변환하는 전체적인 과정을 '투영한다'라고 합니다. 3D좌표를 2D에 매핑하기 쉬운 NDC로 투영하기 때문입니다.

정규 좌표(NDC)는 1을 기준으로 하는 2차원 좌표입니다. 이 좌표계의 원점은 화면(Device)의 정 중앙에 위치하며, 화면의 우상단 좌표가 (1.0, 1.0), 좌하단 좌표가(-1.0, -1.0)이 됩니다.

정규 좌표를 사용하면 해상도에 따른 화면좌표 계산이 단순화됩니다. x좌표를 계산할 때 계산하는 과정을 줄일 수 있으며, 해상도를 제외한 값을 계산해 두면 해상도가 변할 경우에도 쉽게 실제 화면 좌표를 계산할 수 있게 됩니다.

즉, 화면 해상도 차이에 빠르게 적응하기 위한 하나의 도구입니다.

3D 공간을 나타내는 화면상의 어느 한 점을 표현하기 위해서는 물체의 Local 좌표를 카메라를 기준으로 하는 화면 좌표로 변환해야 하는 과정이 필요합니다. 이러한 작업을 '투영(Projection)'이라고 합니다. 즉, 투영을 하기 위해서 우리가 사용하는 좌표를 변환하는 과정이 필요하다는 의미입니다.

처음으로 물체는 로컬 공간(Local Space)에 정의 되어있다. 로컬 공간에 정의된 물체는 월드 변환을 통해서 월드 공간(World Space)로 이동합니다. 이 월드 공간에 렌더링할 대상의 물체들과 카메라, 광원 등이 배치됩니다. 다음으로는 카메라 행렬에 의해서 뷰 공간(View Space)로 변환됩니다. 이 변환을 통해서 카메라를 기준으로 하여 새로운 좌표체계가 완성되게 됩니다.

이제 이 카메라를 통해서 화면 공간(Screen Space)에 물체를 표현해야 하기 때문에 3차원 공간(화면 공간)을 2차원 공간(화면 공간)으로 변환해야하는 과정이 필요합니다. 이 과정을 투영 변환이라고 합니다.

 왼쪽의 그림은 카메라 좌표계의 XZ 평면을 나타내며, 이 상태에서 투영변환 된 것이 오른쪽의 XZ 평면이다. 왼쪽 그림의 원점에 카메라가 존재하고, 카메라가 비출수 있는 공간이 빨간 선이 둘러진 부분입니다. 카메라의 표현이 가능한 공간은 유한하며, 왼쪽 그림의 두 평면 (Near, Far)의 공간 사이의 물체만 화면에 나타나게 됩니다. 왼쪽 그림의 빨간색 부분이 화면을 표현하는 공간인 절두체(Frustrum) 영역입니다. 투영 변환은 이 절두체 영역을 오른쪽 그림과 같은 공간으로 변환하는 것을 의미합니다.

먼저 투영행렬을 유도하기 위해서는 카메라 좌표계를 구성하는 각 성분에 대해서 이해가 필요합니다. 카메라가 표현하는 공간까지의 거리인 d의 값을 알아야 합니다. 이 값을 구하기 위해서, 카메라의 시야각(FOV)을 이용합니다. 삼각함수를 이용하여 tan의 값을 구할 수 있는데, 그 값은 다음과 같습니다.

이 식을 d로 정리를 하면, d는 다음과 같습니다.

이제 다시, 처음의 그림으로 돌아가서, 공간상의 점을 화면에 표현을 할수 있도록 해봅니다.

절두체 내부의 모든 점들은 투영 평면((1, d) ~ (-1, d)) 위에 표현됩니다. 두 점과, 삼각형의 닮은꼴을 이용하여 투영 평면 위에 표현되는 모든 점들을 찾아낼 수 있습니다. 즉 투영 평면 상의 점 P의 y 성분의 값은 다음 비를 만족합니다. 또한, 오른손 좌표계에 의해서 Pview의 Z값은 -Zview값이 됩니다.

이 비율을 이용하여 Yndc값은 다음과 같이 나타나게 됩니다.

똑같은 방법으로 XZ 평면상의 점또한, 다음 비를 만족할 것입니다.

이 비율을 이용하여 Xndc의 값은 다음과 같이 나타나게 됩니다.

그러나, 이경우는 투영평면이 정사각형으로 표현되는 경우 나타나게 되는 경우이며, 일반적인 화면의 비는 가로가 더 넓기 때문에, 종횡비 a의 역수를 Xndc의 성분에 곱해주게 되면 투영 평면 위의 점을 구할 수 있습니다.

최종적인 투영변환 공식은 다음과 같습니다.

이제, 뷰 공간의 점을 화면 공간의 점으로 선형 변환하는 행렬이 있다고 가정합니다.

.

그러나 Xndc와 Yndc의 값은 구했으므로, 위의 행렬은 다음과 같이 표현이 가능합니다.

여기에서, W'의 값이 Zview의 값과 같다고 가정하게 되면, 점의 정의가 동차 좌표계의 정의와 일치하게 되며, Zview값을 모두 바꿀 수 있게 됩니다. 즉 행렬식을 변경하면 다음과 같게 됩니다.

이제 마지막으로 k와 l의 값을 구하는 일이 남았습니다. 두개의 미지수는 근평면(Near Plane)의 거리와 원평면(Far Plane)의 거리를 이용하여 다음과 같은 행렬식을 유도할 수 있습니다.

각각의 행렬에서 다음과 같은 식을 알 수 있습니다.

두 식을 연립방적식을 통하여 구하면 k와 l의 값은 다음과 같습니다

최종적으로 우리가 구하는 투영 행렬은 다음과 같게 됩니다.

-컬링(Culling) 이란?

 씬의 최종 단계에 보이지 않는 불필요한 폴리곤을 잘라내어 렌더링을 하지 않는 기법. 컬링의 종류는 백페이스 컬링(BackFace Culling), 오클루전 컬링(Occlusion Culling), 프러스텀 컬링(ViewFrustum Culling)이 있다.

-백페이스 컬링(Backface Culling)이란?

카메라에서 보이지 않는 뒷면의 폴리곤을 제거하는 기법. 백페이스 컬링은 폴리곤은 두 개의 면을 가지고 있으며 하나의 면을 전면, 다른 면을 후면이라 부르고 전면을 향하고 있는 폴리곤들이 뒤쪽의 후면 폴리곤을 가리고 있을때 후면 폴리곤을 그리지 않음으로써 최적화적 이득을 취하는 컬링 기법이다. 

오클루젼 컬링(시야에 보이지 않는 오브젝트는 그리지 않는 컬링 기법)과도 비슷하다고 볼 수 있다. 

시계방향으로 변경하면 전면을 보이지 않도록 제거할수 있다.

벡터의 외적이란?

서로다른 두 벡터 각각에 수직인 방향벡터를 만드는 것.

외적의 특징

1. 벡터 A와 B의 외적 A X B는 벡터 A와 수직이고, B와도 수직이다.

2. 내적과 달리 교환 법칙이 성립되지 않으며, 순서를 바꾸면 반대 방향의 벡터가 나온다. A X B = -(A X B)

3. 내적과 동일하게 분배 법칙은 성립한다. A X ( B + C ) = ( A X B ) + ( A X C )

4. 외적의 벡터의 크기는 평행사변형의 넓이 이다.

5. 두 벡터가 평행하면 크기는 0이다. sin0의 값이 0이기 때문이다.

왼쪽 오른쪽 판별하기

월드 공간의 UP 방향 벡터를 U, 플레이어의 Forward 방향을 F, 플레이어에서 물체를 가르키는 방향을 A라고 했을 때, 벡터 F와 벡터 A를 외적한다. 이 외적한 벡터를 월드 벡터와 내적을 하였을 때, 양수이면 오른쪽 음수이면 왼쪽에 존재하게 된다.