October 28, 2020, 11:51:41 PM

Author Topic: [bmx]FloodFill for 2 bit images, no stack, no recursion, and no extra arrays  (Read 2227 times)

Offline TomToad

  • Hero Member
  • *****
  • Posts: 517
Someone on another forum needed a floodfill algorithm for a 4 color image (2 bits per pixel).  Due to limited memory, the algorithm couldn't use recursion, stacks, extra arrays, linked lists, etc...

I thought I could get something working by storing all the info I needed directly into the image as it was being filled.  This proved to be very difficult as you only have space to store 4 values.  Just following the edge doesn't work as odd shapes and 1 pixel wide paths make parts of the area unreachable.  Instead, I needed to implement some kind of path finding algorithm, but keep all information limited to only 4 values.  One value is needed for testing the source pixel color, so cannot be used in the pathfinding, otherwise the program gets confused.  This limits me to 3 values.  Impossible you say?  You need 4 values to determine direction, North, South, East, and West.  You also need 4 values to remember which direction you last checked, making at least 8 values needed.  You also need a value to indicate the start of the flood fill so you know when you are finished making 9 total. 

First, you can eliminate the start value.  Since there is only one initial pixel, you can spare a bit of extra memory to store its value, comparing the current pixel with the stored pixel to determine when you are finished.  As for the other 8, I figured out a way to determine direction by keeping track of which direction you turn.  So all I need to do is store values for Left, Straight, and Right.   From those three values, I can infer which direction is next and also infer where I came from.  This means that I can now store all the information I need into just 2 pixels.

I had one more bit of a problem to solve.  Remember when I said I couldn't use the source color as it would confuse the program?  Since the source color can be any value from 0-3, I have to shift the L/S/R values to compensate.  I did this by first adding 2 to the turn value to bring it into the range of 1-3, then add that to the source color, and then mod the result by 4.  To read back the value, I just reverse the process.  This insures that I never need to store the source color value.

Anyway, without further adieu, I bring you the non-recursive, no stack, no extra arrays, 2 bit per pixel FloodFill routine.  The code below implements an abstract type which should be extended by your own type that defines the image layout.  The type should extend ReadPixel and WritePixel which sets/gets the color index located at the x,y coordinates.  Your type also needs to set the Width and Height fields to the dimensions of the image.  The example code after the type shows how you can do this.

The example code is a simple image editor.  Just left-click the mouse to draw lines, right-click to fill an area with the current color, and pres the number keys 1-4 to change color.
Code: BlitzMax
  1. SuperStrict
  2.  
  3. 'This type is the base for a 2 bit, 4 color image.  To use, just extend it,
  4. '    implement the abstract methods, and add whatever functionality you need to it
  5. Type T4ColorImageBase
  6.         Field width:Int
  7.         Field height:Int
  8.        
  9.         Method ReadPixel:Int(x:Int,y:Int) Abstract
  10.         Method WritePixel:Int(x:Int,y:Int,Index:Int) Abstract
  11.        
  12.         Const North:Int = 0 'define some constants for the floodfill method
  13.         Const East:Int = 1
  14.         Const South:Int = 2
  15.         Const West:Int = 3
  16.         Const Done:Int = 4
  17.         Const Left:Int = -1
  18.         Const Straight:Int = 0
  19.         Const Right:Int = 1
  20.         Const Backup:Int = 2
  21.        
  22.         'This method will fill an area of one color index with another
  23.         '       StartX and StartY is coordinates for where to start the fill and should
  24.         '               be within the range of (0,0)-(width-1,height-1).  Outside this range
  25.         '               will return with nothing done.
  26.         '       Color is the index of the color you will be filling the area with.  This
  27.         '               should be in the range of 0-3.  Anything outside this range will be
  28.         '               mod 4, if the color at (StartX,StartY) is the same as Color, then the
  29.         '               funtion returns doing nothing
  30.         Method FloodFill(StartX:Int, StartY:Int, Color:Int)
  31.                 If StartX < 0 Or StartX >= Width Then Return 'Do nothing if pixel out of image
  32.                 If StartY < 0 Or StartY >= Height Then Return
  33.                
  34.                 Color = Color & 3 'Mod color to 2 bits
  35.                 Local SourceColor:Int = ReadPixel(StartX,StartY)
  36.                 If Color = SourceColor Then Return 'do nothing if colors are the same
  37.                
  38.                 Local CurrentDirection:Int = North 'This is the direction to check next
  39.                 Local NextX:Int, NextY:Int 'The coordinates of the pixel to check
  40.                 Local x:Int = StartX, y:Int = StartY 'The current pixel coordinates
  41.                 Local Turn:Int = Straight 'The direction to turn
  42.                 Repeat
  43.                         Select (CurrentDirection + Turn) & 3 'calculate the next pixel
  44.                                 Case North
  45.                                         NextX = x
  46.                                         NextY = y-1
  47.                                 Case East
  48.                                         nextX = x+1
  49.                                         NextY = y
  50.                                 Case South
  51.                                         NextX = x
  52.                                         NextY = y+1
  53.                                 Case West
  54.                                         NextX = x-1
  55.                                         NextY = y
  56.                         End Select
  57.                         'Test if next pixel is within the image and if it equals the source pixel
  58.                         If NextX >= 0 And NextX < Width And NextY >= 0 And NextY < Height And ReadPixel(NextX,NextY) = SourceColor
  59.                                 WritePixel(x,y,(SourceColor+Turn+2) & 3) 'write the turn value into the pixel
  60.                                 x = NextX 'update the coordinates
  61.                                 y = NextY
  62.                                 CurrentDirection = (CurrentDirection + Turn) & 3 'Update the direction of travel
  63.                                 Turn = Left 'Point the path to the left
  64.                         Else
  65.                                 If x = StartX And y = StartY 'if first pixel, then update direction else update turn
  66.                                         CurrentDirection :+ 1
  67.                                         If CurrentDirection = Done 'If we have gone all 4 directions, we're through
  68.                                                 WritePixel(x,y,Color)
  69.                                                 Return
  70.                                         End If
  71.                                 Else
  72.                                         Turn :+ 1
  73.                                         If Turn = Backup 'We have tried all directions, so back up to the previous cell
  74.                                                 WritePixel(x,y,Color)
  75.                                                 Select CurrentDirection 'previous cell is opposite of current direction
  76.                                                         Case North
  77.                                                                 y :+ 1
  78.                                                         Case East
  79.                                                                 x :- 1
  80.                                                         Case South
  81.                                                                 y :- 1
  82.                                                         Case West
  83.                                                                 x :+ 1
  84.                                                 End Select
  85.                                                 Turn = ReadPixel(x,y)-2-SourceColor 'Get the turn value stored in the cell
  86.                                                 If Turn < -1 Then Turn :+ 4 'A sort of shifted mod 3 to bring value to -1 - 1
  87.                                                 CurrentDirection = (CurrentDirection - Turn) & 3 'turn opposite direction to get the
  88.                                                                                                                                                         'original direction value
  89.                                         End If
  90.                                 End If                                         
  91.                         End If
  92.                 Forever
  93.         End Method     
  94. End Type
  95.  
  96. '--------------------------------------------------------------------------
  97. '
  98. '               Example usage
  99. '               Left mouse button to draw
  100. '               Right mouse button to flood fill
  101. '               Number keys 1-4 to choose color.
  102. '
  103. '-------------------------------------------------------------------------
  104.  
  105. 'create our 2 bit per pixel image format and define the ReadPixel and WritePixel methods
  106. Type T4ColorImage Extends T4ColorImageBase
  107.         Field BitMap:Int[]
  108.         Field Color:Int[] = [$000000,$FF0000,$00FF00,$0000FF]
  109.         Field RowWidth:Int
  110.        
  111.         Function Create:T4ColorImage(Width:Int, Height:Int)
  112.                 Local Image:T4ColorImage = New T4ColorImage
  113.                 Image.Width = Width
  114.                 Image.Height = Height
  115.                 Image.RowWidth = Ceil(Width/16.0)
  116.                 Image.BitMap = New Int[Image.RowWidth*Height] 'make enough room for the bitmap
  117.                 Return Image
  118.         End Function
  119.        
  120.         Method ReadPixel:Int(x:Int,y:Int)
  121.                 If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return 0
  122.                
  123.                 Local RowIndex:Int = y * RowWidth
  124.                 Local Index:Int = RowIndex + x / 16
  125.                 Local PixelGroup:Int = BitMap[Index]
  126.                 Local Pixel:Int = x Mod 16
  127.                 Local Value:Int = (Pixelgroup & (3 Shl (Pixel*2))) Shr (Pixel * 2)
  128.                 Return Value
  129.         End Method
  130.        
  131.         Method WritePixel(x:Int,y:Int,Color:Int)
  132.                 If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return
  133.                 Color :& 3
  134.                
  135.                 Local RowIndex:Int = y * RowWidth
  136.                 Local Index:Int = RowIndex + x / 16
  137.                 Local PixelGroup:Int = BitMap[Index]
  138.                 Local Pixel:Int = x Mod 16
  139.                 Local Result:Int = (PixelGroup & ~(3 Shl (Pixel*2))) | (Color Shl (Pixel * 2))
  140.                 BitMap[Index] = result
  141.         End Method
  142.        
  143.         Method GetColor:Int(x:Int,y:Int)
  144.                 Return Color[ReadPixel(x,y)]
  145.         End Method
  146.  
  147.         Method line(x1:Int,y1:Int,x2:Int,y2:Int,color:Int)
  148.                 'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
  149.                 Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1)                 'Boolean
  150.                 If Steep
  151.                         Local Temp:Int=X1; X1=Y1; Y1=Temp               'Swap X1,Y1
  152.                         Temp=X2; X2=Y2; Y2=Temp         'Swap X2,Y2
  153.                 EndIf
  154.                 Local DeltaX:Int=Abs(X2-X1)             'X Difference
  155.                 Local DeltaY:Int=Abs(Y2-Y1)             'Y Difference
  156.                 Local Error:Int=0               'Overflow counter
  157.                 Local DeltaError:Int=DeltaY             'Counter adder
  158.                 Local X:Int=X1          'Start at X1,Y1
  159.                 Local Y:Int=Y1         
  160.                 Local XStep:Int
  161.                 Local YStep:Int
  162.                 If X1<X2 Then XStep=1 Else XStep=-1     'Direction
  163.                 If Y1<Y2 Then YStep=1 Else YStep=-1     'Direction
  164.                 If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color)          'Draw
  165.                 While X<>X2
  166.                         X:+XStep                'Move in X
  167.                         Error:+DeltaError               'Add to counter
  168.                         If (Error Shl 1)>DeltaX         'Would it overflow?
  169.                                 Y:+YStep                'Move in Y
  170.                                 Error=Error-DeltaX              'Overflow/wrap the counter
  171.                         EndIf
  172.                         If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color)          'Draw
  173.                 Wend
  174.         End Method
  175. End Type
  176.  
  177. Graphics 800,600
  178. Local Image:T4ColorImage = T4ColorImage.Create(200,150)
  179. Local ColorIndex:Int = 1
  180. Local PixelColor:Int
  181. Local PixelImage:TImage = CreateImage(5,5)
  182. Local Pixmap:TPixmap = LockImage(PixelImage)
  183. Pixmap.ClearPixels($FFFFFFFF)
  184. UnlockImage(PixelImage)
  185. Local MouseFlag:Int = False
  186. Local OldX:Int, OldY:Int
  187.  
  188. While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
  189.         Cls
  190.         For Local x:Int = 0 Until 200
  191.                 For Local y:Int = 0 Until 150
  192.                         PixelColor = Image.GetColor(x,y)
  193.                         SetColor PixelColor Shr 16,(PixelColor Shr 8) & $FF, PixelColor & $FF
  194.                         DrawImage PixelImage,x*5,y*5
  195.                 Next
  196.         Next
  197.         Flip
  198.         If MouseDown(1)
  199.                 Local mx:Int = MouseX()/5
  200.                 Local my:Int = MouseY()/5
  201.                 If MouseFlag
  202.                         If mx <> OldX Or my <> OldY
  203.                                 Image.Line(OldX,OldY,mx,my,ColorIndex)
  204.                         End If
  205.                 Else
  206.                         MouseFlag = True
  207.                         Image.WritePixel(mx,my,ColorIndex)
  208.                 End If
  209.                 OldX = mx
  210.                 OldY = my
  211.         Else
  212.                 MouseFlag = False      
  213.         End If
  214.         If MouseHit(2)
  215.                 Local x:Int = MouseX()/5
  216.                 Local y:Int = MouseY()/5
  217.                 Image.FloodFill(x,y,ColorIndex)
  218.         End If
  219.         If KeyHit(KEY_1) Then ColorIndex = 0
  220.         If KeyHit(KEY_2) Then ColorIndex = 1
  221.         If KeyHit(KEY_3) Then ColorIndex = 2
  222.         If KeyHit(KEY_4) Then ColorIndex = 3
  223. Wend
  224.  
  225.  
------------------------------------------------
8 rabbits equals 1 rabbyte.

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal