< Culling의 종류 >

출처는 http://www.lameproof.com/ 요기에서 뽑아왔습니다.

 

 

컬링의 종류는 조사한 바에 의하면 3가지가 있는거 같다.

 

1. Backface culling 
2. View frustum culling 
3. Occlusion Culling

 

2번, 3번은 질의로 나온 문제였는데... 보기 좋게 제대로 못 적었다. 컄컄컄

 

Backface Culling은  object 가 closed polygon 으로 구성되어있다고 가정할때, 각 face 의 방향이 시점의 반대쪽을 바라보고 있을때에는 찍을 필요가 없다는 것을 의미한다.

 

 Frustum 은 절단체라는 것인데, 이것은 피라미드 모양에서 위의 뾰족한 부분을 잘라낸 모양을 생각하면 된다. frustum 이란 개념이 왜 나오냐 하면, 월드상에서 인간의 눈에 보이는 부분을 골라내면 바로 frustum 의 모양을 하기 때문이다. 눈에 가까운 쪽은 작은 사각형쪽에 해당하고 멀리 있는 쪽은 큰 사각형쪽에 해당한다. 물론 인간의 시야는 무한히 먼 곳을 바라볼 수 있게 되어있지만, 보통 3d 엔진에서는 시야에 어느정도 한계를 두도록 되어있다. 예를 들면 눈으로 볼 수 있는 가장 가까운 거리는 10 이고 가장 먼 거리는 5000 으로 정하는 식이다. 폴리곤이 카메라에 너무 가까와져서 모델의 내부가 보인다던가 하는 일은 거리가 최소거리보다 작은 폴리곤을 출력할때 나오는 현상인 것이다

 

  frustum 을 활용하기 위해서는 frustum 의 자료구조를 디자인하고, 실제적인 데이타 (최소거리, 최대거리, fov) 등으로부터 frustum 데이타를 만들어내는 법을 알아야 한다. frustum 은 보통 6 개의 평면이 이루는 것으로 구현하게 되어있다. 즉 near plane, far plane, left plane, right plane, top plane, bottom plane 의 6 개가 그것이다. 

  그렇다면 실질적으로 월드를 구성하는 폴리곤이 화면상에 들어오는가 안 들어오는가를 판단하기 위해서는 어떻게 하는 것일까? 그것은 각각의 폴리곤이 6 개의 plane 의 안쪽에 속하는지를 검사하는 것이다. 

  plane 은 보통 카메라좌표계에서 정의되고, 월드상의 폴리곤은 월드좌표계상에서 정의되기때문에 서로 비교를 하려면 같은 좌표계상에 오도록 변환을 해야 한다. 카메라좌표계를 기준으로 하는 것이 좋을까 월드 좌표계를 기준으로 하는 것이 좋을까? 당연히 월드좌표계를 기준으로 하는 것이 좋다. 만약 카메라 좌표계를 기준으로 한다면 폴리곤이 1 만개일 경우, 월드->>카메라 변환을 1 만번 해야 하지만, 월드좌표계를 기준으로 하면 카메라->>월드 역변환을 평면의 갯수만큼, 즉 6 번만 해주면 되기 때문이다. 평면을 변환, 역변환하는 방법에 대해선 역시나 수학책을 참고하길 바란다. 

  이제 frustum 을 구성하기도 했고, 각각의 폴리곤이 frustum 에 속하는지 비교하는 방법도 알긴 했지만 이것만으로는 부족하다. 왜냐하면 수만개의 폴리곤이 화면에 찍히는지 안찍히는지 일일이 frustum 에 대해 검사를 해야하기 때문에 실질적으로 큰 소득을 얻지 못했기 때문이다. 어떻게 해야지 간단한 방법으로 (적은 수의 계산으로) frustum 안에 들어오는 polygon 만을 골라낼 수 있을까? 

  그 해답은 polygon 을 그룹을 지워놓고 나서, 그룹단위로 frustum 에 들어오는지를 판별하는 것에 있다. 예를 들어서 월드상의 인접한 폴리곤들을 100 개정도의 그룹으로 분리(partition 을 구성)를 해 놓은 다음에 그 그룹을 최대한으로 감싸는 bounding box 를 계산해놓고, bounding box 와 frustum 간의 포함관계여부를 검사를 하면 어떻게 될까? 물론 훨씬 계산량이 줄어들 수 있게 된다. 왜냐하면 그룹의 bounding box 가 frustum 과 전혀 충돌하지 않는다는 것을 알게 되면 (적은 수의 계산으로 알 수 있다) 그 그룹안에 포함된 수백개의 폴리곤들또한 전혀 frustum 에 속하지 않는 다는 결론을 내릴 수 있기 때문이다. 

  이 방법만 쓰더라도 폴리곤 한개씩을 frustum 에 대해 비교하던 방법보다는 훨씬 나은 효과를 얻을 수 있다. 참고로 폴리곤을 일정한 단위로 그룹을 짓는다는 것은, 각각의 폴리곤이 전혀 움직이지 않는다는 가정을 했기 때문에 가능한 것이다. 만약 폴리곤이 일부라도 움직이게 되면 그룹을 다시 짜거나, 또는 그룹의 bounding box 를 재계산 해야만 할 것이다. 

  이 방법은 좋긴 하지만 더 좋게 할 수 있는 방법이 더 많이 있는데, 그중 하나는 그룹을 계층적으로 구성하는 것이다. 말하자면 월드 전체를 커다란 한개의 그룹으로 일단 구성하고, 그 그룹을 어떤 기준에 의해서 2 개나 4 개, 혹은 8 개의 소그룹으로 나누고, 그 소그룹을 다시 또 기준에 의해서 소그룹으로 분할하는 방법을 말한다. 이런식으로 일정단계까지 (예를 들면 5 단계까지) 나누고 나면 월드 전체는 그룹들로 구성된 트리구조로 표현할 수 있게 된다. 하나의 그룹을 임의의 기울기의 평면을 사용해서 2 개의 소그룹으로 나누는 방법을 Binary Space Partitioning 이라고 부르고, x 축과 z 축의 직교된 평면을 이용해 4 개의 소그룹으로 나누는 방법을 Quad-Tree Partitioning 이라고 하고, x,y,z 축의 평면을 이용해 8 개의 소그룹으로 나누는 방법을 Oct-tree partitioning 이라고 한다. bsp 와 quad-tree, oct-tree 는 각각 구조에 따라 장단점이 있는데, 실질적으로 가장 기본이 되는 것은 bsp 라고 할 수가 있고, quad-tree 나 oct-tree 는 bsp 의 단계를 묶어서 간략화한 형태라고 할 수 있다. 그리고 quad-tree 는 높낮이의 변화가 심하지 않은 2.5 차원 배경을 표현할때 효과적이고, oct-tree 는 높낮이의 변화가 심한 3 차원 배경을 표현할때 효과적이다. 

 이렇게 월드를 그룹으로 나눌때에는 몇가지 주의할 사항이 있다. bsp 건 quad-tree 건 oct-tree 건 평면을 이용해서 폴리곤들을 나누게 되어있는데, 어떤 경우건 폴리곤이 두개의 그룹간에 걸치게 되는 경우가 있다. 이런 때에는 어떻게 해야 할까? 

  첫번째 방법은 폴리곤을 2 개로 쪼개서 각각의 그룹에 하나씩 보내주는 경우이다. 이 경우에는 각각의 그룹은 폴리곤을 완벽하게 포함시키게 되지만, 폴리곤의 갯수가 늘어나게 된다는 단점이 있다. bsp 를 이용해서 은면제거까지 해야한다면 반드시 이 방법을 써야만 한다. 

  두번째 방법은 하나의 폴리곤을 양쪽에 모두 포함시키는 것이다. 이 경우에는 그룹이 폴리곤을 완전히 포함시키지 못하므로 후에 추가적인 테스트가 필요하거나 정확성이 약간 떨어지게 되고, 은면제거의 방법으로 활용할 수 없게 되지만 폴리곤의 갯수는 유지된다는 장점이 있다. 그리고 한 폴리곤이 두번 표시되지 않도록, 폴리곤을 표시했는지 여부를 각 폴리곤마다 기록해줘야 할 필요가 있다. 근래에는 보통 두번째 방법을 많이 쓰는 것으로 알고 있다. 내가 만들었던 엔진에서는 quad-tree 에 두번째 방법을 주로 이용했다. 

  실질적으로 VFC 를 이용해서 화면상에 복잡한 배경을 찍는다는 것은 3 개의 단계로 나뉘어진다 

  첫번째는 월드상의 모든 폴리곤들을 적절한 구분방법에 의해 그룹의 트리구조를 만드는 것이다. 이 구조를 보통 SceneGraph 라고 부른다. 배경(Scene) 이 어떤 구조로 나타나있는지를 표현하는 그래프라는 의미이다. bsp, quad-tree, oct-tree 는 scenegraph 의 종류를 일컫는 말이다. 이 작업은 배경이 변하지 않는 한에는 처음에 1 번만 해두면 된다. 고정된 배경이기 때문에 미리 계산을 해놓을 수 있는 것이고, 미리 계산을 해 놓기 때문에 속도를 빠르게 할 수 있는 것이다. SceneGraph 의 각 요소를 node 라고 하고, node 가 가지는 내용은, node 가 월드상에서 담당하는 범위 (bounding box), node 가 가진 폴리곤들의 리스트, node 에 딸린 자식 node 의 리스트를 나타낸다. 

  두번째는 현재 카메라의 시점을 계산해서 frustum 을 새롭게 만들어 놓는 것이다. (물론 월드 좌표계로) 이것은 시점이 바뀔때마다 매번 해야 하는 일이다. 

  세번째는 SceneGraph 의 각 노드에 대해 frustum 과의 충돌체크를 수행하고 (노드의 bounding box 와 frustum 간의 충돌체크) 만약 frustum 과 조금이라도 충돌하였으면 해당 scenegraph 의 자식 노드들에 대해 다시 각각 충돌체크를 수행하는 것이다. 만약 node 가 자식 노드가 없다면 (즉 최 말단 노드라면) 노드가 갖고 있는 폴리곤들을 화면에 그대로 찍으면 된다. 

  여기서 중요한 점은 각각의 노드들은 자식노드들을 완전히 포함하고 있기 때문에, 하나의 노드가 frustum 과 완전히 충돌하지 않는다는 것을 알게 되면, 그 자식노드들은 전혀 계산할 필요가 없다는 점이다. 이 원리에 의해서 수만개의 폴리곤들이 몇백번 이내의 계산에 의해서 훨씬 적은 수의 화면상에 들어오는 폴리곤들로 컬링되는 것이다 

Occlusion culling 을 사용할지 여부는 내가 표현하고자 하는 배경이 어떤 형태를 지니는가에 따라 달라진다. 즉, 배경이 실외중심으로 되어있느냐, 실내 중심으로 되어있느냐에 따라서 달라진다. Occlusion 이라는 것은 가리기라는 뜻인데, 완전히 불투명힌 벽같은 것 뒤에 완전히 가려진 물체는 View Frustum 상에 들어온다고 하더라도 표시할 필요가 없다는 점에 착안한 것이다. 

 그런데 실외의 경우에는 occlusion 의 발생여부를 따지기가 힘들고, 대부분 frustum 상에 들어온 물체를 모두 표현해야 하기 때문에 실외 표현 전용엔진에서는 occlusion culling 은 도입하지 않는다. 

  하지만 실내의 경우, 커다란 경우가 여러개의 방과 복도로 나뉘어져 있고, 시점이 그 내부에서 이동한다고 할때에는 상당히 많은 부분이 벽에 의해서 가려지게 된다. 이것을 활용하기 위한 방법이 occlusion culling 이다. 

  occlusion 의 체크또한 상당히 많은 량의 계산을 필요로 하게 된다. 따라서 배경이 고정되어있다는 것을 감안하여 최대한 많은 정보를 미리 계산해놓을 필요가 있는데, occlusion 정보를 미리 계산해놓은 것을 PVS (Potential Visible Set) 라고 한다. PVS 는 말 그대로 "보일 가능성이 있는 것들의 집합" 이라는 의미이다.

 

 예를 들어서 건물이 있는데, 건물을 10 개의 방과 복도로 나눌 수 있다고 생각하자. 각 방과 복도 사이에는 문(portal) 과 창이 존재하기 때문에 한 지역 안에서 다른 지역도 볼 수가 있지만, 모든 지역을 다 볼 수는 없다고 가정할 수 있다. 예를 들어서 방 1 에서는 복도를 볼 수 있고, 복도 너머의 방 2 와 방 3 을 볼 수 있다는 점을 미리 계산을 많이 해서 알아낼 수가 있다고 하면, 시점이 방 1 에 있을 때에는 먼저 pvs 정보에 입각하여 방1 (자신) 과 방2, 방3, 복도에 해당하는 폴리곤만을 VFC 할 수 있다는 의미이다. 또한 여기에 3 차원적 clipping 을 더 추가하여 portal 단위로 보이는 부분을 더욱 압축하는 방법도 생각해볼 수 있다. 이것은 portal rendering 이라고 불린다.