BSP Tree

BSP를 이용한 3D Game Programming

강좌 1. BSP의 이해

장면 관리(Scene Management)

실제 게임에 사용하는 폴리곤의 개수는 갈수록 늘어가는 추세이며 이는 하드웨어의 발달에 힘입은 바가 크다. 최신의 비디오 카드들은 CPU를 능가하는 GPU(Graphics Processing Unit)을 탑재하고 있으며 이는 초당 수백만 폴리곤을 화면에 무리없이 그려낸다. 그럼에도 불구하고 3차원 게임 개발이 어려운 이유는 무엇인가? 역설적일지는 모르지만 개발자의 입장에서 보면 하드웨어가 게임을 모두 정석대로 소화하기엔 여전히 느리기 때문이다. 모든 개발자들은 자신이 만든 게임이 시스템 사양과 관계없이 초당 30프레임 이상으로 잘 동작하기를 바란다. 이를 위해 필연적으로 CPU와 GPU의 연산을 줄이는 특별한 방법(어떤 면에서는 trick에 가까운)이 필요하다. 개발자들은 이러한 방법들을 추상화 하여 쉽게 개발하기 위해 게임 엔진을 설계한다.

개발자의 입장에서 게임 시나리오가 확정된 이후 3차원 게임을 개발을 시작하려고 할 때 처음 해야하는 일은 게임 엔진의 기초를 확립하는 것이다. 개발하려는 게임의 특성에 따라 각기 차이점은 있겠지만 엔진은 기본적으로 복잡한 장면(Complex Scene)을 관리할 수 있어야 한다. 장면(Scene)은 크게 정적 객체(Static Object)와 동적 객체(Dynamic Object)로 구분할 수 있다. 정적 객체란 게임의 실행시 한번 로딩한 이후 변하지 않는 객체, 즉 정적 게임 맵(Static Game Map)을 의미한다. 그러나 움직이는 문이나 동적 광원, 캐릭터, 아이템은 모두 동적 객체에 속한다. 그러나 장면 관리를 제어하기 위한 게임 엔진의 설계는 말처럼 쉽지는 않다. 많은 개발자들은 보다 뛰어난 장면 관리를 위한 방법들을 고안하였으며 이중  대표적인 것이 퀘이크(Quake)에서 사용한 BSP 기반 게임 엔진이다.


퀘이크 게임 엔진

둠 시리즈로 유명한 ID소프트웨어의 존 칼막(John Calmak)은 1995년도에 완전한 3D 환경의 게임인 퀘이크를 출시하였는데 이는 BSP, PVS, Light Map등 그 당시로서는 매우 획기적인 기술들을 도입한 놀라울만한 게임이었다. 이후 많은 개발자들이 퀘이크와 유사한 게임 엔진을 개발하기 위해 부단히 노력하였으며 이는 퀘이크 장르의 게임들이 쏟아져 나오는 계기가 되었다. 저자 또한 퀘이크 게임 엔진의 분석을 통해 많은 것을 배울 수 있었다. 이 문서 또한 그와 유사한 게임 엔진을 제작하는 기법에 대한 방법을 다룰 것이다.

[그림 1]. Quake (ID Software)

스크린샷이 최신 게임들에 비해 초라해 보이는가? 그러나 최신 게임들 조차도 이 게임에 적용된 모든 기술들을 아직도 복습해서 사용하고 있다. 그럼 이와 같은 게임을 만들려면 어떻게 해야 하는가? 간단하게 설명하면 다음과 같다.

1. 게임 맵 데이터를 바탕으로 하여 BSP 트리를 구축한다.

2. 이 트리 구조를 응용하여 PVS를 생성한다.

3. 동적 객체에 대한 Object PVS를 생성한다.

4. 라이트맵(Light Map)을 생성한다.

이게 무슨말인지 모른다고 해서 걱정할 필요는 없다. 만약 여러분이 위의 내용을 다 알고 있다면 이 문서를 볼 이유가 없다. 이제 차근차근 도표와 예제를 통해 설명해 나갈 것이다.


사전 지식

이 글은 독자들이 다음과 같은 사전 지식이 있다고 가정한다. 만약 자신이 부족하다고 생각한다면 다른 책들을 참고하길 바란다.

1. Standard C & C++ 프로그래밍

2. STL (Standard Template Library)

3. Visual C++을 이용한 Win32 프로그래밍

4. OpenGL

5. 3차원 그래픽스에 대한 기초 수학 (특히 벡터, 행렬)

글은 되도록 쉽게 쓰려고 노력하였으나 글재주가 엉망이라 내가 봐도 좀 한심한 부분이 있다. 똑똑한 사람일수록 글을 쉽게 쓴다는 말이 일리가 있는 것 같다. 부족한 점이 있더라도 이쁘게 봐주길 바란다.


BSP의 개념

BSP(Binary Space Partitioning)이란 공간을 분할하는 정보를 담고있는 2진 트리를 의미한다. BSP는 원래 은면 제거(Hidden Surface Removal)을 목적으로 고안하였으나 BSP의 공간 분할에 대한 특성으로 인해 그 응용 범위는 넓게 확장되었다. 이 장에서는 고전적인 BSP의 제작 방법을 다룰것이다. 여기서 고전적이란 의미는 일반적으로 그래픽스에서 사용하는 BSP를 의미한다. 고전적 BSP는 실제 게임에서 사용하는 BSP와는 약간 틀린점이 있지만 본질적으로 개념은 동일하다. 게임에서 사용하는 BSP는 고전적인 BSP를 변형한 Solid Leaf BSP를 주로 사용하는데 이는 공간을 개발자들이 관리할 수 있는 형태로 분할하는데 도움을 준다. 또한 적절히 분할한 공간을 이용하여 PVS(Potential Visiblity Set)를 구성할 수 있는 기반으로 사용할 수 있다.

그럼 어떻게 BSP를 생성할 것인가? 폴리곤으로 구성된 입체를 BSP 트리 형태로 표현하는 방법은 다음과 같다.

1. 입체를 구성하는 폴리곤 리스트에서 하나를 선택하여 기준으로 삼는다.

2. 새로운 BSP 노드를 생성하여 선택한 폴리곤을 노드에 추가한다.

3. 선택한 폴리곤의 평면의 방정식을 구한 후에 나머지 폴리곤을 모두 테스트하여 평면의 앞에 있는 폴리곤과 뒤에 있는 폴리곤을 분류하여 리스트를 만든다. 즉, 앞쪽 리스트와 뒤쪽 리스트를 완성한다.

4. 앞쪽 리스트에서 하나의 폴리곤을 선택하여 기준으로 삼는다. 선택한 폴리곤은 이전에 선택한 폴리곤의 하위 Front 노드에 저장한다. 리스트에 남는 폴리곤이 없을 때 까지 2의 과정을 재귀적으로 반복한다.

5. 뒤쪽 리스트에서 하나의 폴리곤을 선택하여 기준으로 삼는다. 선택한 폴리곤은 이전에 선택한 폴리곤의 하위 Back 노드에 저장한다. 리스트에 남는 폴리곤이 없을 때 까지 2의 과정을 재귀적으로 반복한다.

위의 내용이 잘 이해가 되는가? 무슨 말인지 모르겠다면 당신은 정상이다. 그럼 예를 들어 살펴보자.


BSP 트리 구성의 기초

게임 맵은 폴리곤의 집합이다. 이러한 폴리곤은 최소 세개의 정점(Vertex)을 가지고 있으며 이들 정점들은 하나의 평면을 결정한다. 따라서 모든 폴리곤은 자신이 속한 평면의 방정식을 얻을 수 있다. [그림 2]는 하나의 폴리곤이 하나의 평면에 속해 있음을 보여준다. 그럼 이러한 평면을 어떻게 구할 것인지 알아보자.

[그림 2] 삼각 폴리곤 ABC가 하나의 평면을 결정하고 있음

그렇다면 어떻게 폴리곤의 정보를 이용하여 폴리곤이 속한 평면을 구할 수 있을까? 다 알고 있겠지만 초보자들을 위해 간단히 설명하겠다. 일반적으로 평면의 방정식은 다음과 같다.

ax + by + cz + d = 0

(x, y, z는 변수이고 a, b, c, d는 상수)

이중 a, b, c는 평면의 방향벡터(Normal Vector)이므로 벡터 AB와 BC의 Cross Product를 얻으면 그 값은 a, b, c와 일치한다.

Vector(a, b, c) = AB CrossProduct BC

만약 폴리곤의 회전 방향에 대한 표현법이 CW(Clock Wise) 방식이라면 Vector(a, b, c)는 평면의 방향벡터와 일치할 것이다. 그러나 폴리곤의 회전방향이 CCW(Clock Counter Wise)라면 평면의 방향벡터와 반대방향의 값을 얻는다. 이점에 주의하라.

참고 - CW란 시점에서 폴리곤을 바라볼때 폴리곤을 구성하는 정점의 순서가 시계 방향으로 돌아갈 경우 평면이 시점에 대하여 앞면을 향한다고 정의하는 방법이다. 반대로 CCW는 정점의 순서가 반시계 방향으로 돌아갈때 평면이 시점에 대하여 앞면을 향한다고 정의한다. 일반적으로 OpenGL에서는 CW를 기본값으로 사용하며 D3D 에서는 CCW를 사용한다.

이제 a, b, c의 값을 알고 있으므로 d의 값은 다음과 같다.

d = -(ax + by + cz)

폴리곤의 정점은 평면 내부에 위치하기 때문에 x, y, z에 대입하면 성립한다. 따라서 x, y, z에 폴리곤의 정점 중 하나를 선택하여 대입하면 d의 값을 쉽게 얻을 수 있다. 폴리곤이 평면을 결정하는 방법은 BSP를 제작하는데 자주 사용할 것이다. 이제 폴리곤과 평면의 차이를 이해하였으면 다음으로 그림의 표현법에 대해 알아보자.

[그림 3]을 보면 이 맵은 4개의 폴리곤으로 이루어져 있다. 이 그림은 3차원적으로 폴리곤을 표현하고 있지만 [그림 4]는 동일한 내용을 2차원적으로 표현하고 있다. 앞으로는[그림 4]와 같은 형태로 폴리곤의 배치를 표현할 것이다.

[그림 3]

[그림 4]

[그림 4]에서 화살표는 평면의 방향을 의미한다. 그럼 이를 바탕으로 BSP를 직접 생성해 보자. 먼저 BSP는 이진 트리 구조(Binary Tree)이다. 이진 트리 구조란 하나의 노드가 2개의 하위 노드를 가짐을 의미한다. BSP의 첫번째 하위 노드에는 자신을 기준으로 앞쪽에 위치한 폴리곤을 저장하며, 두번째 하위 노드에는 뒤쪽에 위치시키는 것을 규칙으로 한다. 먼저 최상위 루트(root) 노드로 B를 선택하자.

[그림 5]

왜 하필 B를 루트 노드로 선택했을까? 지금으로선 별 의미 없다. 아무거나 선택해도 상관없다. 이제 트리 구조의 루트에 B가 위치할 것이다. [그림 5]를 보면 루트에  B가 위치함을 알 수 있다. B를 기준으로 하위 노드 2개가 있음을 알 수 있는데 이는 각각 자신을 기준으로 앞쪽에 위치한 폴리곤을 가리키는 Front 노드와 뒤쪽을 가리키는 Back 노드를 가지고 있다. 현재는 Front와 Back노드 모두 비어있는 상태이다.

이제 A를 선택하자. [그림 4]을 보면 B를 기준으로 볼 때 A는 B의 뒤에 위치함을 알 수 있다. 루트에는 이미 B가 위치하고 있으므로 B의 하위 Front 노드에 A를 추가한다.

[그림 6]

그런데 좀 이상하지 않은가? 확실히 A노드는 B의 뒤에 위치하는가? [그림 7]와 [그림 8]을 비교해 보라.

[그림 7]

[그림 8]

[그림 7]와 [그림 8]은 A의 방향 벡터가 반대 방향으로 위치해 있다. 그럼에도 불구하고 두 경우 모두 B를 기준으로 A는 뒤에 위치한다고 판단한다. 왜 이런 결과를 얻는가? 폴리곤 A를 구성하는 모든 정점은 폴리곤 B의 뒤에 위치하기 때문에 결국 A는 B의 뒤에 위치한다는 것을 알 수 있다. 다시 말하면 기준이 되는 B의 방향성만 의미가 있을 뿐 A의 방향성은 무시한다. 따라서 [그림 7]과 [그림 8]은 모두 [그림 6]의 형태로 배치함을 원칙으로 한다.

그렇다면 A를 기준으로 선택한다면 어떻게 될까? [그림 7]의 경우 폴리곤 B는 A에 대해 뒤쪽에 위치한다. [그림 8]의 경우 폴리곤 B는 A에 대해 앞쪽에 위치한다.

다음으로 남은 폴리곤 C, D중에서 D를 먼저 선택하자. D를 트리에 넣기 위해 먼저 루트 노드 B와 비교를 한다. D는 B의 앞쪽에 위치하므로 B의 하위 Front 노드에 저장한다. [그림 9]

이제 마지막으로 남은 폴리곤 C를 트리에 넣는다. C를 B와 비교해 보니 B의 앞에 위치한다. 따라서 C를 B의 하위 Front 노드에 추가하면 트리는 [그림 10]와 같은 형태를 이룬다. 하위 Front 노드에는 C, D 두개의폴리곤을 저장하고 있으므로 다음엔 C와 D를 위의 요령으로 다시 분할하자. 이번에는 D를 기준 폴리곤으로 잡으면 D의 뒤에 C가 위치하므로 D의 하위 Back 노드에 C를 보낸다. 이제 BSP 트리를 완성하였다. [그림 11]

2진 트리구조와 효율성

위의 예제에서 폴리곤 A, B, C, D에 대하여 B-A-D-C의 순서로 BSP 트리를 생성하였다. 그런데 어떠한 폴리곤을 먼저 선택하느냐에 따라 여러가지 트리 형태가 나타날 수 있다. 결국 트리 형태는 폴리곤의 선택 순서에 달린 것이다. 만약 폴리곤을 D-C-B-A의 순서로 선택하여 트리를 구성한다면 어떻게 될까? [그림 12]와 같은 형태를 이룬다.

[그림 12]가 [그림 11]에 비해 효율적인 트리라고 말할 수 있는가? 그렇지 않다. [그림 11]의 경우 트리의 깊이가 3인데 반해 [그림 12]는 4이다. 따라서 트리를 탐색하려 할 경우 [그림 11]의 경우가 더 유리하다고 할 수 있다. 따라서 BSP를 생성할 때 기준 폴리곤의 선택을 최적화하여 트리의 깊이를 최소화할 필요성이 있다.


동일 평면상의 폴리곤

BSP는 특정 폴리곤이 다른 폴리곤에 대하여 앞쪽에 있는가 뒤쪽에 있는가를 판단하는 근거를 제공한다. 그러기 위해서 특정 폴리곤을 선택하여 이를 기준으로 삼아 나머지 폴리곤들을 재배치(Classify)하였다. 그런데 선택한 기준 폴리곤의 평면에 대하여 동일한 평면에 위치하는 폴리곤은 어떻게 처리할 것인가? 이때에는 기준 폴리곤을 포함하는 노드에 같이 추가한다.

위의 그림에서 A를 기준 폴리곤으로 선택하였다 가정하자. 나머지 폴리곤 B, C, D를 A의 평면에 관해 분류하려고 보니 모두 동일 평면에 위치하고 있다. 게다가 C와 같은 경우 동일 평면상에 위치하고 있음에도 불구하고 반대 방향을 향하고 있다. 이 경우 어떻게 할 것인가? 정답은 B, C, D를 A를 포함하는 노드에 그냥 추가하는 것이다. BSP 노드는 2개의 연결 리스트(Linked List)를 가지고 있는데 그중 하나는 동일 평면상에 위치하며 동일한 방향성을 가지는 폴리곤을 저장하고, 나머지 하나는 동일 평면상에 위치하지만 반대 방향성을 가지는 폴리곤을 저장한다.

이와 같은 정보를 저장하기 위한 BSP 노드의 클래스를 정의하면 다음과 같다.

class CBspNode
{
public:
    float PlaneEquation[4];                 // 기준 폴리곤에서 얻은 평면의 방정식
    LinkedList SamePolyList;              // 동일 평면, 동일 방향의 폴리곤 저장
    LinkedList OppositePolyList;         // 동일 평면, 반대 방향의 폴리곤 저장
    CBspNode *pFrontNode;             // 하위 Front 노드
    CBspNode *pBackNode;             // 하위 Back 노드
};

[그림 14]

[그림 14]에서 기준 폴리곤 A는 폴리곤 B를 가로지르고 있다. 폴리곤 B의 일부는 A의 앞에 있고 일부는 뒤에 있다. 이러한 경우 폴리곤 B를 두 조각으로 분할하여 각기 저장한다. [그림 15] 을 보면 A를 포함하는 평면에 대해 B가 B1과 B2로 분할된 것을 볼 수 있다. 여기서 B1은 A의 앞쪽이 있고 B2는 뒤쪽에 있으므로 각각 A의 하위 Front 노드와 하위 Back 노드에 추가한다.

예제

지금까지 다룬 내용이 BSP 트리를 구축하기 위해 필요한 모든 내용이다. 위의 내용을 정확하게 알 수 있는지 자신이 없다면 다음 문제를 보며 연습하길 바란다. [그림 16]에 좀 더 많은 숫자의 폴리곤을 배치하였다.  그림에서 보듯이 폴리곤 A, K, L은 동일 평면에 위치하고 폴리곤 B는 폴리곤 E를 분할함에 주의해서 스스로 BSP를 분할해 보고 결과를 비교해 보자. 폴리곤의 선택 순서에 따라 결과가 달라짐에 주의하라.

[그림 16]

1. A를 기준 폴리곤으로 선택한다. K와 L이 동일 평면에 위치하므로 A를 포함하는 노드에 추가한 후에 하위 Front와 하위 Back노드를 추가한다.

2. 하위 Front 노드를 구성하는 B, C, D, E, F, G중에서 B를 기준 폴리곤으로 선택하여 다시 분류한다. 이때 B는 E를 분할(Subdiv)하여 앞쪽에 위치한 E1과 뒤쪽에 위치한 E2를 얻은 후에 각각의 하위 노드에 저장한다.

3. 나머지 폴리곤들도 위의 요령으로 재귀적으로 구성한다. 결과는 다음과 같다.

자, 대충 이해했는가? 다음 강좌에서는 실제적으로 이러한 BSP를 C++을 이용해 구현하는 법에 대해 알아볼 것이다. 지금 다루는 내용은 고전적인 BSP이고 실제 게임에서 사용하는 BSP와는 조금 다르다는것을 기억하고 다음 강좌를 기대하길 바란다.


출처: http://www.gamesync.com.ne.kr/  (신용우)


------------------------------------------------------------------------------------------------
예전에 문제해결 시간에 BSP Tree를 발표하게 되었는데.. 그때 참고했던 자료이다..
덕분에 공간과 벡터에 대한 개념이 아주 약간 더 늘었다고나 할까..