patterncsharpMinor
Optimizing lighting algorithm for a voxel engine
Viewed 0 times
enginelightingalgorithmvoxeloptimizingfor
Problem
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);
Blocks.Add(new Vector3(x, y, z));
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 &&
!
```
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);
Blocks.Add(new Vector3(x, y, z));
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 &&
!
Solution
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)
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);
Blocks.Add(new Vector3(x, y, z));
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);
}
}Code Snippets
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);
Blocks.Add(new Vector3(x, y, z));
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);
}
}Context
StackExchange Code Review Q#7244, answer score: 2
Revisions (0)
No revisions yet.