Good algorithm for flood fill?

Luatee · July 8, 2013, 3:02pm

Hey all, Ive got this algorithm for flood fill:

function floodFill(x,y,fillColor,interiorColor) 
    local colour = screen:get(x,y)
    if (colour==interiorColor) then
        screen:set(x,y,fillColor)
        floodFill(x+1,y,fillColor,interiorColor)
        floodFill(x-1,y,fillColor,interiorColor)
        floodFill(x,y+1,fillColor,interiorColor)
        floodFill(x,y-1,fillColor,interiorColor)    
    end
end

It works in small spaces but due to the huge amount of image:get use a stack overflow occurs, how is this preventable or is there another algorithm I can use that is less memory consuming than this one?

SkyTheCoder · July 8, 2013, 3:14pm

I know there’s one in Spritely, maybe you could check that out?

Luatee · July 8, 2013, 4:07pm

cant find one on there

Andrew_Stacey · July 8, 2013, 5:35pm

Probably not of any use to you, but was fun to do:


function setup()
    displayMode(FULLSCREEN)
    w,h = WIDTH,HEIGHT
    img = image(w,h)
    imga = image(w,h)
    setContext(img)
    noSmooth()
    background(255, 255, 255, 255)
    local x,y,rw,rh,c
    local colours = {
        color(255, 0, 0, 255),
        color(0, 255, 0, 255),
        color(0,0,255,255),
        color(0,255,255,255),
        color(255,0,255,255),
        color(255,255,0,255),
        color(0,127,255,255),
        color(255,0,127,255),
        color(127,255,0,255)
    }
    for n=1,100 do
        x = math.random(1,w)
        y = math.random(1,h)
        rw = math.random(10,100)
        rh = math.random(10,100)
        c = math.random(1,9)
        fill(colours[c])
        rect(x,y,rw,rh)
    end
    setContext()
    m = mesh()
    m.texture = img
    m:addRect(w/2,h/2,w,h)
    m.shader = shader(FloodShader())
    m.shader.width = w*2
    m.shader.height = h*2
    m.shader.fillFrom = color(0, 0, 0, 0)
    m.shader.fillTo = color(115, 123, 50, 255)
end

function draw()
    background(0, 0, 0, 255)
    noSmooth()
    setContext(imga)
    background(0, 0, 0, 255)
    if pt then
        blendMode(ONE,ZERO,ZERO,ONE)
    else
        blendMode(ONE,ZERO,ONE,ZERO)
    end
    m:draw()
    setContext()
    img,imga = imga,img
    m.texture = img
    spriteMode(CORNER)
    sprite(img,(WIDTH-w)/2,(HEIGHT-h)/2)
    if pt then
        local x = math.floor(pt.x - (WIDTH-w)/2)
        local y = math.floor(pt.y - (HEIGHT-h)/2)
        local r,g,b,a = img:get(x,y)
        m.shader.fillFrom = color(r,g,b,a)
        img:set(x,y,r,g,b,0)
        pt = false
    end
end

function touched(t)
    if t.state == ENDED then
        pt = vec2(t.x,t.y)
    end
end


function FloodShader()
    return [[
//
// A basic vertex shader
//

//This is the current model * view * projection matrix
// Codea sets it automatically
uniform mat4 modelViewProjection;

//This is the current mesh vertex position, color and tex coord
// Set automatically
attribute vec4 position;
attribute vec4 color;
attribute vec2 texCoord;

//This is an output variable that will be passed to the fragment shader
varying lowp vec4 vColor;
varying highp vec2 vTexCoord;

void main()
{
    //Pass the mesh color to the fragment shader
    vColor = color;
    vTexCoord = texCoord;
    
    //Multiply the vertex position by our combined transform
    gl_Position = modelViewProjection * position;
}
]],[[
//
// A basic fragment shader
//

//Default precision qualifier
precision highp float;

//This represents the current texture on the mesh
uniform lowp sampler2D texture;
uniform float width;
uniform float height;
float rw = 1./width;
float rh = 1./height;
uniform lowp vec4 fillFrom;
lowp vec4 fillFromA = vec4(fillFrom.xyz,0.);
uniform lowp vec4 fillTo;
//The interpolated vertex color for this fragment
varying lowp vec4 vColor;

//The interpolated texture coordinate for this fragment
varying highp vec2 vTexCoord;

void main()
{
    //Sample the texture at the interpolated coordinate
    lowp vec4 col = texture2D( texture, vTexCoord );
    lowp float a;
    if (col == fillFromA) {col = fillTo;} else {
    if (col == fillFrom) {
        a = texture2D(texture, vTexCoord + vec2(rw,0.)).a;
        if (a < .5) {
            col.a = 0.;
        } else {
        a = texture2D(texture, vTexCoord + vec2(-rw,0.)).a;
        if (a < .5) {
            col.a = 0.;
        } else {
        a = texture2D(texture, vTexCoord + vec2(0.,rh)).a;
        if (a < .5) {
            col.a = 0.;
        } else {
        a = texture2D(texture, vTexCoord + vec2(0.,-rh)).a;
        if (a < .5) {
            col.a = 0.;
        } 
        }
        }
        }
    }
    }
    //Set the output color to the texture color
    gl_FragColor = col;
}
]]
end

Ignatz · July 8, 2013, 5:48pm

This is a simple and successful approach I used. You can’t run out of memory this way.

You need two tables, A=squares to fill, B=squares already examined

Find a starting square x,y, add to A eg table.insert(A,vec2(x,y))
Take the first square in A
Look at all neighbours. Add to A if they meet the conditions and aren’t in B
Fill the square we are in, mark it as examined in table B
Delete the first square in table A
Repeat from step 2 until A is empty

Luatee · July 9, 2013, 9:57am

Well ignatz I tried what you said but I interpreted it atleast 5 different ways, ended up with this:

     function setup()
     local x,y = 0,0
    dir = {vec2(x+1,y),
            vec2(x-1,y),
            vec2(x,y+1),
            vec2(x,y-1),
            vec2(x+1,y+1),
            vec2(x+1,y-1),
            vec2(x-1,y+1),
            vec2(x-1,y-1)}
     end
     if tool == "fill" then
        if t.state == BEGAN then
            filla = {vec2(t.x,t.y)}
            fillpos = vec2(t.x,t.y)
            fillx = t.x
            filly = t.y
            fillcol = col
            intcol = screen:get(t.x,t.y)
            if fillcol ~= intcol then
                filling = true
            end
        end
    end
    --algorithm 1
    if filling and (1/DeltaTime) > 10 then
        for k,v in pairs(filla) do
            for i=1,4 do
                local dx,dy = dir[i].x,dir[i].y
                if screen:get(v.x+dx,v.y+dy) == intcol then
                    screen:set(v.x+dx,v.y+dy,fillcol)
                    table.insert(filla,vec2(v.x+dx,v.y+dy))
                end
            end
            if filla[k] then table.remove(filla,k) end
        end
        oldfilla = #filla
        if oldfilla == 0 then
            filling = false
        end
    end

Ignatz · July 9, 2013, 10:29am

@Luatee - Try this. You can include the diagonal neighbours as well if you wish, just check you don’t fall off the edge of the image. You can make it faster if you check whether the neighbours have already been processed, but this will require another table to keep track of them.

function setup()
    img=readImage("Planet Cute:Character Princess Girl")
    floodFill(img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
    background(220)
    sprite(img,WIDTH/2,HEIGHT/2)
end

function floodFill(img,startX,startY,fillColor,interiorColor) 
    tbl={}
    tbl[1]=vec2(startX,startY)
    --just compare r,g,b and not a
    local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
    while #tbl>0 do
        local x,y=tbl[1].x,tbl[1].y
        local r,g,b,a = img:get(x,y)
        local c2=(r*256+g)*256+b
        if (c1==c2) then
            img:set(x,y,fillColor)
            --add neighbours
            if x<img.width then tbl[#tbl+1]=vec2(x+1,y) end
            if x>1 then tbl[#tbl+1]=vec2(x-1,y) end
            if y>1 then tbl[#tbl+1]=vec2(x,y-1) end
            if y<img.height then tbl[#tbl+1]=vec2(x,y+1) end
        end 
        table.remove(tbl,1)  -- remove the item we've just processed
    end
end

Ignatz · July 9, 2013, 10:43am

This version is more efficient, it keeps track of used pixels as I suggested just above

function setup()
    img=readImage("Planet Cute:Character Princess Girl")
    floodFill(img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
    background(220)
    sprite(img,WIDTH/2,HEIGHT/2)
end

function floodFill(img,startX,startY,fillColor,interiorColor) 
    tbl={}
    tbl2={}
    tbl[1]=vec2(startX,startY) 
    local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
    while #tbl>0 do
        local x,y=tbl[1].x,tbl[1].y
        tbl2[x*3000+y]=1
        local r,g,b,a = img:get(x,y)
        local c2=(r*256+g)*256+b
        if (c1==c2) then
            img:set(x,y,fillColor)
            if x<img.width and tbl2[(x+1)*3000+y]==nil then tbl[#tbl+1]=vec2(x+1,y) end
            if x>1 and tbl2[(x-1)*3000+y]==nil then tbl[#tbl+1]=vec2(x-1,y) end
            if y>1 and tbl2[x*3000+y-1]==nil then tbl[#tbl+1]=vec2(x,y-1) end
            if y<img.height and tbl2[x*3000+y+1]==nil then tbl[#tbl+1]=vec2(x,y+1) end
        end 
        table.remove(tbl,1)  
    end
end

Luatee · July 9, 2013, 10:53am

Just tried that second one ignatz, works about twice as fast as my original one thanks, im guessing you dont mind if I use it anyway? Im guessing when the code is run in its raw format in xcode and not run in an IDE it will be faster aswell?

Ignatz · July 9, 2013, 11:07am

I don’t know about xCode

Sure, use the code.

Just make the two tables local, I forgot that!

Luatee · July 9, 2013, 12:04pm

Ah right, well seeming as I dont own a mac I wont be able to test this, but has anyone else noticed a speed difference in stuff like indexing tables and raw values when changed to xcode, mainly a positive speed increase Id guess.

Thanks, ive done that now

SkyTheCoder · July 9, 2013, 1:02pm

That would depend on how fast your Mac/iPad is.

Luatee · July 9, 2013, 2:08pm

Well exactly but if running a code through an ide it has to be converted first, so heavy use of image functions and such I’m guessing would slow it down whereas if it were converted to xcode and run through that then it would be faster as it isn’t going through the IDE, just logical thinking in guessing that it does so… Correct me if Im wrong.

On the other hand here is an algorithm I thought up earlier, I assume its been thought of before it is quite simple, anyway: http://youtu.be/plN745WuoN4

SkyTheCoder · July 9, 2013, 2:12pm

I think it just has to convert the code when you first start it, not the whole time it’s running. And, of course, in 1.5.3 TLL made sprite() almost as fast as mesh.

SkyTheCoder · July 9, 2013, 2:18pm

I found the flood fill algorithm in Spritely. It’s a little bit down in the EditGrid tab. Code:

function EditGrid:testPix(x, y, c, img)
    local r, g, b, a
    test =false
    if x >= 1 and x <= img.width then
        if y >= 1 and y <= img.height then
            r, g, b, a = img:get(x, y)
            if a == c.a and b == c.b and g == c.g and r == c.r then
                test = true
            end
        end
    end
    return test
end

function EditGrid:floodFill()
    local x, y, c, i, spots, timg
    local spot = {}
    img = self.img:copy()
    -- find the color that was touched
    r, g, b, a = img:get(self.cx, self.cy)
    c = color(r, g, b, a)
    -- if touched = color to use, then exit
    if c == self.clr then
        return nil
    end
    -- use the initial location as first candidate spot
    spots = 1
    spot[1] = vec2(self.cx, self.cy)
    img:set(spot[1].x, spot[1].y, self.clr)
    oldspots = 1
    searching = true
    -- keep going until there are no new spots found
    while searching do
        for i = 1, oldspots do
            -- find candidates
            x = spot[i].x
            y = spot[i].y
            
            -- check down
            if self:testPix(x, y - 1, c, img) then
                img:set(x, y - 1, self.clr)
                spots = spots + 1
                spot[spots] = vec2(x, y - 1)
            end
            -- check left
            if self:testPix(x - 1, y, c, img) then
                img:set(x - 1, y, self.clr)
                spots = spots + 1
                spot[spots] = vec2(x - 1, y)
            end
            -- check right
            if self:testPix(x + 1, y, c, img) then
                img:set(x + 1, y, self.clr)
                spots = spots + 1
                spot[spots] = vec2(x + 1, y)
            end
            -- check up
            if self:testPix(x, y + 1, c, img) then
                img:set(x, y + 1, self.clr)
                spots = spots + 1
                spot[spots] = vec2(x, y + 1)
            end
        end
        if spots > 1024 then
            searching = false
        end
        if spots == oldspots then -- no new pixels to change found
            searching = false
        end
        oldspots = spots
    end
    spot = nil
    self.img = img:copy()
end

Luatee · July 9, 2013, 4:46pm

but how long does it take if you fill an area half the size of the screen?

Ignatz · July 9, 2013, 6:00pm

@Luatee - maybe you should use a shader, if you are converting every pixel of a certain colour. You could draw to an image with setContext and a shader.

But why are you flood filling such a big image anyway?

Luatee · July 9, 2013, 7:42pm

I’m making a drawing app, I’ve never properly looked at shaders i meant to but I never got round to it so i can’t help myself there

Ignatz · July 9, 2013, 8:06pm

A shader can flood fill the entire image, but not just part of the image (it would replace EVERy matching pixel in the whole image), so it wouldn’t work in a drawing app.

Ignatz · July 9, 2013, 8:36pm

@Luatee - if you can’t make flood fill any faster, you can at least entertain the user while it is happening (after all, that’s why splash screens were invented!). This version of the code fills progressively so the user can see how it’s going, using coroutines.

function setup()
    img=readImage("Planet Cute:Character Princess Girl")
    flood=coroutine.create(floodFill)
    coroutine.resume(flood,img,1,1,color(255,255,0,255),color(0,0,0,0))
end

function draw()
    background(220)
    sprite(img,WIDTH/2,HEIGHT/2)
    if flooding then coroutine.resume(flood) end
end

function floodFill(img,startX,startY,fillColor,interiorColor) 
    local tbl={}
    local tbl2={}
    local counter=0
    flooding=true
    tbl[1]=vec2(startX,startY) 
    local c1=(interiorColor.r*256+interiorColor.g)*256+interiorColor.b
    while #tbl>0 do
        local x,y=tbl[1].x,tbl[1].y
        tbl2[x*3000+y]=1
        local r,g,b,a = img:get(x,y)
        --local c2=(r*256+g)*256+b
        --if (c1==c2) then
        if interiorColor.r==r and interiorColor.g==g and interiorColor.b==b then
            img:set(x,y,fillColor)
            if x<img.width and tbl2[(x+1)*3000+y]==nil then tbl[#tbl+1]=vec2(x+1,y) end
            if x>1 and tbl2[(x-1)*3000+y]==nil then tbl[#tbl+1]=vec2(x-1,y) end
            if y>1 and tbl2[x*3000+y-1]==nil then tbl[#tbl+1]=vec2(x,y-1) end
            if y<img.height and tbl2[x*3000+y+1]==nil then tbl[#tbl+1]=vec2(x,y+1) end
        end 
        table.remove(tbl,1)  
        counter = counter + 1
        if counter%10000==0 then coroutine.yield() end
    end
    flooding=false
end