Improve Execution Time in Flood-Fill Lighting Algorithm

Performance Tuning
#1

I have changed a few bits and pieces but it still takes about 6 seconds for one chunk to process the lighting.
I have tried:

[quote]-Nesting (performance intensive)if statements so that if one fail’s, it wont still call the other method(s).
-Like, above if a ‘test’ fails, i exit out of method/move to next item in loop to skip other ‘tests’
-Created a Vector3i class for integers, because i read that casting values to other types (like: float f = (float)intVal) can reduce performance.
-Made it so only points with at least 1 block (directly) adjacent to it would be added to the ‘process list’ called ‘litPoints’, Unless below is true:
—If a points doesn’t have at least 1 block directly to its up, down, n, e, s, w directions then id it does have a block diagonally to it, then it is processed.
[/quote]
I think that is it.

I will post relevant code below(Also current performance output), if you have any ways i can improve performance/execution time please tell me, Thanks.

updateLightMap(ENTRY POINT): http://pastebin.com/XCkn6KZb

updateLightMap Util Methods: http://pastebin.com/yAW0f0K5

Execution Time Output:

[INFO] [Sat Jan 02 14:52:15 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> getNeighbours(true) -> Execution Time: 72ms
[INFO] [Sat Jan 02 14:52:17 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> hasNonAirNeighbour() -> Execution Time: 2ms
[INFO] [Sat Jan 02 14:52:17 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> getNeighbours(true) -> Execution Time: 3ms
[INFO] [Sat Jan 02 14:52:17 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> getNeighbours(true) -> Execution Time: 1ms
[INFO] [Sat Jan 02 14:52:18 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> getNeighbours(true) -> Execution Time: 141ms
[INFO] [Sat Jan 02 14:52:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 5.921s
#2

Object allocation is your main bottleneck -> your getNeighbours() method is absurdly unnecessarily complex. You don’t need that method at all, since all it does is to check that you do not use indices beyond the borders of your level and that the potential neighbor is a solid block. You can include these checks in the method that calls getNeighbors().

#3

So, if i understand correctly, instead of checking if each point is valid in getNeighbours just add each point anyway then when that point is pulled out in while loop check it then?

#4

Basically yes. But you don’t have to “add” anything. My hypothesis is that you can get away with a very fast algorithm that does not allocate anything (no lists, no arrays, no vector objects).
All you need is the indices that you already iterate over in your 3-forloop.

#5

“…does not allocate anything (no lists, no arrays, no vector objects).” and “All you need is the indices that you already iterate over in your 3-forloop.”

That brings recursion to mind, is that what you mean?

#6

No, not recursion. All I am saying is that you don’t need getNeighbours() in its current form, since it doesn’t get you any information that you don’t already know in the caller.
Currently, your code can be compared to wanting to print all numbers from 1 to 10 by doing it this way: :wink:


static int[] getNumbers(int start, int end) {
  int[] res = new int[end - start + 1];
  for (int i = 0; i < res.length; i++) {
    res[i] = start + i;
  }
  return res;
}
public static void main(String[] args) {
  for (int i : getNumbers(1, 10)) {
    System.out.println(i);
  }
}
#7

Ok, got to admit it took me a while ;D. But i think i’ve got it(unless i am in a stupid mood). Will update you later.

#8

OK, here is what i have now. I don’t know if it works though because its either ultra-slow or it is looping indefinitely(if so will try fix):
(I hope this is what you had in mind)

EDIT**Code works,dunno how efficient it is yet(Added visited array, if point has been visited more than set amount, 4 just now, it skips the point):

http://pastebin.com/HPykGPxf

#9

New Solution above takes around 20ms compared to the old solutions 5-7 seconds ;D. But just found small problem with light spread.

#10

Yeah, new solution if ultra fast(compared to old) but doesn’t quite work right: http://puu.sh/mh6Qe/48103c2131.jpg

Code if you want to help me find problem: http://pastebin.com/XPvSzPjf

#11

Nice to see that you improved it that much! Those black spots must just be some minor problem.
You can do that, I’m sure. Hang in there! :slight_smile:

#12

;D Thanks for the help, it amazes me how much a change in algorithm has improved performance.

#13

Does anyone think that this looks right(i can’t tell) as i am trying to get multiple light sources to not conflict each other: http://puu.sh/mhbVz/2aa21f1008.jpg

#14

The marked parts are where it gets suspicious, do you blend the light values from intersecting light cones or do you just choose a light that is authoritative over the brightness value of the quad?

You might want to debug this with blank textures.

#15

Each faces light level is taken from the ‘air’ block opposite it. When assigning a light level to each ‘air’ block it will take the highest light level from adjacent(up, down, n, e, s, w directions) ‘air’ blocks minus 1.

then each vertex of a face is assigned a vertex color which represents its brightness(note that below code is for a single vertex of a face):

float exponentialLightPercentage = (float)Math.pow((1 - 0.2f), 15 - lightLevel);//Light decreases by 20% for each decrease in light level
        
        vertexColors.add(exponentialLightPercentage);
        vertexColors.add(exponentialLightPercentage);
        vertexColors.add(exponentialLightPercentage);
        vertexColors.add(1.0f);

Then in the fragment shader i times the output of texture(texture_sampler, outTexCoord) by the given vertex color.

#16

Set the grass and dirt blocks to white, definitely some lighting anomalies for me to try fix:

http://puu.sh/mhmfB/a6eddbad51.jpg

#17

Its the morning and i managed to get the lighting working well last night, as in multiple lights seem to be mixing well(i think):
http://puu.sh/mhX8d/e8eb6ed330.jpg

Also since it is the toopic here are the final execution times:

[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 36ms
[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 9ms
[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 9ms
[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 13ms
[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 10ms
[INFO] [Sun Jan 03 11:04:19 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 23ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 16) -> updateLightMap -> Loop Points -> Execution Time: 12ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 11ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 10ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(-16, 0, 16) -> updateLightMap -> Loop Points -> Execution Time: 8ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 9ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 12ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(16, 0, -16) -> updateLightMap -> Loop Points -> Execution Time: 9ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(16, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 9ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(0, 0, 16) -> updateLightMap -> Loop Points -> Execution Time: 14ms
[INFO] [Sun Jan 03 11:04:20 GMT 2016] [org.voxelgame.data.Chunk] Chunk(16, 0, 0) -> updateLightMap -> Loop Points -> Execution Time: 10ms
...it goes on

Thanks for the help VaTTeRGeR and especially KaiHH ;D

#18

That looks sweet, good luck!

#19

looks awesome! ;D What did you canged to get it working? Can you post your final code?

#20

Well, here’s a rundown of how the new algorithm works:


//Algorithm Preparation
Step 1: Loop through each index/block of world/chunk data
Step 1.1: If block at the index(x, y, z as using a 3d array with 3 for loops) has a Light Output > 0, set Lightmap arrays value at the blocks index to its Light Output and add its index to a processing queue.
Step 1.2 Else if the above was false, then if its x or z index is == 0 or is 1 less than the world/chunk data array's size(for that index), then set Lightmap arrays value at the blocks index to the highest surrounding light value(I only do N, E, S, W, UP, DOWN directions) minus 1. Also add this blocks indexes to the processing queue.

//Actual Algorithm
Step 2: While the processing queue is NOT empty...
Step 2.1: Poll the queue for the next point/indexes.
Step 2.2: Grab the light level for this position from the array.
Step 2.3: (This is where the magic happens) Now foreach of this indexes/blocks neighbors(Again i only do N, E, S, W, UP, DOWN directions)...
Step 2.3.2: IF this neighboring block is 'Air' or uninitialized AND its current Light Level + 2 is Less than or Equal to the light level from Step 2.2, then set its the level to the light level from Step 2.2 minus 1 and finally add it to the queue.

That’s the rundown i came up with thanks to KaiHH. Some of it may not make sense since i am not great at explaining, if a bit doesn’t just ask.