• entries
  • comments
  • views

Selecting a Terrain Engine

Sign in to follow this  


A few months ago, I implemented a terrain engine using the geometry clipmap technique as described in Chapter 2 of GPU Gems 2. Unfortunately, I discovered that the technique is patented (well, pending at the time this was written) by Microsoft. I tried to ask Microsoft Research for permission to use it, but there was no response.

Why NVidia allowed this technique to be published in GPU Gems 2, knowing full well that Microsoft applied for a patent on it, I'll never know. Does that mean that other techniques in that book are patented as well? Did I spend $160 CDN on both books that are essentially ads for NVidia? ("Look at what our cards can do, but don't implement any of these techniques!")

Unfortunately, this meant that I had to scrap the geometry clipmap engine and replace it with a new engine. So I went over to VTerrain to see what other techniques I could use.

When selecting a new technique for rendering terrain, I needed one that:
  • is able to handle very large terrains (64k x 64k). In the old engine, I used a base height map (e.g, 1024 x 1024) with some artificial detail applied to it in real-time.

  • is GPU friendly. All vertices in a terrain patch must be placed in a single triangle strip so that the patch can be uploaded to video memory and drawn with one call to the graphics library.

  • does not require height-map preprocessing. This allows me to use Perlin noise or some other algorithm to generate the vertices in real-time instead of using a static height map.

  • is easy to add vertex morphing when terrain patches are transitioning between LODs.

With this in mind, I narrowed my choices down to three:
  • Geometrical Mipmapping: This technique looks very easy to implement since each patch has a regular size and contains a regular grid. This also proves to be a drawback as well -- because I needed to be able to render a 64k x 64k grid, I'd either have to use a metric sh*tload of small patches (requiring a huge number of GL calls), or a small number of gigantic patches (requiring a huge number of vertices per patch)

  • Chunked LOD: This method uses a quadtree of terrain patches of various sizes, depending on its LOD. This allows the use of gigantic terrain since the sizes of patches can vary; far-away patches are larger than nearby patches. Unfortunately, this method requires some preprocessing to decimate the number of triangles in each patch before use. Also, the mesh in each patch does not contain a regular grid of triangles, preventing me from easily determining the elevation of a specific point on the terrain.

  • SOAR. I was playing around with a terrain demo called Ranger Mk II which makes use of the SOAR technique. This demo is very impressive. It is fast, it can handle long draw distances, and it can handle a monsterous-sized terrain. After looking at the code, I was really confused about how it worked; the algorithm appeared to be very complicated for my small little mind.

In the end, I ended up using a combination of Chunked LOD and Geometrical Mipmapping. The terrain is stored as a quadtree of patches, and each patch contained a regular grid of n x n vertices. As the viewpoint moves around the terrain, patches are allocated and reallocated as neccessary. Because each patch has the same number of vertices, I can create a reusable pool of patches on the video card. When a patch is needed, the engine selects an unused patch from the pool, and when a patch is no longer needed, the patch is returned to the pool. This technique does everything I need.

Next, I have to figure out how to perform vertex morphing on the patches. Details will come shortly.

(I'm not used to the funny HTML used in these journals :-)
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now