More efficient filling idea..

Luatee · October 6, 2013, 7:03pm

So I was still wondering if there’s a better way around this annoying lack of efficient flood fill algorithms for the iPad i decided to make my own little idea come in to action, what it does is it takes the touch point then fires 200 tracers in a circle around the touch point and it works its way out til they all set, it then fills the area with a mesh consisting of all the 200 points, this is aimed at full screen images but works for others… Touch to fill and watch the progress
Of course this only really works well with regular polygons

Anyway try it out:



--# Main
-- TestProj

-- Use this function to perform your initial setup
function setup()
    screen = image(WIDTH,HEIGHT)
    setContext(screen)
    pushStyle()
        background(40,40,50,255)
        fill(255,255)
        ellipse(WIDTH/2,HEIGHT/2,400)
    popStyle()
    setContext()
    fil  = nil
end

function touched(t)
    if t.state == BEGAN then
    local r,g,b,a = screen:get(t.x,t.y)
    fil = Fill(screen,vec2(t.x,t.y),color(0,255,255),color(r,g,b))
    end
end
-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)
    sprite(screen,WIDTH/2,HEIGHT/2)
    if fil ~= nil then
        fil:draw()
    end
    -- Do your drawing here
end


--# Fill
Fill = class()

function Fill:init(img,pos,fillColor,intColor)
    self.img = img
    self.pos = pos
    self.fillcol = fillColor
    self.intcol = intColor
    if self.intcol == self.fillcol then return end
    self.num = 200
    self.int = (math.pi*2)/self.num
    self.tracker = {}
    for i=1,self.num do
        local tbl = {}
        tbl.dir = vec2(0,1):rotate(self.int*i)
        tbl.pos = self.pos
        tbl.set = false
        table.insert(self.tracker,tbl)
    end
    self.tick = 0
    self.m = mesh()
    self.m:setColors(self.fillcol.r,self.fillcol.g,self.fillcol.b,255)
end

function Fill:draw()
    local setall = true
    for k,v in pairs(self.tracker) do
        pushStyle()
            fill(255,0,0)
            ellipse(v.pos.x,v.pos.y,10)
        popStyle()
        local s = v.pos+v.dir
        local sx,sy = s.x,s.y
        local r,g,b,a = self.img:get(sx,sy)
        if color(r,g,b) == self.intcol and v.set == false then
            v.pos = v.pos + v.dir
        else
            v.set = true
        end
        if v.set == false then
            setall = false
        end
    end
    if setall then
        if self.tick == 0 then
            local tbl = {}
            for k,v in pairs(self.tracker) do
                table.insert(tbl,v.pos)
            end
            self.m.vertices = triangulate(tbl)
            self.m:setColors(self.fillcol.r,self.fillcol.g,self.fillcol.b,255)
            self.tick = 1
        end
    end
    self.m:draw()        
end

function Fill:touched(touch)
    -- Codea does not automatically call this method
end

Luismi · October 6, 2013, 9:26pm

I never see this example before , Is very interesting , Nice Work @luatee

Luatee · October 7, 2013, 4:43am

This one uses 100 points and shows live updating of the mesh, has heavy use of setting vertices and color so its around 30fps, hits 6fps with 200…



--# Main
-- TestProj

-- Use this function to perform your initial setup
function setup()
    screen = image(WIDTH,HEIGHT)
    setContext(screen)
    pushStyle()
        background(40,40,50,255)
        fill(255,255)
        ellipse(WIDTH/2-200,HEIGHT/2,200)
        ellipse(WIDTH/2-50,HEIGHT/2,200)
        rect(WIDTH/2,HEIGHT/2-100,200,200)
    popStyle()
    setContext()
    fil  = nil
end

function touched(t)
    if t.state == BEGAN then
    local r,g,b,a = screen:get(t.x,t.y)
    fil = Fill(screen,vec2(t.x,t.y),color(0,255,255),color(r,g,b))
    end
end
-- This function gets called once every frame
function draw()
    -- This sets a dark background color 
    background(40, 40, 50)

    -- This sets the line thickness
    strokeWidth(5)
    sprite(screen,WIDTH/2,HEIGHT/2)
    if fil ~= nil then
        fil:draw()
    end
    -- Do your drawing here
    text(1/DeltaTime,100,100)
end


--# Fill
Fill = class()

function Fill:init(img,pos,fillColor,intColor)
    self.img = img
    self.pos = pos
    self.fillcol = fillColor
    self.tracker = nil
    self.intcol = intColor
    if self.intcol == self.fillcol then return end
    self.num = 100
    self.int = (math.pi*2)/self.num
    self.tracker = {}
    for i=1,self.num do
        local tbl = {}
        tbl.dir = vec2(0,1):rotate(self.int*i)
        tbl.pos = self.pos
        tbl.set = false
        table.insert(self.tracker,tbl)
    end
    self.tick = 0
    self.m = mesh()
    self.m:setColors(self.fillcol.r,self.fillcol.g,self.fillcol.b,255)
    self.timer = 0
end

function Fill:draw()
    local setall = true
    if self.tracker == nil then return end
    local tbll = {}
    for k,v in pairs(self.tracker) do
        if self.tick == 0 then
        --[[pushStyle()
            strokeWidth(4)
            stroke(255,0,0)
            local si = self.tracker[k]
            local sn
            if k>1 then
                sn = self.tracker[k-1]
                line(sn.pos.x,sn.pos.y,si.pos.x,si.pos.y)
            else
                sn = self.tracker[self.num]
                line(sn.pos.x,sn.pos.y,si.pos.x,si.pos.y)
            end
        popStyle()]]
        table.insert(tbll,v.pos)
        end
        
        local s = v.pos+v.dir
        local sx,sy = s.x,s.y
        local r,g,b,a = self.img:get(sx,sy)
        if color(r,g,b) == self.intcol and v.set == false then
            local d = v.pos+v.dir
            if d.x > 2 and d.x < WIDTH-2 and d.y > 2 and d.y < HEIGHT-2 then
                v.pos = v.pos + v.dir
            else
                v.set = true
            end
        else
            v.set = true
        end
        if v.set == false then
            setall = false
        end
    end
    if setall then
        if self.tick == 0 then
            local tbl = {}
            for k,v in pairs(self.tracker) do
                table.insert(tbl,v.pos)
            end
            self.m.vertices = triangulate(tbl)
            self.m:setColors(self.fillcol.r,self.fillcol.g,self.fillcol.b,255)
            self.tick = 1
            print(self.timer)
            setContext(screen)
                self.m:draw()
            setContext()
        end
    end
    self.m:draw()
    if self.timer < ElapsedTime then
        self.m.vertices = triangulate(tbll)   
        self.m:setColors(self.fillcol.r,self.fillcol.g,self.fillcol.b,255)   
        self.timer = ElapsedTime+0.1
    end
    
end

function Fill:touched(touch)
    -- Codea does not automatically call this method
end

Luismi · October 7, 2013, 10:20am

I like too, u used FPS , but in the iPad 1 Is too slow , but Is very good Ur code @luatee

dave1707 · October 10, 2013, 5:37pm

Here’s a flood fill program that I converted from existing code to run with Codea. My original code was supposed to use recursive calls, but Codea stopped with a “stack overflow” error message. I then changed the code to use a table instead of the stack. To run the program, tap anywhere in the green area. The speed of the floodFill() routine can be changed with the fillSpeed slider. I modified the code to display the fill as it ran, just for demo purposes. Setting the fillSpeed to 30 will run floodFill() at full speed without displaying anything until the fill is complete. It’s kind of interesting to start floodFill() at different positions just to see how the different areas get filled. I added comments to lines of code in floodFill() that were added just for the display and aren’t really needed for floodFill() to work. After running floodFill(), you may notice a green outline around the red fill area. That isn’t a problem with floodFill(). I found out that there are 2 pixels that outline the green areas that aren’t true green (0,255,0). The floodFill() example is set to find true green (0,255,0) pixels and change them to red. Since those pixels aren’t true green, they aren’t getting changed.


function setup()
    parameter.integer("fillSpeed",0,30,15)
    spriteMode(CORNER)
    str="Tap in green area to start fill."
    str=str.."\
Use slider to control the fill speed."
    str=str.."\
A speed of 30 runs floodFill() without the display."
    tab={}
    t=-1
    w=400
    h=400
    img=image(w,h)    
    -- draw read outline around image area
    for x=1,w do
        img:set(x,1,255,0,0)
        img:set(x,h,255,0,0)
        img:set(1,x,255,0,0)
        img:set(h,x,255,0,0)
    end
    -- draw green objects on image area
    setContext(img)
    fill(0,255,0)
    rect(100,100,100,80)
    ellipse(220,200,130,50)
    ellipse(200,250,30,100)
    ellipse(150,300,100,30)
    ellipse(90,300,30,180)
    ellipse(240,350,300,30)
    ellipse(350,200,30,300)
    ellipse(220,55,300,50)
    ellipse(295,200,30,150)
end

function draw()
    background(40, 40, 50)
    fill(255)
    text(str,250,600)  
    sprite(img,50,100)
    if t==0 then
        str="Press restart to run again."
    else
        floodFill(color(0,255,0),color(255,0,0))
    end
end

function floodFill(old,new)
    local x,y,r,g,b
    count=0    -- not needed
    while t>0 do
        count=count+1    -- not needed
        x=tab[t].x
        y=tab[t].y
        t=t-1
        r,g,b=img:get(x,y)
        if r==old.r and g==old.g and b==old.b then
            img:set(x,y,new.r,new.g,new.b)
            t=t+1
            tab[t]=vec2(x-1,y)
            t=t+1
            tab[t]=vec2(x+1,y)
            t=t+1
            tab[t]=vec2(x,y+1)
            t=t+1
            tab[t]=vec2(x,y-1)
        else -- not needed
            count=0 -- not needed
        end
        if count>fillSpeed and fillSpeed~=30 then -- not needed
            return -- not needed
        end -- not needed
    end 
end

function touched(t1)
    if t1.state==BEGAN then
        t=1
        tab[t]=vec2(t1.x-50,t1.y-100)
    end
end

Luatee · October 10, 2013, 5:46pm

I quite like that, its the same speed as I was achieving before with my recursive fill method but I’m trying to find something quicker than this, which I knew would be achievable with meshes but its limited

dave1707 · October 10, 2013, 5:55pm

@Luatee I haven’t played around with meshes for a long time, but can’t the color of a mesh be changed really easy. So if an area was colored with a mesh or several meshes, wouldn’t changing the color be easy and a floodFill routine not be needed. I’ll have to try meshes again to see what’s involved. Maybe I’m way off in what I’m thinking.

Luatee · October 10, 2013, 6:36pm

Yeah @dave1707 you’re right, I can have a mesh with 200 vertices and set the colour with little hindrance, that’s why I put it forward as an idea, but if I used it on the image you use I would have to fill certain areas at a time and it doesn’t cover every single pixel, I think its due to the way codea draws ellipses, but I used a mesh and that didn’t show up any better so I think it can be solved, I added 0.5 to the pixels to even the fill area but you still get a 1 pixel line going around the edges… The trackers go out from the centre so it only works well with regular shapes using the code from the op

dave1707 · October 10, 2013, 8:26pm

@Luatee Is this floodFill fast enough. I just did an ellipse and triangle, but I could have added a circle, rectangle, or any other shaped object. I haven’t played with meshes for awhile.


displayMode(FULLSCREEN)

function setup()
    tab={}
    ctab={}
    mtab={}
    m=mesh()
    a=WIDTH/2
    b=WIDTH/4
    for x=-a,a do
        y=math.sqrt((1-(x^2)/a^2)*b^2)
        table.insert(tab,vec2(x+a,y+a))
    end  
    for x=a,-a,-1 do
        y=math.sqrt((1-(x^2)/a^2)*b^2)
        table.insert(tab,vec2(x+a,-y+a))
    end   
    for z=2,#tab do
        table.insert(mtab,(vec2(tab[1].x,tab[1].y)))
        table.insert(mtab,(vec2(tab[z-1].x,tab[z-1].y)))
        table.insert(mtab,(vec2(tab[z].x,tab[z].y)))
        table.insert(ctab,vec3(0,255,0))
        table.insert(ctab,vec3(0,255,0))
        table.insert(ctab,vec3(0,255,0))
    end  
    
    table.insert(mtab,vec2(100,150))
    table.insert(mtab,vec2(200,250))
    table.insert(mtab,vec2(200,150))
    table.insert(ctab,vec3(0,255,0))
    table.insert(ctab,vec3(0,255,0))
    table.insert(ctab,vec3(0,255,0))    
end

function draw()
    background(40, 40, 50)
    fill(255)
    text("keep tapping the screen to change the color.",WIDTH/2,150)
    m.vertices=mtab
    m:setColors(255,0,0)
    for z=1,#ctab do
        m:color(z,ctab[z].x,ctab[z].y,ctab[z].z) 
    end 
    m.draw(m)
end

function floodFill()
    r=math.random(255)
    g=math.random(255)
    b=math.random(255)
    for z=1,#ctab do
        ctab[z]=vec3(r,g,b)
    end
end

function touched(t)
    if t.state==BEGAN then
        floodFill()
    end
end

Ignatz · October 10, 2013, 8:43pm

@Dave1707 - The speed killer is extracting pixel values (and doing it more than once per pixel).

I think your flood fill is pulling out the same pixel values multiple times. Ideally you only want to do it once for each pixel, eg by keeping a table that keeps track of when a pixel has been used.

So instead of saying

t=t+1  
tab[t]= vec2(x+1,y)

you would say

if tbl[x+1][y] ==nil then --only add if not used before
    t=t+1  
    tab[t]= vec2(x+1,y)
   tbl[x+1][y] =1 --Mark as used
end

I also think you’ll find that it breaks when filling at the edge of the image, because it doesn’t check before adding pixels from all sides.

dave1707 · October 10, 2013, 9:13pm

@Ignatz I think I know what you’re saying about checking the same pixel multiple times. But I think for the floodFill to work properly, I have to back my way out the same way I went in when I hit a pixel that doesn’t get changed. If I start skipping pixels because I checked it before, I think I might miss a path going in the reverse direction to go in a new direction. I think I need to try this out on a piece of graph paper to see if I’m doing it correct. That way I might be able to visually see what you’re saying also.

Ignatz · October 10, 2013, 9:32pm

This code deals with edge pixels and also avoids looking at any pixel twice. This makes it a bit faster.

--v = starting pixel, vec2
--c1 = new colour
function Flood(img,v,c1)
    local R,G,B=img:get(v.x,v.y)
    local w,h=img.width,img.height
    local tbl={v}
    local seen={} --prevents looking at a pixel twice
    for i=1,w do seen[i]={} end
    seen[v.x][v.y]=1
    --use a queue, FIFO
    while #tbl>0 do
        local x,y=tbl[1].x,tbl[1].y
        local r,g,b=img:get(x,y)
        if r==R and g==G and b==B then
            img:set(x,y,c1)
            if x>1 and seen[x-1][y]==nil then table.insert(tbl,vec2(x-1,y)) seen[x-1][y]=1 end
            if x<w and seen[x+1][y]==nil then table.insert(tbl,vec2(x+1,y)) seen[x+1][y]=1 end
            if y>1 and seen[x][y-1]==nil then table.insert(tbl,vec2(x,y-1)) seen[x][y-1]=1 end
            if y<h and seen[x][y+1]==nil then table.insert(tbl,vec2(x,y+1)) seen[x][y+1]=1 end
        end
        table.remove(tbl,1) 
    end
end

dave1707 · October 10, 2013, 9:57pm

@Ignatz That does run a lot faster. I need to play with this until I understand what’s happening any why it’s working.

Ignatz · October 10, 2013, 10:24pm

As you know, the important thing is to include every neighbour of a replaced pixel, in the table, so it gets looked at later.

My code does this no differently from yours, but it avoids including the same pixels more than once in the table, that’s all. And it tests for edge pixels.

Luatee · October 11, 2013, 6:31am

Wow that is fast, I’m still getting edge pixels though, less than usual though. Nice one @Ignatz

Ignatz · October 11, 2013, 7:23am

I noticed that there seems to be an edge of green pixels around the outside that don’t get converted. I think this is because Codea blends pixels where colours change, so the green of those pixels isn’t the exact same colour we are trying to change. That’s why those edge pixels are not being converted.

dave1707 · October 11, 2013, 8:22am

@Ignatz Up in one of my earlier posts I mentioned that there were 2 pixels that outlined the objects and they wreen’t getting changed. I found that one ring had values around (0,241,0) and the other had values of (0,39,0) instead of the true green of (0,255,0).

Luatee · October 11, 2013, 8:36am

Well if you’re using codeas primitives then im pretty sure that is the case @ignatz because of the shader used, as you say they blend the pixels which doesn’t give use the actual value… But we do have the shader, and the equation used to blend the pixels, so would it not be possible to reverse this with the right math to calculate what’s pixels are blended and fill them?

dave1707 · October 11, 2013, 10:54am

@Luatee In the above situation, the 2 rings of pixels surrounding the objects code be considered a match since the red and blue values are 0. The code could be changed to look for r=0 and b=0 and g>0. I tried that and it eliminated the green ring around the red fill area. Of course, determining the color values in a real situation would be a lot harder.

Luatee · October 11, 2013, 2:11pm

@dave1707 That’s only on a black backround though if I’m correct? @Ignatz I’m sure I’ve asked you this before, can I use that algorithm you posted?