Lightmap Generator : Raytracing with DirectCompute

September 28, 2013

I always wanted to try GPGPU programming but never had the opportunity and doing business applications in .NET doesn’t really helps doing that (still, there are people doing this in high frequency trading applications but that’s not my case).

But for a game, this is completely different.

Let say you want to have lights and shadows in a game. You can have everything computed real time with ShadowMaps and the like (and then you have to be careful about performances), or you can precompute some details during compile time to create light maps. At runtime, rendering precomputed shadows is just about sampling the light mapped texture and applying it to models. A lot cheaper.

How to create light maps then ?

  • Using a modeling application. 3ds Max can do that quite beautifully, but that doesn’t really teach how to do GPGPU computing.
  • By baking Shadow Maps. This is what I did for AirMess during ImagineCup. This works quite well and is very simple to implement.
  • By generating a light texture using a compute shader to create ray traced shadows.

The last solution is the funnier and is a good occasion to learn how to use compute shaders. There are several technologies available to do that: CUDA, DirectCompute, OpenCL … but then, as a learning platform DirectCompute seemed to be the simpler as I already have a running DirectX application during the build process of the game. So let’s do this !

The algorithm

So we know we want to do a compute shader. But how to do it ? Let’s try something simple.

  1. Create a map of the model we want to light map. Each triangles should be mapped once into a texture representing the model.
  2. For each pixel of the map, we store the corresponding position on the model surface. For each triangle (3 points) we will have a projection containing all the points of the rasterized triangle (n points) up to the resolution of the map.
  3. For each light
    • For each model of the environment
        For each mapped pixel
        • For each triangle of the model
          1. Check if there’s an intersection with the ray from the pixel position with the triangle and coming in the light direction
          2. If so, mark it as shadow, if not light it with the standard light equation
          3. We could do more fun and also sample the texture color of the occluder to produce global illumination result. I will perhaps do that later.
  4. Save the resulting map as the light map and use it to light the model during rendering


Creating the map

For a model to be light mapped, it have to have light map coordinates. There are several ways to do that:

  • UVAtlas, a DirectX API that creates a texture mapping for any 3D object. Well, almost any. There are sometimes errors but it mostly works. Downside is that this does requires obscure C++ code mix inside of a C# engine to have models converted in the DirectX way.
  • A good 3D modeling application (Blender, 3Dmax, …) will do this for you.
  • If you like to code and read paper, basically it’s about implementing a LCSM algorithm. That’s a very long path to have fun, so I’ve chosen the second option πŸ™‚

Then, creating the original model map can be done in a simple pixel shader. We are also taking normals for the light computation:


struct PIXEL_IN
	float4 texturePosition : SV_POSITION;
	float3 worldPosition : TEXCOORD0;
	float3 worldNormal : TEXCOORD1;

// The world
float4x4 World;
float4x4 NormalWorld;

// We are storing the bounding box to output a value in [0..1]
float3 bboxMin;
float3 bboxMax;

// SLIM10_VERTEX_IN is the vertex format used internally by Kadma
// contains texture positions, normals and so on
	float3 wPosition = mul(float4(input.Pos.xyz, 0), World).xyz;

	// (x - min) / (max - min)
	float3 relativePosition = (wPosition - bboxMin) / (bboxMax - bboxMin);

	PIXEL_IN output = (PIXEL_IN)0;
	// GetLightmapCoord takes the coordinates of the lightmap channel
	output.texturePosition = float4(GetLightmapCoord(input) * 2 - 1, 0, 1);
	output.worldPosition = relativePosition;

    output.worldNormal = normalize(mul(float4(input.Normal, 1), NormalWorld).xyz);

	return output;

	float4 Position : SV_TARGET0;
	float4 Normal : SV_TARGET1;


	result.Position = float4(input.worldPosition.xyz, 1);
	result.Normal = float4(encodeNormal(input.worldNormal), 0, 1);

	return result;

When having several lights, the simplest way is to just have them additively blend into the light map. Let say we have one directional light. For other light types we would have to make a ray going to that light following the light geometry.
Directional lights can be done my tracing a ray from the world pixel to the direction of the light, and looking if it intersects some triangle along the way:

[numthreads(numthread_x, numthread_y, 1)]
void CSDirectional( uint3 dIndex : SV_DispatchThreadID)
	float2 txPosition = float2(dIndex.xy);
	if(txPosition.x < PositionsMapDimensions.x && txPosition.y < PositionsMapDimensions.y)
		// Get the original world position of the reference pixel
		float4 positionsValue = PositionsMap[txPosition.xy];
		float3 normalsValue = decodeNormal(NormalsMap[txPosition.xy].xy);

		float3 worldPosition = bboxMin + (bboxMax - bboxMin) * positionsValue.xyz;

		float originalMinimumIntersectDistance = computedMap[txPosition.x + txPosition.y * PositionsMapDimensions.x].w;

		if(originalMinimumIntersectDistance >= FLT_MAX - 0.1f)
			// Are we looking in a lighted way ?
			if(dot(-directionalDirection, normalsValue) > 0)
				float minimumIntersectDistance = FLT_MAX;

				bool found = false;

				// For each triangle of the occluder
				for(int index = occluderIndexOffset; index < occluderIndexCount + occluderIndexOffset; index += 3)
					float3 bar;

					SLIM10_VERTEX_IN tA = occluderVertices[occluderVertexOffset + occluderIndices[index + 0]];
					SLIM10_VERTEX_IN tB = occluderVertices[occluderVertexOffset + occluderIndices[index + 1]];
					SLIM10_VERTEX_IN tC = occluderVertices[occluderVertexOffset + occluderIndices[index + 2]];

					// Does a ray coming from the world position and going to the right intersect the triangle ?
					if(triangleIntersect(worldPosition, -directionalDirection, mul(float4(tA.Pos,1), occluderWorld).xyz, mul(float4(tB.Pos, 1), occluderWorld).xyz, mul(float4(tC.Pos, 1), occluderWorld).xyz, bar))
						float3 directionToBar = bar - worldPosition;

						// Are we in the correct side ? (not finding an intersection behind the point)
						if(dot(directionToBar, -directionalDirection) > 0)
							float curDistance = length(bar - worldPosition);

							// Not really necessary, but using that we could make a global illumination algorithm
							if(curDistance > comparisonOffset && curDistance < minimumIntersectDistance && curDistance < originalMinimumIntersectDistance)
								minimumIntersectDistance = curDistance;

								found = true;

					// No intersection for this part, compute a light contribution
					computedMap[txPosition.x + txPosition.y * PositionsMapDimensions.x] = float4(ComputeLight(1, normalsValue, directionalDirection, (float3)0, directionalDiffuse, 0).xyz, FLT_MAX);
			// An intersection have been found, no light
			computedMap[txPosition.x + txPosition.y * PositionsMapDimensions.x] = float4(0,0,0,0);			

The only caveat is, if it takes to munch time to run Windows will kill the process trying to restore the graphics card to an usable state. To prevent that, you can tell Windows not to do that by allowing more time for you graphic card to be unresponsive (laaame) or split the process into several smaller chunks. I chose the later option and that’s why I use FLT_MAX (maximum value of a float) to mark the state of “we didn’t find an intersection in this chunk, but we may find one in another part”.

Because this is a build time operation, we have time to add little things like a Gaussian blur on shadows and stroke some border pixels to prevent seams in the Texture:

End result

Sampling this texture in the model shader that’s what we get.


A little free advantage is that we can get several levels of shadows: the shadows of the huge building, and the more closer shadow of the ship.
One problem though is that we don’t have the shadows of the building over the ship, but this can be fixed. Perhaps later πŸ™‚

Btw, I now live in Ireland!


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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: