XNA Large Terrain

This is my technique for rendering large scale terrain using XNA (also applies to DX9 with SM3.0)

Quick Recipe

• At startup create or load two triangle shaped planar meshes (pizza slices)
• Each frame position and orient these meshes to cover the terrain area visible in the view frustum
• In the vertex shader transform world-space positions into texture-space, sample the height map using VTF (Vertex Texture Fetch) and displace the height of the mesh
• Use Catmull-Rom interpolation to determine the heights of mesh vertices that lay between height texels
• Use Uniform Basis Spline interpolation to create perfectly smooth normals

You have a simple and efficient large scale terrain renderer which uses almost no CPU, no CPU-to-GPU bandwidth, and is very GPU friendly! There is no need for quadtrees, octrees, clipmaps, roam or dynamic mesh generation.

Overview

My goal was to render large-scale high-quality terrain with the simplest and most efficient approach possible.
I have read many papers about terrain rendering and they all seem very over-complicated.

One technique that caught my eye was “projecting screen space grid into world space” which is often used in ocean rendering. This uses the absolute minimum no of vertices but, for terrain, suffers from terrible shimmering.
This taught me that the height map, terrain mesh and world space had to align at all times.
(Imagine that the height texture is placed into world space – creating a uniform grid of height points, the mesh must always snap to this grid)

Intersecting the view frustum with a plane is trivial – for the typical case the resulting shape is a triangle … why not create a single triangle-shaped mesh and rotate it around the camera?
I found that two 22.5 degree “pizza” slice shaped static meshes could be positioned around the camera and cover the full 360 degrees.

I use VTF (Vertex Texture Fetch) with a height map to displace the vertices vertically.

By building the static meshes in blocks in near-to-far order it is possible to limit the triangles rendered to the visible bands by using the vertex offset and count.
This approach also plays nicely with the depth buffer and hierarchical & early z culling etc.

What about Level-of-Detail (LOD) ?
As the meshes will always be rendered in near-to-far order, the distance based LOD could be static.
Because the LOD transitions are known in advance there is no need for LOD stitching etc.

Thanks to jwatte on the XNA forums I read "Computer Graphics Principles & Practices" and found that the bicubic surface equations worked perfectly with HLSL as a cubic equation can be solved with a dot product … and a bicubic surface can be interpolated by multiplying a 4×4 geometry matrix with a 4×4 basis matrix etc.
In other words bicubic interpolation was going to be FAST! Sampling 16 8 bit height texels can’t be that expensive …
It also had a great by-product – the same height data and cubic coefficients could be used to calculate slopes and then surface normals.

The end result is: whilst other techniques waste time, resources and bandwidth trying to optimize the mesh – my technique has already finished rendering.

Implementation

Create two static planar triangle-shaped meshes:

One for 0 to 22.5 degrees:

One for 22.5 to 45 degrees:

Note! The right hand edge of the second mesh is a straight line:

For squares which overlap both meshes – the mesh which includes the center point (or the left mesh if that is both) takes the square.

Tesselation

Each numbered cell in the above meshes is tesselated according to its LOD band.

The meshes are tesselated like this:

Which means there is no need for LOD stitching, and the mesh looks the same when rotated by a multiple of 90 degrees etc.

Unit Transformation

Use a 2×2 unit transformation matrix to reflect / rotate the meshes around the mesh origin:

Get a height map

8 or 16 bit grayscale

I use Alpha8 DDS with 8192×4096 resolution.

Vertex Buffer

I created a function that creates the terrain meshes using parameters for size, no of lod levels and position of lod transitions.
The function builds the mesh in left to right, near to far order and records the vertex number of the start of each row.

The vertex numbers are used to draw only the visible rows.

Example:

In the above diagram only rows 2 to 13 inclusive are visible.

Vertex Buffer continued

Use the VertexElementFormat.Short2 (ushort) format to reduce the size of each vertex to only 32 bits (and therefore use integer coordinates for the vertices)
You can put both meshes in a single vertex buffer – as long as you keep track of the vertex offsets. (This saves the expense of switching vertex buffers during drawing)
With this approach we can fit 8 vertices into 32 bytes.

Decide scales

The object space mesh must fit the view frustum without any gaps.

Use the Far Plane to calculate a scale factor that ensures that the shortest side of the mesh (taking into account position rounding) is longer than the longest line in the view frustum (from near top left to far bottom right)

LODs and Interpolation

There should be a 1:1 Vertex:Texel ratio at the lowest resolution LOD level.

As the resolution increases so will the number of vertices per texel.

The heights of the intermediate vertices (between height texels) are calculated using a Catmull-Rom or Basis Spline (BSpline) bicubic surface.

Geometry Implementation

Origin Determination

To stop shimmering the mesh and height map must be fixed in world space

That means we need to round the world space origin of our terrain slices:

– Project the view space Z axis onto the terrain plane
– Find the nearest height point in the opposite direction
– Use this as the mesh origin

Note! This is the location of the nearest height map texel, behind the camera, in world space.

Frustum Culling

– Project the view frustum on to the terrain plane
– Calculate the slices which intersect
– Calculate the near and far rows that are visible
– Repeat for 3 or 4 terrain planes between min and max height (y = 0%, y = 25%, y = 50%, y = 75%, y = 100%)
– For each visible slice define the unit 2×2 transformation and the vertex offset and count

What about looking vertically down?

If you are close to the ground then looking down will result in all 16 slices being rendered.
But the number of vertices will be low due to the small no of visible rows.
As the camera’s height increases this can lead to all 16 slices being rendered in full – too many vertices!
A solution is to either clamp the camera’s height or to scale the mesh up by powers of 2 as the height increases (Vertical LOD?)

Vertex Shader Implementation

Effect Parameters

The vertex shader needs:

float    VertexSpacing;     // world distance between vertices (at highest resolution lod level) (Example 1.0)
float    TexelSpacing;      // world distance between height texels (Example 4.0)
float3   TerrainOriginInWorldSpace; // rounded world space position of terrain origin
float4   UnitTransform;     // 2x2 transformation matrix used to orient current slice into world space
float4x4 matView;           // standard view matrix
float4x4 matProj;           // standard projection matrix

You can convert the float4 in HLSL like this:

static const float2x2 mat2x2 = (float2x2)UnitTransform;

then use it:

float2 Ptransformed = mul(Pmesh, mat2x2);

Transformation

– Orient the slice using the Unit Matrix
– Scale the slice into World Space
– Translate the slice into Position using TerrainOriginInWorldSpace

Vertex Texture Fetch

Transform the world space position into height map texture space and use VTF Vertex Texture Fetch to read the height:

float2 texHeight = WorldSpaceToTextureSpace(posWorld.xz);
float height = tex2Dlod(smpHeightMap, float4(texHeight, 0, 0)).r;

Cubic Interpolation

This diagram shows Linear, Catmull Rom and BSpline interpolation:

Linear is just straight lines which will look horrible

Catmull-Rom interpolates exactly but can wobble

BSpline doesn’t interpolate exactly but is perfectly smooth

The graph above of the Catmull Rom second derivative shows that surface is not perfectly smooth
compare with graph of BSpline second derivative:

You can use either scheme – as long as your terrain collision uses the same.
For per-pixel normal calculation bsplines give C2 continuity aka “perfectly smooth”.

Some CSharp code to perform cubic interpolation:

public static Matrix MatCatmullRom =
    new Matrix(
        -0.5f,  1.0f, -0.5f,  0.0f,
         1.5f, -2.5f,  0.0f,  1.0f,
        -1.5f,  2.0f,  0.5f,  0.0f,
         0.5f, -0.5f,  0.0f,  0.0f);

public static Matrix MatBasisSpline =
    new Matrix(
        -1,  3, -3,  1,
         3, -6,  0,  4,
        -3,  3,  3,  1,
         1,  0,  0,  0) * (1.0f / 6.0f);

public void CubicInterpolation(
        ref Matrix MatCubic,
        ref Vector4 Geometry,
        float IP,
        out float Height,
        out float Slope) {

    Vector4 T = Vector4.Zero;
    Vector4 ABCD = Vector4.Zero;

    // Calculate Cubic Coefficients
    Vector4.Transform(ref Geometry, ref MatCubic, out ABCD);

    // T Vector
    T.W = 1;
    T.Z = IP;
    T.Y = T.Z * T.Z;
    T.X = T.Y * T.Z;

    // Solve Cubic for Height
    Vector4.Dot(ref T, ref ABCD, out Height);

    // T Vector for Derivative
    T.W = 0;
    T.Z = 1;
    T.Y = 2.0f * IP;
    T.X = 3.0f * IP * IP;

    // Solve Quadratic for Slope
    Vector4.Dot(ref T, ref ABCD, out Slope);

}//method

// Usage:
float Height;
float Slope;

Vector4 Heights = new Vector4(0, 1, 2, 1);

for (float ip = 0.0f; ip <= 1.0f; ip += 0.1f) {

    CubicInterpolation(ref MatCatmullRom, ref Heights, ip, out Height, out Slope);
    Debug.WriteLine(Height);

}//for

This function also calculates the slope of the curve, which can be used to calculate normals.

To calculate the height at a point on a heightmap we need to use a bicubic surface:

1) Sample 16 heights
2) Calculate the unit interpolation parameter
3) Interpolate 4 heights for Y (using 4 vertical splines)
4) Calculate the final height for X (using the 4 heights from previous step)

To find the slopes in both directions:

1) Using the cubic coefficients for the horizontal spline at Y – calculate the slope
2) Interpolate 4 heights for X (using 4 horizontal splines)
3) Calculate the cubic coefficients from these heights
4) Use these coefficients to solve for slope
5) See below to convert these 2 slopes into a surface normal

Height Scaling

The distance between texels in the height map probably relates to a real world distance (say 10 km)
Now we need to scale the unit height into world space so that it is proportional to the real world distance between height texels.
So if the maximum height is 10 km and height samples are 4 km apart – the ratio between horizontal and vertical is 2.5:

height *= UnitHeightToWorldSpace;

Normal Calculation

Convert the horizontal and vertical slopes to vectors:

float3 nx = float3(-1, dx, 0);
float3 ny = float3(0, dy, -1);

Cross these vectors to find the surface normal:

float3 n = cross(ny, nx);

Don’t forget to normalize() it at some point …

Support for very large terrain

Planet Earth at 4 km resolution takes 8192 x 4096 x 8bit = 32 MiB

Using height (and slope) based texture splatting means no large color textures are required

I use a 8192 x 4096 DXT1 Color Map which takes 22 MiB on the GPU.

Using 4 height samplers in the vertex shader enables a simple tiling system – when combined with background texture loading (on an unused XBOX 360 CPU core) this enables very large terrains.

CPU terrain collision detection

– Pull the Alpha8 texture data into memory
– Use CSharp bicubic surface interpolation
– This requires 32 MiB on the CPU side
– As an experiment to save memory I created a Height Query shader – but readback performance is terrible on XBOX 360.

Conclusion

This approach is essentially brute force with a twist.
But the cost of processing any extra triangles is outweighed by savings in CPU cycles, system bandwidth and the very low number of draw calls (average 4.5 draw calls per frame)
The LOD artifacts are limited to slight popping in the distance – which usually goes unnoticed – unlike the horrific popping in many more advanced approaches.

Optimisations

These meshes can also be converted from indexed triangle lists to indexed triangle strips, for another performance boost.
Geometry instancing using a small texture for instance data, updated with DUP (DrawUserPrimitives) could reduce the draw calls to 2.
Using a depth only pass might give a boost, if the pixel shading is expensive.

Video

Make sure to switch to 720P and disregard the mpeg compression artifacts … there are also couple of bugs in this video as I have been reworking things.

http://www.youtube.com/FloodleObb

Screen shots