Terrain triangulation

The last post on this is here, and explains how I’ve been trying to remove the texture projection artifacts I have due to how the normals are interpolated over a limited resolution.


Different tessellation implementations discussed in this post.


I got some feedback that I should use a higher resolution grid, and perhaps ditch the quad re-orientation. The quad re-orientation is done on the CPU and means that we need to prepare a unique vertex buffer for each terrain chunk we render. This makes it overall less flexible.

I tried a few different implementations with increased grid resolutions, but the best I’ve gotten so far involves the use of weighted sample points. Using the floor/ceiling/frac intrinsics in HLSL, we can sample the four closest points in the original heightmap, and output a weighted average of those four. This is demonstrated in the diagram below for sample point S:

This allows me to use any grid size I want with minimal changes. The results aren’t that much different than using a 1-to-1 grid size – it’s just that we get a bit of extra smoothing because we’re adding new points that are the result of interpolating between 4 different points, instead of the getting the result from the interpolated triangulation. We also have the option to massage the weights a bit to provide more of a power curve (this doesn’t improve things that much though).

A more interesting improvement comes when we consider how we generate the normals in this case. The standard way to generate normals from a height map involves using four surrounding points (essentially ignoring the point itself). When sampling discrete positions on a heightmap, this is really the only way to go about it, since a point itself doesn’t have any normal associated with it – you need to get a normal from somewhere. It’s not ideal though, as you can see from the left side of the diagram below (simplified in 2D):

The normals don’t really make sense where steep transitions occur.

However, if we have enough grid resolution and we’re taking weighted sample points, we can do something better. We can use the actual “face normal” of the line/surface between two points. At compile time I calculate these and store them in the heightmap itself (in the spare channels). The texel at (100, 100) stores the height for (100, 100), but the normal for (100.5, 100.5).

In the vertex shader, we take the same weighted average of 4 points for the normal, but we offset the sample position by a half texel (yes, this means an additional 4 texture samples to calculate the normal – some of them may be the same sample points as for position, but it’s difficult to see how to optimize this).

For a 1-to-1 grid-to-heightmap resolution, this will produce bad artifacts. But once your grid resolution is sufficient (say 4-to-1), things look better.


The 5 images below are comparisons between my original method and the method described above. The original is on top and the new method is on the bottom. The texture projection artifacts (which are based on the normal) are sharply reduced, but there is significant blockiness.

To recap, the original method uses a 1-to-1 grid resolution, and re-orients quads so that they are triangulated along the axis with minimal height change. The normals are pre-calculated (and my calculations are actually a bit off, I’m not using the standard mechanism – but the difference isn’t significant). The new method uses a 4-to-1 grid resolution and nearly all work done in the vertex shader (and thus no quad re-orientation).


I think I still strongly prefer my original technique. The quad re-orientation adds a lot of visual fidelity given the coarse grid. Ignoring the texture projection artifacts, a 1-to-1 grid with quad re-orientation actually looks better than a 4-to-1 without (look at the snow image above). The quad re-orientation essentially modifies the geometry to makes smoother outlines, really. I’m frankly a bit astonished at how good it can look with such a coarse grid.

What next? I suppose I should look at ways to keep the quad re-orientation with higher resolution grids. Either take the extra complexity and performance impact it requires on the CPU, or find a way to do it in the GPU. I suspect this might be easy to do with the tessellation available in DX11, but I’m currently still targeting DX9 (XNA). I can think of some ways to implement it in DX9, but they are all fairly complex and involve rendering additional primitives, or no longer sharing vertices among primitives.


5 comments on “Terrain triangulation

  1. I think it should not be too difficult to do quad re-orienting on GPU (but of course I do not know the precise detail of your method).
    It requires that you sample all information about your vertex (other than 2D coordinate and per-quad data) from textures (or calculate in vertex shader). Then you will add quad information (center point or such) to all your vertices (not a big problem, as now all your vertex buffers will be the same). Now in vertex shader you can check for each vertex, which direction (45 or 135 degrees) is the best one – and if it is 135 degrees you will rotate the 2D position of given vertex 90 degrees around quad center. Then you sample and calculate all vertex properties from it’s new 2D coordinates.
    As all vertices of the same quad will be rotated identically you get reoriented triangles that fit seamlessly with other terrain.

    • It sounds like something like that could work. But that does mean that the triangles can no longer share vertices. That means I am roughly tripling the number of vertices I’m processing (assuming near ideal use of the vertex cache with my current implementation).

      Of course, if I can do this all on the GPU, I don’t need to prepare chunks of terrain vertices ahead of time, so I can avoid sending large number of vertices that would be off-screen anyway.

  2. Another good article – definitely see the benefits of quad re-orientation 🙂

  3. […] This is getting to be almost a daily thing! The previous post is here. […]

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Just another WordPress site

Just another WordPress.com site

Harebrained Schemes

Developer's blog for IceFall Games

kosmonaut's blog

3d GFX and more


Turn up the rez!

bitsquid: development blog

Developer's blog for IceFall Games

Game Development by Sean

Developer's blog for IceFall Games

Lost Garden

Developer's blog for IceFall Games


Developer's blog for IceFall Games

Casey Muratori's Blog

Developer's blog for IceFall Games


Developer's blog for IceFall Games

Rendering Evolution

Developer's blog for IceFall Games

Simon schreibt.

Developer's blog for IceFall Games

Dev & Techno-phage

Do Computers Dream of Electric Developper?

- Woolfe -

Developer's blog for IceFall Games

Fabio Ferrara

Game Developer

Clone of Duty: Stonehenge

First Person Shooter coming soon to the XBOX 360

Low Tide Productions

Games and other artsy stuff...


Just another WordPress.com site

Sipty's Writing

Take a look inside the mind of a game developer.

%d bloggers like this: