Voxel Lighting implementation

[afonsolage]

Closes #29

This PR implements voxel lighting inspired on links provided on issue #29. It's a BFS flood-fill algorithm which will propagate the light value across the chunks.

[afonsolage]

Before continuing the implementation, I think it's time to draw the current genesis flow, so I can have a better understanding where insert the light propagation algorithm, since this algorithm needs to run after all chunks neighborhood is built but before faces merging.

[afonsolage]

Ok the bedrock of natural light propagation is done. But before I go to artificial light, there's still things to be done:

• [x] Fix light data being gathered from the voxel itself, not from the neightbor;
• [x] Add light propagation to neighborhood
• [x] Add light removal algorithm

[afonsolage]

Before adding light removal algorithm, I'll add more tests on natural light neighborhood propagation, since this code is a little complicated.

[afonsolage]

Finished natural light propagation and added some tests. Next is light removal algorithm.

It will look better when AO is added.

Also, no performance reduction was noticed. Still takes around 45 seconds to generate 16^256^16^8^8 chunks.

[afonsolage]

Added natural light removal algorithm, but before continuing to add/remove/propagate artificial light, I would like to add one more complex example for light removal across neighbors.

[afonsolage]

While doing some in-game tests, I noticed a problem: Currently the genesis workflow is mainly focused on generated chunks. So there is no way for light_propagator know when the chunk was generated or just updated.

I'll have to rework this inside this PR, since light propagation is different from generated or just updated chunks.

[afonsolage]

Light propagation flow was reworked, but there are two issue to be solved:

• [x] There is a bug on light when removing chunks: It seems only the last light value on the merged faces is used.
• [x] Light propagation isn't working as intended on neighbors
• [ ] Chunk generation is likely 10x slow, needs to be optimized

This picture shows the two first issues:

[afonsolage]

There is a bug on light when removing chunks: It seems only the last light value on the merged faces is used

[afonsolage]

Currently the logic behind the light propagation algorithm is using a logic to propagate inwards, in other words, it looks on the neighbor voxels and take the light if the outside is greater than inside.

This is due to how neighborhood works, but I'll rework this to a outwards flood fill algorithm

[afonsolage]

I made a lot of rework on natural light propagation, but there are still some bugs. I've managed finally to create a test which reproduce the last one I was hunting, so it should be easier to fix (I hope).

I feel like I should still make some rework on current function flow, since I think it's still a little mess, but not that much.

[afonsolage]

Ok, light propagation seems working fine now:

Now I I'll optimize it, since it's take too long and I still feel the code can be reorganized and optimized.

Maybe create a struct LightPropagator which can be generic over LightTy? Dunno, first I'll do some benchmarks to check which function is taking longer to run.

[afonsolage]

Here are some time measurements when generating 16^256^16^4^4 chunks (~1m voxels):

Step	Duration (secs)
Chunk Generation (noise)	<1
update_kind_neighborhoods	4
propagate_natural_light_on_new_chunks	29
faces_occlusion	9
faces_merger::merge	69
Write to disk	32
Total	144

Write to disk is out of scope of this PR, but I'll take a look on propagate_natural_light_on_new_chunks and faces_merger::merge

[afonsolage]

Reduced propagate_natural_light_on_new_chunks from 29 to 19, which as a 34% reduction!

[afonsolage]

Step	Duration (secs)
Chunk Generation (noise)	<1
update_kind_neighborhoods	1
propagate_natural_light_on_new_chunks	13
faces_occlusion	1
faces_merger::merge	12
Write to disk	5
Total	33

I think it's good now, reduced from 144s to 33s. Also when running on Release mode, it takes around 2s, so it's pretty fast.

Time to merge now!