Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am using C# and XNA. My current algorithm for lighting is a recursive method. However, it is expensive, to the point where one 8x128x8 chunk calculated every 5 seconds.

  • Are there other lighting methods that will make variable-darkness shadows?
  • Or is the recursive method good, and maybe I am just doing it wrong?

It just seems like recursive stuff is fundamentally expensive (forced to go through around 25k blocks per chunk). I was thinking about using a method similar to ray tracing, but I have no idea how this would work. Another thing I tried was storing light sources in a List, and for each block getting the distance to each light source, and using that to light it to the correct level, but then lighting would go through walls.

My current recursion code is below. This is called from any place in the chunk that does not have a light level of zero, after clearing and re-adding sunlight and torchlight.

world.get___at is a function that can get blocks outside of this chunk (this is inside the chunk class). Location is my own structure that is like a Vector3, but uses integers instead of floating point values. light[,,] is the lightmap for the chunk.

    private void recursiveLight(int x, int y, int z, byte lightLevel)
    {
        Location loc = new Location(x + chunkx * 8, y, z + chunky * 8);
        if (world.getBlockAt(loc).BlockData.isSolid)
            return;
        lightLevel--;
        if (world.getLightAt(loc) >= lightLevel || lightLevel <= 0)
            return;
        if (y < 0 || y > 127 || x < -8 || x > 16 || z < -8 || z > 16)
            return;
        if (x >= 0 && x < 8 && z >= 0 && z < 8)
            light[x, y, z] = lightLevel;

        recursiveLight(x + 1, y, z, lightLevel);
        recursiveLight(x - 1, y, z, lightLevel);
        recursiveLight(x, y + 1, z, lightLevel);
        recursiveLight(x, y - 1, z, lightLevel);
        recursiveLight(x, y, z + 1, lightLevel);
        recursiveLight(x, y, z - 1, lightLevel);
    }
share|improve this question
1  
Something is horribly wrong if you're doing 2 million blocks per chunk - especially since there's only 8,192 blocks actually in an 8*128*8 chunk. What could you be doing that you're going through each block ~244 times? (could that be 255?) –  Jonathan Hobbs Oct 30 '11 at 1:27
1  
I did my math wrong. Sorry :P. Changing. But the reason why you need to go though so many is you have to "bubble out" from every block until you hit a light level greater than the one your setting. That means every block might get overwritten 5-10 times before it hits actual light level. 8x8x128x5 = a lot –  khyperia Oct 31 '11 at 0:28
2  
How are you storing your Voxels? That is important to reduce traversal times. –  Samaursa Oct 31 '11 at 2:23
1  
Can you post your lighting algorithm? (you ask if you're doing it badly, we have no idea) –  Jonathan Hobbs Oct 31 '11 at 6:32
    
I am storing them in a array of "Blocks", and a Block consists of a enum for material, plus a metadata byte for future use. –  khyperia Oct 31 '11 at 21:30

4 Answers 4

  1. Every light has a precise (floating point) position, and bounding sphere defined by a scalar light radius value, LR.
  2. Every voxel has a precise (floating point) position at it's centre, which you can easily calculate from its position in the grid.
  3. Run through every one of 8192 voxels once only, and for each, see if it falls within each of N lights' spherical bounding volumes by checking |VP - LP| < LR, where VP is the voxel's position vector relative to origin and LP is the light's position vector relative to origin. For each light whose radius the current voxel is found to be in, increment it's light factor by the distance from the light centre, |VP - LP|. If you normalise that vector and then get its magnitude, this will be in range 0.0->1.0. The maximum light level a voxel can reach is 1.0.

The runtime is O(s^3 * n), where s is the side length (128) of your voxel region and n is number of light sources. If your light sources are static, this is no problem. If your light sources move in real time, you can work solely on deltas rather than recalculating the whole shebang every update.

You could even store the voxels which each light affects, as references within that light. This way, when the light moves or is destroyed, you can go through just that list, adjusting light values accordingly, rather than having to traverse the entire cubic grid again.

share|improve this answer
    
If I understood his algorithm correctly, he tries to do some sort of pseudo-radiosity, by allowing light to reach far-away places even if it means it has to go "around" some corners. Or, in other words, a flood-fill algorithm of the "empty" (non-solid) spaces with a bounded max distance from the origin (the light source) and the distance (and from it, light attenuation) being calculated according to the shortest path to the origin. So - not quite what you propose currently. –  Martin Sojka Nov 1 '11 at 12:25
    
Thanks for the detail @MartinSojka. Yep sounds more like an intelligent flood fill. With any attempt at global illumination, costs tend to be high even with clever optimisations. Thus it's good to attempt these problems in 2D first, and if they're even remotely expensive, know that you'll have a definite challenge on your hands in 3D. –  Nick Wiggill Nov 1 '11 at 13:03
up vote 2 down vote accepted

Someone said to answer your own question if you figured it out, so yeah. Figured out a method.

What I am doing is this: First, create a 3d boolean array of "already changed blocks" overlayed over the chunk. Then, fill in sunlight, torchlight, etc (just lighting up the block that its on, no flood filling yet). If you changed something, hit the "changed blocks" in that location to true. Also go though and change every solid block (and therefore no need to calculate lighting for) to "already changed".

Now for the heavy stuff: Go though the entire chunk with 16 passes (for each light level), and if its 'already changed' just continue. Then get the light level for the blocks around itself. Get the highest light level of them. If that light level equals the current passes' light level, set the block you are on to the current level, and set "already changed" for that location to true. Continue.

I know its kind of complicated, I tried to explain my best. But the important fact is, it works and is fast.

share|improve this answer

I'd suggest an algorithm that sort of combines your multi-pass solution with the original recursive method, and is most likely quite a bit faster than either of them.

You'll need 16 lists (or any kind of collections) of blocks, one for each light level. (Actually, there are ways to optimize this algorithm to use fewer lists, but this way is easiest to describe.)

First, clear the lists and set the light level of all blocks to zero, and then initialize light sources as you do in your current solution. After (or during) that, add any blocks with a non-zero light level to the corresponding list.

Now, go through the list of blocks with light level 16. If any of the blocks adjacent to them have light level less than 15, set their light level to 15 and add them to the appropriate list. (If they were already on another list, you can remove them from it, but it doesn't do any harm even if you don't.)

Then repeat the same for all the other lists, in decreasing order of brightness. If you find that a block on the list already has a higher light level than it should for being on that list, you can assume it was already processed and not even bother checking its neighbors. (Then again, it might be faster to just check the neighbors — it depends on how often that happens. You should probably try it both ways and see which way is faster.)

You may note that I haven't specified how the lists should be stored; really pretty much any reasonable implementation ought to do it, as long as inserting a given block and extracting an arbitrary block are both fast operations. A linked list should work, but so would any halfway decent implementation of variable-length arrays too. Just use whatever works best for you.


Addendum: If most of your lights don't move very often (and neither do the walls), it might be even faster to store, for each lit block, a pointer to the light source that determines its light level (or to one of them, if several are tied). That way, you can avoid global lighting updates almost entirely: if a new light source is added (or an existing one brightened), you only need to do a single recursive lighting pass for the blocks around it, while if one is removed (or dimmed), you only need to update those blocks that point to it.

You can even handle wall changes this way: when a wall is removed, just start a new recursive lighting pass at that block; when one is added, do a lighting recalc for all blocks that point to the same light source as the newly walled block.

(If several lighting changes happen at once — e.g. if a light is moved, which counts as a removal and an addition — you should combine the updates into a single one, using the algorithm above. Basically, you zero out the light level of all blocks pointing to removed light sources, add any lit blocks surrounding them as well as any new light sources (or existing light sources in the zeroed out areas) to the appropriate lists, and run the updates as above.)

share|improve this answer

Minecraft itself doesn't do the sunlight this way.

You simply fill the sunlight from the top to the bottom, every layer is gathering light from neighbor voxels in the previous layer with attenuation. Very fast - single pass, no lists, no data structures, no recursion.

You have to add torches and other non-flooding lights in a later pass.

There are so many other ways to do this, including fancy directional light propagation etc. , but they are obviously slower and you have to figure out if you want to invest in the additional realism given those penalties.

share|improve this answer
    
Wait, so how exactly does Minecraft do it? I couldn't get exactly what you were saying... What does "every layer is gathering light from neighbor voxels in the previous layer with attenuation" mean? –  khyperia Nov 3 '11 at 19:47
1  
Start with the topmost layer (slice of constant height). Fill it with sunlight. Then go to the layer below, and every voxel there gets its illumination from the closest voxels in the previous layer (above it). Put zero light in solid voxels. You have a couple of ways to decide the "kernel", the weights of the contributions from the voxels above, Minecraft uses the maximum value found, but decreases it by 1 if the propagation is not straight down. This is the lateral attenuation, so unblocked vertical columns of voxels will get the full sunlight propagation and light bends around corners. –  Bjorn Wesen Nov 3 '11 at 20:14
    
Please note that this method is in no way based on any real physics whatsoever :) The main problem is that you are in essence trying to approximate a non-directional light (the atmospheric scattering) AND bouncing radiosity with a simple heuristic. It looks pretty good. –  Bjorn Wesen Nov 3 '11 at 20:15
2  
What about a "lip" that hangs over, how does light get up there? How does light travel in an upward direction? When you only go top-down, then you cannot go back upwards to fill in overhangs. Also torches/other light sources. How would you do this? (they could only go down!) –  khyperia Nov 4 '11 at 20:47
1  
@Felheart: it was a while now that I looked at this, but in essence there is a minimum ambient light level that is usually enough for the underneath of overhangs so they are not completely black. When I implemented this myself, I did add a second pass from down->up, but I didn't really see any big aesthetic improvements compared to the ambient method. Torches/pointlights have to be handled separately - I think you can see the propagation pattern used in MC if you put a torch on the middle of a wall and experiment a bit. In my tests, I propagate them in a separate lightfield then add. –  Bjorn Wesen Dec 28 '12 at 13:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.