Near Field Landscape Decoration

A challenge for large scale terrain engines is the ability to provide enough detail in the near field of view, with grass, vegetation, rocks and other ground cover. In a brute force implementation these would all be represented by individual meshes (perhaps using billboards or imposters for distant objects) in an series of 2D rectangular areas stored in a quadtree, which are then rendered when in the view frustum and within the feature specific far clipping plane.

Individually placed trees in a landscape

A problem with this approach is the vast scale of storage required to store every bush, rock and grass clump, even though retrieval is fast (using a quadtree) this is still a huge data set.

A more scalable, fast, method of achieving this is to store the above but with a small spatial sample of the decoration required. This can be randomly scattered in a 1.0 x 1.0 rectangle at a given density appropriate to your decoration type. This is then stored with the area of coverage in the quadtree, but crucially the sample vegetation covers only a fraction of the area of coverage – the perception of continuous coverage is generated within the vertex shader.

In the above example individual trees do require constant geolocation, but smaller features, visible at only shorter ranges, can get away with a repeating wrap of a small set of meshes.

Assuming a maximum visible range for a feature is 100 world units, and a scatter of sample of meshes inside a 1×1 world unit square, the user can trigger the DrawIndexedPrimitives() when their camera position encounters the large area of coverage.

Inside the VertexShader the position passed in can be scaled and wrapped on a 100×100 scale to produce a repeating field of vegetation that seems to the viewer fixed in space, but in reality is being wrapped in the same way that repeating textures are wrapped in a texture sampler.

float wrap(float value, float lower, float upper)
{
  float dist = upper - lower;
  float times = (float)floor((value - lower) / dist);

  return value - (times * dist);
}


VertexShaderOutput VertexShaderFunction_Decoration(VertexShaderInput input)
{
    VertexShaderOutput output;

    // This calculation from http://books.google.co.uk/books?id=08fx86eFQikC&pg=PA240&lpg=PA240&dq=billboard+rotation+inside+shader&source=bl&ots=0ApjfGYTyu&sig=wIGHzbjmn_B2S4koEc5nRgZIkVQ&hl=en&sa=X&ei=BtTmUPLSMK6k0AWln4HoCw&ved=0CHUQ6AEwCQ#v=onepage&q=billboard%20rotation%20inside%20shader&f=false

    // Wrap the coordinates based on the camera position.
    input.Position.x = wrap(input.Position.x - frac(Param_CameraPosition.x / 100)  ,-0.5,0.5);
    input.Position.z = wrap(input.Position.z - frac(Param_CameraPosition.z / 100)  ,-0.5,0.5);

    // Scale X,Y to 100,100
    input.Position.x *= 100;
    input.Position.z *= 100;

    float4 worldPosition = mul(input.Position,Param_WorldMatrix);

Example vertex shader fragment for wrapped surface features

The view above of grass clumps continues for 1000 world space units, wrapping the visible 100 world units of textures continuously as the camera moves giving the impression of endless grass.

In the above the trees are placed specifically in the landscape, but the grass is a wrapped randomised set of billboards.

In this shot it more clearly shows that the grass coverage is thicker nearer to the camera. This is done by rendering the same vertex buffer of grass, camera centred, at two different X,Z scales – the first at a world scale of 150 and a second pass at 30, giving a 5:1 density ratio of grass nearer to the camera. This technique reuses the existing vertex buffer and effect, just changing the World matrix.

Near Camera Noise in Regular Landscapes

A generated landscape using Geo-ClipMapping or other LOD technique can suffer from an excess of available geometry near to the camera, without any heighmap to support it, giving an interpolated smoothness that is undesirable.

The generated triangles near to the camera have been interpolated between two height samples and translate into a perfectly smooth surface.

If we sample a Perlin noise generated texture in the vertex shader for nearby locations we can inject some semi random height noise to provide a better experience.

Vertex Shader Fragment

    float cameraDistance = length(Param_CameraPosition - worldPosition) ;
    if(cameraDistance < 500 )
    {
        // Now sample the noise texture to add some variation into the nearby tiles.
        float4 noiseCoordinates = (float4)0;
        // Use any texture coordinate system you want here – in my case its based on a variable called worldPercentile

        noiseCoordinates.x = textureCoords.u * 25;
        noiseCoordinates.y = textureCoords.v * 25; 
        noiseCoordinates.z = 0.0f;
        noiseCoordinates.w = 0.0f; // First mip map
        float4 noiseHeight = tex2Dlod(VertexNoiseTextureSampler, noiseCoordinates) ;
        worldPosition.y += (noiseHeight - 0.5f);
    }

And heres my noise texture;

And the result;

There are subtle, but present, pertubations in the near field geometry which prevents it now being perfectly smooth. The down-side to this technique is the need to calculate the normals in the shader; but thats no bad thing.

Fractal Landscapes and River Courses

Generating a fractal landscape using the Diamond Square method (shown in Generating Random Fractal Terrain ) generates a useful “alpine” style landscape with deep (but not linear) valleys and nice sharp peaks.

A side effect of this algorithm is that it creates primordial glacial style landscapes with no weathering. If this is what you want, then great

If you want to drive a river through your generated landscape using a path finding algorithm like A-Star, modifying the distance measurements between points to take into account changes in elevation, the fractal method becomes impossible to work with.

As illustrated in the landform described in the above link the outcome is almost always a series of “pits” surrounded by “peaks”.

 

This is a typical problem for route finding algorithms because there is never a logical, measureable, course between a point on the map and the edge of the map (the “sea”) as the course must traverse many “pits” out of which there is no escape.

I found the best combination to use to generate useful landforms was a Perlin noise based heightmap, with three levels of frequency, followed by selective regions where I would apply a fractal overlay to it. I chose a set of rectangles of random size, clamped the edges to zero (so they would blend into the existing heightmap) and generated a 2D array of height overlays based on the diamond square. I then applied this over the top of the existing Perlin based heightmap to create a composite region of Fractal overlaying Perlin.

Because the Perlin base layer provides a “boring” landscape of connected valleys (very similar to a heavily glaciated, “rounded” landform) any route finding algorithm for river courses would always find a route to the sea, and the overlay of some randomly sized fractal portions provided the “interesting” areas.

One side effect of using Perlin is that it is self-similar and that all sense of scale is lost; its very smooth but lacks any features; by applying a few sets of fractal landscape areas over the top the basic landform stays the same but the new areas of more detail provide a sense of scale.

Perlin based landscape. All rounded and glaciated.

Same Perlin based landscape with Fractal patches overlaid

References

Instead of using Perlin, I had good results using Simplex Noise and the implementation at Heikki Törmälä’s Code.Google.com archive

My A-Star path finding implementation from Eric Lippert’s Blog "Path Finding Using A* in C# "

The Humble For()

In most C# is normal to use the fantastically easy foreach() construct to iterate a set. This comes with a hidden cost;

1. An incrementor object is created for the duration of the loop and then destroyed, which is fine if you dont suffer from heap fragmentation, or are not aware that different C# .net frameworks have different GC implementations (XBox for instance).
2. the incrementor cannot easily be used in an anonymous code block within the loop, as, by the time the code is executed, the incrementor may yield a different value to the one it had when the code block was constructed.

Reconsider our old friend for() which is faster to execute, doesn’t lead to heap allocations and doesn’t suffer from the anonymous code block problem.