Terrain LOD for DirectX 10 Graphics Cards, using SlimDX and Direct3D 11

Last time, we discussed terrain rendering, using the tessellation stages of the GPU to render the terrain mesh with distance-based LOD.  That method required a DX11-compliant graphics card, since the Hull and Domain shader stages are new to Direct3D11.  According to the latest Steam Hardware survey, nearly 65% of gamers have a DX11 graphics card, which is certainly the majority of potential users, and only likely to increase in the future.  Of the remaining 35% of gamers, 31% are still using DX10 graphics cards.  While we can safely ignore the small percentage of the market that is still limping along on DX9 cards (I myself still have an old laptop with a GeForce Go 7400 in my oldest laptop, but that machine is seven years old and on its last legs), restricting ourselves to only DX 11 cards cuts out a third of potential users of your application.  For that reason, I’m going to cover an alternative, CPU-based implementation of our previous LOD terrain rendering example.  If you have the option, I would suggest that you only bother with the previous DX11 method, as tessellating the terrain mesh yourself on the CPU is relatively more complex, prone to error, less performant, and produces a somewhat lower quality result; if you must support DX10 graphics cards, however, this method or one similar to it will do the job, while the hull/domain shader method will not.

We will be implementing this rendering method as an additional render path in our Terrain class, if we detect that the user has a DX10 compatible graphics card.  This allows us to reuse a large chunk of the previous code.  For the rest, we will adapt portions of the HLSL shader code that we previously implemented into C#, as well as use some inspirations from Chapter 4 of Carl Granberg’s Programming an RTS Game with Direct3D.  The full code for this example can be found at my GitHub repository, https://github.com/ericrrichards/dx11.git, under the TerrainDemo project.

Dynamic Terrain Rendering with SlimDX and Direct3D 11

A common task for strategy and other games with an outdoor setting is the rendering of the terrain for the level.  Probably the most convenient way to model a terrain is to create a triangular grid, and then perturb the y-coordinates of the vertices to match the desired elevations.  This elevation data can be determined by using a mathematical function, as we have done in our previous examples, or by sampling an array or texture known as a heightmap.  Using a heightmap to describe the terrain elevations allows us more fine-grain control over the details of our terrain, and also allows us to define the terrain easily, either using a procedural method to create random heightmaps, or by creating an image in a paint program.

Because a terrain can be very large, we will want to optimize the rendering of it as much as possible.  One easy way to save rendering cycles is to only draw the vertices of the terrain that can be seen by the player, using frustum culling techniques similar to those we have already covered.  Another way is to render the mesh using a variable level of detail, by using the Hull and Domain shaders to render the terrain mesh with more polygons near the camera, and fewer in the distance, in a manner similar to that we used for our Displacement mapping effect.  Combining the two techniques allows us to render a very large terrain, with a very high level of detail, at a high frame rate, although it does limit us to running on DirectX 11 compliant graphics cards.

We will also use a technique called texture splatting to render our terrain with multiple textures in a single rendering call.  This technique involves using a separate texture, called a blend map, in addition to the diffuse textures that are applied to the mesh, in order to define which texture is applied to which portion of the mesh. 

The code for this example was adapted from Chapter 19 of Frank Luna’s Introduction to 3D Game Programming with Direct3D 11.0, with some additional inspirations from Chapter 4 of Carl Granberg’s Programming an RTS Game with Direct3D.  The full source for this example can be downloaded from my GitHub repository, at https://github.com/ericrrichards/dx11.git, under the TerrainDemo project.

Diving into the Tessellation Stages of Direct3D 11

In our last example on normal mapping and displacement mapping, we made use of the new Direct3D 11 tessellation stages when implementing our displacement mapping effect.  For the purposes of the example, we did not examine too closely the concepts involved in making use of these new features, namely the Hull and Domain shaders.  These new shader types are sufficiently complicated that they deserve a separate treatment of their own, particularly since we will continue to make use of them for more complicated effects in the future.

The Hull and Domain shaders are covered in Chapter 13 of Frank Luna’s Introduction to 3D Game Programming with Direct3D 11.0, which I had previously skipped over.  Rather than use the example from that chapter, I am going to use the shader effect we developed for our last example instead, so that we can dive into the details of how the hull and domain shaders work in the context of a useful example that we have some background with.

The primary motivation for using the tessellation stages is to offload work from the the CPU and main memory onto the GPU.  We have already looked at a couple of the benefits of this technique in our previous post, but some of the advantages of using the tessellation stages are:

• We can use a lower detail mesh, and specify additional detail using less memory-intensive techniques, like the displacement mapping technique presented earlier, to produce the final, high-quality mesh that is displayed.
• We can adjust the level of detail of a mesh on-the-fly, depending on the distance of the mesh from the camera or other criteria that we define.
• We can perform expensive calculations, like collisions and physics calculations, on the simplified mesh stored in main memory, and still render the highly-detailed generated mesh.

The Tessellation Stages

The tessellation stages sit in the graphics pipeline between the vertex shader and the geometry shader.  When we render using the tessellation stages, the vertices created by the vertex shader are not really the vertices that will be rendered to the screen; instead, they are control points which define a triangular or quad patch, which will be further refined by the tessellation stages into vertices.  For most of our usages, we will either be working with triangular patches, with 3 control points, or quad patches, with 4 control points, which correspond to the corner vertices of the triangle or quad.  Direct3D 11 supports patches with up to 32 control points, which might be suitable for rendering meshes based on Bezier curves.

The tessellation stages can be broken down into three component stages:

• Hull Shader Stage – The hull shader operates on each control point for a geometry patch, and can add, remove or modify its input control points before passing the patch onto the the tessellator stage.  The Hull shader also calculates the tessellation factors for a patch, which instruct the tessellator stage how to break the patch up into individual vertices.  The hull shader is fully programmable, meaning that we need to define an HLSL function that will be evaluated to construct the patch control points and tessellation factors.
• Tessellator Stage – The tessellator stage is a fixed-function (meaning that we do not have to write a shader for it) stage, which samples the input patch and generates a set of vertices that divide the patch, according to the tessellation factors supplied by the hull shader and a partitioning scheme, which defines the algorithm used to subdivide the patch.  Vertices created by the tessellator are normalized; i.e. quad patch vertices are specified by referring to them by their (u,v) coordinates on the surface of the quad, while triangle patch vertices use barycentric coordinates to specify their location within the triangle patch.
• Domain Shader Stage – The domain shader is a programmable stage (we need to write a shader function for it), which operates on the normalized vertices input from the tessellator stage, and maps them into their final positions within the patch.  Typically, the domain shader will interpolate the final vertex value from the patch control points using the uv or barycentric coordinates output by the tessellator.  The output vertices from the domain shader will then be passed along to the next stage in the pipeline, either the geometry shader or the pixel shader.

With these definitions out of the way, we can now dive into the displacement mapping effect from our previous example and examine just how the tessellation stages generate the displacement mapped geometry we see on the screen.

First, let’s take a look at one of the techniques we have defined in our DisplacementMap.fx shader.  The Light1 technique is probably our most basic technique, using only a single directional light and no advanced pixel shading techniques.

technique11 Light1
{
    pass P0
    {
        SetVertexShader( CompileShader( vs_4_0, VS() ) );
        SetHullShader( CompileShader( hs_5_0, HS() ) );
        SetDomainShader( CompileShader( ds_5_0, DS() ) );
        SetGeometryShader( NULL );
        SetPixelShader( CompileShader( ps_4_0, PS(1, false, false, false, false) ) );
    }
}

Notice that in addition to setting the vertex and pixel shaders as we have done in our Basic.fx shader, we also have to set the hull and domain shader.  These two stage operate as a pair; you should always have a hull shader if you have a domain shader, and vice-versa. 

Setting up to Render with the DisplacementMap Effect

To draw our geometry correctly with the tessellation stages, we have to instruct the GPU that the data in our vertex buffers defines a triangle patch, rather than a simple triangle.  Thus, we have to set the PrimitiveTopology to one of the PatchListWithXControlPoints enumeration members, rather than TriangleList.

ImmediateContext.InputAssembler.PrimitiveTopology = PrimitiveTopology.PatchListWith3ControlPoints;

Vertex Shader

Remember that our vertex buffer data, when using the tessellation stages, defines the control points of a patch, rather than actual vertices.  Besides the normal transformations that we would perform on a vertex, we also will need to calculate any control values that the tessellation stages will need for control points.  For our displacement mapping effect, this is a per-vertex tessellation factor, based on the distance of the vertex from the camera viewpoint.

struct VertexOut
{
    float3 PosW       : POSITION;
    float3 NormalW    : NORMAL;
    float3 TangentW   : TANGENT;
    float2 Tex        : TEXCOORD;
    float  TessFactor : TESS;
};

VertexOut VS(VertexIn vin)
{
    VertexOut vout;
    
    // Transform to world space space.
    vout.PosW     = mul(float4(vin.PosL, 1.0f), gWorld).xyz;
    vout.NormalW  = mul(vin.NormalL, (float3x3)gWorldInvTranspose);
    vout.TangentW = mul(vin.TangentL, (float3x3)gWorld);

    // Output vertex attributes for interpolation across triangle.
    vout.Tex = mul(float4(vin.Tex, 0.0f, 1.0f), gTexTransform).xy;
    
    float d = distance(vout.PosW, gEyePosW);

    // Normalized tessellation factor. 
    // The tessellation is 
    //   0 if d >= gMinTessDistance and
    //   1 if d <= gMaxTessDistance.  
    float tess = saturate( (gMinTessDistance - d) / (gMinTessDistance - gMaxTessDistance) );
    
    // Rescale [0,1] --> [gMinTessFactor, gMaxTessFactor].
    vout.TessFactor = gMinTessFactor + tess*(gMaxTessFactor-gMinTessFactor);

    return vout;
}

Hull Shader

Our hull shader actually consists of two parts: one portion that runs per control point that is to be output, transforming the input control points from the vertex shader into the form expected by the domain shader, and a parallel portion that computes the per-patch constants that instruct the tessellator stage how to subdivide the patch.  The first component is our hull shader proper, while the second is called the patch constant function.

For our DisplacementMap effect, our hull shader simply passes through the control points from the vertex shader, stripping off the TessFactor element, as only the hull shader cares about that information.  Our hull shader has visibility into all of the control points comprising the patch in the InputPatch parameter, with the control point currently being processed indexed by the SV_OutputControlPointID semantic parameter.  The index of the patch being processed can also be accessed using the SV_PrimitiveID semantic parameter.

struct HullOut
{
    float3 PosW     : POSITION;
    float3 NormalW  : NORMAL;
    float3 TangentW : TANGENT;
    float2 Tex      : TEXCOORD;
};

[domain("tri")]
[partitioning("fractional_odd")]
[outputtopology("triangle_cw")]
[outputcontrolpoints(3)]
[patchconstantfunc("PatchHS")]
HullOut HS(InputPatch<VertexOut,3> p, 
           uint i : SV_OutputControlPointID,
           uint patchId : SV_PrimitiveID)
{
    HullOut hout;
    
    // Pass through shader.
    hout.PosW     = p[i].PosW;
    hout.NormalW  = p[i].NormalW;
    hout.TangentW = p[i].TangentW;
    hout.Tex      = p[i].Tex;
    
    return hout;
}

The hull shader declaration has a number of attributes applied to it, which serve different purposes.

• [domain(domain_type)] – The domain attribute defines the type of patch used by the hull shader.  Valid values in DX11 are “tri”, “quad” or “isoline.”  This domain hints to the tessellator how to subdivide the patch, as well as indicating the coordinate system used to specify the point sampled from the patch; a 2D UV coordinate if using quad or isoline, and a 3D barycentric coordinate if using tri.


• [partitioning(partition_scheme)] – This attribute instructs which partitioning scheme the tessellator should follow when it subdivides the patch.  Valid values are:




• integer – The tessellation factor is always rounded up to the nearest integral value, in the range [1..64]


• pow2 – The tessellation is rounded to the next greatest power of 2, yielding the effective range [1, 2, 4, 8, 16, 32, 64]


• fractional_even – The tessellation is rounded up to the next even integer, however, the samples will be spaced differently, depending on the fractional component, resulting in smaller triangles for two of the strips of vertices. 


• fractional_odd – Similar to fractional_even, except the tessellation factor is rounded to the next odd integer, i.e. [1, 3, 5..63]


• [outputtopology(topology)] – This attribute specifies the type of primitive the tessellator generates.  Valid values are “point”, “line”, “triangle_cw” and “triangle_ccw.”  The last two primitive types specify the winding order of the triangles produced (c)lock(w)ise or (c)ounter-(c)lock(w)ise.


• [outputcontrolpoints(n)] – This attribute specifies the number of control points the hull shader outputs per patch.  In our examples, this will match the number of input coordinates, but you could output more or less control points per patch, if you desired.


• [patchconstantfunc(“function_name”)] – The attribute specifies the name of the patch constant function, which will be evaluated once per patch and set the inner and outer tessellation factors, as well as any other per-patch data.  We’ll cover this in more detail in just a bit.


• [maxtessfactor(f)] – We don’t use this attribute here, but if we know the maximum tessellation factor that we will compute for the patch, then we can specify it here, which may allow the GPU to make certain optimizations.

Patch Constant Function

The primary role of the patch constant function is to compute the tessellation factor that will instruct the tessellator how much to subdivide the patch.  This constant function will most likely be unique to your particular application, and highly dependent on the particular domain used.  The tessellation factors required for each particular domain are different:

struct TriTess {
    float EdgeTess[3] : SV_TessFactor;
    float InsideTess  : SV_InsideTessFactor;
}
struct QuadTess {
    float EdgeTess[4] : SV_TessFactor;
    float InsideTess[2]  : SV_InsideTessFactor;
}
struct IsolineTess{
    float DensityDetail[2] : SV_TessFactor;
}

For triangles, we have a tessellation factor for each edge, and an interior tessellation factor; for quads, an exterior tessellation factor for each edge and two factors for the interior factor (rows and columns), while for isolines, we have a density factor, which controls the number of instances of the line that are created, and a detail factor, which controls the number of points in the line.

If we wanted to ignore a patch and not display it to the screen, for instance, if we implemented frustum culling in the hull shader, we can specify a tessellation factor <= 0.  This will cull the entire patch.

The patch constant takes as an input an InputPatch consisting of the control points for the patch, and an integer id, which identifies the patch.

In our DisplacementMap effect, we average the edge tessellation factors of our control points, and select one of these values for the interior tessellation factor. 

struct PatchTess
{
    float EdgeTess[3] : SV_TessFactor;
    float InsideTess  : SV_InsideTessFactor;
};

PatchTess PatchHS(InputPatch<VertexOut,3> patch, 
                  uint patchID : SV_PrimitiveID)
{
    PatchTess pt;
    
    // Average tess factors along edges, and pick an edge tess factor for 
    // the interior tessellation.  It is important to do the tess factor
    // calculation based on the edge properties so that edges shared by 
    // more than one triangle will have the same tessellation factor.  
    // Otherwise, gaps can appear.
    pt.EdgeTess[0] = 0.5f*(patch[1].TessFactor + patch[2].TessFactor);
    pt.EdgeTess[1] = 0.5f*(patch[2].TessFactor + patch[0].TessFactor);
    pt.EdgeTess[2] = 0.5f*(patch[0].TessFactor + patch[1].TessFactor);
    pt.InsideTess  = pt.EdgeTess[0];
    
    return pt;
}

Tessellator Stage

We do not have to write any code for the tessellator, as it is a purely fixed-function component.  We have already set all of the state for the tessellator, as attributes on our hull shader function.

Domain Shader Stage

The domain shader is invoked for each vertex generated by the tessellator.  The inputs for the domain shader are the patch constant data, computed per-patch by the hull shader patch constant function, the normalized position of the generated vertex within the patch, generated by the tessellator, and the control points of the patch, as returned by the main hull shader.  Generally, we will want to interpolate the final vertex data from the tessellated position and the patch control points.  Often, we will then modify this vertex data, for instance by sampling a texture and modifying the vertex position, as simply tessellating the patch will not add any additional detail.

For our DisplacementMap effect, we sample the heighmap stored in the alpha channel of the normal map, and offset the vertex position along the vertex normal using this value.  Note that we must project the vertex position into clip space using the camera’s view-projection matrix in the domain shader after we have modified the vertex world position.  Also note that we have to select the mip-map level of the texture to sample ourselves, using the Texture2D.SampleLevel method, since the Sample method we have used previously is only available in the pixel shader stage.

After passing through the domain shader stage, the generated vertices are passed to the pixel shader and processed as usual.