Scanline fill? (flood fill / paint bucket)

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
stout
Citizen
Posts: 64
Joined: Sun Oct 07, 2012 4:42 pm

Scanline fill? (flood fill / paint bucket)

Post by stout »

(brush size isn't implemented yet so ignore that line in the menu // EDIT: also the right mouse button doesn't work when zoomed in, forgot to copy code, ignore that)

So what I've got going is a basic painting thing. I thought I had a paint bucket/fill figured out - same as in mspaint, et cetera - but then realized that it would only work if the "shape" I was working in was completely empty. No good! So let's say you have a table like this:

Code: Select all

1 1 1 1 1 1 1
1 2 2 2 2 1 1 
2 1 1 1 1 2 1
2 1 2 1 1 2 1 
2 1 1 1 1 2 1 
1 2 2 2 2 1 1 
1 1 1 1 1 1 1
What does your loop look like to iterate through that table? How do you determine the "edges" that you're supposed to be filling in? After some searching I found this which is exactly what I was thinking of, but I don't understand how it knows to "skip" the eyes but stop at the edge of the greater circle/face.
Attachments
worldgen.love
(120.18 KiB) Downloaded 131 times
stout
Citizen
Posts: 64
Joined: Sun Oct 07, 2012 4:42 pm

Re: Scanline fill? (flood fill / paint bucket)

Post by stout »

No takers on this? =/ I found this but don't know what language it's in or how to port it; it doesn't look too dissimilar to basic Lua but still too much for me.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Scanline fill? (flood fill / paint bucket)

Post by Roland_Yonaba »

The problem remains unclear, to me. Then i'm going to ask a few more questions.
Basically, it seems you are willing to perform some sort of "floodfill" on a 2d map.
If so, from where do you start it (I meant, the seed(s) cells). From the boundaries, flooding to the inner cells ?
Are there some unwalkables tiles not be labelled by the algorithm ?
stout
Citizen
Posts: 64
Joined: Sun Oct 07, 2012 4:42 pm

Re: Scanline fill? (flood fill / paint bucket)

Post by stout »

Er, I don't know how else to explain it. It's a paint bucket/fill function. If you open up any paint/graphics application you can see. If you click the link in my second post you can play with a version, with code, but as I said I can't parse the code. Let's say you start with:
Image

If you click to the left of the eye, you get:
Image

If you click outside of the face, you get:
Image

If you click in the left eye, you get:
Image

Assume every pixel is an entry on a basic tilemap table.

The problem is: I don't know how to write this feature. =p I included my test app so that someone would have some working code to play with.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: Scanline fill? (flood fill / paint bucket)

Post by Roland_Yonaba »

Well I can reproduce a similar behaviour using a simple floodfill processing. Unoptimized, though, bust fast enough.
To illustrate, see the attached picture. The initial map state (9x9), each pixel is a single cell. 0's and 1's represents different colors.
Performing flood fill from a starting point, which is the one labelled 'X' (using a simple 4-connected variant), all cells connected are flooded with a single color (labelled 'F'), leaving 1's cell untouched, as well as the inner area.
Attachments
Untitled 1.png
Untitled 1.png (76.67 KiB) Viewed 3475 times
User avatar
miko
Party member
Posts: 410
Joined: Fri Nov 26, 2010 2:25 pm
Location: PL

Re: Scanline fill? (flood fill / paint bucket)

Post by miko »

stout wrote: What does your loop look like to iterate through that table? How do you determine the "edges" that you're supposed to be filling in? After some searching I found this which is exactly what I was thinking of, but I don't understand how it knows to "skip" the eyes but stop at the edge of the greater circle/face.
If you have unusual shapes, then loop will not work, you need a recurrent function. The idea is this:
1. at any given point, check if you can change its color. If so, do step 1 for pixels at the top, bottom, left and right to this pixel (and optionally in additional 4 diagonal directions).

However, I found out that it may be too slow, so my next idea was to fill whole lines at once (instead of each pixel) - for this you need find boundaries first, so you know how long your line could be.
I have never finished this, but I am attaching what I did already (it is for older love 0.7). Hope it helps you.
Attachments
fill.love
(1.8 KiB) Downloaded 103 times
My lovely code lives at GitHub: http://github.com/miko/Love2d-samples
User avatar
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Re: Scanline fill? (flood fill / paint bucket)

Post by Kadoba »

Here are two flood fill methods. The first one is a simpler recursive method and the second one is a queue based method. If you're planning on using larger grids I recommend against the recursive method since you can overflow your stack pretty easily with a flood fill.
RecursiveFill.love
(762 Bytes) Downloaded 138 times
QueueFill.love
(850 Bytes) Downloaded 165 times
stout
Citizen
Posts: 64
Joined: Sun Oct 07, 2012 4:42 pm

Re: Scanline fill? (flood fill / paint bucket)

Post by stout »

Thanks! This gives me something to play with. Will tackle it this weekend.
User avatar
miko
Party member
Posts: 410
Joined: Fri Nov 26, 2010 2:25 pm
Location: PL

Re: Scanline fill? (flood fill / paint bucket)

Post by miko »

Kadoba wrote:If you're planning on using larger grids I recommend against the recursive method since you can overflow your stack pretty easily with a flood fill.
...unless you are using tail calls, then the stack does not grow:
http://www.lua.org/pil/6.3.html
My lovely code lives at GitHub: http://github.com/miko/Love2d-samples
User avatar
Kadoba
Party member
Posts: 399
Joined: Mon Jan 10, 2011 8:25 am
Location: Oklahoma

Re: Scanline fill? (flood fill / paint bucket)

Post by Kadoba »

miko wrote:
Kadoba wrote:If you're planning on using larger grids I recommend against the recursive method since you can overflow your stack pretty easily with a flood fill.
...unless you are using tail calls, then the stack does not grow:
http://www.lua.org/pil/6.3.html
Can tail calls occur even when calling the recursion 4 times?
Post Reply

Who is online

Users browsing this forum: No registered users and 18 guests