Theory & Practice - Issue 05 - Landscapes by (05 July 2000) Return to The Archives
 Introduction
 I'd like to thank you guys for your responses to my Intermediate Issue 4.5. Among other things, I've received quite a few emails from readers who were enthuastic about my writing an issue on landscape engines. I have had to pause my writing this column due to being very busy with a host of other things. But in the meantime I have thought about the topic and what I want to present. Landscapes are a big topic to cover, and I will spend at least 2 issues on it.Why are landscapes all the rage with some people? Well, I suppose, for different reasons. First, if done right they can look really nice. Second, generating landscape data, either through an editor or by other means, is easier than for other types of environments, such as indoors. So pretty much, once you have an engine you can go and quickly make tests for it. Once your engine reaches an advanced state, you can make good looking demo maps to show to everyone :-)

 In General
 Landscape is of a nature quite different from other types of things, such as the insides of buildings. If we assume some things about the nature of a landscape we can come up with good ways of modeling it, which are both efficient and versatile. Generally, we store a landscape using one or more heightmaps. A heightmap records the height of the landscape at evenly spaced points, so you get a 2-dimensional grid filled with height values. For a landscape that has only one height at any point, one heightmap is all we really need to store. This is a small restriction, because you can make a lot of great-looking landscapes that don't have parts hanging over other parts. In fact, most landscapes don't have that.

 Interpreting The Data
 So you are representing the landscape with a heightmap. The heightmap is, of course, of finite size. That means you will not be storing the height of every point on the landscape, but instead the heights of evenly spaced points. To have a continuous surface for the landscape, we will have to have some sort of transitions between these points.Static height - This method basically just takes the height specified at a grid point and uses it as the height for the whole heightmap cell that point represents. It connects heights by using vertical bars. So it looks like a staircase or some kind of bar graph. Not very realistic.Linear interpolation - With this method, you interpolate the height linearly between the points. It is as if you had a quad for each cell in the grid whose vertices were the four points around the cell. There is a big chance that the quad won't be planar, so instead of having a quad you split it into two triangles. The results are a bit different depending on how you split it, but you should split every quad from the map the same way. That way you can generate triangle strips and other nice stuff (more on that later).Curved surfaces - These can come in handy when you to have smooth transitions. Remember that with curved surfaces you can vary the level of detail, so you can tesselate a lot up close and less as you get further, until you switch to linear interpolation. I will discuss this in more detail later, but generally this addition is slower but more flexible. In general we can call curved surfaces here interpolation of higher than linear order.

 Bringing Out The Details
Now, if you had just implemented a simple algorithm that would read a heightmap, connect the points using triangles (linear interpolation), and send these triangles to the rasterizer, you'd already have a simple engine that could draw basic landscape. The heightmap points would be spaced evenly in squares, and the resulting top view of your landscape would look something like:

This is already pretty good for a basic landscape. But we're just getting started. Here is our first problem: when you render this landscape up close you will see that it seems a bit jerky and lacks realistic detail. If you want more detail in the landscape you'll have to place the heightmap's points closer together. But then you will have a lot more triangles to render overall, because you'd be increasing the detail on the entire map! (Perhaps one day we will have computers so fast we won't care about this, but as I write, we don't.)

Instead, we want to have a system where the landscape would be rendered with more detail up close, but further away it should have less and less detail. One way to do it is have mipmapped heightmaps -- several versions of the same heightmap, with different detail. But that usually isn't a good solution because it still doesn't give you a big enough LOD range, and takes up a lot of space in memory.

Rather, what we want can be done using progressive mesh techniques. For a progressive map, you would have a basic map with a constant level of detail, but also store information for various sections of the map which will increase the detail according to a detail level specified. Then when time comes to render, you try render the close-up polygons with a high level of detail. This will attempt use the information for increasing detail that is contained in the map for that section. If there is enough information to match the LOD chosen, that amount of detail will beused. Otherwise the closest amount of detail to the chosen LOD will be used. As you go further away you lower the LOD requirement until it drops to the default detail.

In short, you have information on how to increase details in sections of the map given a certain detail level, and when you're moving around the map with a camera you specify high detail levels close to the camera and lower levels further away. Now, we will explore how that information is stored. There are various algorithms for storing progressive landscape maps, such as the quadtree. However, you've probably noticed that I like to write about things from a different point of view, or present new techniques. Why duplicate something which has already been written? If you want information on standard quadtree techniques you can check out the links section at the end.

So, in this case, we'll develop our own method of storing and using progressive heightmaps. We'll have our basic heightmap, split up into triangles as usual, but some triangles might contain further detail. This detail is achieved using the structure Face. Imagine a Face to be a triangle facing outward from the landscape. This Face might be split into 3 faces, by introducing an extra vertex.

We can define our structure like this:

 ```struct Face { Face *Details; Vertex *Tip; }; ```

Let's take a look at what this means. Details is a pointer to an array of 3 faces into which the face can split. If it is NULL, then no more detail can be achieved. (Notice the recursion -- struct Face contains a member of type Face*... we use recursion to implement progressive meshes because we split faces recursively). Tip is the vertex that's used to split the face into 3. It's the tip of the pyramid that results.

Let's forget about the landscape for a moment and focus on how we're going to implement drawing in this progressive detail scheme. Suppose we had a triangle (3 vertices) and a Face pointer. If we were to write a function that took face, a level of detail and sent primitives to the rasterizer, it would look something like:

 ```Vertex *V[3]; // global (unfortunately), for efficiency/simplicity /* Recursive Drawing Routine for faces */ int Face::Draw(int LOD) { Vertex *temp; // Assume here that V[0],V[1],V[2] have been set // according to vertices 0,1,2of the face's triangle, // respectively. We'll see why in a minute... if (LOD < 0) return -1; if (!Tip || LOD == 0) { DrawTriangle(V[0], V[1], V[2]); return 0; // no errors } else if (LOD == 1 || !Details) { DrawFan(Tip, V[0], V[1], V[2]); return 0; // no errors } else { temp = V[2]; V[2] = Tip; Details[0].Draw(LOD-1); // Vertices 0,1,Tip V[2] = temp; temp = V[0]; V[0] = Tip; Details[1].Draw(LOD-1); // Vertices 1,2,Tip V[0] = temp; temp = V[1]; V[1] = Tip; Details[2].Draw(LOD-1); // Vertices 2,0,Tip V[1] = temp; return 0; // no errors } } ```

Since we have a triangle (3 vertices) and a face pointer corresponding to that triangle, we would draw the thing as follows. First we'd fill the V array with the vertices from the polygon, then call the Draw function of the face with the LOD we wanted. When it returns, the face would have been drawn with that level of detail, or as much detail as could have been mustered to match. DrawFan and DrawTriangle are functions that do the actual drawing. Functions like that can be found in APIs like OpenGL or DirectX.

Using this method, we can draw our landscape, adjusting the level of detail depending on distance. For the triangles which are up close we would call Face::Draw with a high LOD. As we move further away we will call it with smaller and smaller LOD, until the LOD drops to 0. When the LOD is 0, we could continue calling Face::Draw(0), but that would draw each triangle individually. Since now the level of detail is minimal we can just send the triangle strips instead!

Notice how in the basic heightmap the squares are split into triangles in such a way as to allow triangle strips to be formed easily. Thus they can be sent to the rasterizer all at once. So far away you can draw a lot of terrain quickly, but take your time up close, where you're not drawing polygon strips, but instead filling in the detail.

 Storing Progressive Maps
Okay, back to our landscape. Now that we know how to draw our progressive meshes, we should also figure out how to store them. We already know that the basic heightmap is stored as a 2D array (grid) of heights. Each square from that grid is divided into 2 triangles. Each triangle can potentially have a Face structure attached to it. But usually not all will. In fact, most probably won't.

Say you're making a game where you drive along a road in the countryside. Here you can restrict where the camera will be (or at least assume where it will usually be). In this case it's in the vicinity of the road. So, you can store nice detail on the road and around it (rocks, crevices, rough hills, landslides, etc.), but for the rest of the map you will simply have the default detail that the heightmap allows. In this case, a small part of your map will have details. If, instead, you're making a game where you can go anywhere and do anything, you still probably won't want to make every section of the map very detailed. A large percentage of the map will have default detail.

In this case, it is wasteful to have, along with the NxN heightmap, a 2NxN array of Face pointers. If most of the map has default detail, most of the entries in the Face pointer array will be NULL. So we might try and come up with a more space-saving scheme for storing Face pointers for appropriate triangles.

One such scheme is as follows. You have your heightmap as a 1-dimensional array. The [x][y] are turned into [x+y*width].

 `float *Heights; `

Then you also have an array (1-dimensional) of Faces, sorted in the order that their pointers would have been sorted in the 2NxN array. But in this array you don't have all 2N2 elements, since large portions of the map are not detailed. Instead, it is as if you were storing the Faces in order they would otherwise be stored, but skipping some as you go.

 ```Face *Faces; long FaceCount; ```

Now comes the interesting part. You also store a sorted array of integers, with the same number of elements as the Faces array. Element number X of the array holds the index of the triangle in the Heights array that associates with element number X of the faces array.

 `long *Triangles; `

What we've actually done here is this: instead of using the array of triangles and storing an array of corresponding pointers to Faces, we've got an array of Faces and storing an array of corresponding pointers to triangles. Now, how do we take advantage of this as we're drawing? Well, as we draw a particular triangle we find whether or not it has a corresponding Face by searching the Triangles array for the index of the triangle we're processing. This might seem computationally more expensive, but it's really very bad: since the Triangles array is sorted, we can use a binary search, which will produce its results in at most (log2n)+1 steps. So for 1,000,000 elements you'll need 20 steps.

Moreover, if you're processing the triangles sequentially (as you probably will when you're drawing the heightmap), you could have interesting optimizations. Say you start processing triangles from the beginning. You can check the Triangles array for the value of the first element, x1=Triangles[0]. Now you know there are no detailed triangles up to that x1. So you can just draw a triangle strip up to triangle x1 and save time. Then once you reach that triangle, you find the value of the next element of the Triangles array, x2 = Triangles[1]. Draw the triangle with the appropriate LOD (by calling Face::Draw) and then draw another triangle strip for all the triangles between x1 and x2... and so on, until your LOD drops to 0, in which case you don't have to consult the Faces array anymore for that frame, just draw triangle strips for the rest of the triangles in the scene.

 Generating Landscape
The progressive maps we've seen so far have all had their detail stored beforehand. The basic heightmap and detail could have been generated by artists with a lot of time on their hands, or by an external computer program, but in any case it would have to be stored in its entirety somewhere -- either in RAM, or on a HD, etc.

Alternatively, instead of storing information for a progressive mesh, you can generate one programmatically. In this case you can have very large maps, and in most cases increase level of detail indefinitely, but the results aren't totally specified by you. Rather, they are obtained by some algorithm.

There are many algorithms that do this sort of thing. Most that produce realistic looking landscapes are fractal-based. They make big changes on a large scale, and then make smaller and smaller details. This reflects what usually happens in nature -- as the scale gets smaller, so does the severity of the changes.

Some algorithms want you to provide them with a series of parameters affecting how they will generate the landscape. Perhaps some random seeds, a few basis coefficients, and that's it. Some algorithms are more interactive, and give you this in addition to letting you specify your own "rough" heightmap, so you can have control over where approximately you want valleys, moutaineous regions, plains, craters, etc. Below, I'll talk about an algorithm of the latter kind.

That's the rather fancy name I give to a method that basically combines curved surfaces with deformation of the landscape. As you tesselate further and further, the deformation becomes less and less. Here is a description of the algorithm with more detail:

From the heightmap points, I can generate biquadratic Bezier patches. Biquadratics are quicker to tesselate than bicubics, and also require less control points. However, I personally don't use Bezier patches, but rather the curved triangles I described in previous tutorials. This is because of being able to switch LOD easily as I described in those tutorials. If an edge of a triangle doesn't have enough subdivisions, you can split the triangle (with n subdivisions on each side) along that edge into two triangles (each with n subdivisions on each side), and as a result that one edge will have twice as many subdivisions as before. With rectangular patches you cannot do this, because you can't split a rectangle (with n subdivisions on each side) into other rectangles (each with n subdivisions on each side) and only increase the number of subdivisions along one edge of it.

So, anyway, you have your bi-quadratic patches, whether they be quadrangular or triangular. These were obtained from a pretty sparse heightmap -- the points might have been located 200 "meters" away from each other. If you just draw these patches as they are, you will get smooth rolling hills... which are nice, but aren't that realistic if they're everywhere. Instead, it would be nice to introduce some deformations in the landscape. They could be large deformations when the tesselation is only beginning, but as we get a higher and heigher level of detail the deformations will be smaller and smaller. The deformations I refer to are simply adding or subtracting some values from the actual height, each time subtracting smaller and smaller. Instead of curved surfaces, in fact, you could generate progressive maps like we described before, only algorithmically, creating the Tip vertices yourself based on random seeded deformations. Actually, you can have the following parameters for the landscape:

 Heightmap - Approximate layout of the map, to guide the algorithm and enforce your vision. Functions - These determine the correspondence between tesselation level and deformation scale. (Smoothness<-->Deformation) Seeds - For random (or otherwise calculated) deformations, which are then multiplied by the deformation scale.

The functions and seeds, like the heightmap, can be changed on a per-area basis. The individual areas are generated, but you can control what kinds of areas are where. If you have the exact same height, functions and seeds in two areas, they will look the same. But the chance of that is small, and you control that chance... you build the map. Each of these values is smoothly blended between the points of the map that you specify.

Note that these things are all landscape data, and must be specified. When you have a multiplayer game and several people are in the same place, you want them to see the same landscape. If you use this approach to half-specify, half-generate landscape, you can generate very, very large maps, that will have a lot of detail, and where anyone in any place will see the same thing. You can use other such algorithms or modify this one, to produce limitless (in theory) maps, but for those maps you probably won't specify the heightmaps and other things yourself -- just leave it up to the landscape generator.

 Texturing

 Lighting & Fogging