Flood fill

Monkey Forums/Monkey Programming/Flood fill

Sub_Zero (Posted 2013) [#1]

Does anyone have a gradient fill function? Edit: Should be flood fill! (sorry) :)

Goodlookinguy (Posted 2013) [#2]

I ripped these from my code library and changed them to work with default mojo. I was going to make one that could do a gradient fill at any angle but lost interest when I realized that I would never use it. Well, anyways, here you go. Function RGBToInt:Int( r:Int, g:Int, b:Int, a:Int = 255 ) Return (a Shl 24) | (r Shl 16) | (g Shl 8) | b End Function IntToA:Int( color:Int ) Return (color Shr 24) & $FF End Function IntToR:Int( color:Int ) Return (color Shr 16) & $FF End Function IntToG:Int( color:Int ) Return (color Shr 8) & $FF End Function IntToB:Int( color:Int ) Return color & $FF End Function CreateHorzGradient:Image( width:Int, height:Int, startColor:Int, endColor:Int ) Local image:Image, x, y, r, g, b, a, percent:Float, color:Int Local rr, gg, bb, aa, startR, startG, startB, startA Local pixels:Int[width * height] image = CreateImage(width, height) startR = IntToR(startColor) startG = IntToG(startColor) startB = IntToB(startColor) startA = IntToA(startColor) rr = (IntToR(endColor) - startR) gg = (IntToG(endColor) - startG) bb = (IntToB(endColor) - startB) aa = (IntToA(endColor) - startA) For y = 0 Until height percent = y / Float(height) r = startR + rr * percent g = startR + gg * percent b = startR + bb * percent a = startR + aa * percent color = RGBToInt(r, g, b, a) For x = 0 Until width pixels[y * width + x] = color Next Next image.WritePixels(pixels, 0, 0, width, height) Return image End Function CreateVertGradient:Image( width:Int, height:Int, startColor:Int, endColor:Int ) Local image:Image, x, y, r, g, b, a, percent:Float, color:Int Local rr, gg, bb, aa, startR, startG, startB, startA Local pixels:Int[width * height] image = CreateImage(width, height) startR = IntToR(startColor) startG = IntToG(startColor) startB = IntToB(startColor) startA = IntToA(startColor) rr = (IntToR(endColor) - startR) gg = (IntToG(endColor) - startG) bb = (IntToB(endColor) - startB) aa = (IntToA(endColor) - startA) For x = 0 Until width percent = x / Float(width) r = startR + rr * percent g = startR + gg * percent b = startR + bb * percent a = startR + aa * percent color = RGBToInt(r, g, b, a) For y = 0 Until height pixels[y * width + x] = color Next Next image.WritePixels(pixels, 0, 0, width, height) Return image End

Sub_Zero (Posted 2013) [#3]

Thanks for that... Does anyone have a simple fill function? Single color will do fine. It needs to work similar to that of bucket fill in mspaint.

Nobuyuki (Posted 2013) [#4]

That's doubtful. Why don't you take a look at this? http://en.wikipedia.org/wiki/Flood_fill Disclaimer: I used to use recursive floodfill back in high school and managed to overflow the call stack in VB on anything larger than a small sprite's worth of fill. My suggestion is to look into the alternative method. These sorts of things have very limited application, so you won't usually see them around in a zillion easy-to-digest forms.

Goodlookinguy (Posted 2013) [#5]

I think I misunderstood the original question... Anyways, if we're talking about flood filling, I've also done recursive flood filling and caused a stack overflow. I strongly recommend the queue version talked about in the Wikipedia page. It has a much lower chance of this problem and is a lot faster.

Sub_Zero (Posted 2013) [#6]

Thanks guys :) Will have a look :)

Sub_Zero (Posted 2013) [#7]

Ended up with these two: 4-way flood fill function using stacks: Method FloodFill:Int(x:Int, y:Int, tcolor:Int, rcolor:Int) Local q:= New IntStack Local nx:Int, ny:Int Local trect:Int[] = New Int[DeviceWidth() * DeviceHeight()] ReadPixels(trect, 0, 0, DeviceWidth(), DeviceHeight()) If trect[x + (y*DeviceWidth())] <> tcolor Return 0 q.Push(x) q.Push(y) While q.Length > 0 ny = q.Pop() nx = q.Pop() If trect[nx + (ny*DeviceWidth())] = tcolor trect[nx + (ny*DeviceWidth())] = rcolor If nx > 0 q.Push(nx-1); q.Push(ny); 'Print "West.." Endif If nx < DeviceWidth() q.Push(nx+1); q.Push(ny); 'Print "East.." Endif If ny > 0 q.Push(nx); q.Push(ny-1);' Print "North..." Endif If ny < DeviceHeight() q.Push(nx); q.Push(ny+1); 'Print "South..." Endif Endif Wend img = CreateImage(DeviceWidth(), DeviceHeight()) img.WritePixels(trect, 0, 0, DeviceWidth(), DeviceHeight()) Return 0 End Method Flood fill Scanline function using stacks (faster): Method FloodFillScanlineStack:Int(x:Int, y:Int, newColor:Int, oldColor:Int) If(oldColor = newColor) Return 0 Local qx:= New IntStack Local qy:= New IntStack Local y1:Int Local spanLeft:Int, spanRight:Int qx.Push(x) qy.Push(y) Local screenBuffer:Int[] = New Int[DeviceWidth() * DeviceHeight()] ReadPixels(screenBuffer, 0, 0, DeviceWidth(), DeviceHeight()) While(qx.Length > 0) x = qx.Pop() y = qy.Pop() y1 = y While(y1 >= 0 And screenBuffer[x+(y1*DeviceWidth())] = oldColor) y1 -= 1 Wend y1 += 1 spanLeft = 0 spanRight = 0; While(y1 < DeviceHeight() And screenBuffer[x+(y1*DeviceWidth())] = oldColor ) screenBuffer[x+(y1*DeviceWidth())] = newColor; If(Not spanLeft And x > 0 And screenBuffer[(x - 1)+(y1*DeviceWidth())] = oldColor) qx.Push(x-1); qy.Push(y1) spanLeft = 1; Elseif(spanLeft And x > 0 And screenBuffer[x - 1+(y1*DeviceWidth())] <> oldColor) spanLeft = 0; Endif If(Not spanRight And x < DeviceWidth() - 1 And screenBuffer[x + 1+(y1*DeviceWidth())] = oldColor) qx.Push(x+1); qy.Push(y1) spanRight = 1; Elseif(spanRight And x < DeviceWidth() - 1 And screenBuffer[x + 1+(y1*DeviceWidth())] <> oldColor) spanRight = 0; Endif y1 += 1; Wend Wend img = CreateImage(DeviceWidth(), DeviceHeight()) img.WritePixels(screenBuffer, 0, 0, DeviceWidth(), DeviceHeight()) Return 0 End Method

Gerry Quinn (Posted 2013) [#8]

If you need a fill that always works properly, it might be better to find out how to edit the stack size on your target(s). EDIT: Never mind, I didn't read properly and thought people were talking about an old memory-saving technique using a cyclic buffer, which used relatively little memory at the cost of sometimes doing an incomplete fill. The various techniques to replace stack by heap allocation are fine.

maltic (Posted 2013) [#9]

Or just use your own stack data-structure, like Sub_Zero's example code. Using the call stack or using your own stack is (in this case) functionally equivalent. A stack based flood-fill is optimal, I think. You consider every pixel only once--which you have to do to draw them anyway, and use at most O(L) memory on the stack (where L is the length in pixels from the start point to the furthest away pixel to be filled) as opposed to O(W) using a queue (where W is the maximum size in pixels of the perimeter of your flood fill area).