이 글은 조만간 출판될 Game Programming Gems 2 한국어판(류광 역, 정보문화사)의 일부입니다. 이 글에 대한 모든 권리는 정보문화사가 가지고 있으며, 사전 허락 없이는 웹 사이트 게시를 비롯한 어떠한 형태의 재배포도 금지되어 있습니다.

이 글은 최종 교정 전의 상태이므로 오타나 오역이 있을 수 있습니다. 또한 웹 페이지의 한계 상, 실제로 종이에 인쇄된 형태와는 다를 수 있습니다.

Game Programming Gem 2 한국어판에 대한 정보는 GPG 스터디(http://www.gpgstudy.com/)에서 얻을 수 있습니다.

4.2 맞물린 타일들을 이용한 단순화된 지형 시스템

Greg Snook
gregsnook(at)home.com

최근의 3D 렌더링 하드웨어의 발전 덕분에, 이제는 많은 게임 개발자들이 야외 환경에 관심을 기울이는 것 같다. 먼 수평선과 산맥을 갖춘, 그리고 안개와 원단면(far clipping plane)에 의해 가려진 경치가 이제 상당한 현실감을 가지게 되었다. BSP 트리와 스팬 기반 렌더링 방법들에 몰려갔던 게임 프로그래머들이 이제는 ROAM이나 VDPM같은 새로운 약자들을 입에 달고 다닌다.

ROAM(Real-time Optimally Adapting Meshes) [Duchaineau]와 VDPM(View Dependent Progressive Meshing) [Hoppe98]에 대해 자세히 설명한 자료들은 많이 있으므로("참고 자료"를 볼 것), 여기서는 간단히 요약만 하고 넘어가겠다. ROAM과 VDPM은 모두 전체 지형 중 자세히 그릴 필요가 없는 부분, 예를 들면 어느 정도 평평한 부분이나 카메라로부터 멀리 떨어져 있는 부분들의 다각형 갯수를 줄이기 위한(그럼으로써 렌더링 성능을 높이기 위한) 기법들이다. 반대로 이야기하면, 이런 기법들은 카메라와 가깝거나, 굴곡이 심한 지형 처럼 좀 더 많은 다각형들이 필요한 부분을 자세하게 그리기 위한 것이라고도 할 수 있다. 간단히 말하면, ROAM이나 VDPM은 본질적으로 필요한 부분에는 더 많은, 필요하지 않은 부분에는 더 적은 다각형들을 렌더링한다는 동일한 목표를 가지고 있다.

ROAM이나 VDPM 같은 방법들은 세부 수준이 낮은 영역과 높은 영역 사이에 매끄러운 전이가 일어나도록 하기 위해 지형을 절차적으로(procedurally) 생성하는 접근 방식을 사용한다. ROAM은 삼각형 교점들의 이진 트리를 이용해서 주어진 높이 필드로부터 실제 지형 기하 구조를 만들어 낸다. VDPM은 저해상도 지형을 표현하는 듬성듬성한 메시 하나로 부터 시작하며, 세부 수준이 높아져야 한다면 그 메시의 정점들을 분리시킴으로써 세부 수준의 변화를 반영한다. 대부분의 경우, 이러한 동적이고 연속적인 삼각형 분할들때문에, 정적인 기하 구조일 때 가장 효율적인 하드웨어적 변환 및 조명(T&L)을 제대로 활용할 수가 없다.

이런 문제의 근본 이유는, 이러한 방법들이 너무 잘 작동한다는 데 있다. 이런 방법들은 지형을 다각형 수준으로 분석해 나가면서, 유지되는 것들과 축소되는 것들을 일일이 집어내는 능력을 가지고 있다. 이 때문에 지형 기하 구조의 변화에 많은 시간이 소비되며, 지형이 변할 때마다 전체 과정을 매 번 다시 처리해야 한다. 기하 구조에 대한 세밀한 제어를 어느 정도 희생한다면, 정적 기하의 커다란 영역을 다룸으로써 하드웨어를 최대한 활용할 수 있으며, 시간에 따른 지형 변화에도 유연하게 대처할 수 있다.

이 글에서 제안하는 것은 대부분의 응용 분야에서 아주 적은 코딩만으로도 이득을 얻을 수 있는 상당히 간단한 방법이다. 이 방법으로 얻을 수 있는 렌더링 품질은 ROAM이나 VDPM 방법으로 얻을 수 있는 시각적 품질보다 좀 떨어질 것이다. 그러나, 동적으로 적응하는 세부 수준들과 애니메이션의 유연성이 더 중요한 단순한 지형이라면 이 방법이 더 유리할 수도 있다. 이 방법의 핵심은 하드웨어 변환 및 조명에 매우 적합한 자료구조를 유지하는 것이다.

타일의 재등장

예전에는 게임 프로그래머들이 2D 타일(tile)들을 이용해서 게임 세계를 표현했다. 타일을 사용했던 이유는 간단하다. 같은 크기의 게임 세계를 만드는 데 필요한 그래픽 작업이 더 적고, 게임 세계를 관리하는 것도 쉬웠기 때문이다. 초기 게임들은 많은 양의 픽셀 데이터를 담을 만한 메모리를 사용할 수 없었으므로, 조그만 그림을 타일 방식으로 화면에 채워서 커다란 영역을 만들어 내는 방식은 좋은 대안이 되었다. 그러한 조그만 그림(타일)들은 그리거나 화면에 표시하는 것이 용이했다. 예를 들어 작은 32x32 타일들을 이용해서 부드럽게 스크롤되는 2D 게임을 만드는 것은 어렵지 않은 일이었다.

이 글에서 이야기하는 지형 표현 방법도 2D 타일 기법과 동일한 개념에 기초한다. 즉 커다란 지형을 작고 재사용 가능한 타일들로 나누는 것이다. 이에 의해 얻을 수 있는 장점 또한 비슷하다. 다뤄야 할 데이터도 적고, 그리기 루틴을 최적화하기도 좋고, 메모리 사용도 더 효율적이다. 물론 지금 이야기하는 지형은 3D 지형이므로 타일 안의 픽셀 데이터를 다루는 것은 아니다. 여기서 말하는 3D 지형 타일들이란 구체적으로는 지형의 정점들을 서로 연결하는 색인 버퍼들이다.

3D 타일들은 지형을 위에서 내려다 봤을 때(즉 기준 평면에 투영했을 때) 생기는 하나의 격자라고 생각하면 된다. 격자의 각 칸은 지형 시스템의 한 타일에 해당한다. 지형이 비교적 무작위적인 기하 구조를 가지는 한, 실제 표면에서 지형 타일들이 반복되는 것처럼 보이지는 않는다. 표면에서 지형이 반복되는 경우는 없으나, 내부적으로는 타일링과 재사용을 위한 방대한 데이터가 존재한다.

각 지형 타일은 하나의 정점과 색인 버퍼로 구성된다. 각 타일이 고유한 정점 집합을 가진다 해도, 그 타일을 그리는데 쓰이는 색인 버퍼들은 공유될 수 있다. 사실 정점 데이터를 현명하게 만들어 두면, 유한한 종류의 색인 버퍼들을 이용해서 방대한 지형 전체를 그릴 수 있다(역주: 이는 2D 타일 기법에서 상, 하, 좌, 우 모두 매끄럽게 반복될 수 있는 타일 이미지를 그리는 것과 개념적으로 유사하다. 물론 구체적인 구현은 다르다).

그러한 타일들을 만들기 위해서는, 타일의 기하 구조에 약간의 제한을 가해야 한다. 첫 번째로, 각 타일은 반드시 동일한 갯수의 정점들을 가져야 하며, 외곽의 변을 이루는 정점들은 인접한 타일과 공유되게 해야 한다. 이러한 정점들은 가장 높은 세부 수준 버전의 타일을 표현한다. 두 번째로, 타일의 정점들은 x-y 평면의 규칙적인 격자 구조에 맞게 배치되어야 한다. 이 때 z 는 해수면에 대한 정점의 높이를 표현한다. 마지막으로, 각 타일의 정점을 동일한 순서로 저장해야 한다. 이는 색인 버퍼들이 어떠한 타일에도 쓰일 수 있게 하기 위한 것이다. 그림 4.2.1의 예제 타일을 보자. 그 타일의 정점들은 17x17 개이며, 균등하게 분할된 격자 구조와 정확히 일치되도록 배치되어 있다(물론 x-y 평면 상에서 보았을 때의 이야기이다). 높이(z 값)들은 서로 다를 수 있으며, 그 높이들에 의해 굴곡이 진 하나의 지형 조각이 표현된다. 높이 값들은 지형 비트맵으로부터 가져온 것이다.

정점들을 이런 식으로 조직화하는 이유는 간단하다. 정점 데이터는 항상 규칙적인 격자 구조에 기반하며 동일한 순서를 가지므로, 전체 지형에 대해 하나의 고정된 색인 버퍼 집합을 만들 수 있다. 적절한 색인 버퍼를 사용하면, 하나의 주어진 타일이 어떤 수준(완전한 세부 수준에서부터 한 쌍의 삼각형에 이르기까지)에서도 렌더링될 수 있다. 더 많은 정점들을 사용하는 색인 버퍼들은 더 높은 세부 수준의 지형을 만들어낸다. 마찬가지로, 더 적은 정점들을 사용하는 색인 버퍼들은 좀 더 단순화된 지형을 만든다. 그림 4.2.2는 두 가지 서로 다른 세부 수준에서의 색인 버퍼들에 의해 그려진 타일들이다.

그림 4.2.1 17x17 개의 정점들로 이루어진 하나의 지형 타일
그림 4.2.2 동일한 정점들을 서로 다른 세부 수준의 색인 버퍼들로 렌더링한 예

맵 만들기

타일들로 지형을 만들어 내기 위해서는 각 타일의 높이를 결정하는 데이터가 필요하다. 가장 흔한 방법은 높이 맵으로부터 높이 값들을 읽어 오는 것이다. 높이 맵(height map)은 지형을 표현하는 하나의 그레이스케일 비트맵으로, 각 픽셀의 휘도(luminance, 輝度)가 주어진 위치의 높이를 의미한다. 높이 맵은 2차원 픽셀 맵이므로 이미 격자 구조 형태로 배치되어 있는 셈이며, 따라서 지형 정점 데이터로 변환하는 것이 매우 간단하다. 또한 높이 맵은 애니메이션의 자료로도 쓰일 수 있다. 즉 실행 시점에서 특정 픽셀의 휘도(높이)를 변경함으로써 지형을 동적으로 변화시킬 수도 있는 것이다.

타일 정점들을 만드는 것은 간단하다. 각 타일 정점의 x, y 좌표는 이미 x-y 평면 상의 격자 구조에 고정되어 있으므로, 필요한 것은 z 값뿐이다. z 값은 지형 비트맵으로부터 높이 값을 얻어서 적당한 비율로 변환하기만 하면 된다. 각 지형 타일에 대해, 높이 맵의 픽셀들 중 그 타일의 위치에 해당하는 픽셀의 값을 읽고 그것으로 타일에 대한 정점 버퍼를 만들면 되는 것이다. 애니메이션 높이 맵의 경우에는 지형 타일 정점들의 높이 값을 주기적으로 변화시켜 주어야 한다.

타일 템플릿

색인 버퍼는 타일 정점들에 대해 씌워지는 렌더링 템플릿이라 할 수 있다. 그림 4.2.2에서 볼 수 있듯이, 색인 버퍼는 타일로부터 삼각형들을 뽑아내는 방법을 정의하며, 타일을 어떤 세부 수준으로 그릴 것인가를 제어한다. 모든 타일의 정점 버퍼들은 동일한 순서로 저장되어 있으므로, 정점 버퍼들을 서로 교환하는 것이 가능하다. 예를 들어 9x9 격자의 경우, 어떠한 9x9 타일들에도 적용되는 최고 세부 수준의 색인 버퍼들을 정의하고, 세부 수준이 더 낮은 타일의 경우에는 그 색인 버퍼가 가리키는 정점들 일부를 건너뛰어서 렌더링하면 된다. 최상위 색인 버퍼들은 81개의 정점들을 모두 사용해서 128개의 삼각형들을 그리는 반면, 가장 낮은 수준에서는 네 개의 정점만 사용해서 한 쌍의 삼각형들로 이루어진 사각형 하나만 그리게 된다. 그 사이에 삼각형 32 개 짜리 세부 수준과 8 개 짜리 세부 수준이 존재한다.

9x9의 경우 총 네 개의 세부 수준들이 존재하는데, 그렇다면 언제 어떤 세부 수준을 선택할 것인가가 문제가 된다. 이에 대해서는 타일과 카메라 사이의 거리를 기준으로 하는 아주 간단한 알고리즘에서부터 카메라 각도와 타일의 시각적인 울퉁불퉁함 정도까지 고려하는 복잡한 알고리즘에 이르기까지 많은 방법들이 제안되었다(역주: Game Programming Gems 1권에서 Yossarian King이 쓴 "자연스러운 세부 수준"에 나온 '확대율' 방법도 좋은 선택일 것이다). 가장 좋은 방법은 게임 지형과 카메라 이동에 의존하는 것이다. 이에 대해서는 VDPM 방법에 대한 Hugues Hoppe의 글 [Hoppe]을 참고하는 것이 좋을 것이다. 그 글에서 Hoppe는 각 지형 위치에 대한 세부 수준을 선택할 때 쓰일 수 있는 현명한 발견법 아이디어를 제시하고 있다. 부록 CD에 들어 있는 예제 프로그램 'SimpleTerrain'은 간결함을 위해 타일과 카메라의 거리만 고려한다. 일단 세부 수준을 선택했다면, 나머지는 간단하다. 선택된 세부 수준에 해당하는 색인 버퍼가 가리키는 타일 정점들을 그냥 3D API로 그려 주면 된다(역주: 여기서 텍스쳐 입히기라던가 기본 도형의 선택 등은 다른 차원의 문제이다).

매끄러운 연결

여기까지 구현한다면 기본적인 지형 시스템이 생기게 된다. 그러나 아직은 매끄러운 지형을 얻을 수 없다. 지금의 시스템으로 얻을 수 있는 것은, 서로 다른 세부 수준의 타일들이 임의적으로 들쭉날쭉 그려진 지형일 뿐이다. 게다가 세부수준이 다른 타일들의 경계에 빈틈이 생기기도 한다. 간단히 말해서 지형이라고 주장하기에는 조금 멋쩍은 결과인 셈이다.

이를 개선하기 위한 방법이자 이 글의 핵심을 이루는 기법은, 타일들이 서로 맞물리게 하는 것이다. 인접한 타일들의 세부 수준 차이에 상관없이, 타일의 삼각형들이 틈을 만들지 않고 서로 맞물리도록 할 수 있다면 문제가 해결된다. 그렇게 하기 위해서는, 서로 다른 세부 수준의 타일들을 서로 연결하는데 사용할 또 다른 색인 버퍼들을 만들어야 한다. 그러한 색인 버퍼들은 두 부류로 나뉜다. 하나는 본체, 또 하나는 연결부이다. 본체는 주어진 세부수준에서의 타일의 주된 부분을 표현하며, 인접 타일과는 직접 맞닿지 않는다. 연결부는 이름 그대로 인접 타일과의 끈김없는 연결을 위한 것으로, 서로 다른 세부 수준의 타일들이 연결될 때 틈이 생기지 않게 하는 역할을 한다.

그림 4.2.3 16개의 기본 본체들. 흰 바탕은 연결부에 의해 대치된다.

그림 4.2.3은 임의의 세부 수준의 타일에 쓰일 수 있는 16 개의 기본 본체들을 나타내고 있다. 문제를 간단하게 하기 위해, 타일들은 오직 아래쪽으로만, 즉 높은 세부 수준의 타일이 인접한 낮은 수준의 타일에 맞는 자신의 연결부를 선택해서 낮은 수준의 타일과 연결한다고 하겠다. 그림 4.2.3에서, 각 본체의 흰 바탕 부분은 낮은 수준의 인접 타일과 매끄럽게 연결된 수 있는 연결부에 의해 대체된다.

연결부는 본체보다 좀 더 작은 색인 버퍼로, 본체 가장자리 부분을 대체하게 된다. 연결부 색인 버퍼들은 낮은 세부수준의 인접 타일과 딱 들어맞을 수 있는 갯수의 삼각형들을 구성한다. 그림 4.2.4는 연결부가 세부수준이 다른 두 개의 타일들을 어떻게 연결하는지 보여준다. 9x9 정점들로 이루어진 타일의 경우 세부 수준은 총 네 가지이므로, 가장 높은 세부 수준 타일의 각 변에 대해서는 세 종류의 연결부가 필요하다(가장 높은 세부 수준은 나머지 세 세부 수준 모두와 연결되어야 하므로).

그림 4.2.4 서로 다른 세부수준을 가진 두 타일들을 연결하는데 쓰이는 연결부의 예

표 4.2.1 네 개의 세부 수준을 가지는 9x9 타일에 필요한 모든 색인 버퍼들
 세부 수준  본체 갯수 +  연결부 갯수  = 합계 
 4  16  각 변마다 3개  28 
 3  16  각 변마다 2개  24 
 2  15  각 변마다 1개  19 
 1  1  0  1 
       총합: 72 

9x9 정점 타일의 경우 총 네 개의 세부 수준들을 가지므로, 필요한 색인 버퍼들의 수는 본체 48개 더하기 연결부 24개, 즉 72개이다. 표 4.2.1은 매끄러운 지형에 필요한 색인 버퍼들의 갯수를 종류 별로 정리한 것이다. 당연한 말이겠지만 세부수준의 갯수가 늘어날 수록 색인 버퍼의 갯수도 늘어난다. 그러나 각 색인 버퍼의 크기는 별로 크지 않으며, 지형 전체에 대해 반복적으로 쓰일 수 있으므로, 메모리가 크게 낭비되는 것은 아니다.

더 빠르게, 더 좋게, 더 강하게

이러한 본체와 연결부를 도입했기 때문에, 렌더링 코드도 변경되어야 한다. 이제는 각 타일에 대해 그와 인접한 타일들을 조사해야 한다. 연결이 아래쪽으로만 일어난다고 했으므로, 인접한 타일들 중 자신보다 세부 수준이 낮은 것들만 점검하면 된다. 세부 수준이 낮은 타일을 찾은 후에는 그 타일의 세부 수준에 맞는 자신의 연결부를 선택하고, 본체와 함께 그 연결부의 정점들을 렌더링 API로 보낸다. 최악의 경우 타일 하나 당 다섯 개(본체 하나, 연결부 네 개)의 색인 버퍼들을 보내야 할 것이다. 최상의 경우라면 본체 하나(본체 타일 전체)만 보내면 된다.

색인 버퍼들을 삼각형 띠나 삼각형 부채로 구성한다면 속도를 더욱 높일 수 있을 것이다. 타일 크기가 크다면(정점 33x33 이상), 띠나 부채로 인한 속도 상의 이득도 상당히 커진다. 또한 타일 안의 정점들의 순서를 정점 캐시 효율성을 높일 수 있는 순서로 잘 조정하는 것도 좋은 방법이다. 어떤 순서가 더 효율적인지는 어떤 색인 버퍼가 가장 자주 쓰이는가에 따라 다를 것이다.

결론

그림 4.2.5는 지금까지 이야기한 방법으로 그린 지형이다. 예제 프로그램 SimpleTerrain은 DirectX 8.0을 사용한다. 부록 CD에는 예제 프로그램의 전체 소스 코드가 들어 있다. 그림 4.2.5는 다양한 본체 타일들과 연결부 타일들이 어떻게 쓰이고 있는지를 좀 더 잘 보여주기 위해 텍스쳐들은 생략하고 와이어프레임으로 렌더링한 결과이다.

이 글의 의도는 동적인 지형 렌더링에 인기 있는 절차적 방법들에 대한 하나의 대안, 주로는 하드웨어 T&L을 최대한 활용하는 것에 주안점을 둔 대안을 제시하는 것이었다. 이 글에서 살펴 본 방법을 사용하면, 프로그램의 프레임율에 큰 영향을 미치지 않는 동적인 지형 시스템을 만들 수 있다. 이 방법에 의한 최종적인 지형의 시각적 품질은 잘 만들어진 ROAM이나 VDPM 시스템에서보다 떨어진다. 그러나 이 방법은 그러한 방법들의 기본적인 장점들을 그대로 유지하면서 하드웨어적으로 커다란 속도 향상을 꾀할 수 있다는 장점을 가지고 있다.

그림 4.2.5 타일 본체와 연결부를 이용하는 SimpleTerrain 프로그램의 출력 예

참고자료