In the last part of this series we outlined the algorithm that our lighting system will be using, as well as writing some of the code for our Light Renderer class. If you haven’t already done you’ll need to go back and work through that part, otherwise I’m afraid this tutorial won’t make a lot of sense!

There are still some fairly big gaps to fill in our system, namely the shaders that will be doing all of the work, as well as some of the code that supports these shaders. Over the next few parts of the series we’ll be focussing on writing these shaders, and adding them to our system.

To start with we will be looking at PointLights.

PointLights and SpotLights, whilst similar, require different shaders to unwrap their rays into the columns of our render target ‘unwrapTarget’. This might seem odd at first. Surely a PointLight is just a SpotLight with an arc of 360 degress?

Well, yes, and we could have written our shaders that way, but it would have made our lives (and the lives of any other programmer using our system) rather complicated. In fact, it turns out that because PointLights always light a full 360 degrees around them, that their shaders are rather simpler than those of SpotLights. Let’s have a look at why this is.

**The PointLight ‘Unwrap’ algorithm**

With SpotLights we have to determine for each pixel whether it is inside or outside the arc of the light, as those outside of this arc won’t lie on any of the light’s rays. For PointLights we don’t need to do this, as every pixel is within the arc of the light, and so every pixel will map onto one of the light’s rays.

Let’s outline the steps we need to take in order to Unwrap our rays. Remember – the Graphics Processor effectively iterates over each pixel of the surface we are drawing to, i.e. the unwrapTarget. Recall that for any given pixel on our unwrapTarget, the ‘column’ of pixels it is in (i.e. it’s x coordinate) represents a ray eminating from the light, and the ‘row’ (y coordinate) represents how far along that ray the pixel is. With this in mind, the steps are:

1) Determine which ray on the Shadow casters texture corresponds to the current pixel on the unwrapTarget.

2) Calculate the normal of that ray (i.e. vector pointing from the light along the ray with length 1).

3) Determine the length of that ray (i.e. how long would it appear to be on the shadow casters texture.

4) Use the current pixel’s y coordinate to determine how far along that ray it lies (and so how far from the light it is).

5) Multiply the normal from step 2 by the result in step 4.

6) Add the coordinates of the Light to those found in Step 5, convert the result to texture coordinates and sample that pixel from the shadow casters texture.

7) If the sampled pixel does not cast a shadow, then store the value ‘1’ in the current pixel of the unwrapTexture. Otherwise, store the distance of the sampled pixel from the light (divided by the diagonal distance of the screen to scale it to the range 0 – 1).

Essentially we want to know what pixel on the shadow casters texture corresponds to the current pixel on the unwrapTarget, and then depending on whether or not that pixel casts a shadow, we store a distance from the light to that pixel. Hopefully all will become clear as we write the shader, and I’ll throw in some illustrations which should more light on the issue (pun semi-intended).

**The Unwrap Shader**

Open up your solution from Part 3 and add a new effect file to the Effects folder in the content project that we created. Name this file Unwrap.fx.

Delete the contents of the file that XNA has kindly added for us, we’ll be writing our shader from scratch. If your not familiar with shaders I suggest you go back and work through Part 2, or else try one of the tutorial series that I linked to at the bottom of that post.

First up, let’s create a stubb for the PixelShader we’ll be writing:

float4 PixelShaderFunction(float2 texCoord : TEXCOORD0) : COLOR0 { }

And while we’re here, we’ll add the technique:

technique Technique1 { pass Pass1 { PixelShader = compile ps_2_0 PixelShaderFunction(); } }

Now, before we continue, recall that we are intending to store the left and right halves of the screen in two different channels of the texture. This means that effectively each column of the unwrapTarget corresponds to two rays: one for the part of the target to the left of the light (which we represent in the red channel of the target) and one for the part of the target to the right of the light (which we represent in the green channel.

So for each step of our algorithm we’ll need two sections of code, one for each of the two points on the shadow caster texture that our pixel maps to.

The first step in our shader is to determine which ray (or rather rays) our pixel lies on. To do this we’ll need some trigonometry. First we need to decide on which line should represent the angle zero. The obvious choices are either directly up or down. Up is the normal choice, however in normal geometry ‘up’ is the direction of the positive y axis.

In the case of texture coordinate, the positive y axis points down, and so we shall choose this as our zero line.

Next we need to choose which direction (clockwise or anti-clockwise) is the positive direction. Normally this direction is clockwise, however, in our case, since we are dealing with the two sections of the texture separately, we can choose both directions to be positive. This will simplify some calculations we need to make down the line.

In order to determine what the angle of our ray is, we need to convert it’s x texture coordinate to an angle between zero (our line pointing straight down) and 180 degrees (the angle of the line pointing straight up). However working in degrees isn’t particularly useful in trigonometry, as you may know. Instead we work in radians, in which case the line pointing directly upward from the light would have the angle PI.

So we need to map our x texture coordinate (between 0 and 1), to our angle range of 0 – PI. To do this we simply need to multiply the x texture coordinate by PI:

`float rayAngle = texCoord.x * PI;`

For this to work we first need to define PI. Add the following line at the top of the file:

#define PI 3.14159265

Next, as described in step 2), we will calculate the ray normals (these are just vectors pointing from the light along the rays with length 1):

float sinTheta, cosTheta; sincos(rayAngle, sinTheta, cosTheta); float2 norm1 = float2(-sinTheta, cosTheta); float2 norm2 = float2(sinTheta, cosTheta);

The intrinsic function sincos() takes an angle, and two floats, and stores sin of the angle in the first float, and cos of the angle in the second. Then we use the fact that, for angles that increase in a clockwise direction, the normal at an angle theta is given by (-sin(theta), cos(theta)).

Note for mathematicians: Normally the normal is (**+**sin(theta), cos(theta)) for angles that increase clockwise. However this assumes that the axes have the positive x direction at 90 degrees clockwise from the positive y direction, similar to the normal way of drawing axes for a graph. Texture coordinates are the opposite of this (positive x is 90 degress **anti**-clockwise of positive y), so the sign of the x component in our normals is reversed.

To get the normal for the ray on the other side of the light, we just need to change the sign of the x coordinate. This is because essentially the coordinate system for the other side of the light is a reflection of the normal coordinate system, reflected in the line that passes vertically through our light. I’ve drawn a diagram below to illustrate:

Next we need to calculate the length of the rays. This is actually quite complex so we will start only by considering those rays to the left of the light and will then extend the technique to cover those the right of the light as well.

So, how do we determine the length of a given ray? Well, the length of the ray is determined by the distance between the light and whichever edge of the texture the ray hits. So first of all we’ll need to know the coordinates of our light. The only way we’re going to get that is through a parameter, so we’ll add the following at the top of our shader file:

`float2 LightPos;`

Next we need to determine which edge the ray will hit. This is a bit trickier than it sounds, and took me a bit of time to figure out. My first instinct was to calculate the angle between the corners and the light and compare it to the angle of the ray, but that involves inverse trigonometry, which is expensive, and once that’s done we would still need to calculate where along that edge the ray hit.

The alternative is to calculate the point at which the ray intersects with each of the edges of the rectangle, and then whichever point of intersection is the closest to the ray is the one we want. So how do we do this?

Well, let’s start with the top edge of the rectangle. When the ray intersects this edge, the y coordinate of that point will be 0 (as the y coordinate of the top edge of the rectangle is 0). We also know that the point lies somewhere on the ray. Any point along this line can be described as some multiple of the normal we calculated above, added to the position of the light. In other words a point that is say distance 5 away from the light on the ray with normal norm1 would have the following coordinates:

(5 * norm1.x + LightPos.x, 5 * norm1.y + LightPos.y)

However, we know that norm1 is (sinTheta, cosTheta), from above, so a point that is distance d from the light would have the following coordinates:

(d * sinTheta + LightPos.x, d * cosTheta + LightPos.y)

Now, we know from above that at the point our ray intersects the top edge of the rectangle, the y coordinate is 0, which means that d * cosTheta + LightPos.y = 0.<

We can rearrange this to get d = -LightPos.y / cosTheta, which tells us how far from the light the point of intersection between the ray and the top edge of the texture is!

If we follow the same procedure for the other two possible edges (not 3, as a ray on the left of the light can never hit the right hand edge of the texture), we find that the distance to the left edge is:

d = LightPos.x / sinTheta;

and the distance to the bottom edge is:

d = (TextureHeight – LightPos.y) / cosTheta;

Where TextureHeight is the height of the texture. As an aside, we’ll need to add TextureHeight as a parameter at the top of the file:

`float TextureHeight;`

So now we simply need to choose the smallest positive distance of these 3 distances, and we’ll have the length of our ray! Why the smallest **positive** distance? Well, let’s imagine we have a ray that hits the top of the screen. If you extend this ray on the *other* side of the light, it will also hit the bottom of the screen. However, our equations above will give us the distance as a negative, because it is in the opposite direction to the normal vector. Clearly we want to ignore this result, so we only choose from the positive results.

What does this look like in code? Something like this (but don’t copy it down just yet!):

float LightDist; float topHit = -LightPos.y / cosTheta; float leftHit = LightPos.x / sinTheta; float bottomHit = (TextureHeight - LightPos.y) / cosTheta; topHit = (topHit < 0) ? 2 * TextureWidth : topHit; leftHit = (leftHit < 0) ? 2 * TextureWidth : leftHit; bottomHit = (bottomHit < 0) ? 2 * TextureWidth : bottomHit; LightDist = min(topHit, min(leftHit, bottomHit));

You may be wondering why we’re setting each of the ‘Hit’ values to 2 * TextureWidth if they are less than 0. This is because we need them to be positive (otherwise min would return them instead of the smallest positive value), but we need to ensure it is longer than any of the positive values, hence we choose a value for it longer than any ray can possibly be. We’ll need to add TextureWidth as a parameter while we’re here:

`float TextureWidth;`

However, each of those ternary operators (?: operators) is a ‘branching’ instruction, which are quite expensive in shader programming. So, as a bit of an optimisation (this actually should result in fewer instructions), we change this code to the following (note, still not final code!):

float LightDist; float3 hit = float3(-LightPos.y / cosTheta, LightPos.x / sinTheta, (TextureHeight - LightPos.y) / cosTheta); hit = (hit < 0) ? 2 * TextureWidth : hit; LightDist = min(hit.x, min(hit.y, hit.z));

The line where we use the ternary operator on hit actually performs the same operator on all 3 components at once, which is exactly what we need. However we can’t quite use this code yet unfortunately, as we haven’t yet considered the other side of the light.

Now we get to see where choosing to have the angles increase positively in both directions from the zero line will benefit us. If you look back at the equations for the distance along the ray to the top and bottom of the texture, you’ll see that they only involve cosTheta. This in turn is because they only involve the y component of the normal.

Now, if you look at the equations for our two normals, you will see that the y coordinate is the same for both, meaning that the distance along the ray to the top and bottom edges of the texture will be the same for both sides of the light. So, in order to incorporate the rays on both sides of our light into our code, we only need to calculate the distance to one more edge. In this case, using the same method as above, the equation will be:

d = (TextureWidth – LightPos.x) / sinTheta

Before we add that into our code, let’s consider what will happen to LightDist. At the moment we only need a single float value, since we’re only measuring a single distance. However, the distance to the nearest edge could easily be different between the rays on either side of the light (e.g. the light is in the middle vertically but very close to one of the side edges, and so very far from the other side edge). So we will need to record two LightDist’s, which we will do by converting LightDist to a float2. We’ll also need to take this into consideration when it comes to calculating the value to store in LightDist.

So lets have a look at the new code (this will actually be the final version of this bit of code this time!):

float2 LightDist; //... float4 hit = float4(-LightPos.y / cosTheta, LightPos.x / sinTheta, (TextureHeight - LightPos.y) / cosTheta, (TextureWidth - LightPos.x) / sinTheta); hit = (hit < 0) ? 2 * TextureWidth : hit; LightDist = min(hit.wy, min(hit.x, hit.z));

The main thing we need to explain is the line where we assign a value to LightDist. Essentially we need to end up with LightDist.x holding the minimum of the distance to the top, bottom, and left side of the screen, which are held in hit.x, hit.z, and hit.y respectively. LightDist.y needs to end up holding the minimum between the top, bottom, and right hand side of the screen, i.e. hit.x, hit.z, and hit.w.

Since both LightDist.x and LightDist.y need to know the minimum between hit.x and hit.z, we do that inside the nested min(), and then in the outer min() we find the minimum of that result with each of the right and left distance respectively.

We have one more issue to deal with before we can move on to the next part of the shader. At certain angles either sinTheta or cosTheta may have the value zero. If that happens we will have an issue, as we will be dividing by zero, which in some environments would crash. In shaders it’ll will give us very strange results. Either way we don’t want to do it, so we’ll need to add some code to handle these occassions. Fortunately, it’s very easy to compute the distances manually in these situations. If cosTheta is zero it means are rays are pointing right/ left respectively, which means that the ray lengths are just TextureWidth – LightPos.x and LightPos.x.

If the sinTheta is zero then either both rays are pointing up or both are pointing down. The way to determine which is to check cosTheta. If cosTheta is 1 then the rays are pointing down, if it’s -1 then they are pointing up. We can use some clever maths to avoid using any if statements or ternary operators, and still get the right result. Let’s write the final version of the code to determine the length of the ray:

float2 LightDist; if (cosTheta == 0) { LightDist = float2(TextureWidth - LightPos.x, LightPos.x); } else if (sinTheta == 0) { LightDist = abs((((cosTheta + 1) / 2.0) * TextureHeight) - LightPos.y); } else { float4 hit = float4(-LightPos.y / cosTheta, LightPos.x / sinTheta, (TextureHeight - LightPos.y) / cosTheta, (TextureWidth - LightPos.x) / sinTheta); hit = (hit < 0) ? 2 * TextureWidth : hit; LightDist = min(hit.wy, min(hit.x, hit.z)); }

Phew! You’ll be pleased to know that that’s the hardest part out of the way. Now all that’s left is for us to use the information we’ve gathered so far to determine which pixel on the texture we want to sample. So next up is Step 4) from above, use the y texture coordinate and the length of the ray to find out how far from the light our pixel is. Since the y coordinate is between 0 and 1 we can just multiply it by the length of the ray (as 1 would give us the intersection between the ray and the edge of the texture, and 0 would give us the light itself). So we can add the following line to our shader:

`LightDist = mul(LightDist, texCoord.y);`

Remember that LightDist is a float2, which means that this line actually calculates the distance from the light for both the pixel on the ray to the left of the light and the pixel on the ray to the right of the light.

Next we move on to Step 5). Here we simply multiply the normals by the correct components of LightDist to get the offset from the light (in horizontal and vertical pixels) of the pixels we want to sample:

norm1 = mul(norm1, LightDist.y); norm2 = mul(norm2, LightDist.x);

Next up is Step 6). Here we add the position of the light to our offset to get the actual coordinates (in pixels) of the pixels we want to sample. We then convert them to texture coordinates and sample them from the shadow casters texture:

float4 sample1 = tex2D(shadowCastersSampler, float2((LightPos.x + norm1.x) / TextureWidth, (LightPos.y + norm1.y) / TextureHeight)); float4 sample2 = tex2D(shadowCastersSampler, float2((LightPos.x + norm2.x) / TextureWidth, (LightPos.y + norm2.y) / TextureHeight));

In order for this to work we’ll need to add a sampler for our shadow caster texture to the top of our shader file:

`sampler shadowCastersSampler : register(s0);`

So now finally we’ve sampled the pixels from our shadow caster texture so that we can determine whether or not they are shadow casting pixels. All that remains is for us to store our results for our two rays in the first two channels of our render target. As we described in Step 7), if the pixel we’ve sampled isn’t casting a shadow then we want to store 1 as the result, otherwise we want to store the distance of that pixel from the light divided by the diagonal length of the shadow caster texture:

`return float4((sample1.a < 0.01) ? 1 : LightDist.x / DiagonalLength, (sample2.a < 0.01) ? 1 : LightDist.y / DiagonalLength, 0, 1);`

Once again we’ll need to add a parameter to our shader file for this to work. This time it’s the variable DiagonalLength. We could of course calculate this in the shader from the TextureHeight and TextureWidth. However, it would be expensive to calulate this for every single pixel on our render target when we can just calculate it once on the CPU and pass it in as a parameter:

`float DiagonalLength;`

And… we’re done with our shader! The final code file, fully completed, should look something like this:

#define PI 3.14159265 float2 LightPos; float TextureWidth; float TextureHeight; float DiagonalLength; sampler shadowCastersSampler : register(s0); float4 PixelShaderFunction(float2 texcoord : TEXCOORD0) : COLOR0 { float sinTheta, cosTheta; sincos((texCoord.x * PI), sinTheta, cosTheta); float2 norm1 = float2(-sinTheta, cosTheta); float2 norm2 = float2(sinTheta, cosTheta); float2 LightDist; if (cosTheta == 0) { LightDist = float2(TextureWidth - LightPos.x, LightPos.x); } else if (sinTheta == 0) { LightDist = abs((((cosTheta + 1) / 2.0) * TextureHeight) - LightPos.y); } else { float4 hit = float4(-LightPos.y / cosTheta, LightPos.x / sinTheta, (TextureHeight - LightPos.y) / cosTheta, (TextureWidth - LightPos.x) / sinTheta); hit = (hit < 0) > 2 * TextureWidth : hit; LightDist = min(hit.wy, min(hit.x, hit.z)); } LightDist = mul(LightDist, texCoord.y); norm1 = mul(norm1, LightDist.y); norm2 = mul(norm2, LightDist.x); float4 sample1 = tex2D(shadowCastersSampler, float2((LightPos.x + norm1.x) / TextureWidth, (LightPos.y + norm1.y) / TextureHeight)); float4 sample2 = tex2D(shadowCastersSampler, float2((LightPos.x + norm2.x) / TextureWidth, (LightPos.y + norm2.y) / TextureHeight)); return float4((sample1.a < 0.01) ? 1 : LightDist.x / DiagonalLength, (sample2.a < 0.01) ? 1 : LightDist.y / DiagonalLength, 0, 1); } technique Technique1 { pass Pass1 { PixelShader = compile ps_2_0 PixelShaderFunction(); } }

Before we finish we need to add some code to the project we started in the last part of the series to set the shader parameters.

Open up the LightRenderer class file. First of all add the following field to the top of the class:

`Vector2 screenDims;`

And then add the following to the bottom of Initialize():

screenDims = new Vector2(graphics.GraphicsDevice.Viewport.Width, graphics.GraphicsDevice.Viewport.Height);

Followed by the following at the top of PrepareResources():

unwrap.Parameters["TextureWidth"].SetValue(screenDims.X); unwrap.Parameters["TextureHeight"].SetValue(screenDims.Y); unwrap.Parameters["DiagonalLength"].SetValue(screenDims.Length());

And finally, add the following lines to UnwrapShadowCasters(PointLight pLight):

`unwrap.Parameters["LightPos"].SetValue(pLight.Position);`

And that’s it! We now have a working Unwrap shader for point lights. This generates the input for our CreateOcclusionMap() method which produces our occlusion map. I’ve uploaded the solution so far to codeplex as normal, which you can find here (with some typos fixed from the one I uploaded for the last part in the series. The code in the tutorial itself should be fine, I just failed to copy it correctly!):

In the next part of the series we’ll see how we use the occlusion map to generate our light map for the scene. See you soon!

June 13th, 2013 - 5:42 am

“However, each of those ternary operators (?: operators) is a ‘branching’ instruction, which are quite expensive in shader programming.”

Nope. Branching is expensive, but a ternary op won’t cause a branch. This is a misconception perpetuated by people who don’t read the assembly output of their shaders. 😉

A branch in the high-level code does NOT directly translate to a branching instruction in the compiled shader. You have much less to worry about than you think.

Trivial cases like ternary operations never emit branching instructions. GPUs have dedicated instructions that directly translate to ternary ops: conditional moves which select between A and B depending on a comparison. In the assembly output these will be named like “setgt”, “setle” etc. Simple if and if-else statements directly translate to these operations as well.

For more complex statements it depends on the cleverness of the compiler. Let’s say you have an if-else with two different outcomes. If the two expressions have similar computations then the parts in common will be executed first (only once) and then combined with the differing parts using conditional moves. Ta-da, no branches.

A simple example of this kind of thing:

I write:

if (x>y) x += z;

Which gets translated to:

x += (x>y) ? z : 0;

Which in the assembler will just be:

MOV r0, x

SETGT r1, x, y, 0

ADD r0, r1

This is not branching – if it were a branch there’d be a load of instructions to do with predicates and stack pushes and pops etc. GPUs don’t have jump instructions, so things get ugly quite fast. 🙂

Branches DO get generated for nested complex branching statements, if the compiler can’t figure out how to express it in terms of conditional moves. And it often can’t because it has no time for exhaustive analysis of such things, owing to the real-time nature of the application. That’s bad, and that’s when you should start trying to rearrange your logic in simpler terms – but only then.

To know when to do this you really HAVE to read the assembly. If you care about performance you simply must see what the compiler is actually doing, or you’re fumbling in darkness. And don’t be scared of it – GPU assembly is very simple because of the extremely limited instruction set. Get your hands dirty.

August 20th, 2013 - 11:46 am

Hey, thanks for taking the time to comment – part of the point of doing this series was to learn a bit more about shaders myself, so it’s always useful to hear from someone with a better understanding of them!

I can’t recall exactly now why I thought there was a branching instruction – I know for some parts of the shader I checked the number of instructions generated, but obviously that’s a pretty crude performance measure.

Either way it’s always good to learn more, so thanks again for sharing that bit of knowledge 🙂 I’ll update the tutorial with a note to say that they don’t generate branching instructions.

Travis

September 21st, 2013 - 12:52 am

return float4((sample1.a < 0.01) ? 1 : LightDist.x / DiagonalLength, (sample2.a < 0.01) ? 1 : LightDist.y / DiagonalLength, 0, 1);

There is actually LightDist.y first and then LightDist.x`

Anyway, thanks for the tutorial!

October 27th, 2013 - 3:39 pm

Ah, thanks! One day I’m going to go back and fix all of the bugs with this tutorial (and possibly upgrade it to Monogame, or just redo it all in Unity).