2 Comments

Terrain triangulation – summary

In this post I’ll summarize how I triangulate the terrain for my heightmap, and go over some of the shader implementation.

I use a 2-1 grid-to-heightmap resolution, and triangulate it in the following way, where the red dots are the heightmap points:

 

Using a 2-to-1 grid resolution lets me accomplish two important things: I can use more accurate normals, and I can better align the grid to the natural shape of the terrain. I’ll explain both of these things further along in this post.

The basics – height

Lets say that the vertices that lie between heightmap points are given weighted heights based on the nearest actual heightmap points. Considering our triangulation pattern, there are four unique points (A, B, C, D):

The heights for each are defined by:

  • h(A) = h(xy)
  • h(B) = 0.5 * h(xy) + 0.5 * h(x+y)
  • h(C) = 0.5 * h(xy) + 0.5 * h(xy+)
  • h(D) = 0.25 * h(xy) + 0.25 * h(x+y) + 0.25 * h(xy+) + 0.25 * h(x+y+)

So in our vertex shader, we need to sample from four positions on our heightmap.

At this point you have something that looks relatively similar to what you would get with a 1-to-1 grid-to-heightmap resolution, with the exception that the center point is weighted between four points instead of two “arbitrary” points that would depend on how you orientated your triangulation for a 1-to-1 grid. This actually looks worse in some cases, but we’ll get back to this later.

Next, lets consider the terrain normals.

The basics – normals

The standard algorithm for calculating normals on a heightmap involves taking the cross product of two vectors defined by the heightmap points above and below, and to the left and right of the one for which you are calculating the normal. If d is the texel size in world units, then the binormal, tangent and normal vectors are given by:

  • B = (2 * d, h(x+, y) – h(x-, y), 0)
  • T = (0, h(x, y+) – h(x, y-), 2 *d)
  • N = T × B

The problem with this algorithm is that it is basically doing some averaging, and ignoring the height of the actual center point (not to mention the heights of the points on the diagonals). The can given some pretty bad calculations for the normal, as shown by the following diagram:

You can see that the normals on the “cliff face” are basically incorrect. Ideally we would be able to represent the “face normal” of the cliff more accurately, but that isn’t possible given that we need to use points on either side of a point to calculate the normal.

However, what if we offset our grid by half a texel? Then we can use face normals to get more accurate normals at the halfway points:

So what we do is calculate accurate normals for the points halfway in between texels, and then store them in the heightmap texture itself. So the normal for a point at (x + 0.5, y +0.5) is stored at (x, y). We use the two vectors on the diagonals to calculate the normal. So the calculations for the normal at (x + 0.5, y +0.5) are as follows:

  • B = (d√2, h(x+,y+) – h(x, y), d√2)
  • T = (-d√2, h(x,y+) – h(x+,y), d√2)
  • N = B × T

This does mean there can be some artifacts at two edges of the heightmap, but this shouldn’t be a problem.

We store it at offset (x + 0.5, y + 0.5), so in the vertex shader we need to subtract half a texel to sample from the correct point. So given the following diagram:

our normals would be calculated like so in the vertex shader (pseudo-code):

  • n(A) = 0.25 * n(xy) + 0.25 * n(x-y-) + 0.25 * n(x-y) + 0.25 * n(xy-)
  • n(B) = 0.5 * n(xy-) + 0.5 * n(xy)
  • n(C) = 0.5 * n(x-y) + 0.5 * n(xy)
  • n(D) = n(xy)

This doesn’t mean we need 4 more heightmap samples in the vertex shader though. The normal and the height calculation never require more than 4 samples total. For each vertex we can include the offsets from which we need to sample, and the weights applied to each offset for the heights and for the normals.

Note: I think we can actually avoid need to put the offsets in each vertex if we instead stored the normal for (x – 0.5,y – 0.5) at  (x,y) in the heightmap. Then we would always sample from the same 4 points.

In the shader…

My heightmap is a 16 bit per channel floating point texture. It stores height in the red channel, water level in the green channel, and two components of the normal in the blue and alpha channels (we reconstruct the 3rd component of the normal).

After taking our four sample points (one, two, three, four), calculating the heights is just a simple  dot product:

float4 heightWeights = input.HeightWeights;
float height = dot(float4(one.r, two.r, three.r, four.r), heightWeights);

Then similarly for the water height. And we need to do each component of the normals separately.

Aligning the grid to the terrain shape.

If we were to use a lower resolution grid (1-to-1) like the blue lines in the following image:

 

 

we would see that if the slopes of our terrain are aligned with one of the four sides of the square they look nice. And they also look nice if aligned with the diagonal. But we get some pretty serious grid patterns if they are aligned along the other diagonal:

 

 

Now with the 2-to-1 grid I’ve described so far in this post, we get a slightly less severe grid pattern, but it happens on both diagonals:

 

 

It’s actually worse – or rather more widespread – than it is for the 1-to-1 grid. The problematic vertex in our grid is the one that is weighted to sample from all 4 adjacent heightmap points.

To fix this, we can instead – for that point only – just sample from 2. This mimics the behavior of the 1-to-1 grid’s triangulation, except we can now do it for both diagonals. We need to choose the diagonal whose heights differ the least from each other.

In the vertex shader, we mark this vertex specially (you can add another piece of data to your vertex declaration) and reassign our weights based on the height difference:

// Align this vertex better to the terrain.
 if (abs(two.x - one.x) > abs(four.x - three.x))
 {
     heightWeights = float4(0, 0, 0.5, 0.5);
 }
 else
 {
     heightWeights = float4(0.5, 0.5, 0, 0);
 }

Then we get this:

 

We can do the same thing with the normals, too.

Now we’ve made things look nice for the horizontals, verticals and diagonals in the heightmap. Of course, you’ll still notice a grid pattern if you have terrain perfectly aligned along a line halfway between vertical and diagonal:

 

 

Overall though, the artifacts are sharply reduced, and you really have to have terrain perfectly aligned with such specific angles for it to be noticeable.

 

Here I’ll just list the previous posts I’ve made on this topic:

Thanks to all the folks who have helped me come up with this current implementation!

About these ads

2 comments on “Terrain triangulation – summary

  1. I like your approach. I have been using:

    |\|\|
    |\|\|

    But your method of triangulation (plus using the two heigh weights) produces significantly better results:

    |X|X|
    |X|X|

    Look forward to implementing it this way :)

  2. Great results. I have been working on a random terrain generator as a background task for a future project. Your method will be ideal. Thanks.

    Very well written, very clear.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

- Woolfe -

Developer's blog for IceFall Games

Ferrara Fabio

Game & Application Developer, 3D Animator, Composer.

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...

BadCorporateLogo

Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a young game developer.

Jonas Kyratzes

Writer, game designer, filmmaker.

Indie Gamer Chick

Indie Game Reviews Without Mercy

The Witness

Developer's blog for IceFall Games

Developer's blog for IceFall Games

Developer's blog for IceFall Games

game producer blog

Developer's blog for IceFall Games

A Random Walk Through Geek-Space

Brain dumps and other ramblings

The ryg blog

When I grow up I'll be an inventor.

Developer's blog for IceFall Games

T-machine.org

Developer's blog for IceFall Games

Ocean Quigley's Projects:

Developer's blog for IceFall Games

Wolfire Games Blog

Developer's blog for IceFall Games

The Witness

Developer's blog for IceFall Games

Follow

Get every new post delivered to your Inbox.

Join 282 other followers

%d bloggers like this: