Organic Vectory

 
  • Increase font size
  • Default font size
  • Decrease font size

Shadow mapping on large terrain

 

Introduction

This article will describe a number of enhancements to the original shadow mapping technique to make it more suitable for application on large terrain. A basic understanding of the shadow-mapping technique and graphics programming in general is assumed. The original shadow-mapping technique will not be explained, only the transition to FBOs and shaders. Numerous resources can be found on the web.

Optimizations like “Light Space Projective Shadow Mapping” (LiSPSM) or “Trapezoidal Shadow Mapping” (TSM) can also be adopted in conjunction but are not explained in this article.

The techniques are render API independent. The implementation this article is based on however uses OpenGL. The article will use the OpenGL 2.0 API to explain the technical implementation.

Organic Vectory uses their planetary terrain triangulation library ovPlanet. The library generates a spherical grid. This introduces some extra matrix math since the shortcut “Y is up” is no longer valid. As this is not particular to other terrain rendering implementations that use planar grids, the extra transformation is not explained in this article. Another issue that rises when using realistic planet sizes is precision. The implementation used for this article uses ovPlanet with earth data and realistic earth radius. Therefore everything is rendered in view local space.


Objective

The objective is to develop a method for high quality soft-shadows on terrain of planetary scale. This boils down to; how can I use the available depth-map precision so that it is applied in the area most beneficial to the viewer.

The techniques presented demand the power and flexibility of modern 3D hardware (programmable GPU). They therefore will be implemented using shaders.


Basic technique

In the past few years shadowing has become a more and more common technique to increase image quality and visual feedback in real-time 3D graphics. Two techniques are popular, “Stencil shadows” and “Projective Shadow Mapping” (PSM). Both have their advantages and disadvantages.

Stencil shadows:

Advantages:

- Shadowed area is lit correctly

- In/out shadow test is viewpoint independent, frame-buffer quality

Disadvantages:

- Fast soft-shadows are difficult to do

- Edge detection needed, not mesh complexity independent

- Only shadows from polygons

- A lot of work for CPU

Shadow mapping:

Advantages:

- Soft-shadowing is straight forward

- Bit-masked polygons can cast shadows too.

- Less administration needed, easier to implement

- Mesh complexity independent

- Mostly GPU

Disadvantages:

- Viewpoint dependant shadow test, quality is not constant

- Aliasing

- Large depth-maps needed for decent quality

- Different approach needed for each light type

Since the introduction of the programmable GPU, both power and the flexibility to use pixel maps have hugely increased. More and more techniques used today rely on the hardware’s capability to process pixel maps.

This development made the disadvantages of shadow-mapping smaller. Complex techniques to reduce shadow-mapping drawbacks could be discarded in some cases.

In the light of that development and because of the advantages of the technique, shadow-mapping is a good choice for shadowing on large terrain.

A clear and to the point tutorial on the basic shadow-mapping technique using OpenGL and shaders can be found here:

Carnegie Mellon University (The page seems to to be removed)

Soft shadowing

Soft shadowing can greatly improve the illusion. On modern hardware it is possible to “fake” the effect of light scattering on shadow casting.

A few methods:

  1. Multi pass with alterating light position/direction
  2. Full screen blur of shadow only scene, then combine with main scene
  3. Percentage closer filtering

Option one isn’t actually an option for real-time application. It is not scalable and the amount of passes needed to get decent soft-shadows it far to high.

Option two is a viable technique. The softness however is fixed. Shadows will not get blurrier farther away from the caster. This may not be too bad for many applications though.

Advantage is that it can benefit from other full screen post processing, like HDR or bloom.

Option three stays close to the shadow-mapping algorithm and it can handle the penumbra more realistic then option 2.

In this document the third technique for producing soft shadows will be used.

When NVidia hardware is used, we can benefit from NVidia’s hardware filtering.


Problems to solve

To meet the demands we have to consider the following:

Large terrain

Our terrain engine allows for vast, to the horizon rendering of terrain. Preferable the shadowing should be able to keep up with this or at least be able to cover a big portion (measured in screen-space) of the terrain.

Scalability

Our terrain rendering allows for smooth transition from space to high altitude to on the surface viewpoints. We want to maintain this so the shadowing will have to be capable of this too and meanwhile maintain good quality shadows.

Image quality

For shadows to contribute successfully to the visual simulation, it should not stand out. They should be subtle and realistic. In practice this translates to sufficiently high resolution shadow-maps and the application of filtering. Combining this with the other demands can be a challenge.

Performance

Meeting the other demands is only useful if a good frame-rate is maintained. Also, enough GPU/CPU/memory resources should remain for other features.


Solutions

Large terrain

To maintain quality and performance we have to restrict shadowing to a limited area of interest. This area of interest should be linked to the view position.

Since our light source is assumed to be very far away, we can discard its position and only regard its direction. We then can use an orthogonal projection when generating the depth-map. This causes the frustum to become a box.

To focus on the proximity/vicinity of the viewer, we have this box follow the viewer position.

Scalability

With a fixed orthogonal projection box the area on the terrain that is shadowed is also fixed. Since we allow completely zoomed in and out views of the planet the shadow area should adapt.

This is easily accomplished by scaling the orthogonal projection box relative to the viewers distance from the surface. The dept-map will automatically cover a larger/smaller area on the surface. Scaling the box relative to the ground-clearance also keeps the amount of terrain that has shadows, measured in screen-space, constant.

Having the same resolution depth-map for a larger area will decrease the quality of the shadows. But since the distance of the viewer to the shadows will also be bigger, the image quality will not suffer.

Obviously, at some altitude shadows should fadeout completely and be disabled.

Image quality

Most important is to have a sufficiently large depth-map. As we adapt the shadow area relative to the ground-clearance, there is no need for a multi-depth-map (tiled) implementation to cover larger terrain areas with shadows when the viewpoint changes. We can therefore afford to have a large depth-map of for example 4096x4096 pixels if the hardware so permits.

In such cases even the need for more complex TSM or LiSPSM implementations to counter aliasing may be omitted.

Another technique to improve image quality is the use of filtering. It will emulate realistic shadows more convincing and it can further mask any aliasing that may be noticed otherwise. On some video cards it is possible to enable automatic hardware filtering. Combining this with PCF filtering gives a very smooth result.








Finally we will fade-in/out shadows at the border of the shadow area. This will prevent shadows appearing suddenly which would spoil the illusion.

Fade shadow at shadow area border

Shadow fade-out

Fade-out area in red

Fade-out area in red

Shadow fade-out close-up

Fade-out close-up

Performance

To maintain a good frame-rate and to keep resource use to a minimum the following will be used:

  1. Use smart branching to link the filter kernel size to the fragment’s eye-distance.
  2. Limited shadowing area (orthogonal projection box)
  3. Use lower detail objects and LOD for depth-map generation
  4. Minimise fragment complexity, only depth-values matter
  5. Cull shadow casters to the orthogonal projection box

Since the other optimizations are assumed common knowledge, only the first two will be explained in this article.


Implementation

The shadow mapping algorithm for the fixed functionality in steps (details left out):

1. Preparation

Prepare depth map texture

Prepare filter kernels

Prepare a FBO for shadowing


2. Depth map generation

Calculate shadowing area size

Set orthogonal projection

Calculate and set model-view matrix

Activate FBO and depth map

Render shadow casters to depth map

Deactivate FBO and depth map


3. Shadow rendering

Bind depth map

Set texture parameters for shadow test

Activate shader

Transfer light matrix info to shader

Transfer depth map texture unit to shader

Transfer filter kernels to shader

Draw terrain

Deactivate shader

Stage 1 can be done once at application start up.

Stages 2 and 3 are repeated every frame.

Implementation issue resolution

A few problems have to be solved that are particular to this implementation, or the used graphics API.

Restrictions in shaders for loops

This applies to filter kernel selection.

Version 1.10 of the OpenGL shading language does not allow array indices that are not resolved compile time. In practice this means that the following will not compile:

int RunTimeVariable = 0;

for (int l_Index = 0; l_Index < RunTimeVariable; l_Index++)

{

vec4 l_Stub[l_Index];

}

That gives us a problem for our variable filter kernel.

How many sample offsets we want to access in the array depends on the distance of the fragment to the eye, which is determined run-time.

This code will compile:

#define COMPILE_TIME_VARIABLE 0

for (int l_Index = 0; l_Index < COMPILE_TIME_VARIABLE; l_Index++)

{

vec4 l_Stub[l_Index];

}

The rather laborious solution is to define kernel sizes and to use separate for-loops for every one of them. Then selecting which loop to use runtime.

Reduce bleeding

By reversing winding when rendering to depth-map bleeding can be reduced. A more robust method that offers more control is using polygon offsetting.

Slightly bigger sample offsets for filtering then one texel for better smoothing.

Keep your matrixes normalized!


Depth map clamp behaviour

Shadow intersecting the depthmap border is streched out

Many resources on the web specify the depth-map to clamp to the edge of the map. This is ok as long as the projected depth-map covers the entire (visible scene). In our case however, shadowing is applied to only a portion of the visible terrain. With “clamp to border” this would make shadows intersecting the edge of the depth-map to be stretched over the non shadowed portion of the terrain.

We need to force “always out of shadow” for the area we do not include in shadowing. This is done by having the texture clamp to the border and setting a border colour that would be translated to “out of shadow”.

char l_ClampColor[] = {1.0, 1.0, 1.0, 1.0};

glTexParameterfv(GL_TEXTURE_2D, GL_TEXTURE_BORDER_COLOR, l_ClampColor);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_CLAMP_TO_BORDER);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_BORDER);

Depth-map generation

Prepare the depth map texture

glBindTexture(GL_TEXTURE_2D, ShadowMap);

glTexImage2D(GL_TEXTURE_2D, 0, GL_DEPTH_COMPONENT, *ShadowMapWidth, *ShadowMapHeight, 0, GL_DEPTH_COMPONENT, GL_UNSIGNED_INT, NULL);

glTexParameteri(GL_TEXTURE_2D, GL_DEPTH_TEXTURE_MODE, GL_LUMINANCE);

Preparing the filter kernel(s)

The following image shows when different filter kernels are used.

Green : 5x5 kernel

Yellow : 4x4 kernel

Orange : 3x3 kernel

Red : 2x2 kernel

Blue : 1x1 kernel (no filtering)

At different distances, different filter kernels are used

Preparing kernels can be done once at start-up. To limit the amount of work to be done in the shader we want to organize the sample offsets in the array so that accessing the first N samples in the array will give the coordinates for a MxM=N kernel filter matrix.

Example:

// Each entry has a S and a T offset

float ShadowSampleOffsets[MAX_KERNEL_SIZE*2];

// The depth-map is assumed to be square

float ShadowSampleStride = 1.0f/ShadowMapWidth;

// center

ShadowSampleOffsets[0] = 0.0f;

ShadowSampleOffsets[1] = 0.0f;

// 2x2

ShadowSampleOffsets[2] = ShadowSampleStride;

ShadowSampleOffsets[3] = 0.0f;

ShadowSampleOffsets[4] = ShadowSampleStride;

ShadowSampleOffsets[5] = ShadowSampleStride;

ShadowSampleOffsets[6] = 0.0f;

ShadowSampleOffsets[7] = ShadowSampleStride;

// 3x3

ShadowSampleOffsets[8] = -ShadowSampleStride;

ShadowSampleOffsets[9] = ShadowSampleStride;

ShadowSampleOffsets[10] = -ShadowSampleStride;

ShadowSampleOffsets[11] = 0.0;

ShadowSampleOffsets[12] = -ShadowSampleStride;

ShadowSampleOffsets[13] = -ShadowSampleStride;

ShadowSampleOffsets[14] = 0.0;

ShadowSampleOffsets[15] = -ShadowSampleStride;

ShadowSampleOffsets[16] = ShadowSampleStride;

ShadowSampleOffsets[17] = -ShadowSampleStride;

// etc.

Bleu : Added for centre

Green : Added for 2x2

Red : Added for 3x3

Yellow : Added for 4x4

Magenta : Added for 5x5


























The FBO

Prepare the FBO for shadowing

glGenFramebuffersEXT(1, &m_FrameBuffer);

glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, m_FrameBuffer);

GLuint l_RenderBuffer = 0;

glGenRenderbuffersEXT(1, &l_RenderBuffer);

glBindRenderbufferEXT(GL_RENDERBUFFER_EXT, l_RenderBuffer);

glRenderbufferStorageEXT(GL_RENDERBUFFER_EXT, GL_RGB8, p_Size, p_Size);

glFramebufferRenderbufferEXT(GL_FRAMEBUFFER_EXT, GL_COLOR_ATTACHMENT0_EXT, GL_RENDERBUFFER_EXT, l_RenderBuffer);

glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);

Use FBO

glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, ShadowBuffer);

glFramebufferTexture2DEXT(GL_FRAMEBUFFER_EXT, GL_DEPTH_ATTACHMENT_EXT, GL_TEXTURE_2D, ShadowMap, 0);

glViewport(0, 0, ShadowMapWidth, ShadowMapHeight);

glClear(GL_DEPTH_BUFFER_BIT);

RenderShadowCasters();

glBindFramebufferEXT(GL_FRAMEBUFFER_EXT, 0);

glViewport(0, 0, ContextWidth, ContextHeight);

Orthogonal projection

Shadow area at view altitude of 15 meters

Shadow area and ortho-projection box at altitude of 15 meters

Shadow area at view altitude of 50 meters

Shadow area and ortho-projection box at altitude of 50 meters

Shadow area at view altitude of 100 meters

Shadow area and ortho-projection box at altitude of 100 meters

Shadow area at view altitude of 200 meters

Shadow area and ortho-projection box at altitude of 200 meters

TODO: The size of the box

TODO: Placement of ortho box relative to viewer and terrain

TODO: Updating the box

Applying shadows to the scene

Setup the depth-map

Before we can use the depth-map in the shader we have to set the correct texture parameters so we can use the convenient shadow compare functions in the shader.

glActiveTexture(ShadowMapUnit);

glEnable(GL_TEXTURE_2D);

glBindTexture(GL_TEXTURE_2D, ShadowMap);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_MODE, GL_COMPARE_R_TO_TEXTURE);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_COMPARE_FUNC, GL_LEQUAL);

Shader

These shots clearly show the penumbra area:

Shadow penumbra in red

Filtering is needed in the red area

Red : Penumbra area

Green : Full shadow

In the following shader, texturing and lighting is kept simple. The focus is on shadowing.

Vertex shader

#version 110

//*** Variables for fragment shader

varying float m_LightIntensity;

varying vec3 m_FragPos;

void main(void)

{

vec4 l_Position = gl_ModelViewMatrix * gl_Vertex;

m_FragPos = l_Position.xyz;

gl_TexCoord[0] = gl_MultiTexCoord0;

gl_TexCoord[1] = gl_TextureMatrix[1] * l_Position;

//*** Do lighting

vec3 l_Normal = normalize(gl_NormalMatrix * gl_Normal);

// GL_LIGHT0 is a directional light

m_LightIntensity = max(0.0, dot(l_Normal, normalize(gl_LightSource[0].position.xyz)));

gl_Position = ftransform();

}

Fragment shader

The function “SoftShadowFetch” returns a float [0.0, 1.0] that indicates how much the fragment is in light.

#version 110

// Shadow map sample count for PCF

#define PCF_SAMPLE_COUNT_25 25

#define PCF_SAMPLE_COUNT_16 16

#define PCF_SAMPLE_COUNT_9 9

#define PCF_SAMPLE_COUNT_4 4

#define PCF_SAMPLE_COUNT_1 1

// Shadow filter borders

#define SHADOW_BORDER_1 8.0

#define SHADOW_BORDER_2 16.0

#define SHADOW_BORDER_3 32.0

#define SHADOW_BORDER_4 64.0

// Make position in object space available in fragment shader

varying vec3 m_FragPos;

// The light intensity is calculated in the vertex shader

varying float m_LightIntensity;

// At what distance from the eye shadowing stops

uniform float g_ShadowRadius;

// The diffuse map

uniform sampler2D g_TextureMap;

// The depth map

uniform sampler2DShadow g_ShadowMap;

// The 5x5 PCF filter kernel

uniform vec2 g_ShadowSampleOffsets[PCF_SAMPLE_COUNT_25];

float

SoftShadowFetch(float p_Distance)

{

float l_RetVal = 0.0;

// Depth map coordinates are stored on unit 1

vec3 l_ShadowCoord = (gl_TexCoord[1].xyz/gl_TexCoord[1].q);

vec3 l_ShadowCoordOffset = l_ShadowCoord;

// Best quality near by

int l_Index = 0;

if (p_Distance < SHADOW_BORDER_1)

{

for (l_Index = 0; l_Index < PCF_SAMPLE_COUNT_25; l_Index++)

{

l_ShadowCoordOffset.st = l_ShadowCoord.st + g_ShadowSampleOffsets[l_Index].st;

l_RetVal += shadow2D(g_ShadowMap, l_ShadowCoordOffset).r / float(PCF_SAMPLE_COUNT_25);

}

}

else if (p_Distance < SHADOW_BORDER_2)

{

for (l_Index = 0; l_Index < PCF_SAMPLE_COUNT_16; l_Index++)

{

l_ShadowCoordOffset.st = l_ShadowCoord.st + g_ShadowSampleOffsets[l_Index].st;

l_RetVal += shadow2D(g_ShadowMap, l_ShadowCoordOffset).r / float(PCF_SAMPLE_COUNT_16);

}

}

else if (p_Distance < SHADOW_BORDER_3)

{

for (l_Index = 0; l_Index < PCF_SAMPLE_COUNT_9; l_Index++)

{

l_ShadowCoordOffset.st = l_ShadowCoord.st + g_ShadowSampleOffsets[l_Index].st;

l_RetVal += shadow2D(g_ShadowMap, l_ShadowCoordOffset).r / float(PCF_SAMPLE_COUNT_9);

}

}

else if (p_Distance < SHADOW_BORDER_4)

{

for (l_Index = 0; l_Index < PCF_SAMPLE_COUNT_4; l_Index++)

{

l_ShadowCoordOffset.st = l_ShadowCoord.st + g_ShadowSampleOffsets[l_Index].st;

l_RetVal += shadow2D(g_ShadowMap, l_ShadowCoordOffset).r / float(PCF_SAMPLE_COUNT_4);

}

}

else // No filtering

{

l_RetVal = (shadow2DProj(g_ShadowMap, gl_TexCoord[1]).r < 1.0 ? 0.0 : 1.0);

}

// Fade out at border of shadow area (last 10 %)

if (l_RetVal < 1.0) // Only do fading if fragment is in shadow

{

// Start fadeout at 90% from the shadow border

float l_FadeStart = g_ShadowRadius * 0.9;

// If the fragement is inside the fade area...

if (p_Distance > l_FadeStart)

{

l_RetVal = max((p_Distance - l_FadeStart)/

(g_ShadowRadius - l_FadeStart),

l_RetVal);

}

}

return clamp(l_RetVal, 0.0, 1.0);

}

void main (void)

{

vec4 l_Colour;

// Calculate the distance of the fragment to the eye

float l_EyeDistance = length(m_FragPos.xyz);

//*** Texturing

l_Colour = texture2D(g_TextureMap, gl_TexCoord[0].st);

//*** Shadowing

float l_InLight = SoftShadowFetch(l_EyeDistance);

//*** Lighting

// Combine lighting with shadowing

L_InLight *= m_LightIntensity;

// Combine lighting with diffuse colour

l_Colour *= (gl_LightSource[0].ambient + (gl_LightSource[0].diffuse * L_InLight));

l_Colour.a = 1.0;

gl_FragColor = l_Colour;

}


Optimizations

- First filter one dimension then the other. TODO

- Use random sample locations to reduce kernel size TODO

- Restrict multi sampling to penumbra TODO

- Make good use of hardware PCF filtering on NVidia by using shadow sampling functions in the shader and:

glTexParameteri(GL_TEXTURE_2D, GL_DEPTH_TEXTURE_MODE, GL_LUMINANCE);

glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR);

for the depthmap.

Plain shadowing without filtering

No filtering

Shadowing with PCF filtering

PCF filtering

Shadowing with PCF and hardware filtering

PCF & Hardware filtering


See NVidia forum: Kevin Bjorke: “
On NVIDIA hardware, simply declaring a surface as a SHADOWMAP format --e.g., D24S8_SHADOWMAP -- lets the driver know to set up the appropriate filtering for you and all you need to do is call tex2Dproj() in HLSL. The result is filtered automatically.”

Also see: http://http.download.nvidia.com/developer/presentations/2005/SIGGRAPH/Percentage_Closer_Soft_Shadows.pdf


The result

The final result


The final result

The final result

Future improvements

- Separate shadow-map (lower definition) for terrain shadows

- Point or spot-light light sources

- Multiple combined light sources

- It shouldn’t be too difficult to build in support for different amounts of softness in the shadows. This way, for a clear day, less soft shadows can be produced and for a cloudy day, softer shadows. Or in general, dependant on how dispersed the light is.


References

- Doug L. James: http://www.cs.cornell.edu/~djames/

Carnegie Mellon University: http://www.cs.cmu.edu/afs/cs/academic/class/15462/web.06s/asst/project3/shadowmap/

- GPU Gems 2

- TSM (http://www.comp.nus.edu.sg/~tants/tsm.html)

- LiSPSM (http://www.cg.tuwien.ac.at/research/vr/lispsm/)

- Stencil shadows (http://www.opengl.org/resources/code/samples/mjktips/rts/index.html)

- ovPlanet (http://www.organicvectory.com/planet/planet_index.html)

- OpenGL (http://OpenGL.org)

- Shadows in computer graphics paper publication listing: http://artis.imag.fr/Membres/Xavier.Decoret/bib/shadows/