If you fill an area of M x N pixels with data, you will inevitably do M*N writes and therefore your complexity is still order M*N. Running this on a GPU gives you a fixed amount of parallelism, but the complexity is still order M*N. You cannot magically make M*N writes (= observable changes) with order log(M*N) complexity. Practical speed-up (which is super valuable) is not the same as complexity.
I believe this comment is correct. In the case of purely filling a volume the jump flood algorithm has no advantage over breath first, or depbh first search.
it doesn't change the complexity because as N,M -> infinity, your gpu's parallelism, even if it's a factor of 10,000,000x, whatever it is, has some phyiscal limits, due to the number of cores, the clock speed, visual RAM, and so on. Therefore you still have O(NM) with a gpu. That being said, basically, the complexity would look logarithmic for a while, and then eventually become dominated by c*NM. Hope that helps! (I have NO clue what I'm talking about lmao but I still think it's correct)
The “gpu” complexity also assumes the GPU can work on infinitely large amounts of work in parallel and is a measure of how well the algorithm parallelizes under ideal hardware. Even single-thread time complexity is not physically accurate. Memory latency grows with memory size so an O(1) operation is in reality O(sqrt(N))
@@canaDavid1as long as you are using the same GPU, we can consider K to be constant, so that it's still O(M*N) . Of course the calculation time can be reduced by a hardware upgrade, but that's not what's usually meant when we talk about the time complexity of an algorithm.
This works for empty rectangles, but given a painting tool, you have to account for bounds (pre-filled space), which if I understand correctly this algorithm does not account for?
Bounds checking even has to happen in the rectangular case, but the cost of the bounds checking is simple and constant. I believe bounds checking for a general polyhedral can be reduced to below linear time (with respect to the number of sides). So, the cost of it will unlikely dominate the cost of the computation of the flood itself.
@@adamluterNot just bounds, but filled spaces, as the parent comment notes. If I draw a donut and fill the outside, flood fill will not fill the middle because there's no path to the center of the donut. I'm with the parent comment here -- I don't understand how this takes that into account.
If there are a some kind of wave front collision? Flood fill can fill arbitrary any shape, but this alghorithm is not, or it is not demonstrated. Also, does it work for 3d? Can it handle light propagation like in minecraft, where bhread first floodfill alghorithm is used?
I wish you explain a couple of the next steps at 5:30... Like for example at 5:38 point 1,0 is green, how? From where this was calculated? This is more than 2 from its origin at 1,4. Is this a neighbor of the neighbor? If so then which one? If will be calculating every neighbor of the neighbor this could be an infinite loop. 5:40 why the algorithm continues only with blue and green and didn't even start working on yellow?
If I followed the explanation, then to answer you question you have a list of seed points for each color. You are processing say the color green, this means going to every current point for this color (which is initially just the seed point), and adding up to 8 more entries. If while you are doing this you discover a non-empty color you *only* lookup two more points: you look up the seed point for you color, which is the first entry of your current list, and the seed point of the discovered color, which is also the first entry of the discovered color's list. This is the peudo code for the algorithm: lookup = { green: [0,0], yellow: [3,3], blue: [2,1] }; jumptable = [[-1,-1],[0,-1],[1,-1],[-1,0],[0,0],[1,0][-1,1],[0,1],[1,1]; jump = 8; while(jump = jump/2 > 1) { foreach(color, points in lookup) { thisseed = points[0]; foreach(point in points) { foreach(jumpdir in jumptable) { checkpoint = point + jumpdir * jump; if (checkpoint.color == empty) { checkpoint.color = color; points.push(point); else { otherseed = lookup[checkpoint.color][0]; closercolor = closer(thisseed, otherseed); if(closercolor == color) { checkpoint.color = color; points.push(point); } } } } } } (I'm not clear if in the final else, do we need to remove the othercolors point from his list. I think you do not, though that means the number of these closer checks is rather high)?
So Wikipedia says 'constant-time performance' then says O(N x log N). This video says O(log N). One comment here says O(N x N) - literally MN. Another comment says O(N x N x log N) - literally O( n^2 log(n) / p ). My goodness, which is it???
If you fill an area of M x N pixels with data, you will inevitably do M*N writes and therefore your complexity is still order M*N. Running this on a GPU gives you a fixed amount of parallelism, but the complexity is still order M*N. You cannot magically make M*N writes (= observable changes) with order log(M*N) complexity. Practical speed-up (which is super valuable) is not the same as complexity.
I believe this comment is correct. In the case of purely filling a volume the jump flood algorithm has no advantage over breath first, or depbh first search.
it doesn't change the complexity because as N,M -> infinity, your gpu's parallelism, even if it's a factor of 10,000,000x, whatever it is, has some phyiscal limits, due to the number of cores, the clock speed, visual RAM, and so on. Therefore you still have O(NM) with a gpu. That being said, basically, the complexity would look logarithmic for a while, and then eventually become dominated by c*NM. Hope that helps! (I have NO clue what I'm talking about lmao but I still think it's correct)
The “gpu” complexity also assumes the GPU can work on infinitely large amounts of work in parallel and is a measure of how well the algorithm parallelizes under ideal hardware.
Even single-thread time complexity is not physically accurate. Memory latency grows with memory size so an O(1) operation is in reality O(sqrt(N))
It can, however, be of the form O(M*N/K), where K is the number of cores in your GPU.
@@canaDavid1as long as you are using the same GPU, we can consider K to be constant, so that it's still O(M*N) . Of course the calculation time can be reduced by a hardware upgrade, but that's not what's usually meant when we talk about the time complexity of an algorithm.
I love videos like these. Didn't understand it at all, though. I wish you went more into details on the efficiency part.
This works for empty rectangles, but given a painting tool, you have to account for bounds (pre-filled space), which if I understand correctly this algorithm does not account for?
Bounds checking even has to happen in the rectangular case, but the cost of the bounds checking is simple and constant. I believe bounds checking for a general polyhedral can be reduced to below linear time (with respect to the number of sides). So, the cost of it will unlikely dominate the cost of the computation of the flood itself.
@@adamluterNot just bounds, but filled spaces, as the parent comment notes. If I draw a donut and fill the outside, flood fill will not fill the middle because there's no path to the center of the donut. I'm with the parent comment here -- I don't understand how this takes that into account.
If there are a some kind of wave front collision? Flood fill can fill arbitrary any shape, but this alghorithm is not, or it is not demonstrated. Also, does it work for 3d? Can it handle light propagation like in minecraft, where bhread first floodfill alghorithm is used?
Seems like this algorithm can be adapted to all of those cases at a first glance.
I wish you explain a couple of the next steps at 5:30...
Like for example at 5:38 point 1,0 is green, how? From where this was calculated? This is more than 2 from its origin at 1,4.
Is this a neighbor of the neighbor? If so then which one? If will be calculating every neighbor of the neighbor this could be an infinite loop.
5:40 why the algorithm continues only with blue and green and didn't even start working on yellow?
If I followed the explanation, then to answer you question you have a list of seed points for each color. You are processing say the color green, this means going to every current point for this color (which is initially just the seed point), and adding up to 8 more entries.
If while you are doing this you discover a non-empty color you *only* lookup two more points: you look up the seed point for you color, which is the first entry of your current list, and the seed point of the discovered color, which is also the first entry of the discovered color's list.
This is the peudo code for the algorithm:
lookup = { green: [0,0], yellow: [3,3], blue: [2,1] };
jumptable = [[-1,-1],[0,-1],[1,-1],[-1,0],[0,0],[1,0][-1,1],[0,1],[1,1];
jump = 8;
while(jump = jump/2 > 1) {
foreach(color, points in lookup) {
thisseed = points[0];
foreach(point in points) {
foreach(jumpdir in jumptable) {
checkpoint = point + jumpdir * jump;
if (checkpoint.color == empty) {
checkpoint.color = color;
points.push(point);
else {
otherseed = lookup[checkpoint.color][0];
closercolor = closer(thisseed, otherseed);
if(closercolor == color) {
checkpoint.color = color;
points.push(point);
}
}
}
}
}
}
(I'm not clear if in the final else, do we need to remove the othercolors point from his list. I think you do not, though that means the number of these closer checks is rather high)?
Thanks! I've searched for such algorithm!
Very informative. Thanks for your video.
Not helpful if you want to fill an arbitrary shape and that's what foodfill is for.
Best explanation out there! Thanks a lot!
Brilliant
Thank you so much)
thank you!
So Wikipedia says 'constant-time performance' then says O(N x log N). This video says O(log N). One comment here says O(N x N) - literally MN. Another comment says O(N x N x log N) - literally O( n^2 log(n) / p ).
My goodness, which is it???
I'll give you another one, it's O(n) because n is the number of pixels not the dimension of a side.
It seems nice, but it's not cache-friendly with real world usage like in a 4k texture for example.
Cache