January 20, 2021, 10:57:21 AM

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

• Hero Member
• Posts: 522
##### [bmx]FloodFill for 2 bit images, no stack, no recursion, and no extra arrays
« on: May 04, 2018, 01:09:02 AM »
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.
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
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.
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)
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
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
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.