Flood Fill Help
BlitzMax Forums/BlitzMax Programming/Flood Fill Help
| ||
| Could someone please help me? I am playing about with a routine to flood fill areas of the screen and have got it almost working - but not quite. I am using a black and white line drawing and the idea is that you click on the image and it fills that section with a random colour. But what actually happens is it fills most of the area but not right up to the lines. At first I thought it was because the picture was greyscale rather than just black and white, but I changed it to be only 2 colours and the problem still occurs. Below is my code - I am sure it is just my logic on how to do this is a little screwed, but can't see for looking. I got the image from here (sorry I don't have anywhere to host it at the moment), and just cropped to 1024*768 and reduced to just 2 colours. http://www.bbc.co.uk/cbeebies/printables/printcolour/storymakers/ Any help would be really appreciated. |
| ||
| Stupid jpg format! Okay my fault the code works fine - even though I was setting the image to be two colours, on saving as a jpg some sort of dithering was happening so it wasn't two colours anymore. Saving as a png instead solves this. But - whilst this code works fine; it is really slow to fill larger areas. Does anyone have any suggestion on how to improve this to speed things up a bit? |
| ||
| Presuming you're only filling up only a single colour. What you could is scan the image and make a lookup table (array the size of your image) of all the valid pixels you can write too and ones that you can't, true and false. Then you can perform all your gfx operations by just consulting the lookup table and you'll only need to plot the pixels, should cut down significantly on the number of readpixels going on, quicker to read your array of ints. Briefly scanning your code you appear to be kind of like bleeding your pixels around and checking its neighbours, looking at true or false values is better than checking the colours every time (since you're often checking the same pixel more than once) May be worth a look, might be faster. |
| ||
| Snarty's fill code was one of the best for BB and here's a Bmax version. <edit>because it's BlueCow...
'Fill Routines
' Written By Paul Snart (Snarty) - Converted to BMax by klepto2 in Oct 2005
' Oct 2001
' RCol = RGB Color To Fill with
' Ax = X Start on Image To Fill
' Ay = Y Start on Image To Fill
' Image = Image To fill on
Strict
Type Point
Global Point_List:TList
Field x
Field y
Method New()
If Point.Point_List = Null Then Point.Point_List = New TList
Point.Point_List.AddLast(Self)
End Method
End Type
Function FloodFill(RCol,ax,ay,Image:TPixmap)
Local timeit=MilliSecs()
Local y:Int
Local BCol=Image.ReadPixel(ax,ay)
Local ImW=Image.width
Local ImH=Image.Height
If BCol<>RCol
Local Hlt=-1
Local Hlb=-1
Local Hrt=-1
Local Hrb=-1
Local Entrys=1
Local FP:Point = New Point
Fp.x=ax
Fp.y=ay
Repeat
FP:Point=Point(Point.Point_List.First())
Local Lx=Fp.x
Local Rx=Fp.x+1
Local HitL=False
Local HitR=False
Hlt=-1
Hlb=-1
Hrt=-1
Hrb=-1
Repeat
If Lx=>0 And HitL=False
Local CColL=Image.ReadPixel(Lx,Fp.y)
If CColL=BCol
Image.WritePixel Lx,Fp.y,RCol
If Fp.y>0
CColL=Image.ReadPixel(Lx,Fp.y-1)
If CColL=BCol
Hlt=Lx
Else
If Hlt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hlt
Hlt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
EndIf
If Fp.y<ImH-1
CColL=Image.ReadPixel(Lx,Fp.y+1)
If CColL=BCol
Hlb=Lx
Else
If Hlb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hlb
Hlb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
EndIf
Lx=Lx-1
Else
HitL=True
If Hlt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hlt
Hlt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
If Hlb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hlb
Hlb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
Else
HitL=True
If Hlt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hlt
Hlt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
If Hlb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hlb
Hlb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
If Rx<=ImW-1 And HitR=False
Local CColR=Image.ReadPixel(Rx,Fp.y)
If CColR=BCol
Image.WritePixel Rx,Fp.y,RCol
If Fp.y>0
CColR=Image.ReadPixel(Rx,Fp.y-1)
If CColR=BCol
Hrt=Rx
Else
If Hrt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hrt
Hrt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
EndIf
If Fp.y<ImH-1
CColR=Image.ReadPixel(Rx,Fp.y+1)
If CColR=BCol
Hrb=Rx
Else
If Hrb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hrb
Hrb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
EndIf
Rx=Rx+1
Else
HitR=True
If Hrt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hrt
Hrt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
If Hrb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hrb
Hrb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
Else
HitR=True
If Hrt<>-1
y=Fp.y-1
FP:Point = New Point
Fp.y=y
Fp.x=Hrt
Hrt=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
If Hrb<>-1
y=Fp.y+1
FP:Point = New Point
Fp.y=y
Fp.x=Hrb
Hrb=-1
FP:Point = Point(Point.Point_List.First())
Entrys=Entrys+1
EndIf
EndIf
Until (HitR=True And HitL=True) Or KeyHit(1)
FP:Point=Point(Point.Point_List.First())
Point.Point_List.Remove(FP)
Entrys=Entrys-1
Until Entrys=False Or KeyHit(1)
EndIf
Local mhit=False
DebugLog (Float(MilliSecs()-TimeIt)/1000)+" seconds"
End Function
Graphics 800,600
Local image:timage=LoadImage("bluecow.png")
While Not KeyHit(1)
Cls
DrawImage image,0,0
If MouseHit(1)
Local Test:TPixmap = LockImage(image)
FloodFill($FFff00ff,MouseX(),MouseY(),Test)
EndIf
Flip
Wend
|
| ||
| My BB flood fill is faster and easier to understand, but nobody cares about old me... I think I'll convert it to blitzmax. http://www.blitzbasic.com/codearcs/codearcs.php?code=314 |
| ||
| thanks guys. @Enay - good idea, this seems to be kinda what Curtastic's code does, so definitely worth looking at using arrays. @Tony - thanks for this, this is loads quicker than mine! (I just need to work through the code to get my head around it). @Curtastic - thanks for your code. I do think it is a little easier to understand initially (even though I don't know BB at all). It seems to be a little similar to my code in essence, except you track each pixel you check in an array, so that it only gets read once, whereas in mine each pixel could potentially be read several times - obviously slowing things down a lot. Be interesting to see it converted into blitzmax to compare. Thanks chaps - big help as always |
| ||
| thanks for checking it out. Expanding on what Enay was saying is that if you have all the pixel colors in an array, you can just keep track of every pixel you change and you never EVER have to use readpixel! |
   |