Async Flood Filling & Flood Filling Optimizations Example

[kevin]

Async Flood Filler Example

    Here's a bit of flood filling example using the PlayBASIC Async flood filling library (you already have it !),  to make it a little more interesting to look at, the attached project includes a picture for you to randomly paint.  
     

PlayBASIC Code: [Select]

   ; include the filling library that comes with PlayBASIC
   #include "AsyncFloodFill.PBA"

   ; load our image for something interesting to paint
   img=loadnewimage("gfx/Colouring-Book-Picture.png",2)

   ; load a font that's a bit larger than the default
   loadFOnt  "veranda",2,32,1
   setfont 2               

   ;----------------------------------------------------------------------------
   Do  ; MAIN LOOP
   ;----------------------------------------------------------------------------

      ; draw our picture to the screen
      drawimage img,0,0,false
   
      ; are we filling ?
      if floodIndex=0

            ; check if the mouse button is down ?
            if mousebutton()=1
                  ; oko so we want to start filling
                  rendertoimage img

                  ; get mouse position
                  Mx=mousex()
                  My=mousey()
                  
                  ; check if the user clicled on a pixel that's not really dark or black   
                  ThisRGB=Point(MX,my)
                  if (RgbGreyScale(ThisRGB) and 255)>5      
                     ; ok, open a new flood ifller
                     FloodIndex=NewFloodFill(Mx,my,rndrgb())
                  endif
                  rendertoscreen
            endif

      else
      
            ; update the flood fill, this scans renders to the surface, returning at set
            ; intervals, so the program doesn't become inactive
            UpdateFloodFill(FloodIndex)   

            ; is the flood filling complete ?
            if GetFloodFillComplete(Floodindex)=1
               ; if it is, we can delete this filler and reset our index
               DeleteFloodFill(FloodIndex)
               FloodIndex=0            
            endif               

            ; draw a message so the user knows the program is working
            centertext Getsurfacewidth()*0.5,GetSurfaceHeight()*0.48,"Working Working Working Working Working"

      endif

      ; draw what flood index we're using in the top left corner of screen
      setcursor 0,0
      ink $00ff00ff
      print "FillIndex:"+str$(floodindex)

      Sync
   ;----------------------------------------------------------------------------
   loop
   ;----------------------------------------------------------------------------

[monkeybot]

have you tried dll'ing the floodfill routine?

[kevin]

 Async Flood Filler Example - DLL Version - PlayBASIC V1.64P revisions

    This version of the demo include a compiled to DLL version of the Async flood fill library.    Works the same as the standard version, although it's bound to V1.64P revisions.  Anybody with PB2DLL and a spare 30 seconds free time can surely build future version if need be..  

[kevin]

 Pre-computed Flood Filling Optimizations - (for PlayBASIC V1.64P)

     The attached examples take the input image, scan through and filling it with unique colours (palette mapping it).   Once we have a palette mapped version of the image, we can simple run though and replace any colour we want.  

     There's three versions of flood filling example included.  The first version is the base version, where it palette maps the image, converts it to a bank and uses that to for filling.   This works ok, but the filling has a fixed cost.    

     The second 2 version computes the area (rect) around unique coloured shape within the palette mapped image.   Then to fill, we only scan through the generally small zone.   This is faster again, but as we're still got comparisons in the inner loops.  We can get rid 90% (or more) of those  by span converting the palette mapped image.

     In version 3, we build a structured in a bank that has a scan line table and a representation of each scan line in the palette mapped image.  Where each scan line is made up of series of spans of colour blocks.   So all we do is scan a line and count up how many times the same pixel occurs in a row,  then dump this to our structure and continue on along the line under reaching the end.  Repeating the process for every scan line, so we're effectively  Run Length Encoding the image.   Then to render flood fill, we scan the row for spans on each row that match our fill colour, when we find a span, we can draw it in one hit using a BOXC command.  This removes virtually all the work per pixel at runtime  
 
      You could of course just use Palette Mapping in PLayBASIC, but that'd make it too easy ! :)

[monkeybot]

nice

[kevin]

  The following code demos a way to emulate what the BOX command is doing in the previous span filling example.   Except this time, we're using copymemory to render from a pre-computed span of coloured 32bit integers stored in a bank directly to the screen.    The example outputs to the screen just so we can see it, ideally you'd be drawing to some off screen chunk of memory when using such an approach.    Using copymemory, just means we can avoid doing masses of manual PokeInt or  PokeBankInt's to memory and thus avoiding the VM overhead that would create.  Making this approach much faster at runtime !       On my legacy test system (10 year old Athlon) you can fill approximately 1/2 the screen at over 200 fps (about a 5 millisecond refresh in other words)

PlayBASIC Code: [Select]

 ; get output images width & height from the current screen width & height   
 IMage_Width    = GetScreenWIdth()
 Image_Height   = GetScreenHEight()
  
 ; define structure of a span 
 type tSpan
     X,Y,Width
 endtype

 ; define array that     
 Dim Spans(IMage_Height) as tSpan

 ; fill in our mock up span list so there's something to see in the demo
 for lp =0 to Image_height-1
       Spans(lp) = new tspan
       Spans(lp).x = 0
       Spans(lp).y = lp
       Spans(lp).Width = ((Image_Width/float(Image_Height))*lp)
 next


 ; create a bank that we'll use for fill rows of pixels
 StripBank=NewBank(Image_Width * 4)


do 
  cls 255
 
  Fill_Colour_ARGB=rndrgb()
 
  ; fill the strip bank with the colour you want to fill in
  for lp=0 to Image_Width-1
       pokeBankInt StripBank,lp*4,Fill_Colour_ARGB 
  next 



  lockbuffer

   ; get address of screen
  ScreenPtr=GetImagePtr(0)
  ; get number of bytes accross of row of screen memory
  ScreenPitch=GetImagePitch(0)

   ; get address of bank
   StripBankPtr=GetBankPtr(StripBank)

    ; now we run through and use copy memory to draw our spans into the picture bank
    for lp=0 to IMage_height-1 
    
         ; calc the location in memory this row of pixels will be
         RowPtr = ScreenPtr + (Spans(lp).y *ScreenPitch) + (Spans(lp).x *4)

         ; copy a run of pre coloured bytes from the stripBank to the screen
         copymemory  StripBankPtr,RowPtr,Spans(lp).width*4
 
    next
    unlockbuffer
   
 Sync
loop esckey()=true