fill tool

okay, let's say I'm making a paint program (I'm not actually, it's a texture system, but this is easier to explain if I leave you in the dark about everything).
Now, I'm designing a function like a fill tool. It just fills black into an area within surrounding lines, no matter what their shape, as long as they form an enclosed area. How can I make this work?
In other words, How can I make a paint bucket tool function? (like in paint, photoshop, and all other drawing programs)

In C++ but fairly readable http://www.codeproject.com/gdi/QuickFill.asp

Also a good explanation of some of the simpler methods http://www.cs.unc.edu/~mcmillan/comp136/Lecture8/areaFills.html

OT:

I remember reading somewhere that in the early days at Micro$oft some hotshot programmer started to pull the 'Fill' code in the early version of Paint apart... saying how badly coded it was... what a moron the original programmer must be to write such poorly optimised code. Turned out that good old Bill had written that routine himself. Caused a bit of a frosty relationship.

Moral: choose a good 'Fill' example or only hire people who are less smart than you are ;-)

Hoi

Heres many routines:

Graphics 640, 480, 32, 2
rgbalt% = 0
rgbneu% = 255*$10000 + 100*$100 + 50
Color 255, 255, 255
Oval 0, 0, 200, 200, 0
WaitKey()
LockBuffer FrontBuffer()
fuellen_rekursiv(100, 100, FrontBuffer(), 640, 480, rgbalt%, rgbneu%)
UnlockBuffer FrontBuffer()
Flip
WaitKey()
End


Function fuellen_rekursiv(x%, y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)   
   ;x%, y% -> Koordinaten des Pixels
   ;buffer% -> Identität des Buffers, in dem gearbeitet wird
   ;breite%, hoehe% -> Größe des Buffers
   ;rgbalt% -> RGB-Wert der Farbe, die geändert werden soll
   ;rgbneu% -> RGB-Wert der Farbe, die das Pixel annehmen soll
   ;      => rgb = r*$10000 + g*$100 + b
   If (ReadPixelFast(x%, y%, buffer%)And $FFFFFF)=rgbalt% Then
      WritePixelFast(x%, y%, rgbneu%, buffer%)
      If (x% + 1)<breite% Then fuellen_rekursiv((x% + 1), y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (x% - 1)>=0 Then fuellen_rekursiv((x% - 1), y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (y% + 1)<hoehe% Then fuellen_rekursiv(x%, (y% + 1), buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (y% - 1)>=0 Then fuellen_rekursiv(x%, (y% - 1), buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
   EndIf
End Function

; Kreisfunktion

Graphics 640, 480, 16, 2
AppTitle "Kreisfunktion"

Print "Press any key to start"
WaitKey

Start = MilliSecs()
 Kreis(320,240,100,1,255,0,0) ; Kreis(X, Y, Radius, Füllung, r,g,b)
Zeit = MilliSecs() - Start

Color 255,255,255
Print "Benötigte Zeit: " + Zeit + "ms"

WaitKey
End


Function Kreis(PosX, PosY, Radius, Fill, r, g, b)

 LockBuffer FrontBuffer() 
  If Fill = 0
   For grad# = 0 To 360 Step .05
    x = ((Sin (grad#) * radius) + PosX)
    y = ((Cos (grad#) * radius) + PosY)
    WritePixelFast x, y, a*$1000000 + r*$10000 + g*$100 + b
   Next
  EndIf

  If Fill = 1 Then
   For rad = radius To 0 Step -1
    For grad# = 0 To 360 Step .3
     x = ((Sin (grad#) * rad) + PosX)
     y = ((Cos (grad#) * rad) + PosY)   
     WritePixelFast x, y, a*$1000000 + r*$10000 + g*$100 + b
    Next
   Next
  EndIf
 UnlockBuffer FrontBuffer()

End Function

Graphics 800,600,32
SeedRnd MilliSecs()

Global x1,y1,NeueFarbe,AlteFarbe
Global xstart,xend,ystart,yend

xstart=100
xend=400
ystart=100
yend=400

NeueFarbe=$ff0000ff
AlteFarbe=$ffff0000

While Not KeyHit(1)

  Cls
  Color 255,0,0
  Oval 100,100,Rand(100,300),Rand(100,300),1
  Color 255,255,0
  Rect 200,90,Rand(10,60),Rand(100,400)
  h#=MilliSecs()
   LockBuffer FrontBuffer()
     Flood_Fill_Now 150,150,AlteFarbe,NeueFarbe
   UnlockBuffer FrontBuffer()
  Text 100,500,MilliSecs()-h+" ms"
  Delay 1000

Wend

WaitKey
End


Function Flood_Fill_Now (Xpos,Ypos,AlteFarbe,NeueFarbe)
     LeftX=Xpos
     RightX=Xpos
     WritePixel Xpos,Ypos,NeueFarbe
     While (LeftX>xstart)
       rgb=ReadPixel(LeftX-1,Ypos)
       If rgb=AlteFarbe LeftX=LeftX-1 WritePixel LeftX,Ypos,NeueFarbe Else Exit
     Wend

     While (RightX<xend)
        rgb=ReadPixel(RightX+1,Ypos) 
        If rgb=AlteFarbe RightX=RightX+1 WritePixel RightX,Ypos,NeueFarbe Else Exit
     Wend

    If Ypos>ystart Then
        For i=LeftX To RightX
          rgb=ReadPixel(i,Ypos-1)
          If rgb=AlteFarbe Flood_Fill_Now i,Ypos-1,AlteFarbe,NeueFarbe
        Next
    End If

    If Ypos<yend Then
        For i=LeftX To RightX
          rgb=ReadPixel(i,Ypos+1)
          If rgb=AlteFarbe Flood_Fill_Now i, Ypos+1,AlteFarbe,NeueFarbe
        Next
    End If
End Function

cu

thanks a lot. That's less work for me :D
Looks like a bit of code from myself will finally be coming as soon as I stop planning for my other stuff.

In my experience I wouldn't use a recursive fill routine. You'll blow the stack with any 'complicated' fill.

hm. I may just use it for referance then. I'm planning to set up files for the images to be filled containing x and y positions for spots within the same lines.

I'm using the bottom example for now though, so I'm just wondering what AlteFarbe and NeueFarbe is? (all I know is that it is some kind of colour thing) I'm kind of guessing right now. Also, when I right click to draw the fill it only fills in a little bit, then I have to drag the mouse to fill more. What am I doing wrong with the function?

;includes
;the flood fill function
Include "FloodFill.bb"

;graphics setup
Graphics 800,600,16,2

;double buffer setup
SetBuffer BackBuffer()

While Not KeyDown(1)

;the line drawing stuff

;uh, me being lazy
CursorX=MouseX()
CursorY=MouseY()
;end me being lazy and not bothering to fix my lame code

If MouseDown(1)
	
	If linebefore=0
		lastmouseX=CursorX
		lastmouseY=CursorY
		linebefore=1
	EndIf

	Line lastmouseX,lastmouseY,CursorX,CursorY
	lastmouseX=CursorX
	lastmouseY=CursorY
EndIf

;flood fill function

If MouseDown(2)
	;lock buffer for speed up
	LockBuffer FrontBuffer()
	flood_fill_now(MouseX(),MouseY(),$ff000000,$ff0000ff)
	;unlock buffer
	UnlockBuffer FrontBuffer()
EndIf

;double buffering
Flip

Wend

Hoi

AlteFarbe = Old color, NeueFarbe = New color.


Here is my best way :\

Graphics 800,600,16,2

Global x1,y1,NeueFarbe,AlteFarbe
Global xstart,xend,ystart,yend

BGimage = CreateImage(800, 600)


;double buffer setup
SetBuffer BackBuffer()

While Not KeyDown(1)
;the line drawing stuff
;uh, me being lazy
CursorX=MouseX()
CursorY=MouseY()
;end me being lazy and not bothering to fix my lame code
If MouseDown(1)
	If linebefore=0
		lastmouseX=CursorX
		lastmouseY=CursorY
		linebefore=1
	EndIf

    SetBuffer ImageBuffer(BGimage)
	Line lastmouseX,lastmouseY,CursorX,CursorY
	lastmouseX=CursorX
	lastmouseY=CursorY
EndIf



;flood fill function
If MouseDown(2)
	;lock buffer for speed up
	LockBuffer ImageBuffer(BGimage)
	colorfill(MouseX(),MouseY(),ImageBuffer(BGimage),GraphicsWidth(),GraphicsHeight(),$ff000000,$ff0000ff)
	;unlock buffer
	UnlockBuffer ImageBuffer(BGimage)
EndIf

SetBuffer BackBuffer()
Cls
DrawBlock BGimage, 0, 0


;double buffering
Flip
Wend

Function colorfill(x%, y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
   If (ReadPixelFast(x%, y%, buffer%) )=rgbalt% Then
      WritePixelFast(x%, y%, rgbneu%, buffer%)
      If (x% - 1)>=0 Then colorfill((x% - 1), y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (x% + 1)<breite% Then colorfill((x% + 1), y%, buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (y% + 1)<hoehe% Then colorfill(x%, (y% + 1), buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
      If (y% - 1)>=0 Then colorfill(x%, (y% - 1), buffer%, breite%, hoehe%, rgbalt%, rgbneu%)
   EndIf
End Function