Author Topic: Very fast floodfill  (Read 6522 times)

Offline fuzzy70

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 828
  • Look left, Look right, LOOK OUT!!
    • View Profile
Very fast floodfill
« on: 2012-Oct-31 »
No idea what site the algorithm came from but found it as a text file on my HD, all I do know was it was a very long time ago so I just converted the pseudo code into a GLB function using types & MEM2SPRITE etc.

I made it so it can be used for floodfills on a whole screen or just a sprite & even on my lowly system its very very quick (millsecs rather than seconds  =D )

Lee

Code: GLBasic [Select]
// --------------------------------- //
// Project: fastfloodfill
// Start: Wednesday, October 31, 2012
// IDE Version: 10.283


// FREE-VERSION:
// Need Premium for Features:
// 3D Graphics
// Network Commands
// INLINE C/C+++ code

SETCURRENTDIR("Media") // go to media files
SETSCREEN 800,600,0
SYSTEMPOINTER TRUE
SEEDRND GETTIMERALL()

TYPE Fillpixel
        x%
        y%
ENDTYPE

GLOBAL pixels%[]

LOCAL mx%,my%,b1%,b2%,col%,sx%,sy%

GETSCREENSIZE sx,sy

LOADSPRITE "grab.png",0 // Load an image as CBA to write a filled circle function at present to test non-square borders ;)
//GRABSPRITE 0,0,0,sx,sy
REPEAT
        MOUSESTATE mx, my, b1, b2
        IF MOUSEAXIS(3)
                col = RGB(255,255,255)
                FillFast(mx,my,sx,sy,col,0)
        ENDIF
        DRAWSPRITE 0,0,0
        SHOWSCREEN
UNTIL KEY(57)
END


FUNCTION FillFast: startx%,starty%,width%,height%,fillcol%,id%

        LOCAL i[]  AS Fillpixel
        LOCAL newi AS Fillpixel
        LOCAL newx%,newy%,dir%
        LOCAL fillover%,fillcolour%
        LOCAL fillmap%[]
        LOCAL red%,green%,blue%,alpha%

        IF startx<0 OR starty<0 OR startx>=width% OR starty>=height
                DEBUG "Out of area."
                RETURN
        ENDIF

        SPRITE2MEM (pixels[],id)

        // Convert the fill colour to SPRITEMEM format.
        fillcolour=BOR(fillcol, ASL(255, 24))

        // Get the colour that will be filled over.
        red=BAND(pixels[startx+starty*width%], 0xff)
        green=BAND(ASR(pixels[startx+starty*width%],8), 0xff)
        blue=BAND(ASR(pixels[startx+starty*width%],16), 0xff)
        alpha=BAND(ASR(pixels[startx+starty*width%],24), 0xff)
        fillover=BOR(RGB(red,green,blue), ASL(alpha, 24))

        // If the fill pixel is same colour as then abort.
        IF fillover=fillcolour THEN RETURN

        // Set the start position.
        newi.x=startx
        newi.y=starty
        pixels[startx+starty*width%]=fillcolour
        DIMPUSH i[],newi

        // Reset the fill check map.
        DIM fillmap[width%][height]
        fillmap[startx][starty]=1

        FOREACH pixel IN i[]

                // New test position based on the direction.
                FOR dir=0 TO 3

                        SELECT dir

                        CASE 0                  // Right
                                newx=pixel.x+1
                                newy=pixel.y
                        CASE 1                  // Down
                                newx=pixel.x
                                newy=pixel.y+1
                        CASE 2                  // Left
                                newx=pixel.x-1
                                newy=pixel.y
                        CASE 3                  // Up
                                newx=pixel.x
                                newy=pixel.y-1
                        ENDSELECT


                        IF newx>=0 AND newy>=0 AND newx<width% AND newy<height  // Make sure the new position is in the boundaries of the screen/sprite.
                                IF fillmap[newx][newy]=0                                                        // If not already checked continue
                                        fillmap[newx][newy]=1                                                   // Flag this pixel as now checked
                                        IF pixels[newx+newy*width%]=fillover                    // Check pixel colour is the correct fill over colour.
                                                pixels[newx+newy*width%]=fillcolour                     // Fill and make a new pixel.
                                                newi.x=newx
                                                newi.y=newy
                                                DIMPUSH i[],newi
                                        ENDIF
                                ENDIF
                        ENDIF
                NEXT
                DELETE pixel                                                                            // Remove pixel from list
        NEXT

        MEM2SPRITE (pixels[],id,width%,height)

        DIM fillmap[0][0]
ENDFUNCTION
 
   
« Last Edit: 2012-Nov-01 by fuzzy70 »
"Why don't you just make ten louder and make ten be the top number and make that a little louder?"
- "These go to eleven."

This Is Spinal Tap (1984)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1577
  • Particle Hawk
    • View Profile
    • Silver Volumetric Software
Re: Very fast floodfill
« Reply #1 on: 2012-Oct-31 »
very awesome, love it..

to use this with other size images you need to use this:

GETSPRITESIZE 0,sx,sy
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

http://silver.binhoster.com/

Offline fuzzy70

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 828
  • Look left, Look right, LOOK OUT!!
    • View Profile
Re: Very fast floodfill
« Reply #2 on: 2012-Oct-31 »
Originally I just made it for full screen fills then decided to add a width & height parameters to the function to give it a bit more flexibility.

Glad you like it :)).

Next step is gradient fills but don't hold your breath lol

Lee

Sent from my GT-I5700 using Tapatalk 2

"Why don't you just make ten louder and make ten be the top number and make that a little louder?"
- "These go to eleven."

This Is Spinal Tap (1984)

Offline Hemlos

  • To boldy go where no pixel has gone before!
  • Global Moderator
  • Prof. Inline
  • *******
  • Posts: 1577
  • Particle Hawk
    • View Profile
    • Silver Volumetric Software
Re: Very fast floodfill
« Reply #3 on: 2012-Oct-31 »
Cool stuff  :good:

The reason you need to use the sprite size is because the program will crash if the sprite is smaller than the screensize.

Perhaps theres is another solution you can work into the original algorithm.
Volume_of_Earth(km^3) = 4/3*3.14*POW(6371.392896,3)

http://silver.binhoster.com/

Offline fuzzy70

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 828
  • Look left, Look right, LOOK OUT!!
    • View Profile
Re: Very fast floodfill
« Reply #4 on: 2012-Oct-31 »
I think the algorithm is not a problem, perhaps more checks in the function for sizes passed to it or similar may be required.

Will play around later when back home.

Lee

Btw thanks for moving it to the correct location ^-^
Sent from my GT-I5700 using Tapatalk 2
« Last Edit: 2012-Oct-31 by fuzzy70 »
"Why don't you just make ten louder and make ten be the top number and make that a little louder?"
- "These go to eleven."

This Is Spinal Tap (1984)

Offline fuzzy70

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 828
  • Look left, Look right, LOOK OUT!!
    • View Profile
Re: Very fast floodfill
« Reply #5 on: 2012-Nov-01 »
I think I have addressed the crashing problem, the code that checks if it is in bounds
Code: GLBasic [Select]
IF startx<0 OR starty<0 OR startx>=width% OR starty>=height THEN DEBUG "Out of area."
didn't exit the function if it was passed co-ords that where outside the image, so should read
Code: GLBasic [Select]
IF startx<0 OR starty<0 OR startx>=width% OR starty>=height
                DEBUG "Out of area."
                RETURN
ENDIF
so have amended the above attachment

To test the algorithm I originally used SETPIXEL & GETPIXEL which worked fine but as you know they are seriously slow. Once I knew it was working that is when I abandoned them in favour of SPRITE2MEM for a boost (and what a boost that made lol).

Due to GLBasic being double buffered & the SPRITE2MEM command only working on the back buffer I have yet to figure out an elegant way to do a fill on the entire screen without resorting to using GRABSPRITE prior to calling the fill. So if you want to fill on the entire screen at the moment the following steps are required
  • Draw your graphics
  • Do a GRABSPRITE (prior to SHOWSCREEN)
  • Draw your grabbed sprite so you can select an area to fill
  • Call the fill function
  • Draw the modified sprite then SHOWSCREEN to see it

The above is not required if filling an existing sprite as you just pass the function the SPRITEID.

Any thoughts or suggestions on the fullscreen issue would be appreciated & I am trying to figure out a better solution at the moment.

Lee
"Why don't you just make ten louder and make ten be the top number and make that a little louder?"
- "These go to eleven."

This Is Spinal Tap (1984)

Offline CW

  • Mr. Polyvector
  • ***
  • Posts: 155
    • View Profile
Re: Very fast floodfill
« Reply #6 on: 2013-Apr-10 »
This flood fill is just what I need for my current project. Thanks a ton, Fuzzy.  :good:
-Science_1

Offline CW

  • Mr. Polyvector
  • ***
  • Posts: 155
    • View Profile
Re: Very fast floodfill
« Reply #7 on: 2013-Apr-17 »
Hi Fuzzy,

I hope you don't mind, but I have built upon your outstanding fast-fill code to improve its efficiency when filling a lot of small areas on the screen.
The updated function is called FloodFill.

* Instead of operating on the entire screen, we can now flood within a small subset of the screen. This efficiency can provide a nice speed boost when we have a lot of elements on the screen which we need to fill, as with the cells of a game board, for example.
* Definitions and types used by the function are now internal to the function, so that it can better stand alone.
* Many of the parameters are optional. The default values are based on sizes from the full screen. 
* There is now a Preview mode, to help programers see the exact section of the screen they are capturing, and the starting pixel.
* A description of each of FloodFill's parameters is now included in the comments.
* Several example calls to FloodFill are available in the example program, to demonstrate the behavior of the modified function.
   (To use FloodFill as a stand-alone function, delete the demonstration program in favor of your own.)

Check it out.
-CW
Code: GLBasic [Select]
SETSCREEN 1000,750,FALSE
CLEARSCREEN

// Let's draw an object on the screen and split it in half, so that we can capture the object to a sprite and flood-fill one of the halves.
DRAWRECT 350,350,60,60,RGB(255,255,255);DRAWRECT 351,351,58,58,RGB(0,255,0)
DRAWLINE 351,351,409,409,RGB(255,255,255)

//////////////////////////////////////////////////////////////////////////////
//
// Activate any of these example FloodFill settings to see how the FloodFill function behaves.
// Note that in each case of flood filling inside the square, the starting x and y pixel locations are set to avoid the white lines.
// ------------------------------
// If you disable all of the floodfill commands below, the screen will show a square with both triangle halves the same green color, on a black background.
// ------------------------------
 FloodFill (351,352,RGB(0,0,255)) // Sets the starting pixel within the lower triangle of the box, and uses the entire screen. Capturing the entire screen to fill a small area is not very efficient, but operating on the entire screen has its uses, such as coloring a border. By default, the entire screen is used.
// FloodFill (03,5,RGB(0,0,255),350,350,60,60) // captures only the drawn-box area and uses pixel 3,10 within that box to avoid the outline. Therefore the lower triangle will be filled in. This focused fill does the same job as the line above, but much more efficiently.
// FloodFill (0,0,RGB(0,0,255)) // Sets the start pixel at x=0,y=0 using the entire screen. Therefor everything around the box will be colored in, because everything shares the background pixel color of pixel 0,0.
// FloodFill (345,345,RGB(0,0,255),325,300) // Captures only part of the screen and fills it, surrounding the box. Because no width or height is given, the defaults are the limits of the screen.
// FloodFill (345,345,RGB(0,0,255),325,300,500,400) // Captures only part of the screen and fills it, surrounding the box. Here a width and height are given, and the flood is limited by the size of the captured screen.
// FloodFill (03,05,RGB(0,0,255),350,350,60,60,TRUE) // Targets only the box, but turns Preview mode on. Preview mode allows you to see exactly what your settings will capture, before the flood, and its position on the screen.
//                                                   // The pixel Pix_Num_X, Pix_Num_Y is marked in white, unless the background is already white, in which case it is marked in Black.
//                                                   // (A single pixel is hard to see, so you will have to look carefully to see it.)
//                                                   // This pixel color is restored to its original color before the flood fill is applied.
// FloodFill (345,345,RGB(0,0,255),325,300,TRUE)     // Preview mode can be called even if one or more optional parameters are omitted.
//
//  -----------------------------
SHOWSCREEN
KEYWAIT
END
//////////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
// ----------------        FloodFill      -----------------------------------
// Adapted from Fuzzies excellent FastFloodFill code from
// October of 2012, by Craig Waterman.
// ---------------------------------------------------------------------------
 
FUNCTION FloodFill: Pix_Num_X,Pix_Num_Y,fillcol%,screenx%=-1,screeny%=-1,width%=-1,height%=-1,Preview%=FALSE
//
// Pix_Num_X, Pix_Num_Y This the starting point to flood within the captured area of screen.
//                      These numbers are in relation to the sprite of the captured area, not the location of the pixel on the screen itself.
//
// fillcol              This is the fill color Floodfill will use to flood. The fill covers all pixels within the captured area which share the original color of
//                      the starting pix_num, and is limited by the edges of the captured area contained in the sprite, and will not cover other colors
//                      or jump lines across the captured area which have some other color.
//  
// screenx,screeny      This is the optional starting x,y for the screen area capture. If no x,y is given, the default is (0,0), the upper left corner of the screen.
//
// width, height        This is the optional width and length of the screen capture. If no width or height is given, the ending screensize values are used, which is the lower right corner of the screen.
//
// Preview         When the optional Preview parameter is set for TRUE, the captured screen area is displayed against a grid background;
//                      and the selected starting pixel is set to black, unless the background is already black in which case it is set to white.
//                      As a single pixel is very small and hard to see, so you will have to look very closely to spot it.
//                       (Note: If Preview mode is used, ALL optional parameters must be used.)
//                      This mode is intended for programer use to check his or her screen capture area.
// ---------------------------------------------------------------------------------------------------------------------------------------
LOCAL id% = GENSPRITE()
LOCAL sw,sh
GETSCREENSIZE sw,sh

// If default values are present, set them based on the screen size.

IF screenx < 2 THEN screenx=0
IF screeny < 2 THEN screeny = 0
IF width < 2 THEN width = sw-screenx
IF height < 2 THEN height = sh-screeny

// Errorcheck to avoid overrunning the limits of the screen
IF screenx+width > sw THEN width = sw-screenx
IF screeny+height > sh THEN height = sh-screeny

GRABSPRITE id%,screenx,screeny,width,height  

IF Preview = TRUE

        LOCAL PixHold%
       
        CLEARSCREEN
        DRW_Grid() // Draws a gridwork on the background so the captured section of screen is easy to recognize.
        ALPHATESTING 1.0       
        DRAWSPRITE id,screenx,screeny
       
        // Now we display the starting pixel in either black or white, depending on the background.

        PixHold = GETPIXEL (screenx+Pix_Num_X,screeny+Pix_Num_Y)
        IF PixHold = RGB(0,0,0)
                SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y, RGB(255,255,255)
        ELSE
                SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y, RGB(1,1,1)
        ENDIF
        SHOWSCREEN;     KEYWAIT
        ALPHATESTING 0.0
        SETPIXEL screenx+Pix_Num_X,screeny+Pix_Num_Y,PixHold // Here we restore the original color of the starting pixel for the flood fill to work on.

ENDIF

TYPE Fillpixel
        x%
        y%
ENDTYPE

GLOBAL pixels%[]


        LOCAL i[]  AS Fillpixel
        LOCAL newi AS Fillpixel
        LOCAL newx%,newy%,dir%
        LOCAL fillover%,fillcolour%
        LOCAL fillmap%[]
        LOCAL red%,green%,blue%,alpha%

        IF Pix_Num_X<0 OR Pix_Num_Y<0 OR Pix_Num_X>=width% OR Pix_Num_Y>=height
                DEBUG "Out of area."
                RETURN
        ENDIF

        SPRITE2MEM (pixels[],id)

        // Convert the fill colour to SPRITEMEM format.
        fillcolour=BOR(fillcol, ASL(255, 24))

        // Get the colour that will be filled over.
        red=BAND(pixels[Pix_Num_X+Pix_Num_Y*width%], 0xff)
        green=BAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],8), 0xff)
        blue=BAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],16), 0xff)
        alpha=BAND(ASR(pixels[Pix_Num_X+Pix_Num_Y*width%],24), 0xff)
        fillover=BOR(RGB(red,green,blue), ASL(alpha, 24))

        // If the fill pixel is same colour as then abort.
        IF fillover=fillcolour THEN RETURN
       
//      CLEARSCREEN;PRINT fillover+" "+fillcolour,50,50;SHOWSCREEN;KEYWAIT;END

        // Set the start position.
        newi.x=Pix_Num_X
        newi.y=Pix_Num_Y
        pixels[Pix_Num_X+Pix_Num_Y*width%]=fillcolour
        DIMPUSH i[],newi

        // Reset the fill check map.
        DIM fillmap[width%][height]
        fillmap[Pix_Num_X][Pix_Num_Y]=1

        FOREACH pixel IN i[]

                // New test position based on the direction.
                FOR dir=0 TO 3

                        SELECT dir

                        CASE 0                  // Right
                                newx=pixel.x+1
                                newy=pixel.y
                        CASE 1                  // Down
                                newx=pixel.x
                                newy=pixel.y+1
                        CASE 2                  // Left
                                newx=pixel.x-1
                                newy=pixel.y
                        CASE 3                  // Up
                                newx=pixel.x
                                newy=pixel.y-1
                        ENDSELECT


                        IF newx>=0 AND newy>=0 AND newx<width% AND newy<height  // Make sure the new position is in the boundaries of the screen/sprite.
                                IF fillmap[newx][newy]=0                                                        // If not already checked continue
                                        fillmap[newx][newy]=1                                                   // Flag this pixel as now checked
                                        IF pixels[newx+newy*width%]=fillover                    // Check pixel colour is the correct fill over colour.
                                                pixels[newx+newy*width%]=fillcolour                     // Fill and make a new pixel.
                                                newi.x=newx
                                                newi.y=newy
                                                DIMPUSH i[],newi
                                        ENDIF
                                ENDIF
                        ENDIF
                NEXT
                DELETE pixel                                                                            // Remove pixel from list
        NEXT
//
        MEM2SPRITE (pixels[],id,width%,height)
        DRAWSPRITE id,screenx,screeny//;USEASBMP;SHOWSCREEN;KEYWAIT

        DIM fillmap[0][0]
        RETURN id

ENDFUNCTION
// ------------------------------------------------------------- //
// ---  DRW_Grid  --- // Just Some Interesting Wallpaper.
// ------------------------------------------------------------- //
FUNCTION DRW_Grid:

// Red Grid Lines, for lay out. ///////////
CONSTANT RED% = RGB(255,0,0),GREY% = RGB(100,100,100)
LOCAL sw%,sh%
GETSCREENSIZE sw,sh
LOCAL cnt%,sw_Inc% = sw/32,sh_Inc%=sh/32
FOR cnt = -16 TO 16
        DRAWLINE sw/2-sw_Inc*cnt,0,sw/2-sw_Inc*cnt,sh,GREY
        DRAWLINE 0,sh/2-sh_Inc*cnt,sw,sh/2-sh_Inc*cnt,GREY
NEXT

DRAWLINE sw/2,0,sw/2,sh,RED
DRAWLINE 0,sh/2,sw,sh/2,RED

ENDFUNCTION // DRW_Grid
« Last Edit: 2013-Jun-01 by CW »

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4042
    • View Profile
    • Portfolio
Re: Very fast floodfill
« Reply #8 on: 2013-Apr-17 »
I do get the feeling you guys have something really special going on here.
Altough I donĀ“t have an immediate use for such, somehow I think this could be usefull on a free-drawn- screen-> compile-sprite-block situation.

That situation is something I think about a maybe future project.
Thanks for sharing the knowledge! :good:

Offline CW

  • Mr. Polyvector
  • ***
  • Posts: 155
    • View Profile
Re: Very fast floodfill
« Reply #9 on: 2013-Apr-17 »
I am using it for my Hexboard engine. Here is a snapshot of a board captured in mid draw. Each hex has a color assigned to it, so each hex must be flood-filled individually. Working on small screen sections the size of one hex is much faster than filling a single hex on an area the size of the entire screen. This is what motivated me to revise Fuzzy's original program.
 :)
-CW

Offline fuzzy70

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 828
  • Look left, Look right, LOOK OUT!!
    • View Profile
Re: Very fast floodfill
« Reply #10 on: 2013-Apr-17 »
Glad you found a good use for the routine CW & thanks for the improvements

Lee

Sent from my HTC Wildfire using Tapatalk 2

"Why don't you just make ten louder and make ten be the top number and make that a little louder?"
- "These go to eleven."

This Is Spinal Tap (1984)

Offline CW

  • Mr. Polyvector
  • ***
  • Posts: 155
    • View Profile
Re: Very fast floodfill
« Reply #11 on: 2013-Apr-17 »
Thanks Lee.  :)

P.S. I fixed a minor bug in Preview mode on 04/17/13, and updated the function listing above.
« Last Edit: 2013-Apr-24 by CW »

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4042
    • View Profile
    • Portfolio
Re: Very fast floodfill
« Reply #12 on: 2013-Apr-17 »
That hex board looks really great! :good:

Offline Brick Redux

  • Mr. Drawsprite
  • **
  • Posts: 60
    • View Profile
Re: Very fast floodfill
« Reply #13 on: 2013-Apr-24 »
Brilliant!
A mournful owner of a HP HDX18 Laptop that has died...FECK!

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 4042
    • View Profile
    • Portfolio
Re: Very fast floodfill
« Reply #14 on: 2013-Apr-24 »
heey brick! back again uh!

Hope all that mailing cd went ok and that you are all fine!
Welcome again! :good: