Flood fill

[MrTAToad]

A flood fill routine.  It needs a bit of speeding up unfortunately :

Code (glbasic) Select Expand

// --------------------------------- //
// Project: TestFloodFill
// Start: Monday, May 24, 2010
// IDE Version: 7.341

TYPE tPixel
x%
y%
ENDTYPE

GLOBAL pixels[] AS tPixel
LOCAL sW%,sH%

GETSCREENSIZE sW%,sH%

CLEARSCREEN
DRAWRECT 0,0,400,400,RGB(255,255,0)
DRAWRECT 0,0,140,140,0
DRAWRECT 8,8,8,8,RGB(255,255,0)
SHOWSCREEN
DRAWRECT 0,0,400,400,RGB(255,255,0)
DRAWRECT 0,0,140,140,0
DRAWRECT 8,8,8,8,RGB(255,255,0)

FloodFill(0,0,RGB(0,0,0),RGB(255,255,255))
SHOWSCREEN
KEYWAIT
DEBUG "Finished\n"
END

FUNCTION FloodFill%:x%,y%,targetColour%,replacementColour%
LOCAL Q AS tPixel
LOCAL N AS tPixel
LOCAL w%,e%,loop%
LOCAL tempPixels[] AS tPixel

IF GETPIXEL(x%,y%)<>targetColour% THEN RETURN FALSE

DIM pixels[0]

Q.x%=x%
Q.y%=y%
DIMPUSH pixels[],Q

WHILE TRUE
IF BOUNDS(pixels[],0)=0 THEN RETURN FALSE

DIM tempPixels[0]

FOREACH Q IN pixels[]
IF GETPIXEL(Q.x%,Q.y%)=targetColour%
y%=Q.y%
w%=Q.x%-1
e%=Q.x%+1

WHILE w%>=0 AND GETPIXEL(w%,y%)=targetColour%
DEC w%
WEND

WHILE e%<=400 AND GETPIXEL(e%,y%)=targetColour%
INC e%
WEND

DRAWLINE w%+1,y%,e%-1,y%,replacementColour%

FOR loop%=w%+1 TO e%-1
N.x%=loop%
N.y%=y%-1

IF N.y%>-1
IF GETPIXEL(N.x%,N.y%)=targetColour%
DIMPUSH tempPixels[],N
ENDIF
ENDIF

N.x%=loop%
N.y%=y%+1

IF N.y%<400
IF GETPIXEL(N.x%,N.y%)=targetColour%
DIMPUSH tempPixels[],N
ENDIF
ENDIF
NEXT
ENDIF
NEXT

pixels[]=tempPixels[]
WEND
ENDFUNCTION


[I love my Brick]

I managed to speed it up slightly by substituting SETPIXEL with DRAWSPRITE ( a single white pixel )
This led me into an experiment where I removed GETPIXEL and replaced it with SPRCOLL – which didn't work too well.
What about MEM2SPRITE – cant you fill the array with new colour values via a fill algorithm. 
Apologies if that seems silly as I cannot use MEM2SPRITE.  I once used it in the hope of changing all pixels with a certain RGB value. I had a ship sprite and toyed with altering pixels around it to create a burnt effect.  Sadly I failed to get any results  The targeted RGB values never changed.
I read online that the OPENGL GETPIXEL command can be speeded up by turning off some so called "safe mode", another suggestion but no doubt a fruitless one.

[MrTAToad]

I will have to experiment with it some time...  Using SPRITEMEM could be quite quick...

[Kitty Hello]

You need to call drawsprite for every pixel. Using a sprite eith mem2sprite is the way I'd say.

[I love my Brick]

I think going through a loop and drawing each pixel again - which i think the code snippet does - delays the new filled areas. I also think using While/Wend should be avoided when carrying out this execution of code - it creates gremlins effecting a smooth frame rate. I altered the code into a SUB and made a call from a loop which allowed free exit from its execution.

How about grabbing the screen or area as a sprite, redrawing it and then using the new detected areas without a Dim loop? That would put less strain on Getpixel() (going through so many calculations in the loop).

Just a "thinking out of the box" idea to improve speed.

[MrTAToad]

Lets see what you can come up with 

[I love my Brick]

I will have to laugh too as I put my theory into action and found the checking along vast distances (in pixels) was the prob. Bugger!

Code (glbasic) Select Expand

// Slow line fill

SETSCREEN 800,600,0
SETPIXEL 100,100,RGB(255,255,255)
GRABSPRITE 50,100,100,1,1

list=0
newlist=list

TYPE flood ; y ; w ; e ; ENDTYPE

GLOBAL paint[] AS flood ; DIM paint[1000]

paint[list].y = 45 ; paint[list].w = 632 ; paint[list].e = 632

upflag = 0 ; downflag = 0

// Create list Sprite te work with
 
    DRAWRECT 600,40,63,63,RGB(0,255,0) ; DRAWRECT 602,42,60,60,0

FOR list=0 TO 359
DRAWRECT 630+COS(list)*20,70+SIN(list)*20,2,2,RGB(255,0,255)
NEXT

GRABSPRITE 1,600,40,64,64

//
///
// Da Loop
///
//

WHILE TRUE

DRAWSPRITE 1,600,40
ZOOMSPRITE 1,30,30,2,2

GOSUB fillroutine
// To quit the fill : list & newlist need to be measured.
// If list=newlist - job done. (No increase on the list variable.
// if list>newist - keep filling.
SHOWSCREEN

WEND

SUB fillroutine:

a=list // only focus on the highest past of the ARRAY

IF GETPIXEL(paint[a].w,paint[a].y)=RGB(0,0,0) // check left
DEC paint[a].w,1
ENDIF

IF GETPIXEL(paint[a].e,paint[a].y)=RGB(0,0,0) // check right
INC paint[a].e,1
ENDIF

// Draw a line when W & E boundaries are found.

IF GETPIXEL(paint[a].w,paint[a].y)<>RGB(0,0,0) AND GETPIXEL(paint[a].e,paint[a].y)<>RGB(0,0,0)

// Draw line.

FOR loop=paint[a].w+1 TO paint[a].e-1

DRAWSPRITE 50,loop,paint[a].y

NEXT

newflag=1 // Place a call for a new fill position.

GRABSPRITE 1,600,40,64,64

ENDIF

// Set up a new fill area called by "newflag"

IF newflag=1

FOR loop=paint[a].w+1 TO paint[a].e-1

IF GETPIXEL(loop,paint[a].y+1)=RGB(0,0,0)

INC list
paint[list].w=loop
paint[list].e=loop
paint[list].y=paint[a].y+1

BREAK
ENDIF
NEXT

ENDIF

newflag=0

ENDSUB






[I love my Brick]

I never give up on something that challenges me

Ive tried to use sprite2mem followed by a location check within the sprite. (I.e.: the centre)

This worked fine and began growing left & right displaying white pixels (rewriting the sprite) where it found a 0 value.

Sadly, I cannot understand how or why my code isnt detecting the RGB value different to nought.

Im left with a fast flowing flood fill of white.

I will say here, this idea is fast in operation compared to drawline or setpixel.

It acts and jumps along like that found in Pro Motion 6, Pro Pixel, Dogwaffle etc

Any Ideas?


Heres the basis of my code.



// getscreensize w,h
// dim area%[w*h]
// type flood....paint as flood with W & E ...    paint[0].w=420*height / paint[0].e=420*height
// list=0 - increases when it finds a new gap to fill

// loop
// mem2sprite
// goto fill routine
// sprite2mem

////

// fill routine

// for each part of "list"
// check West value: (IF area%[paint(list).west]=0 (or) 0xff000000 THEN area%[paint

.west]=0xffffffff - white)
// dec west value
// repeat check for east value
// if west and east hit boundary do a check above and below for new gaps to fill
// new gap found - increase list variable (paint(list).w etc, with new found x settings within the sprite/bmp.

[MrTAToad]

Better put it in code brackets!