Lighting technique

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.

It takes too long for this to finish, its like 2-3 seconds now for one chunk :/

Kiyaku : In terms of your algorithm you are missing a check on whether the block is already filled with a light value of equal or greater strength. If you hit a block that is already filled with a brighter (or equal strength) light value then you should stop or else you are going to be needlessly filling the same blocks. In fact you may end up overwriting a bright light value with a lower one.

In terms of the implementation; The bottlenecks are things like calls to the math library (Abs), memory allocation library (New), and the dictionary would be a big no-no i reckon.

These operations may appear small and inconsequential in your code but they actually involve loads of code in the background. Take a simple area like dimming the lights value...

In my code it's...

Light -= 1

It's a simple +1 to an Unsigned Short variable. It probably equates to a single IL instruction.

In your's it's...

if(light.strength * 0.8f > 2)

Light nextLight = new Light(light.color, (byte)(light.strength * 0.8f));

You do the calculation twice, but the major area you are losing speed is the second line which consists of...

a floating point multiply
a cast to a byte
a call a class constructor (which leads to memory being allocated)

By the time this little lot has executed you will have run through ten's, if not 100+ IL instructions.

A small tip:

Download IL Spy (I used to recommend reflector but its no longer free)

http://wiki.sharpdevelop.net/ILSpy.ashx

Once you compile your code, point IL Spy at the exe and then find the routine you want to examine.

IL Spy decompiles the exe and shows you what is actually generated, including casts etc.

My routine as posted equates to the following...

Code:


private static void AddLightNode_SUN(int PTR, ushort Light)
{
    bool VB$CG$t_bool$S = Light < 1;
    if (!VB$CG$t_bool$S)
    {
        PTR %= 94633984;
        VB$CG$t_bool$S = (PTR < 0);
        if (VB$CG$t_bool$S)
        {
            PTR += 94633984;
        }
        VB$CG$t_bool$S = clsBlockDescriptions.Blocks[(int)clsBlocks.BLOCKS[PTR].BlockNo].SolidToPropLight;
        if (!VB$CG$t_bool$S)
        {
            VB$CG$t_bool$S = (Light <= (clsBlocks.LIGHTSBACK[PTR] & 15));
            if (!VB$CG$t_bool$S)
            {
                clsBlocks.LIGHTSBACK[PTR] = ((clsBlocks.LIGHTSBACK[PTR] & 65520) | Light);
                Light -= 1;
                clsBlockLight.AddLightNode_SUN(PTR + 256, Light);
                clsBlockLight.AddLightNode_SUN(PTR - 256, Light);
                clsBlockLight.AddLightNode_SUN(PTR + 155648, Light);
                clsBlockLight.AddLightNode_SUN(PTR - 155648, Light);
                clsBlockLight.AddLightNode_SUN(PTR - 1, Light);
            }
        }
    }
}


The only problem i spot there, off the bat, is the (int) cast in the middle of the code. I've found cast's to be a real bottleneck.

But also, IL Spy will let you click on your function calls and examine the code that they execute. I don't have any calls in my routine so i know that what i see is what i get.

Good luck

@Slaihne
Thanks a lot for the detailed post.
You are right, i totally forgot the check if that block already has an equal or bigger light value to skip it. It got lost when i rewrote that script.

But yeah even if i add this again, i would have to do the same steps (declaring lots of variables to find the block in my dictionary) to find the block, which would slow it down again.

I felt awkward when writing this code and saw what i need to do in order to find a block. I think the dictionary approach is really not good speed-wise (it's awesome to store/find stuff though heh).

So i guess i will rewrite it, using a one dimensional array. I'm a bit afraid it would take a lot to find the block in it as well, but i saw your code earlier and it doesn't look like too much work to find the right block.

I also actually used negative coordinates for my chunk array. I think using unsigned ints for block positions would be better in this case, and just wrap it around, like you did i think.

Thanks again, i'll definitely try ILSpay, looks like a really good debugging tool.

Alright, time to make a backup and rewrite stuff. I'll let you know how it goes

So, picture of my trouble:
img268 . imageshack . us/img268/8310/unled1bow.jpg (delete spaces)
How calculate correct position?

I uploaded a pic of how the buffer works.

https://blokworld.forumotion.co.uk/gallery/General-Images/2d-Circular-buffer-pic_14.htm

In your diagram you seem to have 'shifted' the buffer up an element. This doesn't happen in a circular buffer. You don't move the buffer, you move the player inside the buffer and make sure that you wrap around any access to an element in the array (see 2 + 3 + 4) in the diagram.

For the buffer to work, you need to be putting the correct data in each element. The way i do it is this...

I have a chunk overlay of the world. It's a simple 2d array containing X and Z coords for each chunk. This buffer holds the WORLD coords of the chunk that EXISTS in the underlying block data.

I also have a second overlay that holds the WORLD coords of the chunk that we EXPECT to be in the underlying data. As the player moves, this is the array i update.

Now, it is simple enough to pass through each 'chunk' in the loaded world and compare what EXISTS with what we EXPECT. If they differ, then we need to make what EXISTS the same as what we EXPECT.

I hope that clears some of it up.