Lighting technique

Page 3 of 3 Previous  1, 2, 3

View previous topic View next topic Go down

Re: Lighting technique

Post by Kiyaku on Mon Aug 15, 2011 9:45 am

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

Posts : 5
Join date : 2011-08-11

View user profile

Back to top Go down

Re: Lighting technique

Post by Slaihne on Mon Aug 15, 2011 11:15 am

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
avatar
Slaihne

Posts : 264
Join date : 2011-03-17
Age : 50

View user profile

Back to top Go down

Re: Lighting technique

Post by Kiyaku on Mon Aug 15, 2011 11:55 am

@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 Smile
avatar
Kiyaku

Posts : 5
Join date : 2011-08-11

View user profile

Back to top Go down

Re: Lighting technique

Post by ArchiDevil on Mon Aug 15, 2011 12:28 pm

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

ArchiDevil

Posts : 21
Join date : 2011-07-26

View user profile

Back to top Go down

Re: Lighting technique

Post by Slaihne on Mon Aug 15, 2011 1:05 pm

I uploaded a pic of how the buffer works.

http://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.
avatar
Slaihne

Posts : 264
Join date : 2011-03-17
Age : 50

View user profile

Back to top Go down

Re: Lighting technique

Post by Slaihne on Mon Aug 15, 2011 1:15 pm

Kiyaku, you also may want to explore unsafe arrays..

http://msdn.microsoft.com/en-us/library/chfa2zb8%28v=vs.71%29.aspx
http://msdn.microsoft.com/en-us/library/aa288474%28v=vs.71%29.aspx

I'm not a C# guy really so haven't messed with them but my understanding is that they could get you closer to the C / C++ style of handling memory and could give a speed boost.

Unsafe would work well (i think) with the routine i posted earlier.
avatar
Slaihne

Posts : 264
Join date : 2011-03-17
Age : 50

View user profile

Back to top Go down

Re: Lighting technique

Post by ArchiDevil on Tue Aug 16, 2011 2:47 pm

Slaihne, thanks! I'll try to use it.
Later: you early shown me function that return pointer (index) of element from your big array. Do you use only this 1 function? In circular array this function will return incorrect value of element. You don't process any conditions in this function, do you process condition before using?

ArchiDevil

Posts : 21
Join date : 2011-07-26

View user profile

Back to top Go down

Re: Lighting technique

Post by Slaihne on Wed Aug 17, 2011 1:12 am

ArchiDevil: The routine does return the correct index into my array. Don't forget, my array is circular on 2 axis (x,z).

The routine takes the WORLD x and z coords and maps them onto the ARRAY x and z coords. Thats what the MOD's are all about. Then it performs a small calculation at the end to convert x, z, and y to an index into a single dimension array.
avatar
Slaihne

Posts : 264
Join date : 2011-03-17
Age : 50

View user profile

Back to top Go down

Re: Lighting technique

Post by ArchiDevil on Thu Aug 18, 2011 2:59 am

Slaihne, i'm so stupid, sorry. I tried your system and it works very well, i don't know how i can.t understand it early, it so easy.
Now i have one little question - how you calculate light on initial loading. Your function you shown before works only near player (not on borders of the world). In initial loading you must check borders in you main array (if you load data unsorted). How i imagine loading:
Pseudocode:
Code:

GetInfoFromFile(filename);
for ...
SetCubeType(PTR, Type);
But in this case border of the world can be somewhere not in real border. And you can't process lightpropagation for left (or right) blocks. What are you doing in this situation (not code, only how it looks in words)?

ArchiDevil

Posts : 21
Join date : 2011-07-26

View user profile

Back to top Go down

Re: Lighting technique

Post by Slaihne on Thu Aug 18, 2011 3:28 am

This was one of the hardest parts for me to get. But basically you can't generate light for a chunk unless ALL it's neighbours contain the correct blocks.

If the player is at the center you end up with...

Code:

33333
32223
32123
32223
33333

3 = these chunks have only blocks
2 = these chunks can be lit
1 = these chunks can have their mesh built.

You can't light 3 since it's neighbours aren't loaded / generated.
You can't build meshes for 2 since they touch 3's (which aren't lit)

I'll leave organising this up to yourself since it is difficult to explain.
avatar
Slaihne

Posts : 264
Join date : 2011-03-17
Age : 50

View user profile

Back to top Go down

Re: Lighting technique

Post by ArchiDevil on Sat Sep 17, 2011 8:13 am

Slaihne, big thanks for all! I've rewrote my world storage system into one circular array, and it's so fast (some troubles here as: inline functions, hyper-using of stack and etc.).

ArchiDevil

Posts : 21
Join date : 2011-07-26

View user profile

Back to top Go down

Re: Lighting technique

Post by Sponsored content


Sponsored content


Back to top Go down

Page 3 of 3 Previous  1, 2, 3

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum