매쉬를 메시로 바꿨습니다. '매'는 오타라고 봤구요.. 쉬를 시로 한 것은.. 비슷한 두 발음 중 더 쉬운 발음을 택한다는 의미로...

그리고 enable-disable에 대해 고민을 좀 더 해봐야겠네요.. -- 2002-09-22 18:15, 류광

흐음... 가능-불가능으로는 약간 부족한.. 마땅한 한글 단어가 없는 부분이군요. 켬-끔 도 좋지 않을까 생각합니다. 아래에서 적으셨던 것 처럼요. ^_^ -- redpixel

켬-끔도 나쁘지 않은데 뭔가 느낌이 오지 않네요... 나중에 일괄적으로 변경할 수 있도록, enable과 disable은 번역하지 않고 그냥 그대로 쓰기로 하죠... --류광

열혈적으로 하고 있지는 않지만 재미있습니다. ^^; 쪼끔씩 하고 갑니다. -- redpixel

엠파스 정보통신용어사전에 보니 "정상-금지"라는 표현을 썼더군요. http://itdic.empas.com/view.tsp/?q=3171&s=l를 참조해보시고 어떨지 의견 부탁드립니다. -- redpixel

재미있으시다니 다행.. 제가 길을 잃은 듯한 느낌이 드는 것이 재미를 못 느껴서일 수도 있겠다는 생각이 듭니다. (시점에 정렬된 지형 메시.. 를 빨리 만들고 싶은 마음 때문일 수도 -.-). 정상 - 금지도 후보로 올려둬야겠네요. 기본적으로는, 영어의 동사를 명사로 만들고 거기에 ~화를 붙이고 다시 ~하다 를 붙이는 식의 번역어 만들기에 좀 식상한 느낌입니다. activate -> activation -> 활성화 -> 활성화하다 -> activate ... 이건 어쩔 수 없는 번역가의 운명일 듯.. --류광

Continuous LOD Terrain Meshing Using Adaptive Quadtrees

적응적인 쿼드트리를 이용한 연속성 LOD 지형 메시 생성

by Thatcher Ulrich

Gamasutra

February 28, 2000

http://www.gamasutra.com/features/20000228/ulrich_01.htm

지형 렌더링은 게임 프로그래밍 세계에서 항상 뜨거운 주제이다. 지금 현재 우리는 지형 렌더링 기술의 발전에서 특별히 흥미로운 지점에 와 있다. 왜냐하면, 처리할 수 있는 다각형 개수가 최신의 게임 엔진들이 상당히 상세한 지형을 그릴 수 있을 정도로 높아 졌기 때문이다(일부는 기존에 발표된 학술 논문들로부터 가져온 실시간 LOD 메시 생성 알고리즘들 덕분이다). 그러나 현재 널리 쓰이고 있는 기법들은 지형 크기와 확대 시 세부도(close-up detail) 사이에서 절충을 해야 하는 수준이다.

내가 현재 제작에 관여하고 있는 게임 Soul Ride (http://www.soulride.com )을 위한 연구&개발의 일환으로, 나는 기존의 알고리즘들을 시험해 봤으며, 결국에는 지형 크기와 확대시 세부도의 절충을 제거하는 확장을 찾아내었다. 이 글에서는 기존 알고리즘들과의 유사성 및 차이점을 통해서 나의 알고리즘을 제시하겠다.

우선 지형 랜더링의 문제점을 되짚어보고, ^[1], ^[2], ^[3]에 의해 해결된 문제들을 설명하겠다.(이 글 끝의 참고문헌을 참조하라.) 그리고나서 나는 내가 제시한 알고리즘에 의해 해결된 추가적인 문제점을 설명할 것이다. 나는 알고리즘의 세부 설명을 제시할 것이며, 그 알고리즘에 관련된 몇 가지 문제점들과 아직 드러나지 않은 잠재성도 이야기하겠다. 그리고 중요한 것을 하나 덧붙이자면, 이 글의 알고리즘을 구현하는 데모의 소스 코드로 제공할 것인데, 그 소스 코드를 이 글을 이해하는 데 사용해도 좋고, 효율성을 평가하거나 원한다면 여러분 자신의 프로젝트에 써먹어도 된다는 점이다.

이 글이 지형 렌더링에 대한 일반적인 튜토리얼이나 개론은 아니다. 이 글이 말하고자 하는 문제에 대해 독자가 어느 정도 익숙하다고 가정하겠다. 만일 잘 이해가 되지 않는다면, 이 글 끝에 나열된 나열된 훌륭한 참고자료들에서 도움을 받기 바란다.

The Problems (문제점들)

우리가 지형 랜더러로부터 원하는 것은 이런 것들이다 : 빈틈 혹은 T자형의 접합부가 보이지 않는, 곧바로 지평선까지 뻗어있는 단일한 연속적인 메시를 만들어 내야 하며, 광범위한 세부 수준에 걸쳐서 광대한 영역을 볼 수 있어야 하며, 우리 발앞의 울퉁불퉁한 세부에서부터 저 멀리 배경의 산 까지를 한 눈에 볼 수 있어야 한다. 토론을 위해, 우리는 1미터에서 100000미터(10의 5승) 이상의 범위를 유효범위로 놓기를 원한다고 정하자.

그걸 어떻게 할 수 있을까? 막무가내(brute-force) 접근방식은 2000년 경의 일반적인 컴퓨터들에는 적합하지 않다. 16 비트 높이 값을 가진 100000m x 100000m 격자를 만들고 그걸 그냥 하나의 메시로 그린다고 하면(그림 1), 두 가지 커다란 문제에 봉착하게 된다. 첫 번째로, 삼각형 문제 - 프레임 당 거의 200 억개의 삼각형들을 렌더링 API에 보내야 한다. 두 번째는 메모리 문제이다. 그러한 높이맵은 20 GB의 용량을 차지한다. 이러한 막무가내식 방법으로 좋은 결과를 얻을 수 있을 정도로 하드웨어가 발전하려면 몇 년은 걸릴 것이다.

그림 1. 높이필드 메시의 막무가내 접근방식.

이러한 삼각형 문제를 성공적으로 해결하는 방법들 몇 가지가 이전에 발표되었었다. 가장 널리 쓰이는 것은 일단의 현명한 재귀적 메시 생성 알고리즘들을 채용한 ^[1], ^[2], ^[3]이다. 이들 중 하나를 사용하면 메시를 효과적으로 다룰 수 있게 된다 - 실시간에서 100 억개의 데이터 중 지능적으로 정점들을 선택함으로서 수 천 개의 사각형들로 끊김없는 지형을 그릴 수 있다.

그러나 높이필드 데이터 집합이 20 GB(거기에 메시 생성 알고리즘을 지원하기 위한 약간의 부담이 추가된다)를 소비한다는 메모리 문제는 여전하다.

이에 대한 한 가지 명백한 해결책은, 높이필드의 크기를 줄여서 세부도를 낮추는 것이다. 오늘날의 컴퓨터에서 1k x 1k는 현실적으로 나쁘지 않은 크기이다. 최근 출시된 TreadMarks라는 게임은 1k x 1k의 데이터 집합으로 훌륭한 효과를 보여준다(이 글 끝의 참고자료를 볼 것 ^[4]). 그러나 1k x 1k와 100k x 100k의 차이는 너무 크다. 1k x 1k를 사용한다면 지형과 시점 거리의 크기를 제한해야 하거나, 아니면 전경 세부의 수준을 낮춰야 한다.

이 글에서 말하고자 하는 해결책은 지형 높이 정보를 표현할 때 규칙적인 격자대신 적응적인 쿼드트리(adaptive quadtree)를 사용하는 것이다. 이 쿼드트리를 이용하면 지형의 서로 다른 영역들에서 높이 정보를 서로 다른 해상도로 표현할 수 있다. 예를 들어서, 자동차 경주 게임이라고 한다면 도로 위와 주변은 좀 더 세부적으로 그리고(이상적으로는 모든 울퉁불퉁한 세부들을 표현하도록), 차를 몰고 갈 수 없는 주변 지형은 덜 자세히 그려야 할 것이다. 그런 주변 지형은 언덕과 계곡의 전반적인 형태만 보여줄 수 있을 정도면 된다.

쿼드트리는 또한 절차적인 세부를 통해서 메모리 문제를 해결할 수 있다. 아이디어는, 성긴 수준에서 지형의 모양을 미리 정의해두고, 관찰자 바로 부근의 영역에 대해 컴퓨터가 실시간적으로 좀 더 세밀한 메시를 만들어 내는 것이다. 쿼드트리의 적응성 때문에, 관찰자가 움직일 때 이러한 세부를 폐기하고 다른 영역 안에서의 절차적 세부를 생성하기 위한 메모리를 확보할 수 있다.

2D 함수의 적응적인 표현을 위해 쿼드트리를 사용하는 법(the use of quadtrees for adaptive representation of 2D functions)^[1]이나 재귀적인 메시 생성을 위헤 쿼드트리를 사용하는 법^[3]은 둘다 (개별적으로) 이미 잘 알려져 있다. 그러나, ^[1]과 ^[3] 모두 높이필드의 표현에 규칙적인 격자를 사용한다. 그런 기법들의 메시 생성 접근방식을 진정한 적응적 쿼드트리로 확장하려면 상당히 많은 복잡한 문제들이 발생하며 다소 변칙적인 프로그래밍이 필요하다. 이 글과 이글에 함께 제공되는 데모 코드도 역시 그렇다.

Meshing (메시 생성)

나의 메시 생성 알고리즘은 ^[1]에 기초하며, 또한 ^[2]와 ^[3]의 영향을 받았다. 핵심 부분을 약간 수정했지만, 기본적인 접근법이 동일하며, ^[1]에서 사용된 용어의 많은 부분을 채용했다.

메시 생성은 두 단계로 나뉜다. ^[1]을 읽은 이후에는, 나는 첫번째 단계를 Update()라고 하고, 두번째 단계를 Render()라고 부른다. Update()가 진행되는 과정에서 결과물 메시안에 포함될 정점들이 결정된다. 그리고 나서, Render()가 진행되는 과정에서는 Update()에서 결정된 정점들을 포함하는 삼각형 메시가 생성된다.

극히 간단한 3 * 3 형태의 높이 필드(그림 2)를 위한 Update()와 Render()를 설명하는 것으로 시작하겠다. 이들에 대한 Update() 과정에서는, 주어진 각 정점(점선으로 되어있다)들을 살펴보고, 그것들을 메시에 추가할 것인지를 결정한다. ^[1]의 용어를 따라 다시 말하자면, 우리는 정점이 enabled 상태일 때에만 그 정점을 메시에 사용한다.(역주 - 다르게 말하면, 메시에는 항상 enabled 정점들만 포함된다).

그림 2. 3 * 3 높이필드. 점선과 그에 딸린 정점들은 LOD 메시안에서는 생성시 선택사항이 될 수 있다. (A 3x3 heightfield. Dashed lines and vertices are optional in an LOD mesh)

그림에서 주어진대로, 중앙과 각 귀퉁이 정점들은 enabled 상태라고 정하자. 그러므로 해야할 일은 뷰 포트와 정점 속성을 고려한 몇몇 LOD 계산법에 따라 4개의 가장자리 정점들의 enabled 여부를 계산하는 것이다.

일단 어떤 정점들이 enable인 지 결정한 후에는, Render()로 메시를 만든다. 메시를 생성하는 것은 간단하다. 중앙의 정점을 중심으로 하며 그 주변의 enabled 정점들을 반시계방향으로 포함하는 삼각형 부채(fan)을 생성하면 된다. 그림 3에 예들이 나와 있다.

그림 3. 3 * 3 높이 필드상의 LOD 메시의 예. 검은 점은 가능하지 않은 정점들이다.Examples of LOD meshes on the 3x3 heightfield. Disabled vertices in black.

To Update() and Render() an adaptive quadtree heightfield, we extend the above process by starting with that same 3x3 square and recursively subdividing it. By subdividing, we can introduce new vertices, and treat them like we treated the vertices of the original square. In order to prevent cracks, however, we'll have to observe some rules.

적응적(adaptive) 쿼드트리 높이필드를 Update()와 Render()처리를 하기 위해서는, 우리는 같은 3 * 3 정사각형 칸으로 시작하고 그것을 재귀적으로 내부 분할함으로써 위 처리방법을 확장해야한다. 분할에 의해서, 우리는 신규 정점들을 끼워넣을 수 있고, 그것들을 원래의 정사각형의 정점들과 마찬가지로 다둘 수 있을 것이다. 어쨌거나, 틈새(crack)을 방지할 목적으로 우리는 몇가지 규칙들을 관찰해야 할 것이다.

First, we can subdivide any combination of the four quadrants. When we subdivide a quadrant, we'll treat the quadrant as a sub-square, and enable its center vertex. For mesh consistency, we will also have to enable the edge vertices of the parent square which are corners of the quadrant (Figure 4). We'll define enabling a square to imply the enabling of its center vertex as well as those corners.

먼저, 우리는 4개의 사분면의 어떤 조합으로써 내부 분할하는 것이 가능하다. 사분면으로 내부 분할한다면, 우리는 내부에 포함된 정사각형으로써 사분면을 다룰 수 있고, 그것의 중앙 정점을 가능한 상태로 지정할 것이다. 메시의 일관성을 위해, 우리는 또한 사분면에 있어서 각 귀퉁이 정점이 되는, 부모 정사각형의 선분 정점들을 가능한 상태로 지정할 필요가 있다. (그림 4)

Figure 4. 정사각형의 북동쪽 사분면을 내부 분할한 결과. 회색 정점들은 이미 이전에 가능한 상태였던 것들이지만, 검은 정점은 분할 시점에서 가능하게 설정되어야만 한다. (Subdividing the NE quadrant of a square. The gray vertices are already known to be enabled, but the black vertices must be enabled when we subdivide.)

Next, notice that an edge vertex in a sub-square is shared with a neighboring sub-square (except at the outside edges of our terrain). So when we enable an edge vertex, we will have to make sure that the neighboring sub-square which shares that vertex is also enabled (Figure 5). Enabling this neighbor square can in turn cause other vertices to be enabled, potentially propagating enabled flags through the quadtree. This propagation is necessary to ensure mesh consistency. See ^[1] for a good description of these dependency rules.

다음으로, 하위사각형 안의 한 변의 정점이 이웃하는 하위사각형(지형 가장자리 바깥의 것을 제외한)과 공유된다는 점에 주목하자. 따라서, 한 변 정점을 가능하게 하려면, 그 정점을 공유하는 이웃하는 하위사각형 역시 가능하게 해야 한다(그림 5). 이 이웃하는 사각형을 가능하게 하면, 그 사각형의 변 정점들도 가능하게 만들어야 하며, 결과적으로 가능화된 플래그들이 쿼드트리를 따라서 전파되어야 할 것이다. 이러한 전파는 메시의 일관성을 보장하는 데 필수적이다. ^[1]에 이러한 의존성 규칙들에 대해 잘 설명되어 있다.

Figure 5. While updating the NE quadrant, we decide to enable the black vertex. Since that vertex is also shared by the SE quadrant (marked in gray), we must enable that quadrant also. Enabling the SE quadrant will in turn force us to enable the gray vertices.

그림 5. 북동쪽 사분면을 갱신할 때, 검은 정점을 가능하게 해야 한다. 그 정점은 남동쪽 사분면(회색)에도 속하므로, 그 사분면도 가능하게 만들어야 한다. 남동 사분면을 가능하게 만들면 회색 정점들도 가능하게 만들어야 한다.

After we're done with the Update(), we can Render() the quadtree. Rendering is actually pretty simple; the complicated consistency stuff was taken care of in Update(). The basic strategy is to recursively Render() any enabled sub-squares, and then render any parts of the square which weren't covered by enabled sub-squares. (Figure 6) shows an example mesh.

Update() 를 마친 후에는(메시 정점들을 결정한 후에는) Render()로 쿼드트리를 렌더링할 수 있다. 렌더링은 상당히 간단하다. 복잡한 의존성 문제는 이미 Update()에서 해결되었기 때문이다. 기본적인 전략은, Render()를 재귀적으로 호출함으로써 가능화된 하위사각형들을 재귀적으로 렌더링하고, 그런 다음 가능화된 하위사각형들에 해당하지 않는 사각형의 나머지 부분을 렌더링하는 것이다. 그림 6의 예제 메시를 보면 이해가 될 것이다.

Figure 6. An example mesh. Enabled vertices are marked in black. The gray triangles are drawn by recursive calls to Render() on the associated sub-squares. The white triangle are drawn by the original call to Render().

그림 6. 예제 메시. 검은색 정점은 가능화된 정점. 회색 삼각형들은 해당 하위사각형들에 대한 Render()의 재귀적 호출을 통해서 그려진다. 흰 삼각형은 Render()의 원래의 호출에 의해 그려진다.

Evaluating vertices and squares 정점과 사각형의 평가

In the above description, I glossed over the part about deciding whether a vertex should be enabled. There are a few different ways to do this. All of them take into account what I'll call the "vertex interpolation error", or vertex error for short. What this is, is the difference in height between the correct location of a vertex, and the height of the edge in the triangle which approximates the vertex when the vertex is disabled (Figure 7). Vertices which have a large error should be enabled in preference to vertices which have a small error. The other key variable that goes into the vertex enable test is the distance of the vertex from the viewpoint. Intuitively, given two vertices with the same error, we should enable the closer one before we enable the more distant one.

위의 설명에서는 어떤 정점을 enable 시킬 것일 지 결정하는 부분을 자세히 이야기하지 않았다. 그러한 결정에 사용할 수 있는 방법들이 몇가지 있는데, 공통적으로 필자가 "정점 보간 오차" (또는 간단히 줄여서 "정점 오차")라고 하는 문제에 직면한다. 여기서 말하는 정점 오차란, 한 정점의 정확한 위치와 그 정점이 disable 되었을 때 그 정점과 근사(近似)하는 삼각형의 변 사이의 높이 차이를 말한다(그림 7). 오차가 작은 정점들보다 오차가 큰 정점들을 우선적으로 enable시켜야 한다. 정점의 enable 여부를 결정할 때 고려할 또 다른 핵심적인 요인은 시점과 정점 사이의 거리이다. 직관적으로 볼 때, 두 정점의 오차가 동일하다고 하다면 먼 것보다는 가까운 것을 먼저 enable 시켜주어야 한다.

Figure 7. Vertex interpolation error. When a vertex is enabled or disabled, the mesh changes shape. The maximum change occurs at the enabled vertex's position, shown by the dashed line. The magnitude of the change is the difference between the true height of the vertex (black) and the height of the original edge below the vertex (white). The white point is just the average of the two gray points.

그림 7. 정점 보간 오차. 정점이 enable/disable될 때, 메시의 모양이 변경 된다. 가장 큰 변경은 enable된 정점의 위치에서 발생하며, 이 것은 위 그림에서 점선으로 표시되어있다. 변경의 규모는 정점(검은 색)의 실제 높이와 정점 아래의 원래 선분의 높이(하얀 색)간의 차이이다. 하얀 색 정점의 높이는 단지 양쪽 두 회색 정점 높이의 평균이다.

There are other factors that can be included as well. ^[1] for instance takes into account the direction from the viewpoint to the vertex. The justification is based on the idea of screen-space geometric error; intuitively the vertex errors are less visible when the view direction is more vertical. ^[1] goes through the math in detail.

그 외에도 다른 요인들이 있다. 예를 들어서 ^[1]은 시점에서 정점으로의 방향을 고려한다. 이는 화면 공간의 기하학적 오차를 보정하기 위한 것이다. 당연한 이야기겠지만 정점 오차들은 시선 방향이 좀 더 수직일 수록 덜 나타난다. 이에 관한 세부적인 수학적 처리는 ^[1]에 잘 나와 있다.

However, I don't think screen-space geometric error is a particularly good metric, for two reasons. One, it ignores texture perspective and depth buffering errors -- even if a vertex does not move in screen space because the motion is directly towards or away from the viewpoint, the vertex's view-space z value does affect perspective-correction as well as depth-buffering. Two, the viewpoint-straight-down case is both an easy case for terrain LOD algorithms, and not a typical case.

그러나 필자는 화면 공간 기하 오차가 실질적으로 좋은 수치라고는 생각하지 않는데, 이유는 두 가지이다. 첫 번째로, 그런 오차에 대한 보정은 텍스처 원근 및 깊이 버퍼링 오차들을 무시한다. 움직임이 시점을 향해 직접 가까와지거나 시점으로부터 직접 멀어지기 때문에 정점이 변하지 않는 경우에도, 정점의 시야 공간 z 값은 원근 보정 및 깊이 버퍼링에 영향을 받는다는 점을 생각하기 바란다. 두 번째로, 시점으로 직접 내려가는 경우는 지형 LOD 알고리즘들에서 쉽게 해결할 수 있을 뿐만 아니라 그리 흔한 경우도 아니다.

In my opinion, there's no point in optimizing for an atypical easy case in an interactive system. The performance of the more typical and difficult case, when the view axis is more horizontal and much more terrain is visible, will determine the minimum system frame-rate and hence the effectiveness of the algorithm.

필자의 견해로는 상호작용적인 시스템에서 전형적이지 않고 손쉬운 경우를 위한 최적화는 그리 쓸모가 없다. 좀 더 전형적이고 어려운 경우(시야 축이 좀 더 수평이고 훨씬 많은 지형이 보이는 경우)의 성능이 최소의 시스템 프레임율을, 따라서 알고리즘의 효율성까지 결정하게 된다.

Instead of screen-space geometric error, I advocate doing a similar test which results in 3D view-space error proportional to view distance. It's really very similar to the screen-space-error test, but without the issues I mention above. It involves only three quantities: an approximation of the viewpoint-vertex distance called the L1-norm, the vertex error, and a detail threshold constant. Here it is:

화면 공간 기하 오차 대신에, 필자는 뷰(view)와의 거리에 비례하는 3D 뷰 공간 오차를 산출하는 유사 테스트를 하는 것을 주장해본다. 이것은 화면 공간 오차 테스트와 정말로 상당히 유사하지만, 위에서 언급한 논점들과는 전혀 상관없는 것이다. 이 테스트는 세가지 값들(L1-norm 이라고 불리는 시점-정점간 거리의 근사치, 정점 오차, 그리고 세부 오차범위 상수)을 수반하여 실행된다. 다음을 보자.

L1 = max(abs(vertx - viewx), abs(verty - viewy), abs(vertz - viewz));
enabled = error * Threshold

You probably recognize the L1-norm, even if you didn't know it had a fancy name. In practice, using the L1-norm instead of the true viewpoint distance will result in slightly more subdivision along the diagonals of the horizontal terrain plane. I've never been able to detect this effect by eye, so I don't worry much about it. ^[4] and others use view-space -z rather than the L1-norm, which is theoretically even more appropriate than true viewpoint distance. Nevertheless, the L1-norm works like a champ for me, and ^[3] uses it too.

L1-norm이라는 용어를 들어보지 못했어도, L1-norm이 어떤 것인지는 분간할 수 있을 것이다. 실제에서, 진짜 시점 거리 대신 L1-norm를 사용하면 수평 지형 평면의 대각선을 따라 약간 더 많은 하위분할이 생기게 된다. 그러나 그런 효과를 눈으로 식별할 수 있었던 적은 없었기 때문에, 별로 신경쓰지 않아도 된다. ^[4]나 기타 다른 방법든은 L1-norm 대신 시점 공간 -z을 사용하는데, 이론적으로는 그렇게 하는 것이 진짜 시점 거리보다도 적합하다. 그렇긴 해도 필자의 경우는 L1-norm이 잘 작동했으며, ^[3]도 L1-norm을 사용한다.

You can treat the Threshold quantity as an adjust-for-best-results slider, but it does have an intuitive geometric interpretation. Roughly, it means: for a given view distance z, the worst vertex error I'll tolerate is z / Threshold. You could do some view-angle computations and relate Threshold to maximum pixel error, but I've personally never gone past the adjust-for-best-results stage.

위에 나온 Threshold는 가장 좋은 결과가 나올 때까지 그냥 이리 저리 조정해 볼만한 수치로 취급해도 되나, 기하학적으로 이해하는 것도 어렵지 않다. 대충 말해서, 시점 거리 z가 주어 졌을 때, 허용할 수 있는 최대의 정점 오차가 바로 z / Threshold이다. 적당한 시점-각도 계산을 수행하고 Threshold를 최대 픽셀 오차에 연관시키는 것도 가능하나, 개인적으로는 그냥 가장 좋은 결과가 나올 때까지 이리 저리 조정하는 방법으로도 충분하다고 본다.

So that covers the vertex enabled test. But if you were paying attention earlier, you may also have noticed that I glossed over another point, perhaps more important: during Update(), how do we know whether to subdivide a quadrant or not??The answer is to do what I call a "box test". The box test asks the question: given an axis-aligned 3D box enclosing a portion of terrain (i.e. a quadtree square), and the maximum vertex error contained within that box, and no other information about what's inside the box, is it possible that the vertex enable test would return true??If so, then we should subdivide the box. If not, then there's no reason to subdivide.

이렇게 해서 정점의 enabled 여부를 판정하는 부분을 이야기했다. 그런데 앞의 글을 잘 읽어보면, Update() 도중에 하나의 사분면을 분할할 것인지 말것인지 판단하는 방법을 자세히 이야기하지 않았다는 점이 마음에 걸릴 것이다. 이 부분은 필자가 "상자 판정(box test)"라고 부르는 방법으로 판단한다. 상자 판정이 판정하는 것은 다음과 같다: 지형의 한 부분(즉 하나의 쿼드트리 사각형)을 감싸는 축에 정렬된 3D 상자 하나와, 그 상자에 담긴 최대 정점 오차가 주어졌들 때(상자 안에 무엇이 들어 있는 지에 대한 정보는 주어지지 않는다), 정점 enable 판정이 참을 돌려주는 것이 가능한가? 가능하다면 상자를 더 분할해야 하고, 그렇지 않다면 더 이상 분할할 이유가 없다.

The beauty of it is, by doing the box test, we can potentially trim out thousands of vertices from consideration in one fell swoop. It makes Update() completely scalable: its cost is not related to the size of the full dataset, only to the size of the actual data that's included in the current LOD mesh. And as a side benefit, the precomputed vertical box extent can be used during Render() for frustum culling.

The box test is conservative, in that a square's max-error could be for a vertex on the opposite side of the box from the viewpoint, and thus the vertex test itself would/will fail for that actual vertex, whereas the box test might succeed. But once we subdivide, e'll go ahead and do four more, more accurate box tests on the sub-squares, and the penalty for conservatism is fairly small: a few extra vertex and box tests, and a couple extra vertices in the mesh.

Fortunately, given the above simple vertex test, a suitable box test is easy to formulate:

bc[x,y,z] == coordinates of box center

ex[x,y,z] == extent of box from the center (i.e. 1/2 the box dimensions)

L1 = max(abs(bcx - viewx) - exx, abs(bcy - viewy) - exy, abs(bcz - viewz) - exz)

enabled = maxerror * Threshold < L1

Details

That covers the essentials of the algorithm. What's left is a mass of details, some of them crucial. First of all, where is the height data actually stored??In all of the previously-published algorithms, there is a regular grid of height values (and other bookkeeping data), on top of which the mesh is implicitly ^[1] & ^[3] or explicitly ^[3] defined. The key innovation of my algorithm is that the data is actually stored in an adaptive quadtree. This results in two major benefits. First, storage can be allocated adaptively according to the actual dataset or the needs of the application; e.g. less storage can be used in smoother areas or areas where the viewpoint is not expected to travel. Second, the tree can grow or shrink dynamically according to where the viewpoint is; procedural detail can be added to the region near the viewpoint on-the-fly, and deleted when the viewpoint moves on.

In order to store heightfield information in a quadtree, each quadtree square must contain height values for at least its center vertex and two of its edge vertices. All of the other vertex heights are contained in other nearby nodes in the tree. The heights of the corner vertices, for instance, come from the parent quadtree square. The remaining edge vertex heights are stored in neighboring squares. In my current implementation, I actually store the center height and all four edge heights in the quadtree square structure. This simplifies things because all the necessary data to process a square is readily available within the square or as function parameters. The upshot is that the height of each edge vertex is actually stored twice in the quadtree.

Also, in my current implementation, the same quadtree used for heightfield storage is also used for meshing. It should be possible to use two separate heightfields, one for heightfield storage and one for meshing. The potential benefits of such an approach are discussed later.

A lot of the tricky implementation details center around the shared edge vertices between two adjacent squares. For instance, which square is responsible for doing the vertex-enabled test on a given edge vertex??My answer is to arbitrarily say that a square only tests its east and south edge vertices. A square relies on its neighbors to the north and to the west to test the corresponding edge vertices.

Another interesting question is, do we need to clear all enabled flags in the tree at the beginning of Update(), or can we proceed directly from the state left over from the previous frame??My answer is, work from the previous state (like ^[2], but unlike ^[1] and ^[4]). Which leads to more details: we've already covered the conditions that allow us to enable a vertex or a square, but how do we know when we can disable a vertex or a square??Remember from the original Update() explanation, the enabling of a vertex can cause dependent vertices to also be enabled, rippling changes through the tree. We can't just disable a vertex in the middle of one of these dependency chains, if the vertex depends on enabled vertices. Otherwise we'd either get cracks in the mesh, or important enabled vertices would not get rendered.

If you take a look at Figure 8, you'll notice that any given edge vertex has four adjacent sub-squares that use the vertex as a corner. If any vertex in any of those sub-squares is enabled, then the edge vertex must be enabled. Because the square itself will be enabled whenever a vertex within it is enabled, one approach would be to just check all the adjacent sub-squares of an edge vertex before disabling it. However, in my implementation, that would be costly, since finding those adjacent sub-squares involves traversing around the tree. Instead, I maintain a reference count for each edge vertex. The reference count records the number of adjacent sub-squares, from 0 to 4, which are enabled. That means that every time a square is enabled or disabled, the reference counts of its two adjacent edge vertices must be updated. Fortunately, the value is always in the range [0,4], so we can easily squeeze a reference count into three bits.

Figure 8. Each edge vertex has four adjacent sub-squares which use it as a corner. If any of those squares are enabled, then the edge vertex must be enabled. For example, the black vertex must be enabled if any of the four gray squares are enabled.

Thus the disable test for an edge vertex becomes straightforward: if the vertex is currently enabled, and the associated reference count is zero, and the vertex test with the current viewpoint returns false, then disable the edge vertex. Otherwise leave it alone. The conditions for disabling a square are fairly straightforward: if the square is currently enabled, and it's not the root of the tree, and none of its edge vertices are enabled, and none of its sub-squares are enabled, and the square fails the box test for the current viewpoint, then disable it.

Memory

A very important issue with this (or any) LOD method is memory consumption. In a fully populated quadtree, a single quadtree square is equivalent to about three vertices of an ordinary heightfield, so it is imperative to keep the square data-structure as compact as possible. Fortunately, the needs of the Update() and Render() algorithms do not require each square to contain all the information about 9 vertices. Instead, this is the laundry list of required data:

• 5 vertex heights (center, and edges verts east, north, west, south)
• 6 error values (edge verts east and south, and the 4 child squares)
• 2 sub-square-enabled reference counts (for east and south verts)
• 8 1-bit enabled flags (for each edge vertex and each child square)
• 4 child-square pointers
• 2 height values for min/max vertical extent
• 1 1-bit 'static' flag, to mark nodes that can't be deleted

Depending on the needs of the application, the height values can usually be squeezed comfortably into 8 or 16 bits. The error values can use the same precision, or you can also do some non-linear mapping voodoo to squeeze them into smaller data sizes. The reference counts can fit into one byte along with the static flag. The enabled flags fit in one byte. The size of the child-square pointers depends on the maximum number of nodes you anticipate. I typically see node counts in the hundreds of thousands, so I would say 20 bits each as a minimum. The min/max vertical values can be squeezed in various ways if desired, but 8 bits each seems like a reasonable minimum. All told, this amounts to at least 191 bits (24 bytes) per square assuming 8-bit height values. 16-bit height values bring the total to at least 29 bytes. A 32-byte sizeof(square) seems like a good target for a thrifty implementation. 36 bytes is what I currently live with in Soul Ride, because I haven't gotten around to trying to bit-pack the child pointers. Another byte-saving trick I use in Soul Ride is to use a fixed-pool allocator replacement for quadquare::new() and delete(). You can eliminate whatever overhead the C++ library imposes (at least 4 bytes I would expect) in favor of a single allocated bit per square.

There are various compression schemes and tricks that could be used to squeeze the data even smaller, at the expense of complexity and performance degradation. In any case, 36 bytes per 3 vertices is not entirely unrespectable. That's 12 bytes/vertex. ^[1] reports implementations as small as 6 bytes per vertex. ^[2] only requires storage of vertex heights and "wedgie thicknesses", so the base data could be quite tiny by comparison. ^[4], using a modified ^[2], reports the storage of wedgie thicknesses at a fraction of the resolution of the height mesh, giving further savings.

However, such comparisons are put in a different light when you consider that the quadtree data structure is completely adaptive: in very smooth areas or areas where the viewer won't ever go near, you need only store sparse data. At the same time, in areas of high importance to the game, you can include very detailed features; for example the roadway in a driving game can have shapely speed bumps and potholes.

Geomorphs

- ^[2] and ^[3] go into some detail on "vertex morphing", or "geomorphs". Basically, geomorphing is a technique whereby when vertices are enabled, they smoothly animate from their interpolated position to their correct position. It looks great and eliminates unsightly popping; see McNally's TreadMarks for a nice example.

Unfortunately, doing geomorphs requires storing yet another height value for the vertices that must morph, which would present a real data-size problem for the adaptive quadtree algorithm as I've implemented it. It could result in adding several bytes per square to the storage requirements, which should not be done lightly. ^[3] incurs the same per-vertex storage penalty, but ^[2] avoids it because it only has to store the extra height values for vertices that are actually in the current mesh, not for every vertex in the dataset.

I have three suggestions for how to address the geomorph issue. The first alternative is to spend the extra memory. The second alternative is to optimize the implementation, so that really small error tolerances would be practical and geomorphs unnecessary. Moore's Law may take care of this fairly soon without any additional software work. The third alternative is to split the quadtree into two trees, a "storage tree" and a "mesh tree". The storage tree would hold all the heightfield information and precomputed errors, but none of the transitory rendering data like enabled flags, reference counts, geomorph heights, etc. The mesh tree would hold all that stuff, along with links into the storage tree to facilitate expanding the mesh tree and accessing the height data. The mesh tree could be relatively laissez-faire about memory consumption, because its size would only be proportional to the amount of currently-rendered detail. Whereas the storage tree, because it would be static, could trim some fat by eliminating most of the child links.

The storage-tree/mesh-tree split could also, in addition to reducing total storage, increase data locality and improve the algorithm's cache usage.

Working Code

The Soul Rider engine is closed source for the forseeable future, but I did re-implement the essentials of this algorithm as a companion demo for this article. The demo source is freely available for you to examine, experiment with, and modify and incorporate into your own commercial or non-commercial projects. I only ask that if you do incorporate the demo source into a project, please acknowledge me in the credits!

I didn't sweat the data-packing issue in the demo code. That would be a good area to experiment with. Also, I didn't implement frustum culling of squares, but all the necessary data is readily available.

The data included with the demo comes from USGS 7.5-minute DEMs of the Grand Canyon (USGS). At Slingshot we have a proprietary tool that crunches the USGS data and stitches neighboring DEMs together; I collected 36 datasets and resampled them at a lower resolution to make the heightfield. I made the texture in a few minutes in Photoshop, by loading an 8-bits per sample version of the heightfield as raw data, running the Emboss filter on it to create shading, and adding some noise and tinting. The texture is just one big 1024x1024 image, stretched over the entire terrain.

The data-loading code should be fairly self explanatory, so if you have some of your own data you want to try, it should be easy to get it in there.

The program uses OpenGL and GLUT for 3D, window setup, and input. I developed it under Win98 using a TNT2 card, but I tried to avoid Windows-isms so it should be easy to port to other systems that support GLUT.

Exercises for the Reader

In addition to the tighter data packing I mentioned, there are a few other things in the Soul Ride engine which aren't in the article demo. The big one is a unique-full-surface texturing system, the details of which are beyond the scope of this article. But I will mention that good multi-resolution texturing, especially containing lighting, is extremely beneficial for exploiting the unique features of the quadtree terrain algorithm.

One thing I haven't yet experimented with, but looking at the demo code would be fairly easy to hack in, is on-demand procedural detail. In my view, on-demand procedural detail looms large in the future of computer graphics. There just doesn't seem to be any other good way to store and model virtual worlds to the detail and extent where they really have the visual richness of the real world. Fortunately, the problem is completely tractable, if complicated. I think this quadtree algorithm, because of its scalability, can be helpful to other programmers working on on-demand procedural detail.

Yet another cool extension would be demand-paging of tree subsections. It actually doesn't seem too difficult; basically you'd flag certain quadsquares at any desired spot in the hierarchy as being "special"; they'd contain links to a whole giant sub-tree stored on disk, with the max-error for the sub-tree precomputed and stored in the regular tree. Whenever Update() would try to enable a "special" square, it would actually go off and load the sub-tree and link it in before continuing. Getting it to all stream in in the background without hitching would be a little interesting, but I I think doable. It would result in basically an infinite paging framework. On-demand procedural detail could exploit the same basic idea; instead of chugging the disk drive to get pre-made data, you'd run a terrain-generation algorithm to make the data on the fly.

And another suggestion for further work would be to identifying and eliminating performance bottlenecks. I suspect that there's some headroom in the code for making better use of the graphics API interface.

Acknowledgements

In addition to the authors of the papers (listed below under References) which this work is based on, I would also like to send shout-outs to Jonathan Blow, Seumas ?McNally and Ben Discoe for their various thought-provoking emails and comments, and also to the participants in the algorithms@3dgamedev.com mailing list, where I've learned a lot of extremely interesting stuff from other programmers about different approaches and the ins-and-outs of terrain rendering.

References

[1] Peter Lindstrom, David Koller, William Ribarsky, Larry F. Hodges, Nick Faust and Gregory A. Turner. "Real-Time, Continuous Level of Detail Rendering of Height Fields". In SIGGRAPH 96 Conference Proceedings, pp. 109-118, Aug 1996.

[2] Mark Duchaineau, Murray Wolinski, David E. Sigeti, Mark C. Miller, Charles Aldrich and Mark B. Mineev-Weinstein. "ROAMing Terrain: Real-time, Optimally Adapting Meshes."?Proceedings of the Conference on Visualization '97, pp. 81-88, Oct 1997.

[3] Stefan R?tger, Wolfgang Heidrich, Philipp Slusallek, Hans-Peter Seidel. Real-Time Generation of Continuous Levels of Detail for Height Fields. Technical Report 13/1997, Universit? Erlangen-N?nberg.

[4] Seumas ?McNally. http://www.LongbowDigitalArts.com/seumas/progbintri.html . This is a good practical introduction to Binary Triangle Trees from ^[2]. Also see http://www.treadmarks.com , a game which uses methods from ^[2].

[5] Ben Discoe, http://www.vterrain.org . This web site is an excellent survey of algorithms, implementations, tools and techniques related to terrain rendering.

Thatcher Ulrich is the lead programmer for Slingshot Game Technology www.sshot.com, which is working hard to make a snowboarding game that doesn't suck. You can gaze at Thatcher's vacation photos at www.tulrich.com, or email him at tu@tulrich.com.