Floodfill lighting

[jacopograndi]

The minecraft lighting works by having a 2 light values for each blocks, each 4 bits (0..16). The first is torchlight, the second is sunlight. The light of the block is max(torchlight, sunlight). The torchlight propagates from block light sources decreasing by one each further block. The sunlight propagates from the top of the world decreasing by one sideways and by zero downwards.

The problem is that a view distance of 300 has 200 million blocks. That's too many to do in 1 frame, or a second.

The propagation algorithms for torchlights i've seen are:

Bruteforce naivity of naiveness
For every block look at the 6 neighbors and set the light as max(neighbors).
Converges after 16 updates.
Recalculates the entire lighting every time.
It's really reeeeeally slow, like 16 seconds slow.

Floodfill
Linear scan for lightsources. Start a breadth first search for each lightsource.
Converges in 1 update.
Can do incremental updates.
source

[magiwanders]

From Tasks.md to be retired

• Floodfill lighting

  Each voxel has a light level from 0 to 15.
  Light sources have a light value > 0.
  A block has the light level of the max(light source - manhattan distance from source).
  A solution to this constraints is a floodfill algorithm:

  1. Each tick, step through each voxel
  2. Look at the 26 neighboring blocks
  3. Block light is max(neighbor light) - 1

  In Minecraft the sun lights all the highest blocks with a value of 15.
  When the night comes, the value goes gradually to 0.
  This may be a performance problem: i have to modify every clear column once every ~15 seconds.

[jacopograndi]

I've implemented the floodfill from the linked article and it's fast enough. Currently it supports adding multiple lights and removing one light at a time. The initial lighting of the chunks needs to happen only at generation time. The sunlight isn't currently being updated on block placed/removed.
To update the sunlight I think it's best to calculate a heightmap and store it into Universe. The heightmap tracks the highest block, so the last one that receives direct sunlight. If an added block occludes the sun beams (> heightmap) or a removed block would let sunlight further down we can generate easily the remaining column of light sources / darkness sources.
Another problem is: we don't have a world height limit from which the sunbeams rain down. Maybe just raycasting down from y=200 or something?

[jacopograndi]

I've implemented the heightfield, initialized by raycasting down from the highest loaded point and updated at each block add/remove.

Followup work:

• Dignity: Refactor into a voxel_automata crate.
• Testing: Make a test suite for the light algorithm, it's a pure system.
• Performance: Review and benchmark the algorithm.
• Performance: Batch add/remove: now every time a block is added/removed the light has to be recalculated. There should be a way to calculate lights after a bunch of add/remove. Maybe all adds and removes are queued up and processed in a single pass after Update.

[jacopograndi]

#12 #13 #14 #15