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

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

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

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

우리가 지형 랜더러로부터 원하는 것이 무엇일까? 빈틈 혹은 T자형의 접합부가 보이지 않는, 곧바로 지평선까지 뻗어있는 단일한 연속적인 메시가 바로 그것이다. 우리는 광범위한 detail level에 걸쳐서 넓은 영역을 보는 것을 원한다 : 배경으로 펼쳐져있는 우리 발앞의 산의 울퉁불퉁함들을 보기를 원하는 것이다. 토론을 위해, 우리는 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를 사용한다면 지형과 시점 거리의 크기를 제한해야 하거나, 아니면 전경 세부의 수준(foreground detail)을 낮춰야 한다.

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

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

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

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

메시 생성은 두 단계로 나뉜다. [1]을 읽은 이후에는, 나는 첫번째 단계를 Update()라고 하고, 두번째 단계를 Render()라고 부른다. Update()가 진행되는 중에는, 우리는 결과물 메시안에 포함될 정점들을 결정할 것이다. 그리고 나서, Render()가 진행되는 중에는 각 정점들을 포함하는 삼각형 메시를 생성할 것이다. 극히 간단한 3 * 3 형태의 높이 필드(그림 2)를 위한 Update()와 Render()를 설명하는 것으로 시작하려한다. Update()를 수행하기 위해서, 우리는 각각의 선택사항으로 주어진 정점(점선으로 되어있다)들을 살펴보고, 그것들을 메시에 추가할 것인지를 결정할 것이다. [1]의 용어를 따라 다시 말하자면, 우리는 정점이 가능한 상태이면, 메시에 그것을 사용할 것이다.

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

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

한번 우리가 어느 정점들이 가능한 상태인지를 알게 되면, 메시를 Render() 처리할 수 있다. 이것은 쉽다 - 우리는 연결점으로써의 중앙 정점과 중앙 주위를 싸고 있는 각 정점들을 시계반대방향 순서로 포함시킴으로써 삼각형 팬(triangle fan)을 생성할 것이다. 예제로서 그림 3을 참조하라.

그림 3. 3 * 3 높이 필드상의 LOD 메시의 예. 검은 점은 가능하지 않은 정점들이다.

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

먼저, 우리는 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.)

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

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

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

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

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.

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.

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.

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.

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:

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

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.

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.

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.

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

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.

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
• 11-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.

[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.

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.

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.

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.

[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öttger, Wolfgang Heidrich, Philipp Slusallek, Hans-Peter Seidel. Real-Time Generation of Continuous Levels of Detail for Height Fields. Technical Report 13/1997, Universität Erlangen-Nürnberg.

[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.