# Optimizing lighting algorithm for a voxel engine

I am creating a Minecraft-like terrain engine in XNA to learn HLSL and more XNA. The problem is my lighting algorithm. Whenever a block which emits light is placed, it takes about half a second to calculate it. I have implemented the lighting in a recursive way.

public void DoLight(int x, int y, int z, float light)
{
Vector3i xDecreasing = new Vector3i(x - 1, y, z);
Vector3i xIncreasing = new Vector3i(x + 1, y, z);
Vector3i yDecreasing = new Vector3i(x, y - 1, z);
Vector3i yIncreasing = new Vector3i(x, y + 1, z);
Vector3i zDecreasing = new Vector3i(x, y, z - 1);
Vector3i zIncreasing = new Vector3i(x, y, z + 1);

if (light > 0)
{
light--;

world.SetLight(x, y, z, (int)light);

if (world.GetLight(yDecreasing.X, yDecreasing.Y, yDecreasing.Z) < light &&
!world.GetBlock(yDecreasing.X, yDecreasing.Y, yDecreasing.Z).IsSolid &&
world.InBounds(yDecreasing.X, yDecreasing.Y, yDecreasing.Z))
DoLight(x, y - 1, z, light);
if (world.GetLight(yIncreasing.X, yIncreasing.Y, yIncreasing.Z) < light &&
!world.GetBlock(yIncreasing.X, yIncreasing.Y, yIncreasing.Z).IsSolid &&
world.InBounds(yIncreasing.X, yIncreasing.Y, yIncreasing.Z))
DoLight(x, y + 1, z, light);
if (world.GetLight(xDecreasing.X, xDecreasing.Y, xDecreasing.Z) < light &&
!world.GetBlock(xDecreasing.X, xDecreasing.Y, xDecreasing.Z).IsSolid &&
world.InBounds(xDecreasing.X, xDecreasing.Y, xDecreasing.Z))
DoLight(x - 1, y, z, light);
if (world.GetLight(xIncreasing.X, xIncreasing.Y, xIncreasing.Z) < light &&
!world.GetBlock(xIncreasing.X, xIncreasing.Y, xIncreasing.Z).IsSolid &&
world.InBounds(xIncreasing.X, xIncreasing.Y, xIncreasing.Z))
DoLight(x + 1, y, z, light);
if (world.GetLight(zDecreasing.X, zDecreasing.Y, zDecreasing.Z) < light &&
!world.GetBlock(zDecreasing.X, zDecreasing.Y, zDecreasing.Z).IsSolid &&
world.InBounds(yDecreasing.X, yDecreasing.Y, zDecreasing.Z))
DoLight(x, y, z - 1, light);
if (world.GetLight(zIncreasing.X, zIncreasing.Y, zIncreasing.Z) < light &&
!world.GetBlock(zIncreasing.X, zIncreasing.Y, zIncreasing.Z).IsSolid &&
world.InBounds(zIncreasing.X, zIncreasing.Y, zIncreasing.Z))
DoLight(x, y, z + 1, light);
}
}


Does anyone see what is costing me so much performance? And if so, could you please suggest any way to fix it?

Especially when I try to update only a single light every frame, I get a depressingly low FPS of 4 (maybe the recursion is the problem). Does anyone know if a iterative would increase performance ? If so, how would I implement it?

• It's always a little surprising when people expect to get decent performance out of voxel rendering engines. Voxels just never caught on in a big enough way for graphics hardware vendors to optimize for them. Expecting voxels to perform like polygons is like expecting a software renderer to perform like a hardware renderer. =/ – Dagg Dec 29 '11 at 15:25
• The problem in this case is the lighting algorythm, not anything else, without it I get like 1440 FPS on average. – Darestium Dec 29 '11 at 21:27

Building upon Vadym's answer - the vector instantiation could probably be eliminated entirely. It appears they are only created to provide nice groupings of x,y,z coordinates, as they are only ever referenced by pulling the x,y,z values back out.

If performance is really an issue, I would suggest keeping individual values instead for xincreasing, xdecreasing, etc. and using those. It saves on the object creation and the property getter calls. (edit: and, to me at least, it is a little easier to read)

public void DoLight(int x, int y, int z, float light)
{
int xDecreasing = x - 1;
int xIncreasing = x + 1;
int yDecreasing = y - 1;
int yIncreasing = y + 1;
int zDecreasing = z - 1;
int zIncreasing = z + 1;

if (light > 0)
{
light--;

world.SetLight(x, y, z, (int)light);

if (world.GetLight(x, yDecreasing, z) < light &&
!world.GetBlock(x, yDecreasing, z).IsSolid &&
world.InBounds(x, yDecreasing, z))
DoLight(x, yDecreasing, z, light);
if (world.GetLight(x, yIncreasing, z) < light &&
!world.GetBlock(x, yIncreasing, z).IsSolid &&
world.InBounds(x, yIncreasing, z))
DoLight(x, yIncreasing, z, light);
if (world.GetLight(xDecreasing, y, z) < light &&
!world.GetBlock(xDecreasing, y, z).IsSolid &&
world.InBounds(xDecreasing, y, z))
DoLight(xDecreasing, y, z, light);
if (world.GetLight(xIncreasing, y, z) < light &&
!world.GetBlock(xIncreasing, y, z).IsSolid &&
world.InBounds(xIncreasing, y, z))
DoLight(xIncreasing, y, z, light);
if (world.GetLight(x, y, zDecreasing) < light &&
!world.GetBlock(x, y, zDecreasing).IsSolid &&
world.InBounds(x, y, zDecreasing))
DoLight(x, y, zDecreasing, light);
if (world.GetLight(x, y, zIncreasing) < light &&
!world.GetBlock(x, y, zIncreasing).IsSolid &&
world.InBounds(x, y, zIncreasing))
DoLight(x, y, zIncreasing, light);
}
}

• Wow, yes, such a simple fix! Thanks! Makes the code look heaps better! :). But it didn't really do anything to performance... Any other suggestions? – Darestium Dec 29 '11 at 20:23

Did you try using performance profiler with this code? Usually profiler can tell you where the problem is or at least show you the whole picture and give a starting point. Here's a decent profiler with 10 days trial period.

On the other hand I see several issues with your code. Every time DoLight is called a bunch of vectors are created. If recursion is deep it can lead to creating a lot of objects. Try placing all those vectors in an container object and pass that object as a parameter of DoLight function.

It is also very suspicious that you do not return from DoLight function after performing recursive DoLight function call. (I do not know the algorithm, so its hypothetical advice). I mean instead of if's use if else constructs.

• Well, in this case if else statements will not work because the algorythim needs to check every block adjacent to it. – Darestium Jan 5 '12 at 6:18

You should really profile the application (as others already suggested), without that nobody knows which are the slow parts.

Anyway, two ideas:

1, Try reordering the conditions:

if (world.GetLight(x, yDecreasing, z) < light &&
!world.GetBlock(x, yDecreasing, z).IsSolid &&
world.InBounds(x, yDecreasing, z))


You use short-circuit operators (&&), so if world.GetLight(x, yDecreasing, z) < light is false the remaining two conditions don't run. The fastest condition should be the first and so on... Of course, without profiling usually hard to tell which is the fastest/slowest method.

2, Maybe you can cache the results of the world.GetLight, world.GetBlock and world.InBounds calls.

Let's say you call DoLigh(0, 0, 0, 0). It calls the following methods when it runs the ifs:

world.GetLight( 0,  1,  0)
world.GetLight( 0, -1,  0) #2
world.GetLight(-1,  0,  0)
world.GetLight( 1,  0,  0)
world.GetLight( 0,  0, -1)
world.GetLight( 0,  0,  1)


If the first if is true, it calls

DoLight(0, -1, 0, light);


which calls

world.GetLight( 0,  0,  0)
world.GetLight( 0, -1,  0) #2
world.GetLight(-1, -1,  0)
world.GetLight( 1, -1,  0)
world.GetLight( 0, -1, -1)
world.GetLight( 0, -1,  1)


In this case the #2 call is the same. I don't know that it is cacheable or not. If it is, a cache could make it faster. The same is true for the other two methods. Anyway, first profile it.

• OK, I have done the first optomisation, and it runs pretty much the same, but the second, I really don't know, if you cache the results you would still have to search for them in the cache. Also I have tryed to add support to remove a light source (this takes about 2 seconds to calculate), and am no longer performing lighting calculations every frame, only when nessercary, but when it is nessercary, there is still alot of lag. – Darestium Dec 30 '11 at 1:06