3
\$\begingroup\$

This question is more about expanding on an answer posted for an old but similar question.

Part of the answer says this:

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.

I actually am having an easier time understanding how you would flood fill light for point lights. But doing so for sunlight, in one pass with no recursions, I still can't understand how it is done step by step.

Specific questions I would like to know about this:

Do you compare lighting of neighbor voxels only to the 4 cardinal directions, or do you check the up and down neighbors too?

If you don't store data structures for the lighting algorithm, how do you check for voxels that are already visited?

If there was a diagram explaining a step by step process of a single-pass light propagation that would be helpful. It seems like it would be easier on performance than casting several rays from each voxel to see if it hits light.

\$\endgroup\$
2
\$\begingroup\$

I can't think of a way to do it wherein you don't revisit nodes...and this is because of the pseudo-radiosity created by the light propagation. In essence, you could have a node closer to one "light source" than another, but lit by both. If you only visit it once, you might wind up with the incorrect lighting value. However, this is only if you are allowing light to "wrap around" corners and such.

But you can indeed perform the propagation without using recursive functions.

In such a case, I did the following:

  1. Create a light 'mask' starting at the top, full light value for empty voxels, 0 for solid ones
  2. As you push down from the top, set the lighting values of empty voxels according to the mask
  3. If a solid voxel is encountered, set the value of the mask at that position to 0
  4. For empty voxels encountered at the edges of the mask, set those to max light value - 1 and add them to the queue
  5. Repeat 2, 3 and 4 until the bottom is reached.

After setting the initial lighting values, you then:

  1. Pop the top off the queue
  2. Check it's neighbors (Top, Bottom, Left, Right, Front, Back) light values
  3. Set neighbors with light values LESS THAN the current value - 1 to the current value - 1 and add them to the queue
  4. Repeat until queue is empty

This resulted in an average light calculation time of 200ms (on a mid-range desktop) for a 256x256x128 voxel map using Google Chrome. Using a queue also eliminates the overhead of a function call (do not underestimate the overhead of function calls).

I will try to migrate my example code over to this answer, but for now you can see it in action here. Requires a browser that allows passing of arraybuffers from web workers.

\$\endgroup\$
2
\$\begingroup\$

The assumption is that like Minecraft, you are only doing lighting that runs perpendicular to sea level, i.e. straight up/down as if the sun is always at midday... you only increase the relative contrast between sunlit and shadowed voxels from dawn to midday, and reduce it from midday to dusk. But the raycast angle is always directly downward, no matter the time of day.

Do you compare lighting of neighbor voxels only to the 4 cardinal directions, or do you check the up and down neighbors too?

Down (or up) are all that's required. All you are doing is casting rays vertically from top to bottom of the voxel space. Vertical attenuation is only needed once you've cast below the ground level (however you care to define that), i.e. into a hole in the terrain, such that you can still see the sky by looking straight up but are now below ground. Horizontal propagation / attenuation might only be needed to soften shadow edges beneath overhangs, floating islands and so on, where sunlight is otherwise blocked and may only infiltrate in by ambient lighting from sunlit, horizontal neighbours.

If you don't store data structures for the lighting algorithm, how do you check for voxels that are already visited?

You don't have to: It's a while loop running on each voxel column from sky to ground (or vice versa), i.e. till the sun-ray hits a solid voxel. Just like any loop, of course you will only run once over each element - whatever's past, is past. You don't need to check for what is already visited. If you are storing your voxels as columns like Minecraft does, then of course this is made even simpler because you can rapidly see where ground ends and sky begins. RLE compression allows for even fewer iterations.

\$\endgroup\$
  • \$\begingroup\$ By "storing voxels as columns", do you mean in a way that makes it easy to iterate in the Y directions? The way I loop through voxels, to check visibility, build meshes etc. is "For every Z in every X, start at the topmost Y with a solid voxel and continue downwards." Don't know if this matters but the chunks are not cubic, they actually 32x32 with 256 in height. \$\endgroup\$ – ChrisC Jan 11 '15 at 23:26
  • \$\begingroup\$ I mean the vertical direction, yes. If the lighting is vertical, you iterate vertically. Chunk size should not matter, though preferably (as in your case) it should be taller than it is wide for good cache performance, assuming also that the each element of each column is stored contiguously in memory. \$\endgroup\$ – Engineer Jan 11 '15 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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