Lighting technique

Blocks are stored in a huge array and light is stored in a completely seperate array ( i actually have 2 light arrays, a front and back buffer as it were).

Each block basically holds a 16 bit block number and a liquid value.

Chunks are notional things really only there for rendering.

I chose the single huge array since there are a lot of checks for neighbours involved throughout. If the blocks were stored in chunks then there would be loads of checks for when you are at the edge which would slow down whatever you are doing.

Slaihne wrote:Blocks are stored in a huge array and light is stored in a completely seperate array ( i actually have 2 light arrays, a front and back buffer as it were).

But when you load new "chunks" you must to sort all your array. It will take a lot of time. Or you have unsorted grid? In this case you must store XYZ coordinates in world of ALL blocks. And in all operations with array you must to find necessary blocks. I can't imagine another way. And why 2 buffers? Is this so defectively to store only 1 buffer for all cubes?

Slaihne wrote:
I chose the single huge array since there are a lot of checks for neighbours involved throughout. If the blocks were stored in chunks then there would be loads of checks for when you are at the edge which would slow down whatever you are doing.

No, just 4 more checks, not too slowly. But non-comfortable with your technique (i need to calculate borders of additional buffer for lightning)

I'm not sure you understand me here. My array is (very roughly) 512x512x256. Each of these elements is 4 bytes. It's just a plain old 3d array, the coords of each block are it's position in the array. I catually use a linear array and perform the calcs myself to get to the block i am interested in.

In terms of performance; most (if not all) of my inner loops have no conditional branching while retreiving blocks. They just have a simple calculation instead. This is one of the reasons i am able to get decent speed.

The 2 buffers are used for the light only.

Slaihne wrote:I'm not sure you understand me here. My array is (very roughly) 512x512x256. Each of these elements is 4 bytes. It's just a plain old 3d array, the coords of each block are it's position in the array. I catually use a linear array and perform the calcs myself to get to the block i am interested in.

Yeah, i understood you. Example:
You need to load from disk (or generate) new "chunk" is about 16x16x256 (for example). In this time you must unload some information from your big array. But if you unload old data and place new instead of old your links (left block have x-1 position) will be broken. How to solve this problem - sorting. But if you sort 512x512x256 blocks (for example) it will be very slow. How you solve this problem?

i use wrap around in x and z directions.

Slaihne wrote:i use wrap around in x and z directions.

Please, explain me. How do you getting a block from your array with using wrapping? After some playing time you will get very unsorted data in your big array.

Check for circular array on google you will have plenty sample.
You have to use the Modulo operator to get the element you want in the array.

S33m3, thx, do you also use circular array?

Indeed

Hi,
i love this forum! It's really informative for people working on something simliar, and you show great techniques here

I'm also working on something for fun, and i'm making good progress.
But a big time consumer is my lighting as well.

I do something pretty simliar, first i set every sunlight block (starting at the top, going down till i hit a block and then go to the next x/z coords), and after that is done i actually go through all blocks again and call a recursive function to spread their light, IF they have a light assigned too.

But that's exactly my problem. Spreading the light takes a long time for a chunk (up to 1-2 seconds for one chunk) so i was wondering how exactly you do it.

In my case i actually look at all 6 surrounding blocks and do something like if(blockIsNotSolid AND blockBrightnessIsLower) THEN callSameFunctionWith(MyLightValue * 0..

I do this until i hit a light value of 1 (starting at 16).

It takes a while.. im not sure how i could make this faster, so if you have any tips that would be great

I think you should use a profiler to know for sure why it is so slow.

This is my actual code to fill in the sunlight (it's roughly the same for the RGB channels too)...

Code:


  Private Shared Sub AddLightNode_SUN(ByVal PTR As Integer, ByVal Light As UShort)

    If Light < 1US Then
      Return
    End If

    ' make sure PTR is within view cube
    PTR = PTR Mod BALL
    If PTR < 0 Then
      PTR += BALL
    End If

    ' can't propogate into a light solid block
    If clsBlockDescriptions.Blocks(clsBlocks.BLOCKS(PTR).BlockNo).SolidToPropLight Then
      Return
    End If

    ' if the light is <= the current blocks light, then no point in continuing with it
    If Light <= (clsBlocks.LIGHTSBACK(PTR) And &HF) Then
      Return
    End If

    ' ************************************************
    ' okay, we need to continue propogating this light
    ' ************************************************

    ' lets keep a record of it to prevent backtracking
    clsBlocks.LIGHTSBACK(PTR) = (clsBlocks.LIGHTSBACK(PTR) And &HFFF0US) Or Light

    ' and dim it a bit
    Light -= 1  ' LightTabSun(Light)

    ' and continue propogating
    AddLightNode_SUN(PTR + BMX, Light)
    AddLightNode_SUN(PTR - BMX, Light)
    AddLightNode_SUN(PTR + BMZ, Light)
    AddLightNode_SUN(PTR - BMZ, Light)
    'AddLightNode_SUN(PTR + 1, Y + 1, Light)
    AddLightNode_SUN(PTR - 1, Light)

  End Sub


Notes:

The "Make sure PTR is within view cube" bit isn't perfect. It can lead to a slight artifact but does keep the PTR within the viewcube. (BALL is short for Blocks All - it is the size of the entire world block array).

The line commented out near the end prevents sunlight from filling upwards.

I use a single dimensional array for the world and the light values. I move through this array using +1 / -1 (up / down), +BMX / - BMX (east / west), +BMZ / - BMZ (north / south).

Hopefully you can follow that.

It actually very simple code, it's been shaved down to the minimum i can think off. I know this routine gets called a whole lot so i spent a long time trying to make it as fast as possible.

Oh, and if anyone has any ideas how to make it faster - i'm all ears

Slaihne, can you show me how you store data in your world and how you get access to it?

It's simple,

My 3 arrays are like so...

Public Shared BLOCKS(BALL - 1) As StructBlock
Public Shared LIGHTS(BALL - 1) As UShort
Public Shared LIGHTSBACK(BALL - 1) As UShort

BALL is basically WorldWidth * WorldDepth * WorldHeight.

If i know the X,Y,Z coords for a block i can calculate the pointer (PTR) to the block using the following code...

Code:


 Public Shared Function GetPTR(ByVal x As Integer, ByVal y As Integer, ByVal z As Integer) As Integer

    Dim bx, bz As Integer

    bx = x Mod BlockBuffWidth
    If bx < 0 Then
      bx += BlockBuffWidth
    End If
    bz = z Mod BlockBuffWidth
    If bz < 0 Then
      bz += BlockBuffWidth
    End If

    Return bx * BMX + bz * BMZ + y

  End Function


If i need to access the block above the one pointed to by PTR, then i can use PTR + 1, if i need the block below then i use PTR - 1.

If i need to access the block to the East i use PTR + BMX, North is PTR + BMZ. BMX and BMZ are easy enough to work out and depend on the size of your buffer.

There are loads of optimisations you can perform using the PTR depending on the operation you are currently carrying out.

Slaihne, thanks!
How do you process streaming (loading world when player moves) with your system? I wish to see your code or algo description. =)

I'm not sure what you mean by 'streaming'?

I use the players position in the world and work through each 'chunk' round him and ask the question...

Is this chunk the one that belongs here?
If not, then is there a chunk on file for this position? If there is, then queue a job to load it.
If not, i better queue a job to generate one.

Whether loaded, or generated it then ends up queueing other jobs to light and generate meshes.

Slaihne, you didn't understand me. My question is: what are you doing in your array, when you needs to load new chunk? And what you doing after loading (your connections left/right, will be broken). You said what you are using circular array, but i can't understand how.

Imagine you have a 2d world of huge size. Now you only want to store a small area close to the player. For this example we will only store a 3x3 area. So the world you are storing is in the following format.

Code:


abc
def
ghi


Where a = (0,0) and i = (2,2)

If the player is at coords (1,1) then you may say he is at position e. Then if the player moves down you might leave him at that position, scroll all the data up and add new data to g, h, and i.

With a circular buffer the player would change his position in the array to h. Now when he looks downwards the buffer wraps around so that he actually looks at the top row (abc) again, you could imagine it like this

Code:


abc
def
gHi
abc  <-- these are the top line again


The player started of at e, but he moved down to H, when he looks down, he sees b.

In this case, the new data needs to put in items a, b, and c.

When the player looks directly below himself he is looking at position (1,3). But that is not within the array, you would MOD the coords with 3 so that he is looking at ARRAY POSITION (1,0).

This means that position b in the array, is actually (1,0) OR (1,3) OR (1,6) OR (1,9) etc depending on where the player is.

Thanks Slaihne for the explanation about your light system
I'm actually doing it pretty simliar, although i found a few unnecessary steps in my code thanks to yours.
So what i tried is:
1) Check light level before continuing. If its to low, stop there.
2) Check if the block is emty or not. If solid, stop there
3) Calculate next light and call the function on the next 6 blocks.

But it didn't really make it faster.
Now i am thinking, it might be the code that calculates the next block for me. Im not using a one dimensional array, but i actually split it into an dictionary of [chunkX, chunkY, chunkZ][cubeX, cubeY, cubeZ] so that i can get the chunk easily.

The problem in this case is that the "wrapping" code is a bit longer (say if you have block 16 and want to know its neighbour on 17, your would have to calculate the position of the next chunk first in that dictionary).

Maybe that's the one that slows things down, i need to test this. I might end up using a one dimensional array if i see speed improvements.

Kiyaku, i can show my code of lightning propagation, but it on c++. Time for 1 chunk (16x16x256) for 1 light (sun only) is about 2-5 ms. It built on chunks system (i store a lot of arrays "chunks", which stores 16x16x256 objects of class). I want to rewrite it on 1 dimensional array, but until now i can't understand some questions. Thx Slaihne for help i'll ask some questions in future.

Slaihne, what doing this code?

Code:

If bx < 0 Then
bx += BlockBuffWidth
End If


What's mean BlockBuffWidth?

Another one question - how you get block from array if you processed streaming? Your code you shown to me should notwork in this case. Or you must to store "number of wrappings/loads". Or you calculate shifting from player position. How?

Blockbuffwidth is the width of my block buffer in world coords. It is roughly 608 * 608 * 256.

I'm not sure what you mean by your second post there?

I can always get the block from the array. The array always exists. It's just a big chunk of ram.

I can't read a chunk's block if it hasn't been generated / loaded. But then i don't even try. I won't light a chunk unless it has 8 chunks surrounding it with fully generated blocks (not meshes).

That would be nice ArchiDevil, maybe i see something that can help

I tried to strip down as much as i can, it's still not faster. I can't really test if it's the code that calculates which block to use, or if calling the function on 6 neighbours is slowing it down, without rewriting the way i store blocks, hmm.

I guess i might have to do it to see if that's the reason, that's gonna be a lot of work though. But maybe it will be worth it, especially memory wise. I'm also still using a 3 dimensional array for my chunks, because before i used more than 1 chunk for the y coordinates, which i already changed so i might as well update it.

My latest version looks like this (C#), i changed it so many times i might have added stupid mistakes, but it also shows what i need to do to find the right block:

Code:


   // Calculate light for block. x = chunkPos.x + blockPos.x, ...
    void SetLightBlock(int x, int y, int z, Light light)
    {
      // Check if the light is bright enough to continue
      if(light.strength * 0.8f > 2)
      {
         // Check if this block is AIR or not
         if (GetDensity(x, y, z) == 0)
         {
              int absX = Math.Abs(x);
              int absZ = Math.Abs(z);
      
              int modX = x < 0 ? (chunkSize.x - absX % chunkSize.x) % chunkSize.x : x % chunkSize.x;
              int modZ = z < 0 ? (chunkSize.z - absZ % chunkSize.z) % chunkSize.z : z % chunkSize.z;
      
              int ciX = x - modX;
              int ciZ = z - modZ;
      
            // Calculate next light value with a lower strength
              Light nextLight = new Light(light.color, (byte)(light.strength * 0.8f));
            
            // Apply light to our light dictionary
            m_tcache.lightData[new IntCoords(ciX, 0, ciZ)][modX, y, modZ] = nextLight;
   
            // Spread lower light to neighbours
                      SetLightBlock(x + 1, y, z, nextLight);
                      SetLightBlock(x - 1, y, z, nextLight);
   
                      SetLightBlock(x, y, z + 1, nextLight);
                      SetLightBlock(x, y, z - 1, nextLight);
   
                // Only spread horizontal for now
                    //SetLightBlock(x, y + 1, z, nextLight);
                    //SetLightBlock(x, y - 1, z, nextLight);
         }
      }
    }

Kiyaku, and what with performance with this code? =)
I know how to find block that i needs. In 1D array, 3D array, in 2D array of 3D arrays... I don't know how to find new positions of block with circular array. I'll make a picture of trouble.