[bmx]FloodFill for 2 bit images, no stack, no recursion, and no extra arrays

[TomToad]

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) Select Expand

SuperStrict

'This type is the base for a 2 bit, 4 color image.  To use, just extend it,
'    implement the abstract methods, and add whatever functionality you need to it
Type T4ColorImageBase
Field width:Int
Field height:Int

Method ReadPixel:Int(x:Int,y:Int) Abstract
Method WritePixel:Int(x:Int,y:Int,Index:Int) Abstract

Const North:Int = 0 'define some constants for the floodfill method
Const East:Int = 1
Const South:Int = 2
Const West:Int = 3
Const Done:Int = 4
Const Left:Int = -1
Const Straight:Int = 0
Const Right:Int = 1
Const Backup:Int = 2

'This method will fill an area of one color index with another
' StartX and StartY is coordinates for where to start the fill and should
' be within the range of (0,0)-(width-1,height-1).  Outside this range
' will return with nothing done.
' Color is the index of the color you will be filling the area with.  This
' should be in the range of 0-3.  Anything outside this range will be
' mod 4, if the color at (StartX,StartY) is the same as Color, then the
' funtion returns doing nothing
Method FloodFill(StartX:Int, StartY:Int, Color:Int)
If StartX < 0 Or StartX >= Width Then Return 'Do nothing if pixel out of image
If StartY < 0 Or StartY >= Height Then Return

Color = Color & 3 'Mod color to 2 bits
Local SourceColor:Int = ReadPixel(StartX,StartY)
If Color = SourceColor Then Return 'do nothing if colors are the same

Local CurrentDirection:Int = North 'This is the direction to check next
Local NextX:Int, NextY:Int 'The coordinates of the pixel to check
Local x:Int = StartX, y:Int = StartY 'The current pixel coordinates
Local Turn:Int = Straight 'The direction to turn
Repeat
Select (CurrentDirection + Turn) & 3 'calculate the next pixel
Case North
NextX = x
NextY = y-1
Case East
nextX = x+1
NextY = y
Case South
NextX = x
NextY = y+1
Case West
NextX = x-1
NextY = y
End Select
'Test if next pixel is within the image and if it equals the source pixel
If NextX >= 0 And NextX < Width And NextY >= 0 And NextY < Height And ReadPixel(NextX,NextY) = SourceColor
WritePixel(x,y,(SourceColor+Turn+2) & 3) 'write the turn value into the pixel
x = NextX 'update the coordinates
y = NextY
CurrentDirection = (CurrentDirection + Turn) & 3 'Update the direction of travel
Turn = Left 'Point the path to the left
Else
If x = StartX And y = StartY 'if first pixel, then update direction else update turn
CurrentDirection :+ 1
If CurrentDirection = Done 'If we have gone all 4 directions, we're through
WritePixel(x,y,Color)
Return
End If
Else
Turn :+ 1
If Turn = Backup 'We have tried all directions, so back up to the previous cell
WritePixel(x,y,Color)
Select CurrentDirection 'previous cell is opposite of current direction
Case North
y :+ 1
Case East
x :- 1
Case South
y :- 1
Case West
x :+ 1
End Select
Turn = ReadPixel(x,y)-2-SourceColor 'Get the turn value stored in the cell
If Turn < -1 Then Turn :+ 4 'A sort of shifted mod 3 to bring value to -1 - 1
CurrentDirection = (CurrentDirection - Turn) & 3 'turn opposite direction to get the
'original direction value
End If
End If
End If
Forever
End Method
End Type

'--------------------------------------------------------------------------
'
' Example usage
' Left mouse button to draw
' Right mouse button to flood fill
' Number keys 1-4 to choose color.
'
'-------------------------------------------------------------------------

'create our 2 bit per pixel image format and define the ReadPixel and WritePixel methods
Type T4ColorImage Extends T4ColorImageBase
Field BitMap:Int[]
Field Color:Int[] = [$000000,$FF0000,$00FF00,$0000FF]
Field RowWidth:Int

Function Create:T4ColorImage(Width:Int, Height:Int)
Local Image:T4ColorImage = New T4ColorImage
Image.Width = Width
Image.Height = Height
Image.RowWidth = Ceil(Width/16.0)
Image.BitMap = New Int[Image.RowWidth*Height] 'make enough room for the bitmap
Return Image
End Function

Method ReadPixel:Int(x:Int,y:Int)
If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return 0

Local RowIndex:Int = y * RowWidth
Local Index:Int = RowIndex + x / 16
Local PixelGroup:Int = BitMap[Index]
Local Pixel:Int = x Mod 16
Local Value:Int = (Pixelgroup & (3 Shl (Pixel*2))) Shr (Pixel * 2)
Return Value
End Method

Method WritePixel(x:Int,y:Int,Color:Int)
If x < 0 Or x >= Width Or y < 0 Or y >= Height Then Return
Color :& 3

Local RowIndex:Int = y * RowWidth
Local Index:Int = RowIndex + x / 16
Local PixelGroup:Int = BitMap[Index]
Local Pixel:Int = x Mod 16
Local Result:Int = (PixelGroup & ~(3 Shl (Pixel*2))) | (Color Shl (Pixel * 2))
BitMap[Index] = result
End Method

Method GetColor:Int(x:Int,y:Int)
Return Color[ReadPixel(x,y)]
End Method

Method line(x1:Int,y1:Int,x2:Int,y2:Int,color:Int)
'Draws a line of individual pixels from X1,Y1 to X2,Y2 at any angle
Local Steep:Int=Abs(Y2-Y1) > Abs(X2-X1) 'Boolean
If Steep
Local Temp:Int=X1; X1=Y1; Y1=Temp 'Swap X1,Y1
Temp=X2; X2=Y2; Y2=Temp 'Swap X2,Y2
EndIf
Local DeltaX:Int=Abs(X2-X1) 'X Difference
Local DeltaY:Int=Abs(Y2-Y1) 'Y Difference
Local Error:Int=0 'Overflow counter
Local DeltaError:Int=DeltaY 'Counter adder
Local X:Int=X1 'Start at X1,Y1
Local Y:Int=Y1
Local XStep:Int
Local YStep:Int
If X1<X2 Then XStep=1 Else XStep=-1 'Direction
If Y1<Y2 Then YStep=1 Else YStep=-1 'Direction
If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color) 'Draw
While X<>X2
X:+XStep 'Move in X
Error:+DeltaError 'Add to counter
If (Error Shl 1)>DeltaX 'Would it overflow?
Y:+YStep 'Move in Y
Error=Error-DeltaX 'Overflow/wrap the counter
EndIf
If Steep Then WritePixel(Y,X,color) Else WritePixel(X,Y,color) 'Draw
Wend
End Method
End Type

Graphics 800,600
Local Image:T4ColorImage = T4ColorImage.Create(200,150)
Local ColorIndex:Int = 1
Local PixelColor:Int
Local PixelImage:TImage = CreateImage(5,5)
Local Pixmap:TPixmap = LockImage(PixelImage)
Pixmap.ClearPixels($FFFFFFFF)
UnlockImage(PixelImage)
Local MouseFlag:Int = False
Local OldX:Int, OldY:Int

While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()
Cls
For Local x:Int = 0 Until 200
For Local y:Int = 0 Until 150
PixelColor = Image.GetColor(x,y)
SetColor PixelColor Shr 16,(PixelColor Shr 8) & $FF, PixelColor & $FF
DrawImage PixelImage,x*5,y*5
Next
Next
Flip
If MouseDown(1)
Local mx:Int = MouseX()/5
Local my:Int = MouseY()/5
If MouseFlag
If mx <> OldX Or my <> OldY
Image.Line(OldX,OldY,mx,my,ColorIndex)
End If
Else
MouseFlag = True
Image.WritePixel(mx,my,ColorIndex)
End If
OldX = mx
OldY = my
Else
MouseFlag = False
End If
If MouseHit(2)
Local x:Int = MouseX()/5
Local y:Int = MouseY()/5
Image.FloodFill(x,y,ColorIndex)
End If
If KeyHit(KEY_1) Then ColorIndex = 0
If KeyHit(KEY_2) Then ColorIndex = 1
If KeyHit(KEY_3) Then ColorIndex = 2
If KeyHit(KEY_4) Then ColorIndex = 3
Wend