Omnimaga

Calculator Community => TI Calculators => Axe => Topic started by: LincolnB on October 04, 2011, 11:13:30 pm

Title: Can You Flood Fill?
Post by: LincolnB on October 04, 2011, 11:13:30 pm
Hi everyone. For PaintPad, I'm really close to releasing the first version, but before I do, I need a flood fill algorithm. I've tried a little bit, but haven't been able to get anything to work. So, I'm making it a contest of sorts.

I'm uploading a very, very, very watered down version of PaintPad, all it supports is pixel drawing and deletion. All I need is a simple flood fill function - the template is there, all that it needs is the code.

So yeah. If you're up to it, check it out, and upload or post the code for your floodfill function.

Also, here's the code for anyone not wanting to go to the trouble of downloading an sending the attached source file, FLOODSRC.

Spoiler For code:
Code: [Select]
.FLOOD
.The challenge is to write a   good,solid floodfill function.

DiagnosticOff

.Cursor coordinates
10->X->Y

.Start the program with the cursor at 10,10

.The arrow keysmove the cursor

.When you pressALPHA, call the flood fill function
.When you press2ND,it draws a  pixel at the X,Yposition

ClrDraw
ClrDraw^^r

.Clear exits
Repeat getKey(15)

.This code is  unoptimized,and I use a lot of  functions, for  clarity purposes
Input()

.^All this function does is getinput from the  arrow keys

.Now,to get input from 2ND and ALPHA
.Remember-
.2ND=Draw pixel
.ALPHA=Flood fill
.And [DEL] deletes pixels

If getKey(54)
Pxl-On(X,Y)^^r
End
If getKey(56)
Pxl-Off(X,Y)^^r
End

.Now,its your  turn to write   some code.
.All I need is someone to writethe Flood() function.
If getKey(48)

Flood()
.^That.
.Scroll down tosee what code   needs to be written.

End


.Now,for some  boring display  stuff

.Everything is stored on the   back buffer
.The front buffer is for displaying the cursor and other stuff

RecallPic

.Display cursor
Cursr()

DispGraph
Pause 75


.End of main   loop
End
Return


.Finally,the flood fill function!
Lbl Flood

.YOUR
.CODE
.HERE

.Remember, dontwrite to the    front buffer,usethe back buffer

Return



.Other functions

Lbl Input
If getKey(1) and (Y<63
Y++
End
If getKey(2) and (X>0
X--
End
If getKey(3) and (X<95
X++
End
If getKey(4) and (Y>0
Y--
End
Return

Lbl Cursr

Rect(X,0,1,63
Rect(0,Y,95,1
Pxl-Off(X,Y

Return

Eh, spacing on the comments is a little weird^^

PS for anyone who doesn't know what I mean by "flood fill function", it's pretty much the bucket tool in mspaint.
Title: Re: Can You Flood Fill?
Post by: Deep Toaster on October 05, 2011, 12:44:11 am
Builderboy once gave me an awesome little tutoring session on how it works. Let's see if I can dig it up...
Title: Re: Can You Flood Fill?
Post by: LincolnB on October 05, 2011, 09:42:49 am
hey, sounds great. PM me or post it here if you find it.
Title: Re: Can You Flood Fill?
Post by: AngelFish on October 05, 2011, 09:44:42 am
Code snippets in spoiler tags are messed up in Chrome. Yay for one line source viewing!
Title: Re: Can You Flood Fill?
Post by: aeTIos on October 05, 2011, 09:44:55 am
ARGH. Code + Spoiler + Chrome = guess?
Argh. you ninja'd me.
Title: Re: Can You Flood Fill?
Post by: Chockosta on October 05, 2011, 02:38:27 pm
I don't know anything about Axe... Does it allow recursive functions ? If yes, it's really easy...
Anyway, Wikipédia is really interesting about that.
http://en.wikipedia.org/wiki/Flood_fill (http://en.wikipedia.org/wiki/Flood_fill)
Title: Re: Can You Flood Fill?
Post by: calc84maniac on October 05, 2011, 02:45:30 pm
I don't know anything about Axe... Does it allow recursive functions ? If yes, it's really easy...
Anyway, Wikipédia is really interesting about that.
http://en.wikipedia.org/wiki/Flood_fill (http://en.wikipedia.org/wiki/Flood_fill)
It does, but the stack isn't big enough to nest so many function calls
Title: Re: Can You Flood Fill?
Post by: Chockosta on October 05, 2011, 02:52:34 pm
Aw, too bad.
So I guess you'll have to use use the fixed memory way (right-hand fill method) to do this.
But it is quite slow with complex shapes.
So, good luck :P
Title: Re: Can You Flood Fill?
Post by: LincolnB on October 06, 2011, 09:38:50 pm
Deep? You find it? (or BuilderBoy, for that matter)
Title: Re: Can You Flood Fill?
Post by: thepenguin77 on October 06, 2011, 10:44:50 pm
I've done flood fills, though, it wasn't for painting or anything, but here's how I did it.

1. Make a buffer the same size as the number of pixels in your drawing area and fill it with 00's.
2. Take all the spaces eligible for filling and mark them with 01 on the new buffer.
3. Mark the space that was picked by the cursor with a 02.

This part is a loop:
4. Search the buffer for a 02
5. When you find it, check the 4/8 (depending on implementation) squares around the 2, if they are 1, mark them with 2, if they are 0, do nothing.
6. Mark the current square with a 03
7. Repeat this part

Flood fill is over when there are no more 02's left.
8. Find all of the 03's and fill them in back on the original picture


This technique should work as long as you don't have a massive buffer. But even if you did have a buffer the size of the screen, a full buffer for this would only require 6,144 bytes. Then, since this method only has values between 0 and 3, you could potentially store 4 pixels to a byte and get your size down to 1,536.

If space is not a problem, I also have an optimization to make this technique run faster. Checking the edges can slow the process down because you always have to figure out whether you need to check all 4 sides. This can be avoided by making your buffer 1 extra row wide and 2 extra rows tall. Let's say you have a 16x16 picture. If you make your buffer 17 pixels wide, you'll have 1 pixel boundary along both edges, this would mean you never have to check left/right boundaries. Then, if you give the buffer an extra row on the top and bottom, you can check the whole thing without fear of going over an edge. Just remember, you obviously don't want to perform your buffer operations on that 17th row, just skip it when checking for 02's.


Edit:
    After I wrote this, I wrote a tutorial on it (http://www.omnimaga.org/index.php?action=articles;sa=view;article=77). I've decided that instead of making posts like this, from now on I'll just write tutorials and link them ;D
Title: Re: Can You Flood Fill?
Post by: LincolnB on October 07, 2011, 10:21:23 am
Hey, great, it works perfect. Except one thing - it's so slow that's faster just to fill in the pixels by hand...I'll post some code in a bit and maybe you guys can help me out?