Landscape Mesh Smoothing using Bicubic Splines

Prompted by a comment from SkyTiger on my previous post “Large Scale Terrain” that I could use bicubic splines to dispense with a large amount of my geometry, I cooked up a version of the landscape generation code which used this technique instead of the linear interpolation I was previously using.

The requirement to have interpolation of any sort is governed by the large size of the terrain we are generating in proportion to the resolution of the heightmap passed to the shader. Typically out heightmap may be a 512×512 texture but we will have vastly more unique terrain vertexes on screen that that. So somehow we need to find the height of terrain vertexes that don’t map exactly to a pixel in the heightmap.

A nasty problem is that Vertex Texture Fetch (i.e. sampling a texture from within a vertex shader) is restricted to point sampling only – you have to do your own calculations as to the relative position within the pixel (typically done for you by a linear sampler) – so beware; if your landscape suddenly goes all “minecraft” its probably because you missed this subtlety.

Linear Interpolation of Heights

Interpolation is a method of taking into account neighbouring pixels to weight the current pixel data. Given two neighbouring pixels of value 10 and 15, the value 10 should only be obtained if the sample was exactly in the centre of the 10 value pixel – any variance in the X and Y coordinate should also take into account the value of the next pixel. In linear interpolation this is a simple distance-proportion; if we are halfway between the centre of the 10 pixel and the 15 pixel, the value should be about 12.5.

It follows that linear interpolation requires that you know the value of the pixels surrounding the one you are positioned over. However because your sample is always in one of the four quadrants of the central pixel you need only consider the pixels adjacent to that quadrant; therefore linear interpolation requires four texture lookups to obtain your height.

Linear interpolation gives an effect like this;

image

(awesome picture Smile)

The linear interpolation prevents the blue (actual sampled value) from being evident, and shows a line between the centre of each pixel sampled, gradually altering to conform to the centre of the next pixel in the sample. The result is a series of flat gradients that do not vary in slope until they hit the next pixel centre.

Heres a picture of landscape using Linear Interpolation for its heights.

image

No matter how dense my geometry is, its clear that all the triangles lie on the same plane if they lie within a single height map pixel.

Bicubic Interpolation of Heights

A quick guide to “what is a bicubic spline” is covered in SkyTiger here. Using the awesome power of Paint.net here is an illustration of the difference

image

Notice that the individual height samples, even when falling between the same two pixels, don’t fall onto the same plane ? This is because (and I haven’t really illustrated it very well here) each height sample takes into account the pixels that neighbour its neighbours; requiring 16 samples for each height to be calculated. Ouch. This gives the sampler a concept of the “trajectory” of the line that it forms part of – it needs to take into account its previous “slope” when deciding how much influence the next sample will have on it – its kind of like an “inertia” applied to the slope transition.

There is some payoff here though – in the example on linear interpolation its clear that most of those triangles are completely wasted – the viewer gets no benefit from their being a high density of triangles; in fact one triangle quad per heightmap texel would be an efficient quantity. Essentially the landscape is low-resolution and that resolution is determined by the heightmap texture size.

When using bicubic interpolation the viewer gets the benefit of all that lovely extra geometry and there is no angular transition betraying the underlying low-res heightmap. Of course, its as smooth as a cueball, so introducing a level of randomness onto the bicubic calculation from another texture (such as a perlin noise generated texture) might break up the monotony a bit.

image

However, 16 texture lookups per vertex painted does sound a bit profligate, especially when you need the same calculation to operate for placing terrain objects like trees and grass billboards

Mixed Linear and Bicubic

If the 16 texture lookups per vertex is a scary thought, you can always blend the two concepts based on distance from camera. Following the technique described in “Large Scale Terrain” each of my “rings” of terrain is rendered as a single pass each and can swap shader techniques for each “ring” – in the following I render the nearest rings as bicubic and the more distant ones as linear, saving a lot of texture lookups and hopefully retaining the high detail and high cost bicubic lookup for the terrain that really matters – the one close to the viewer.

image

For reference; a good source of HLSL interpolation code is here http://code.google.com/p/mcore3d/source/browse/trunk/MCD/Render/DX9/interpolation.hlsl?spec=svn1050&r=1050

Advertisements

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