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.

Strict

Global intSelectedPixel:Int
Global intSelectedRed:Int
Global intSelectedGreen:Int
Global intSelectedBlue:Int
Local intMouseXPos:Int
Local intMouseYPos:Int
Local pxmPixel:TPixmap


'temp as will use argb in later version
Global intFillRed:Int
Global intFillGreen:Int
Global intFillBlue:Int

Global imgPrintable:TImage

Global intScreenWidth:Int = 1024 'temp
Global intScreenheight:Int = 768 'temp

Graphics 1024,768
imgPrintable = LoadImage("Images\Printable1.jpg")
DrawImage(imgPrintable,0,0)

While not KeyHit(KEY_ESCAPE)

	If MouseHit(1) = 1
	
		'get a random flood fill colour
		intFillRed = Rnd(1.0,255.0)	
		intFillGreen = Rnd(1.0,255.0)
		intFillBlue = Rnd(1.0,255.0)
	
		'Grab the pixel that the user clicks on and find out the colour of it
		intMouseXPos = MouseX()
		intMouseYPos = MouseY()
		pxmPixel = GrabPixmap(intMouseXPos,intMouseYPos,1,1)
		intSelectedPixel = ReadPixel(pxmPixel,0,0)
 	'	intAlpha = (intPixel & $ff000000)
  		intSelectedRed = (intSelectedPixel & $ff0000 ) Shr 16
  		intSelectedGreen = (intSelectedPixel & $ff00 ) Shr 8
  		intSelectedBlue = (intSelectedPixel & $ff )

		'if the selected pixel is a different colour from the flood colour then flood fill the area		
		If (intSelectedRed <> intFillRed or intSelectedBlue <> intFillBlue or intSelectedBlue <> intFillBlue)' and..
		   '(intSelectedRed <> 0 and intSelectedGreen <> 0 and intSelectedBlue <> 0)
  		
		   
	  		FloodFill(intMouseXPos,intMouseYPos)
	  		
	  	EndIf
		
	EndIf
	Flip

Wend

Function FloodFill(fnintXPos:Int,fnintYPos:Int)

   SetColor(intFillRed,intFillGreen,intFillBlue)
   Plot(fnintXPos,fnintYPos)
   
   FillRight(fnintXPos + 1, fnintYPos)
   FillDown(fnintXPos, fnintYPos + 1)
   FillLeft(fnintXPos - 1, fnintYPos)
   FillUp(fnintXPos, fnintYPos - 1)

EndFunction

Function FillRight(fnintXPos:Int, fnintYPos:Int)

	Local pxmNextPixel:TPixmap
	Local intNextPixel:Int
	Local intNextRed:Int
	Local intNextGreen:Int
	Local intNextBlue:Int
	
	If fnintXPos <= intScreenWidth

		pxmNextPixel = GrabPixmap(fnintXPos,fnintYPos,1,1)
		intNextPixel = ReadPixel(pxmNextPixel,0,0)
 	'	intAlpha = (intPixel & $ff000000)
  		intNextRed = (intNextPixel & $ff0000 ) Shr 16
  		intNextGreen = (intNextPixel & $ff00 ) Shr 8
  		intNextBlue = (intNextPixel & $ff )
  		
  		If intNextRed = intSelectedRed and intNextGreen = intSelectedGreen and intNextBlue = intSelectedBlue
  		
  			Plot(fnintXPos,fnintYPos)
  			
			FillRight(fnintXPos + 1, fnintYPos)
			FillDown(fnintXPos, fnintYPos + 1)
			FillUp(fnintXPos, fnintYPos - 1)			
  			
  		EndIf
  		
  	EndIf
  		
  EndFunction

Function FillLeft(fnintXPos:Int, fnintYPos:Int)

	Local pxmNextPixel:TPixmap
	Local intNextPixel:Int
	Local intNextRed:Int
	Local intNextGreen:Int
	Local intNextBlue:Int
	
	If fnintXPos > 0

		pxmNextPixel = GrabPixmap(fnintXPos,fnintYPos,1,1)
		intNextPixel = ReadPixel(pxmNextPixel,0,0)
 	'	intAlpha = (intPixel & $ff000000)
  		intNextRed = (intNextPixel & $ff0000 ) Shr 16
  		intNextGreen = (intNextPixel & $ff00 ) Shr 8
  		intNextBlue = (intNextPixel & $ff )
  		
  		If intNextRed = intSelectedRed and intNextGreen = intSelectedGreen and intNextBlue = intSelectedBlue
  		
			Plot(fnintXPos,fnintYPos)
			  			
			FillLeft(fnintXPos - 1, fnintYPos)
			FillDown(fnintXPos, fnintYPos + 1)
			FillUp(fnintXPos, fnintYPos - 1)			
			  			
  		EndIf
  		
  	EndIf
  		
  EndFunction
  
  Function FillDown(fnintXPos:Int, fnintYPos:Int)

	Local pxmNextPixel:TPixmap
	Local intNextPixel:Int
	Local intNextRed:Int
	Local intNextGreen:Int
	Local intNextBlue:Int
	
	If fnintYPos <= intScreenheight

		pxmNextPixel = GrabPixmap(fnintXPos,fnintYPos,1,1)
		intNextPixel = ReadPixel(pxmNextPixel,0,0)
 	'	intAlpha = (intPixel & $ff000000)
  		intNextRed = (intNextPixel & $ff0000 ) Shr 16
  		intNextGreen = (intNextPixel & $ff00 ) Shr 8
  		intNextBlue = (intNextPixel & $ff )
  		
  		If intNextRed = intSelectedRed and intNextGreen = intSelectedGreen and intNextBlue = intSelectedBlue
  		
  			Plot(fnintXPos,fnintYPos)
			  			
			FillRight(fnintXPos + 1, fnintYPos)
			FillLeft(fnintXPos - 1, fnintYPos)
			FillDown(fnintXPos, fnintYPos + 1)			
  			
  		EndIf
  		
  	EndIf
  		
  EndFunction
  
  Function FillUp(fnintXPos:Int, fnintYPos:Int)

	Local pxmNextPixel:TPixmap
	Local intNextPixel:Int
	Local intNextRed:Int
	Local intNextGreen:Int
	Local intNextBlue:Int
	
	If fnintYPos > 0

		pxmNextPixel = GrabPixmap(fnintXPos,fnintYPos,1,1)
		intNextPixel = ReadPixel(pxmNextPixel,0,0)
 	'	intAlpha = (intPixel & $ff000000)
  		intNextRed = (intNextPixel & $ff0000 ) Shr 16
  		intNextGreen = (intNextPixel & $ff00 ) Shr 8
  		intNextBlue = (intNextPixel & $ff )
  		
  		If intNextRed = intSelectedRed and intNextGreen = intSelectedGreen and intNextBlue = intSelectedBlue
  		
  			Plot(fnintXPos,fnintYPos)
  			
			FillRight(fnintXPos + 1, fnintYPos)
			FillLeft(fnintXPos - 1, fnintYPos)
			FillUp(fnintXPos, fnintYPos - 1)		
  			
  		EndIf
  		
  	EndIf
  		
  EndFunction

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!