절두체 선별(Frustum Culling)
목차
- 절두체 선별의 필요성
- 원리와 이론
- 어떠한 점P가 있을때 해당 점이 평면에 대하여 어디에 존재할까
- 절두체를 만드는 방법
- 절두체 생성 의사코드
- 물체의 선별 원리
- 절두체 선별 의사코드
- 부록: 한계벡터
해당 포스팅은 절두체 선별, 다른말로는 Frustum Culling이라는 이론에 관하여 자세한 설명과 이론, 구현과정에 관한 내용을 담고있습니다.
절두체 선별은 그래픽스에서 사용하는 최적화 알고리즘중 하나로, 절두체모양의 가상의 도형을 만들어서 게임에서 매 프레임마다 가상카메라에 찍히는 물체들을 선별하고 가상카메라에 보이지않는 물체들은 렌더링과정에서 제외(culling)시키는 되게 심플하고 기초적인 이론이다.
절두체 선별의 필요성
그렇다면 이 기술은 왜 필요한것인가?
왜 굳이 힘들게 가상의 도형을 만들어서 오브젝트들을 순회하며 하나하나 체크해야하는가?
우선 그 필요성을 알기전에 우리가 메쉬들을 렌더링하는 공정을 한번 더 짚어볼 필요가 있다.
이유는 되게 심플하다.
(DX12기준) DirectX12에서는 렌더링을 하기전에 먼저 렌더링에 필요한 정점, 인덱스, 위상구조에 관한 정보가 필요하며 Input Assembler단계를 통해 우리가 GPU에게 어떠한 구조의 메쉬를 그리게 할지 정해준 다음 실제 렌더링단계에서 GraphicsCommandList를 통해 그려주게 된다.
이때, 당연하게도 그려야 할 오브젝트가 많을수록 GPU연산량이 증가한다.
물론 화면(Screen)에 그려야 할 오브젝트의 수가 적다면 크게 체감이 안될 수도 있다.
왜냐하면 절두체를 만드는과정도 매번 렌더링과정 이전에 업데이트를 실시간으로 해야하기 때문에
오브젝트의 수가 적다면 상관이 없겠지만, 만약 게임의 규모가 커지고 그려야 할 오브젝트의 수가 많아진다면 이때는 좀 문제가 될 수 있다.
요약하자면,
GPU의 연산량을 줄이기위해 CPU단계에서 꼭 화면에 나와야하는 오브젝트들만 미리 선별하는 과정이다.
원리와 이론
우선 절두체 선별은 카메라의 가상구조와 비슷한 절두체모양의 가상도형을 만들어서 해당 절두체안에 있거나, 또는 절두체의 경계면에 걸치는 오브젝트를 제외한 모든 오브젝트들은 그리지 않도록 해야한다.
우선 절두체라는 도형은 총 6개의 면으로 이루어진 도형인데 우리는 이 글에서는 각각의 평면을 그림에서와 같이 top plane, bottom plane, far plane, near plane, left plane, right plane 이라고 부르겠다.
마치 카메라의 가상구조를 연상케하는 도형이다.
절두체 선별의 기본 원리를 설명하기전에 선별원리의 대략적인 흐름은 이렇다.
6개의 평면에 대하여 각각 평면의 방정식을 만든뒤, 임의의 좌표(x, y, z)를 가진 가상도형을 6개의 평면의 방정식에 대입해 보면서 만약 가상도형의 한계벡터(또는 반지름)가 6개의 평면중 하나의 평면 방정식의 결과값보다 작다면 절두체에 포함되지 않는 물체인 것이다
이제 여기서 좀 더 깊게 들어가보기 전에 평면의 방정식의 성질에 대해 알아보겠다.
평면의 방정식
어떠한 그래프에서 한 평면을 구성하는 방정식의 모양은 이렇게 생겼다.
평면의 방정식은 다음과 같은 요소로 구성되어 있다.
(a, b, c): (평면위에 있는 직선과 수직인 벡터 또는) 법선벡터
(x, y, z): 임의의 점
d: 평면과 원점과의 거리
만약에 임의의 점 (x, y, z)를 해당 평면의 방정식에 대입해서 나온 값이 양수라면 평면의 바깥에 존재하는 점이며,
음수라면 안에 존재하는 점이고, 0이라면 평면위에 있는점이다.
ax + by + cz + d > 0 > 평면 바깥에 존재하는 점
ax + by + cz + d = 0 > 평면 위에 있는 점
ax + by + cz + d < 0 > 평면 안에 존재하는 점
그러면 왜? 이렇게 나오는것인지 알아보겠다.
어떠한 점P가 있을때 해당 점이 평면에 대하여 어디에 존재할까
우선 평면은 다음과 같이 형성되며, 법선벡터는 평면에 대하여 수직인 방향으로 나가게 된다.
우선 계산의 편의성을 위해 거리 d는 0으로 가정한 채(평면의 중심이 원점이다) 생각해보겠다.
또한 이때의 점 P를 단위벡터라고 가정하겠다.
그러면 아래의 그림과 같이 임의의 점 P(x, y, z)가 평면의 바깥에 존재하고 두 벡터의 사이각을 θ라고 가정한다.
이랬을때 점 P를 벡터로 바꾸면 파란색의 직선과 같이 벡터가 형성된다.
다음과 같이 파란색벡터는 d가 0이라고 가정했기때문에 다음과 같이 n벡터와 같은좌표계를 가질수 있었다.(왜냐하면 d가 0이라는것은 해당 평면이 중심인 좌표계라고 가정하는거나 마찬가지이기 때문이다.)
이때 점P를 가리키는 벡터와 법선벡터n을 평면의 방정식에 대입하면 내적을 구할 수 있다.
두 벡터의 크기가 각각 1이며, 평면의 방정식에서 우리는 d를 0이라고 가정했기때문에 최종적으로 다음 평면의 방정식에서 cosθ구하게 된다.
우선 cos함수의 범위는 0~90(degrees)라면 양수가 나오고 90도라면 0이 나온다.
또한 만약 90도를 넘어가서 91~180도사이라면 음수가 나오게되는데
이때 θ의 각도는 90도를 넘지 않게되므로 최종적으로 평면의 방정식에서 양수가 나온다는것은 점P가 평면의 바깥에 존재한다는것이다.
음수에서도 이 원리는 똑같이 적용된다.
또한, cosθ이 0나왔다는것은 평면의 법선벡터와 점P를 가리키는 벡터가 수직이라는 의미이므로 점P가 평면 위에있는 점이라는 의미다.
절두체 형성 의사코드
아마 이론은 알더라도 막상 처음 구현하는 사람입장에서는 막막할 수 있다.
따라서 의사코드를 만들어보면서 실제로 절두체를 어떻게 만들 수 있는지 알아보겠다.
우선 나는 DX12기준이기 때문에 왼손좌표계를 사용할 것이며,
y축벡터가 up벡터인 xz평면좌표계를 기준으로 의사코드를 만들었다.
Matrix InvViewMat; // 카메라의 뷰행렬의 역행렬
Matrix InvProjectionMat; // 카메라의 투영행렬의 역행렬
Matrix InvMat = InvProjectionMat * InvViewMat;
// 직육면체모양의 메쉬좌표들을 뷰투영의 역행렬을 곱해줌으로써
// Homogeneous clip space에서의 좌표(절두체모양을 형성하는 점8개)로 변환한다.
Vector3 Vertex[8];
Vertex[0] = (-1.f, 1.f, 0.f) * InvMat;
Vertex[1] = (1.f, 1.f, 0.f) * InvMat;
Vertex[2] = (1.f, -1.f, 0.f) * InvMat;
Vertex[3] = (-1.f, -1.f, 0.f) * InvMat;
Vertex[4] = (-1.f, 1.f, 1.f) * InvMat;
Vertex[5] = (1.f, 1.f, 1.f) * InvMat;
Vertex[6] = (1.f, -1.f, 1.f) * InvMat;
Vertex[7] = (-1.f, -1.f, 1.f) * InvMat;
// 각 면을 형성하는 4개의 점중 3개의 점을 통해 각 평면마다의 법선벡터를 구한다.
Plane plane[6];
plane[near].normal = GetNormalFromPoints(Vertex[0], Vertex[1], Vertex[2]);
plane[far].normal = GetNormalFromPoints(Vertex[4], Vertex[7], Vertex[5]);
plane[left].normal = GetNormalFromPoints(Vertex[0], Vertex[1], Vertex[2]);
plane[right].normal = GetNormalFromPoints(Vertex[0], Vertex[1], Vertex[2]);
plane[bottom].normal = GetNormalFromPoints(Vertex[0], Vertex[1], Vertex[2]);
plane[up].normal = GetNormalFromPoints(Vertex[0], Vertex[1], Vertex[2]);
이때 GetNormalFromPoints라는 함수는 한 평면상에 존재하는 4개의 점중
3개의 점을 통해 해당 평면의 법선벡터를 구하는데
이때 법선벡터가 평면위를 향하게 하려면 시계방향순으로 파라미터를 집어넣어야하며,
아래를 향하게하려면 반시계방향으로 파라미터를 순서대로 집어넣어야 한다(오른손좌표계라면 거꾸로 집어넣어야 함).
다음은 GetNormalFromPoints함수의 의사코드이다.
Plane GetNormalFromPoints(Point p1, Point p2, Point p3)
{
Vector3 x1 = p1 - p2;
Vector3 x2 = p1 - p3;
// cross(a, b) -> a와 b를 외적한다. a x b
Vector3 normal = cross(x1, x2);
// dot(a, b) -> a와 b를 내적한다. a * b
Scalar d_minus = dot(normal, p1);
Scalar d = -d_minus;
Plane plane;
plane.normal = normal;
plane.d = d;
return plane;
}
우선 GetNormalFromPoints함수에서는 x1과 x2를 구해주고 있다.
이것은 두 벡터의 외적을 통해 서로 수직인 벡터인 normal(법선벡터)를 구해주기 위함이다.
왼쪽의 그림은 해당 평면을 카메라로 보고있는 다른시점이다.
법선벡터가 어디를 향하고있는지 정확히 알려주기위해 왼쪽에 눈그림과 법선벡터의 방향을 한번더 그렸다.
그림의 팔레트가 생각보다 좁아서 벡터의 길이를 좀 혼동스럽게 다르게 그렸지만,
두 초록색벡터는 서로 같은벡터이고, 두 파란색벡터는 서로 같은벡터이다.
또한 DX12는 왼손좌표계이므로 나는 해당 부분을 왼손좌표계기준으로 했다.
그다음 그렇게 구해진 normal벡터와 p1벡터를 내적하고 있는데
그 이유는 어떠한 점P가 있을때 해당 점이 평면에 대하여 어디에 존재할까 에서 설명한 평면의 방정식에 따라
점 p1과 p2, p3 벡터는 현재 평면 위에있으므로 normal벡터와 내적하면 0(즉 두 벡터사이의 각이 90도)이 나와야만 한다.
따라서 ax + by + cz = -d 에 따라 최종적으로 해당 평면의 d까지 구해줄 수 있었다.
물체의 선별 원리
그럼 마침내 절두체를 만드는 6개의 평면을 만들어냈다.
이제 어떻게 오브젝트가 절두체 내부에 속한지 알수 있을까?
원리는 되게 단순한데, 오브젝트단위로 6개의 평면을 모두 검사하면서
만약 해당 물체의 한계벡터(또는 반지름)가 평면의 방정식의 결과값보다 큰지 작은지의 여부를 확인하면 된다.
따라서, ax + by + cz + d > e (이때 e는 오브젝트의 반지름 또는 한계벡터이다.) 를 확인해서
6개의 평면중 한개의 평면이라도 값이 참(True)이 나오면 해당 오브젝트는 절두체에 속한 오브젝트가 아니므로 선별(Culling)하면 된다.
절두체 선별 의사코드
다음은 절두체 선별의 최종적인 의사코드가 되겠다.
foreach plane in planes[6]
Boolean t = dot(plane.normal, Object.position) + plane.d > Object.e;
if ( t == TRUE )
return GO_CULLING;
return DONT_CULLING;
정말 설명한 그대로 구현하면된다.
절두체 선별은 그래픽스의 최적화 알고리즘중에서도 매우 쉬운 알고리즘이며 중고등학교수준의 수학만 나오기때문에 사전에 이론에 관한 설명을 듣고나면 구현하는데 막대한 어려움은 없을것이다.
부록: 한계벡터
나는 이 글을 쓰면서 계속 반지름과 함께 한계벡터라는 용어를 사용했는데, 이 단어를 혹시 모르는 사람들을 위해 추가적으로 설명과 구하는 방법을 알려주겠다.
쉽게 말해서 나는 이번에 원모양의 가상도형을 선별할때는 반지름을 사용하라고 권하고 싶으며, 직육면체모양의 가상도형을 사용한다면 한계벡터를 사용하라고 권하고싶다.
한계벡터는 하나의 도형을 이루는 무한개의 정점중 최솟값을 갖는 정점과 최댓값을 갖는 정점을 각각 Pmin, Pmax라고 부를때,
한계벡터는 다음과 같이 구할 수 있다.
그러면 마침내 절두체 선별 의사코드의 코드블럭에서 원의 경우
ax + by + cz + d > 반지름 을 사용하면 되며,
직육면체의 경우,
ax + by + cz + d > 한계벡터의 크기 를 사용하면 된다.