# More efficient filling idea..

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
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
``````

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

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
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
``````

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

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

``````

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

@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.

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

@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

``````

@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.

``````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.

@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.

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
``````

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

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.

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

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.

@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).

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?

@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.

@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?