지형렌더링

■ 3D Engine

** Realtime Dynamic Level of Detail Terrain rendering with ROAM **
원문 : By Bryan Turner Gamasutra April 03, 2000
[번역 : 이봉식 - 2000년 4월 20일]

목 차

▶ Introduction to Terrain Visualization
▶ Explanation of Patch Class
▶ Roam Engine Qualifiers

이 글을 Seumas McNally에게 바칩니다.
이 글의 끝에 있는 에필로그를 봐 주세요.

이 글에 관련된 데모 프로그램은 여기서 다운 받으세요.

많은 사람들과 마찬가지로 나는 굴곡진 언덕과 고요하며 두려움까지 자아내는 아슬아슬한 협곡들의 사진들을 구한다.
게이머로서 자연의 아름다움을 드러낼수 없다는 것은 불행한 일이다.
현재의 유망한 게임들중 소수만이 눈을 위해 이러한 향연을 제공한다.
(Tribes 1 & 2, Tread Marks, Outcast, Myth 1 & 2, and HALO).
이러한 게임들은 삼차원 액션게임들을 스토리와 동작이 연출되는 믿을수 없을 정도로 디테일한 세계로 옮겨놓는다.

이 기사에서 나는 하드웨어에 의해 가속되는 지형엔진들과 이 엔진을 구동하는 알고리즘에 대해 조사할 것이다.
다음 프로젝트에서 지형을 추가하고자 하는 사람들을 위한 시작점으로서 특별히 하나의 알고리즘을 제공하고 논의할 것이며 마지막으로 이 알고리즘을 구현할 것이다.
나는 독자들이 중급정도의 c++지식과 최소한 삼차원 렌더링에 대한 일반적인 지식을 가지고 있다고 가정하고 논의를 시작한다.

Intorduction to Terrain Visualization : 지형 시각화에 대한 도입(소개).

LOD지형 알고리즘들을 참조하지 않고 지형시각화(Terrain Visualization)의 세계로 뛰어들수는 없다.
LOD알고리즘은 정확하게 보이기 위해 지형의 어떤 부분이 더 자세하게 보일 필요가 있는지를 결정하기 위해 경험치의 집합을 사용한다.
의심할 바 없이 여러분은 많은 지형에 대한 참조물과 GPS데이터를 구할 것이다.
이러한 모든 것들은 군용의 SimNet 어플리케이션에서 사용되었지만 지금은 좀더 사소한 목적을 위해 사용되고 있다.

지형을 랜더링하기 위한 많은 기술적 변화들 중 하나는 지형자체에 존재하는 기능들을 저장하는 방법이다.
높이맵(height map)은 산업상의 표준이다.
간단히 말하면 높이맵은 그 위치에서의 지형의 높이값을 저장하고 있는 이차원 배열이다.
측량기사가 자신의 고도 측량툴을 사용하여 각 사각형을 채운 그래프 용지라고 생각하자.
높이필드는 높이맵이라고도 한다.
나는 이 두 용어를 상호교환적으로 사용할 것이다.

Overview of LOD Terrain Algorithms : LOD 지형 알고리즘에 대한 개요.

LOD지형 알고리즘에 대한 좋은 개요는 세 개의 논문에 잘 나타나 있다.
(1. Hoppe, 2. Lindstrom, 3. Duchaineau)

첫 번째 논문에서 Hoppe는 여러분이 좀더 세밀한 지형이 필요할 때 임의의 메쉬에 삼각형들을 추가하는 다소 새롭고 깔끔한 적응적 메쉬에 기반한 알고리즘을 제시한다.
이 논문은 훌륭한 참조서이지만 우리의 요구에는 다소 복잡하고 많은 메모리를 요구한다.

좀 더 우리의 스타일에 가까운 두 번째 논문에서 Lindstrom은 지형의 조각(Patch)을 표현하기 위해 사용되는 쿼드트리라고 하는 구조체를 제시한다.
쿼드트리는 높이 맵에 대한 근사값을 생성하기 위해 지형을 재귀적으로 분할한다.
쿼드트리는 아래의 알고리즘과 많은 설계원칙을 공유하고 있으며 아주 간단하고 효율적이지만 아래의 논문은 추가적인 보너스를 제공한다.

마지막으로 세 번째 논문에서 Duchaineau는 이진 삼각형 트리(Binary Triangle Tree)에 기반한 알고리즘(Real-time Optimally Adapting Meshes: ROAM)을 제시한다.
여기에서 각 패치는 단순히 (우측의) 이등변 삼각형이다. 삼각형의 정점에서 이 삼각형의 빗변의 중점을 분할하면 두 개의 새로운 이등변(우측) 삼각형을 만든다.
이러한 분할은 재귀적이며 원하는 디테일 수준에 이를 때 까지 자식노드들에 대해 반복된다.

연구 기간중 ROAM 알고리즘은 그 간결성과 확장성 때문에 나의 눈길을 끌었다.
불행히도 이 논문은 아주 짧고 구현을 위한 힌트로 최소한의 의사코드(pseudo code)만을 제공한다.
그러나 이 기법은 아주 기본적인 수준에서부터 거의 연속적인 단계로 아주 진보된 최적화까지 구현할수 있다.
각각의 단계는 계속하기 전에 유효화될수 있으므로 도움이 된다.
또한 ROAM은 아주 빠르게 분할하며 높이맵을 동적으로 갱신할 수 있게 해준다.

여기에서 제시하는 알고리즘은 Tread Marks (http://www.TreadMarks.com) 를 본따서 만들었다.
수석 프로그래머 Seumas McNally는 개념에서부터 완성까지 힘이 되어 주었다.
더 자세한 사항은 끝부분의 "Acknowledgment" 란을 보라.

Introduction to the ROAM Implementation : ROAM 의 구현에 대한 도입.

이 아키브에 있는 코드는 비주얼 C++6.0으로 작성되었으며 렌더링을 위해 오픈지엘을 사용한다.
나는 OpenGL에 대해서는 생소하지만 이 프로젝트의 이러한 측면들을 정확하게 코딩하기 위해 가능한 모든 방법들을 사용했다.
엔진의 설계와 구현에 관한 조언이나 충고는 언제나 환영한다.

이 프로젝트는 이 기사에서는 설명하지 않은 몇 개의 파일들을 갖고 있다.
이러한 파일들은 유틸리티 루틴과 WIN32하에서 OpenGL을 실행시키는데 필요한 일반적인 어플리케이션 오버헤드이다.
오직 "ROAMSimple.cpp"와 그 헤더 파일만을 이 기사에서 검토한다.

ROAM Source Explanation: ROAM 소스 설명.

나는 조감도적인 관점에서 이 알고리즘을 소개하고 개별적인 부분들이 어떻게 상호작용하는지에 대해 논의의 초점을 맞출 것이다.

* 높이맵 파일은 메모리에 로드되며 LandScape클래스의 인스턴스와 연결된다.
여러개의 LandScape객체는 무한한 크기의 지형을 만들기 위해 링크될수 있다.

* 새로운 LandScape오브젝트는 로드된 높이맵의 부분들을 새로운 Patch클래스 객체로 분할할수 있다.
이 단계의 목적은 두가지이다.

1. 이 알고리즘의 나머지 부분에서 사용된 트리구조는 깊이에 따라 지수적인 크기로 램의 사용량을 늘린다.
따라서 작은 영역을 유지하는 것은 그 깊이를 제한하는 것이다.

2. 높이맵의 동적갱신을 위해서는 변경된 지역에 대한 편차트리(Variance Tree)를 완전하게 다시 계산해야 한다.
아주 큰 패치의 경우 실시간 어플리케이션에서 계산하기에는 너무 느리다.

* 각각의 Patch객체는 메쉬 근사화(분할)를 위해 호출된다.
패치는 스크린상에 표시될 트라이앵글의 암시적좌표(x, y, z와 같은 명시적 좌표가 아님)를 저장하는 이진 삼각형트리이다.
논리적인 방식으로 버텍스들을 저장함으로써 ROAM은 트라이앵글당 36바이트 이상의 램 사용량을 절약한다.
좌표값들은 렌더링과정의 일부로서 효율적으로 계산된다.

* 분할이 끝난후 엔진은 이전 단계에서 생성된 이진 삼각형트리를 순회한다.
이 트리내의 리프노드(잎노드- 차일드노드를 갖지 않는 노드)는 그래픽 파이프라인을 통해 출력될 필요가 있는 트라이앵글들이다.
삼각형들의 좌표는 순회 도중 즉석에서 계산된다.

Height Map File Format : 높이맵 파일형식.

나는 행우선형식으로 저장된 8비트의 높이 샘플을 담고 있는 raw파일을 읽어들이는 가장 단순한 방법을 택했다.
이는 내 프로그램에서는 정확한 파일 포맷이다.
높이맵은 언제나 메모리에 존재한다.
"고급주제"란에서 좀더 큰 데이터집합에 대해 이 알고리즘을 확장하는 방법에 대해 논의할 것이다.

Binary Triangle Tree : 이진 삼각형 트리.

지형메쉬를 표현하기 위해 거대한 삼각형좌표의 배열을 저장하는 대신 ROAM알고리즘은 이진 삼각형 트리라고 하는 구조체를 사용한다.
이 구조체는 지형을 삼각형플롯(작은 삼각형 영역)들로 분할하는 측량자의 결과로 볼수 있다.
이러한 플롯들의 소유자들은 논리적으로 서로를 이웃하는 관계(좌, 우, 이웃등)로 본다.
마찬가지로 어떤 소유자가 상속을 통해 지형을 주면 이 지형은 두 개의 차일드사이에서 동등하게 분할된다.

이러한 유추를 더 확장하기 위해 플롯의 원소유자는 이진 삼각형트리의 루트노드이다.
다른 원소유자는 그들이 소유한 트리의 루트노드이다.
LandScape클래스는 지역적인 지형등록기와 같은 역할을 한다.
즉 플롯들의 원소유자를 추적하고 어떤 플롯이 여기에 속하는지를 기록한다.
이러한 등록은 또한 부모에서 차일드까지 모든 상속관계를 기록한다.
더 많은 차일드를 생성하면 할수록 지형은 좀더 많이 조사된다.
좀 더 근사화가 필요한 영역의 경우 그 영역에서의 인구(차일드의 수)를 늘림으로서 원하는 정도의 디테일을 얻을수 있다.
예제로 < figure 1 >을 참조하라.

Figure 1. Bindary triangle tree structure levels 0~3

이진 삼각형트리는 TriTreeNode구조체에 의해 표현되며 ROAM을 위해 필요한 다섯가지의 기본적인 관계들을 추적 유지한다.

이러한 관계들에 대한 표준적인 관점은 < figure 2 >를 참조하라.

struct TriTreeNode {
　　　　 TriTreeNode *LeftChild; // Our Left child
　　　　 TriTreeNode *RightChild; // Our Right child
　　　　 TriTreeNode *BaseNeighbor;
　　　　　　 // Adjacent node, below us
　　　　 TriTreeNode *LeftNeighbor;
　　　　　　 // Adjacent node, to our left
　　　　 TriTreeNode *RightNeighbor;
　　　　　　 // Adjacent node, to our right
};

Figure 2. Basic binary triangle with children and neighbors.

높이맵을 위한 메쉬 근사값을 생성할 때 우리는 원하는 디테일 레벨에 도달할때까지 트리에 차일드 노드들을 재귀적으로 추가한다.
이러한 단계가 끝나면 이 트리는 다시 순회되고 이번에는 실제적인 스크린상의 트라이앵글로서 리프노드들을 렌더링한다.
이러한 이중패스방식은 기본적인 엔진이 되며 매 프레임마다 리셋되어야 한다.
재귀적방법의 좋은점 중 한가지는 어떤 버텍스당 데이터(per Vertex Data)도 저장하지 않는다(버텍스에 관련된 어떤 데이터도 저장하지 않음(?))는 점인데 이는 램의 사용량을 줄일수 있다.

사실 TriTreeNode구조체는 너무 자주 생성되고 파괴되므로 가장 효율적인 방법으로 메모리를 할당하는 것은 반드시 필요하다.
또한 여기에는 이러한 구조체들이 수만개가 있으므로 하나의 여분의 포인터도 엄청나게 많은 메모리를 요구하게된다.
TriTreeNode구조체는 정적 메모리 풀(pool)에서 할당되며 따라서 동적인 메모리할당의 오버헤드를 피할수 있으며 상태를 리세팅하는 빠른 방법을 제공한다.

Figure 3. Typical patch of terrain. From left to right,
Wireframe (overhead view), Lit, and Textured

Explanation of LandScape Class : LandScape 클래스의 설명.

LandScape클래스는 지형렌더링의 지겨운 세부사항에 대한 고수준의 캡슐화로 동작한다.
어플리케이션의 관점에서 지형은 몇가지의 간단한 셋업함수를 호출한 후에 스크린상에 나타나야 한다.
여기에 LandScape클래스 정의의 중요한 부분이 있다.

class Landscape {
public:
　　void Init(unsigned char *hMap);
　　　　 // Initialize the whole process
　　void Reset();
　　　　 // Reset for a new frame
　　void Tessellate();
　　　　 // Create mesh approximation
　　void Render();
　　　　 // Render current mesh static
　　TriTreeNode *AllocateTri();
　　　　 // Allocate a new node for the mesh

protected:
　　static int m_NextTriNode;
　　　　 // Index to the next free TriTreeNode
　　static TriTreeNode m_TriPool[];
　　　　 // Pool of nodes for tessellation
　　Patch m_aPatches[][];
　　　　 // Array of patches to be rendered
　　unsigned char *m_HeightMap;
　　　　 // Pointer to Height Field data
};

LandScape클래스는 커다란 정사각 플롯들(정사각형 영역)을 관리하며 각자 자신의 플롯을 가진 다른 LandScape 객체와 동작한다.
이러한 설계는 좀더 큰 지형을 불러들이고 싶을 때 유용하다.
초기화과정에서 높이 맵은 좀더 관리가 용아한 조각들로 분할되며 새로운 Patch객체로 된다.
이러한 조각들은 Patch클래스가 되며 우리가 가장 많은 시간을 소비하는 매써드들과 연결된다.

이 함수의 단순성을 주목하라.
LandScape클래스는 특별히 요즘 이용가능한 하드웨어 z버퍼링의 이점이 주어지는 렌더링 파이프라인에 쉽게 적용할수 있도록 설계되었다.
이 데모를 더 간단히 하게 하기 위해 몇가지의 전역변수들이 사용된다.

▶ Explanation of Patch Class