[ / main / writing / hfield ]

    Heightfields



©1998 Jeff Weeks and Codex software

Sample source code:
X/DJGPP




The concept of the heightfield is very simple; It's a multidimensional array of heights. Think of it as an array indexed with x and z coordinate subscripts where the value in the array is the y coordinate, or height, for the cooresponding x and z coodordinates. Now, in the following tutorial I will commonly refer to the heightfield as a heightmap, simply because it seems a little more intuitive. I will also refer to a colourmap. The colourmap is like a heightmap in that it's indexed with x and z coordinate subscripts but returns a colour value. With both a heightmap and a colourmap you have all the information you need; X, Y, Z and colour.




Like I said, the concept is very simple. What's not so simple, however, is visualization of this data. There are many different techniques; You could create polygons based on the data, for example. The way I prefer, however, is a technique where the data is projected and interpolated through fast vertical line functions. That is the technique I will explain




First of all, the basics. When you render your heightfield scene you will obviously only be rendering a small portion of the whole heightfield. What may not be as obvious is the shape to render. We don't want to render a square area, but rather a cone shaped area. This makes sense when you think about it in terms of the human eye; Our field of view gets larger farther out, and is very small directly infront of the eye. To be even more realistic though, it should be a cone with the top chopped off. Why? Well, we have two eyes; We effectively have two cones of vision (one for each eye) which can be loosely combined to form a single, wide, cone with a flat top near the eyes. If you want to be really fancy you can actually render each cone separately in red and blue shades and have the viewer wear 3D glasses for the true 3D effect that a monitor can't give.




Whatever. All the above three systems will work. Just don't render a square patch. I haven't seen the results but I can guess they would look mighty un-natural. Okay, so now that you've decided upon a shape to render it's about time to render it. The approach is very must like a texture mapping system, and is done on a line by line basis. In simplest terms you will be starting from the far distance (the large end of the cone) and rendering foreward and interpolating between each rendered line.




You'll have two arrays, the size of the width of the screen. These arrays will hold the heights and colours for two rendering lines. You fill these by interpolating (for the length of the array) between the left and right sides of the view cone. It's kind of like texture mapping; You're taking the current rendering line and resizing it (repeating values, or skipping them if necessary) to the width of the screen/array.




      int tx1,ty1,tx2,ty2;          /* coordinates of line to interpolate */
      int hx_step, hy_step;         /* height x and y steps */
      int hx, hy;                   /* height x and y */
      int c;                        /* general purpose counter */
      int pos;                      /* position in heightfield array */
      /* interpolate between the left and right sides */
      tx1 = view.left.x;  ty1 = view.left.y;
      tx2 = view.right.x; ty2 = view.right.y;
      /* interpolation variables used to resize the rendering line to screen width */
      hx_step = ((tx2-tx1))/video.max_x;
      hy_step = ((ty2-ty1))/video.max_x;
      /* start on the left end */
      hx = tx1; hy = ty1;
      /* interpolate */
      for(c = 0; c < video.max_x; c++) {
        pos = int( (hy>>8) * MAP_X + (hx>>8) );
        tbuf[c].c = cmap[pos];
        tbuf[c].h = hmap[pos];
        hx+=hx_step;
        hy+=hy_step;
      }



And you do that for every rendering line in the view area. The above is just a simplified example of what your interpolation might look like (assuming the view structure holds fixed point numbers). Notice, however, the multiply needed to calculate 'pos'. There are ways to get rid of this, the most common being to make the map size a multiple of 2, allowing shifting instead of multiplying.




tbuf in the above example is one of the structures I was speaking of that would be the width of the screen. I have two; tbuf and bbuf, meaning top and bottom buffers. So, once you've filled two of these in you can get to the next step; Filling in between them. First you must project them, ofcourse. Remember, your arrays only hold height values, not screen coordinates. After projecting you'll now have screen coordinates so you can draw a vertical line between them.




      int pos, i;
      int length, x;
      for(x = 0; x < video.max_x; x++) {
        if(bbuf[x].h > tbuf[x].h) {
          /* perform clipping */
          if(tbuf[x].h < 0) tbuf[x].h = 0;
          if(tbuf[x].h > video.max_y) tbuf[x].h = video.max_y;
          if(bbuf[x].h < 0) bbuf[x].h = 0;
          if(bbuf[x].h > video.max_y) bbuf[x].h = video.max_y;
          length = bbuf[x].h - tbuf[x].h;
          pos = (tbuf[x].h*video.max_x+x);
          for(i = length; i; i--) {
            video.virt[pos] = tbuf[x].c;
            pos += video.max_x;
          }
        }
      }



Again, the above code is only how you might code such a function. A nice effect can be gotten by interpolating the colour values between the top and bottom buffer's colours. You'll notice I first check to make sure the buttom buffer is indeed greater than (or lower than) the top buffer. This is not necessary, but only makes sence; Why draw the hills comming up when those lines will just be covered when the hill comes down again (kind of like what goes up must come down)? It's like hidden surface removal for a heightfield.




Okay, now after you've drawn your first vertical lines, you must copy your bottom buffer to the top buffer, reload the bottom buffer with the new rendering line, and again draw vertical lines between the top and bottom buffers. You continue doing this until you reach the very last rendering line (directly infront of the viewer). For asthetic reasons, however, you should special case the last rendering line. Draw from the top buffer to the very bottom of the screen, ignoring the bottom buffer. That way you don't leave any unsightly trails or would-be invisible areas.




That's about it folks. I have the overwhelming feeling that I haven't described this well at all, and so I must make it perfectly clear that I'll take any questions you may have. Please don't hesitate. One thing that may help is a little recap as to what we did here...




First of all, you define your two arrays (the size of the screen) to hold vital heightfield data (height and colour, to be exact). You then fill these in, one rendering line at a time, with the data from the current rendering line. When you have both arrays full then you must project them and draw vertical lines between them. With that done, copy the bottom array to the top array, and reload the bottom array with the new rendering line. You basically continue doing that until you've reached the viewers position and there are no longer any more rendering lines.




One thing I should probably mention about this system are it's restrictions. Due to the vertical line system I'm using this heightfield is limited in the style of rotation it can handle. It cannnot be rotated in either the x or z axis. The only rotation you can handle is the y rotation, which is accomplised by rotating your rendering area. You also can't have holes or burrows in your landscapes because your heightmap is only one level, as seen from above.




Just so you know, I'm currently working on a system that might be able to perform full rotation with multiple levels (allowing for holes and burrows). I'll include a tutorial here if I ever finish it. For now, here are some pictures of what the above heightfield system can do...