ROAM에 관련된 자료.

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

이 글을 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 >을 참조하라.

</TD></TR>
<TR bgColor=#000000>
<TD>

Figure 1. Bindary triangle tree structure levels 0~3

</TD></TR></TBODY></TABLE>

이진 삼각형트리는 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 };

</TD></TR>
<TR>
<TD>

Figure 2. Basic binary triangle with children and neighbors.

</TD></TR></TBODY></TABLE>

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

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

</TD>
<TD width="43%">

</TD>
<TD width="13%">

</TD></TR>
<TR>
<TD colSpan=3>

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

</TD></TR></TBODY></TABLE>

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버퍼링의 이점이 주어지는 렌더링 파이프라인에 쉽게 적용할수 있도록 설계되었다. 이 데모를 더 간단히 하게 하기 위해 몇가지의 전역변수들이 사용된다.

Patch 클래스는 이 엔진의 고기와 감자(핵심)이다. 이 클래스는 대개 두부분으로 분리된다. 주 분할과 재귀적 분할이다. 여기에 데이터 선언과 Patch클래스의 주분할(stub half)이 있다.

class Patch { public: 　　 void Init( int heightX, int heightY, 　　　　　　 int worldX, int worldY, 　　　　　　 unsigned char *hMap); 　　　　　　　　 // Initialize the patch 　　 void Reset(); 　　　　 // Reset for next frame 　　 void Tessellate(); 　　　　 // Create mesh 　　 void Render(); 　　　　 // Render mesh void 　　 ComputeVariance(); 　　　　 // Update for Height Map changes 　　 ... 　　 ... 　　 ... protected: 　　 unsigned char *m_HeightMap; 　　　　 // Adjusted pointer into Height Field 　　 int m_WorldX, m_WorldY; 　　　　 // World coordinate offset for patch 　　 unsigned char m_VarianceLeft[]; 　　　　 // Left variance tree 　　 unsigned char m_VarianceRight[]; 　　　　 // Right variance tree 　　 unsigned char *m_CurrentVariance; 　　　　 // Pointer to current tree in use 　　 unsigned char m_VarianceDirty; 　　　　 // Does variance tree need updating?

TriTreeNode m_BaseLeft; 　　　　 // Root node for left triangle tree TriTreeNode m_BaseRight; 　　　　 // Root node for right triangle tree 　　 ... 　　 ... 　　 ...

코드의 흐름상 아래에 설명한 스텁(stub)함수들(주분할 함수들)는 부모 LandScape에 의해 소유된 각 Patch객체에 대해 호출된다. Patch클래스의 매써드명은 이 매써드들을 호출하는 LansScape의 매써드명과 동일하다. 이러한 매써드들은 너무 단순해서 자세한 분석을 할 필요조차 없다.

Init()는 높이필드배열과 월드에 대한 오프셋을 요구한다. 이러한 오프셋들은 서로 다른 크기의 지형에 대해 패치를 스케일링하는데 사용된다. 높이필드에 대한 포인터는 이 패치 데이터의 첫 번째 바이트를 가리키도록 조정되며 내부적으로 저장된다.

Reset()함수는 각 패치를 구성하는 두 개의 이진 삼각형트리를 다시 링크함으로써 무효한 TriTreeNode에 대한 참조를 제거한다. 지금까지는 언급하지 않았지만 각 패치는 사실 하나의 정사각형(ROAM논문에서는 "Diamond"라고 함)에 딱 들어 맞는 두 개의 이진 삼각형 트리로 구성된다. 혼돈스러우면 그림2를 다시 참조하라. 다음 절에서 이에 대해 더 자세히 살펴볼 것이다.

Tessellate()함수는 첫 번째의 주 분할 함수이다. 이 함수는 단순히 최상위 레벨의 트라이앵글(각 패치에서 두 개의 루트노드)에 대한 적절한 파라미터를 이 함수의 재귀적인 버전에 넘겨준다. Render()와 ComputeVariance()에도 동일하게 적용된다.

ROAM Guts : ROAM 의 내부.

지금까지 우리는 실제적인 알고리즘을 위해 지원되는 구조체에 대해서만 논의했다. 이제 본론으로 들어갈 시간이다. 이 시점에서 ROAM논문의 복사본을 갖는 것이 좋겠지만 어쨋든 나는 우리가 하던 방식대로 진행할 것이다. 삼각형들의 관계에 대해 < figure 2 >를 다시 참조하고 여러분 자신이 다음 상태가 어떻게 될지를 그려보라.

먼저 우리는 메쉬 근사화 과정에서 발생하는 가시적인 에러들을 측정하는 값들을 정의해야 한다. 내가 사용하는 방법은 Tread Marks엔진이 "Variance(편차)"라고 부르는 것의 복사본이다. 우리는 어떤 노드가 더 세밀한 디테일을 위해 분할되어야 하는지를 결정하고 어떤 방법으로 분할 할지를 결정하기 위해 이 측정치들을 사용한다. ROAM논문은 중첩된 월드공간 경계에 기반하여 이 측정치들을 사용한다. 이러한 측정치가 더 정확하긴 하지만 아주 느리다.

Variance(편차, 변이)란 이진 삼각형트리의 빗변의 중점의 보간된 높이와 그 지점에서의 실제 높이 필드값의 차이이다. 간단히 말하면 현재의 이진 삼각형트리가 자신이 커버하고 있는 실제의 높이필드영역과 얼마나 멀리 떨어져 있는가 하는 문제이다. 이러한 계산은 상대적으로 빠르고 높이필드 참조를 위해 한번의 메모리 검사만을 요구한다.

triVariance = abs( centerZ - ((leftZ + rightZ) / 2) );

잠시만! 여기에는 좀더 많은 것이 있다. 이러한 계산과 연관된 에러가 너무 크므로 우리는 각 패치의 두 개의 루트 이진삼각형 트리에 대해서는 이러한 편차를 계산할수 없다. 따라서 더 나은 측정을 위해 이러한 계산은 이 트리의 좀더 깊은 곳에서 계산되어야하고 이러한 계산값들의 평균화된 백업(값)을 계산해야 한다. 데모의 경우 이러한 계산을 위한 깊이는 컴파일시에 지정된다.

대개 편차 계산은 매 프레임마다 필요하지만 배후의 높이필드가 변하지 않는 한 그 값은 변하지 않을 것이다. 따라서 우리는 이진 삼각형트리와 함께 작동하는 편차트리의 개념을 도입할 것이다.

편차트리(Variance Tree)는 순차배열로 작성된 전체 높이의 이진 트리이다. 몇 개의 간단한 매크로들은 트리를 효율적으로 순회할수 있게 해주고 우리가 이 트리에 채워넣은 데이터는 노드당 차이인 한바이트짜리 값이다. 여러분이 이러한 구조에 대해 접해보지 못했다면 < figure 4 >를 참조하라.

</TD></TR>
<TR>
<TD>

Figure 4. Implicit binary tree structure

</TD></TR></TBODY></TABLE>

두 개의 편차트리(하나는 좌측 이진 삼각형트리를 위해 나머지 하나는 우측을 위해)가 패치클래스내에 저장된다.

이제 우리는 근사화된 메쉬를 생성하는 작업으로 돌아갈수 있다. 우리의 에러측정치(편차)가 주어질 때 특정 지점에 대해 이 편차가 너무 높으면 해당 이진 삼각형 트리를 분할하기로 결정할 것이다. 즉 현재 삼각형 아래의 지형이 울퉁불퉁하면 더 나은 근사화를 위해 이 삼각형을 분할해야 한다. 분할은 패어런트의 영역에 꼭 들어맞는 두 개의 차일드노드를 생성한다. < figure 1 참조>

자식노드까지 따라 내려간 후에 우리는 이러한 과정을 반복한다. 편차는 매 순회마다 절반으로 떨어진다. 어떤 시점에서 우리는 하나의 트라이앵글로 근사화할수 있을 정도로 충분히 부드러운 지형을 발견하거나 더 이상 진행할 단계가 없게 될 것이다. 결국 우리는 높이필드의 해상도까지 따라 내려간 메쉬를 생성하게된다.(?)

</TD>
<TD width="36%">

</TD>
<TD width="24%">

</TD></TR>
<TR>
<TD class=bl colSpan=3 height=24>

Figure 5. Terrain displayed at Low, Optimal and High variance settings

</TD></TR></TBODY></TABLE>

여전히 복잡한 문제가 하나 더 있다. 지형상에서 서로 인접하는 이진 삼각형트리들을 분할할 때 메쉬내에 크랙이 종종 발생한다. 이러한 크랙들은 패치경계영역 전체에 걸쳐 이 트리들을 균일하게 분할하지 않은 결과이다. 이러한 문제는 < figure 6 >이 보여준다.

</TD></TR>
<TR>
<TD>

Figure 6. Patch showing cracks in mesh

</TD></TR></TBODY></TABLE>

이러한 문제를 해결하기 위해 ROAM은 네이버포인터와 메쉬 자체의 흥미있는 사실을 이용한다. 특정 노드의 이웃은 동일한 레벨이거나 한레벨 더 디테일(좌/우측 이웃(neighbor)의 경우)하거나 한 레벨 덜 디테일(베이스이웃의 경우)하다. 우리는 메쉬 생성과정에서 우리와 동기화하여 이웃하는 트리들을 유지하기 위해 이 사실을 이용한다.

이는 단순한 규칙으로 귀결된다. 현재노드와 그 베이스네이버(이웃)가 둘다 서로를 가리키는 경우< figure 7 참조 >에만 분할한다.

이러한 관계를 다이아몬드라고 한다. 다이아몬드내의 하나의 노드를 분할하면 메쉬내의 크랙을 발생시키지 않고도 다른 한쪽에 미러링될수 있으므로 이는 특수한 경우이다(?).

Figure 7. Split operation on a diamond

</TD></TR></TBODY></TABLE>

어떤 노드를 분할하려고 시도할 때 세가지의 경우가 존재한다.

1. 이 노드는 다이아몬드의 일부이다. 　　　- 이 노드와 이 노드의 베이스네이버를 분할한다. 2. 이 노드는 메쉬의 가장자리에 있다. 　　　- 단지 이 노드만 분할하라. 3. 이 노드는 다이아몬드의 일부가 아니다. 　　　- 베이스 네이버를 강제적으로 분할하라.

강제분할은 다이아몬드를 발견하거나 가장자리 트라이앵글을 발견할 때 끝나는 메쉬의 재귀적인 순회(traverse)이다. 여기에 강제분할이 작동하는 방법이 있다. 어떤 노드를 분할할 때 먼저 이 노드가 다이아몬드의 일부인지를 검사하라. 만약 그렇지 않다면 다이아몬드를 생성하기 위해 베이스네이버에 대해 두 번째의 분할함수를 호출하고 그후 원래의 분할을 계속하라.

분할함수에 대한 두 번째 호출도 동일한 검사를 수행하며 필요한 만큼 그 과정을 반복한다. 일단 어떤 노드가 재귀풀기(Recursion Unwinds) 분할이 가능한 것으로 판단되면 그 방향(경로)으로 노드들을 분할하라. < figure 8 >은 이 과정을 보여준다.

</TD></TR>
<TR>
<TD>

Figure 8. Forced split operation

</TD></TR></TBODY></TABLE>

이제 복습해 보자. 높이필드의 특정영역을 커버하고 있는 두 개의 이진 삼각형트리로 구성된 하나의 패치가 주어질 때 우리는 다음의 연산들을 수행할수 있다.

1. 편차트리(Variance Tree)를 계산하라. - 완전 높이 이진트리를 각각의 이진 삼각형트리에 대한 편차데이터로 채우라. 여기에서 편차란 우리의 근사화가 충분히 괜찮은지를 결정하기 위해 사용하는 측정값이다. 삼각형의 빗변의 중점에서의 높이값과 이 빗변의 양 끝점에서 보간된 높이사이의 차이다.

2. 지형을 분할하라. - 편차트리를 이용하여 최상위레벨의 편차가 너무 크다면 차일드를 추가함으로써 우리의 이진 삼각형트리를 분할할 것이다.

3. 강제분할. - 우리가 분할하려고 하는 노드가 다이아몬드의 일부가 아니라면 이 노드에 대해 강제분할 함수를 호출하라. 이는 원래의 분할을 완성하는 다이아몬드를 줄 것이다.

4. 반복 - 이러한 분할과정을 이진 삼각형트리내에 존재하는 모든 삼각형들이 현재 프레임내의 편차한계 이하로 될 때까지 또는 더 이상 분할할 노드가 없을 때까지 차일드 노드들에 대해 반복한다.

Return to Patch Guts.

우리는 ROAM알고리즘에 대한 모든 세부 사항들을 살펴 보았으므로 Patch클래스의 구현을 마무리 짓자. Split함수를 제외한 모든 재귀함수들은 삼각형을 표현하는 좌표값을 취한다. 이러한 좌표값들은 스택상에서 계산되며 다음 단계로 넘겨지거나 렌더링을 위해 오픈지엘에 넘겨진다. 이진 삼각형 트리의 가장 깊은 레벨에서 조차 스택상에는 13개 이내의 삼각형이 존재한다.

이는 다음의 함수들이 사용하는 재귀를 위한 기본적인 알고리즘이다.

int centerX = (leftX + rightX) / 2; 　　 // X coord for Hypotenuse center int centerY = (leftY + rightY) / 2; 　　 // Y coord... Recurs( apexX, apexY, leftX, leftY, centerX, centerY); 　　 // Recurs Left Recurs( rightX, rightY, apexX, apexY, centerX, centerY); 　　 // Recurs Right

Recursive Patch Class Functions.

void Patch :: Split ( TriTreeNode *tri );

unsigned char Patch::RecursComputeVariance( 　　　　　　　 int leftX, int leftY, unsigned char leftZ, 　　　　　　　 int rightX, int rightY, unsigned char rightZ, 　　　　　　　 int apexX, int apexY, unsigned char apexZ, 　　　　　　　 int node);

void Patch::RecursTessellate( TriTreeNode *tri, 　　　　　　　　　　　　　 int leftX, int leftY, 　　　　　　　　　　　　　 int rightX, int rightY, 　　　　　　　　　　　　　 int apexX, int apexY, int node);

void Patch::RecursRender( TriTreeNode *tri, 　　　　　　　　　　　　int leftX, int leftY, 　　　　　　　　　　　　int rightX, int rightY, 　　　　　　　　　　　　int apexX, int apexY );

Split()는 강제분할 동작을 포함하여 모든 ROAM 분할을 수행한다. 이 함수는 적절한 다이아몬드인지를 검사하고 차일드노드를 할당하고 이 노드들을 주변 메쉬에 링크하며 필요한 경우 추가적인 분할함수들을 호출한다.

RecurseComputeVariance()는 현재의 삼각형에 대한 완벽한 좌표집합과 우리가 어디에 있는지를 추적하는 여분의 비트들을 갖고 있다. 트라이앵글의 편차는 계산되고 그 자식들과 결합된다. 높이필드 배열에 대한 메모리검사를 감소시키기 위해 x, y좌표뿐만 아니라 높이값도 넘겨주기로 작정했다.

RecurseTessellate()함수는 LOD동작이 수행되는 곳이다. 카메라에 대한 거리를 계산한 후에 이 함수는 현재노드의 편차를 거리에 대한 계수로 조정한다. 이는 좀더 가까운 쪽의 노드가 더 큰 편차를 갖게 됨을 의미한다.

그 결과적인 메쉬는 카메라에 가깝고 거리가 짧은 경우 더 많은 삼각형들을 사용할 것이다. 거리는 단순성을 위해 평방근(제곱근)을 사용하여 계산한다(이는 느린방법이므로 좀더 빠른 방법으로 대체되어야 한다.).

RecurseRender()함수는 아주 간단하지만 고급 주제란의 트라이앵글 패닝 최적화를 담당하고 있다. 기본적으로 현재 트라이앵글이 리프노드가 아니라면 차일드에 대해 반복한다. 그렇지 않으면(리프노드라면) 하나의 삼각형을 OpenGL에 출력한다. OpenGL렌더링은 최대한의 코드 가독성(코드의 이해)을 위해 최적화되지 않았음을 주의하라. 이제 코드를 이해하기 위해 필요한 모든 것을 다루었다. 나머지는 다음 단계로 넘어가려는 사람들을 위한 것이다. 그러나 먼저 나는 몇 가지의 엔진 평가와 편차 계산에 대한 노트를 제공하겠다.

로그인

단축키

단축키