3D 프로그래밍을 한다고 하면 단계별로 알아야 할 것들이 있다.

  첫번째는 기본적인 수학적 지식, 즉 행렬이나 벡터를 활용하여 3차원 공간상의 물체(object)를 어떻게 수치로 표현(representation)하는가에 대한 원리 (vertex, face 등의 개념을 비롯하여) 를 알고, 그 표현된 물체를 화면에 나타내도록 변환(transformation) 하는 방법과 단계 (transform pipeline) 등에 대해 아는 것이다. 많은 3D 이론서들이 이에 대해 언급하고 있으므로 위에 대해 아직 잘 모르는 독자들은 해당 참고서적을 보는 것이 좋을 것이다

  두번째는 OpenGL 이나 Direct3D 등의 3D Programming API 를 이용하여 실질적으로 무언가를 구현해보는 것에 있다. 여기서는 기본적인 연산 이외에 텍스춰링이라던가 알파블렌딩같은 실질적인 표현기법에 대해서 알아야 할 필요가 있다. 여기까지에 대해서도 역시 많은 참고 문서들이 있으므로 해당 자료를 입수, 학습하면 된다.

  이 다음에 해야 할 일은 무엇일까? 내가 다루고 싶은 것은 그 이후에 대해서이다. 물론 모든 3d 프로그래밍을 하는 이들은 멋진 게임엔진을 만들어보고 싶을 것이다. 이후의 방향은 크게 2 가지로 갈라지는데, 하나는 배경표현에 대한 것이고 또 다른 것은 캐릭터 표현에 대한 것이다. 물론 궁극의 3D 엔진을 만들기 위해서는 둘 다 알아야 할 필요가 있지만, 나는 먼저 배경표현에 대한 것을 이 글을 통해서 기초 이론을 설명하고자 한다.

  3D 게임안에는 여러가지 요소들이 등장하지만 크게 나누자면 배경과 캐릭터로 구분할 수가 있다. 배경과 캐릭터는 직관적으로 보아서 나눌 수도 있지만, 내가 생각하는 구분 기준은 동적인 오브젝트이냐, 정적인 오브젝트이냐라는 것을 기준으로 하고자 한다. 한마리도 모양이 변하거나 위치가 변하면 동적인 오브젝트, 즉 캐릭터이고, 그렇지 않으면 정적인 오브젝트, 즉 배경이라는 뜻이다.

  모양이나 위치가 변하지 않는다는 것은 직관적으로 보기에는 고정되어있다는 느낌을 우선 주게 되는데, 그것은 구현상으로 보자면 더 중요한 힌트를 주게 된다. 일반적으로 3D 로 된 물체를 표현하려면 많은 량의 계산을 필요로 하게 되는데, 모양이나 위치가 변하지 않는 다는 뜻은, 미리 계산을 해두고 기억해놓으면 나중에는 계산된 결과만을 가지고도 물체 표현이 가능하다는 것이 있다.

  또한 배경과 캐릭터의 중요한 차이점이라면, 배경의 경우에는 상당히 많은 수의 폴리곤으로 구성된다는 점이다. 커다란 월드맵을 가진 게임의 경우에는 대개 폴리곤의 갯수가 1만개를 넘어가게 된다. 그에 비해 캐릭터는 몇백개정도로 구성되는 것이 보통이므로 찍는 방법에 있어서 상당한 주의를 요하게 된다. 이 말은 캐릭터를 표현하기 위해서는 캐릭터를 구성하는 몇백개의 폴리곤을 매 프레임(frame = 보통 1/60 초)단위로 표시하는 것은 사용할만한(acceptable) 방법이지만, 배경을 표현하기 위해서 수만개의 폴리곤을 매번 찍는 방법은 사용불가능하다는 말이다.

  그렇다면 수만개의 폴리곤으로 구성된 배경을 어떻게 표현해야 리얼타임으로 게임이 진행될 수 있을까? 그 해답은 반드시 필요한 부분만큼만을 골라내기 (culling) 에서 찾아야 한다.

  인간의 눈이란 머리의 상하전후좌우에 몇개씩 달려있는 것이 아니라 전방에 2 개씩만 달려있으므로 우리가 어떤 자세를 취하고 있건 세상의 극히 일부만을 볼 수 있다. 이 말은 다시 말하자면 월드를 구성하고 있는 수만개의 폴리곤중 막상 화면에 찍어야 할 폴리곤은 수천개~수백개에 불과하다는 것이다. 어떤 방법을 써야 전체 수만개에서 필요한 수백~수천개를 골라낼 것인가? 이것이 바로 내가 설명하고자 하는 요지이다

  배경중에서 필요한 부분만을 골라내는 것을 컬링(culling) 이라고 한다. cull 이라는 말은 사전에서 찾아보면 어떤 무리에서 따서 골라낸다는 의미가 있다. 바로 그대로 배경중에서 눈에 보이는 부분만을 따서 골라내고 나머지는 버리는 작업을 의미하는 것이다.

  내가 아는 바로는 컬링에는 3 가지 종류가 있다

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

  영어로 써 놓으니 안그래도 어려운 말이 더 어려워보인다. 하지만 그 근본 개념을 알면 어려운 것만은 아니다

  Backface culling 은 가장 간단한 것이다. 이것은 object 가 closed polygon 으로 구성되어있다고 가정할때, 각 face 의 방향이 시점의 반대쪽을 바라보고 있을때에는 찍을 필요가 없다는 것을 의미한다. 이에 대한 지원은 OpenGL 이나 Direct3D 상에서 기본적으로 이루어지고 있기 때문에 여기서 더 상세히 설명하지는 않도록 하겠다. 만약 위의 설명을 보면서 closed polygon 이란 말이 무슨 의미인지를 이해할 수 없다면 다시 처음으로 돌아가서 책을 보면서 기본단계부터 연마하도록 해야 할 것이다.

  View Frustum Culling 에 대해서 알려면 먼저 Frustum 에 대해서 알아야 한다. 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 과 완전히 충돌하지 않는다는 것을 알게 되면, 그 자식노드들은 전혀 계산할 필요가 없다는 점이다. 이 원리에 의해서 수만개의 폴리곤들이 몇백번 이내의 계산에 의해서 훨씬 적은 수의 화면상에 들어오는 폴리곤들로 컬링되는 것이다

  위까지 VFC 의 개념에 대해 알아보았다. 다음은 Occlusion Culling 에 대해 알아보도록 하자.

  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 이라고 불린다.

  아직 필자는 실내용 엔진을 실제로 구축해보지 않았기 때문에 occlusion culling 의 실질적인 방법에 대해 언급할 수는 없고 다만 이론상의 추측과 자료를 읽어본 것을 토대로 하여 위의 내용을 쓴 것이므로 아직 보완의 여지가 더 남아있다고 할 수가 있다.

  이상 컬링을 이용한 배경표현에 대해 알아보았다. 필자의 글을 읽고나서 실제 프로그래밍을 하려고 하면 여러가지 수학적인 문제에 봉착하게 될 것이다. 예를 들면 aabb (axis aligned bounding box) 나 obb (oriented bounding box) 와 frustum 간의 충돌체크는 어떻게 해야 할 것인가? frustum 의 카메라좌표계로부터 월드좌표계로의 변환은 어떻게 할 것인가? 등이 그것이다.

  이에 대해서는 좋은 참고서적들이 많이 있으므로 직접 책을 보면서 해답을 찾기를 바란다. Tomas Moller 와 Erich Haines 가 같이 쓴 Realtime Rendering (AK Peters 출간) 이란 책은 개론적인 설명과 실제적인 알고리즘 (특히 충돌체크에 대해) 을 많이 소개하고 있기 때문에 필독서라고 할 수가 있다. 최근에 second Edition 이 발표되어 내용도 1.75 배정도 늘어났기 때문에 더욱 소장가치가 높아졌다. 또한 Dave Eberly 가 쓴 3D Game Engine Design (Morgan Kaufmann 출간) 은 실제 완성된 게임엔진과 중요한 수학적 알고리즘, 코드들을 담고 있기 때문에 꼭 갖고 있어야 할 책이다. 난 영어도 약하고 수학도 잘 모르는데 어떻게 하나? 하고 고민하는 사람도 많이 있을 것이다. 솔직하게 말하는 것이지만, 영어책을 보는 것이나 수학 공식을 보는 것이 싫은 사람은 '게임 엔진'을 만드는 길을 포기하는 것이 나을 것이다.

imcgames 의 김학규입니다