A recent discussion in this thread led me to the discover that a decent flood fill implementation was somewhat difficult to find online, most especially for .Net languages like C# or VB.Net. Given the vast number of 3rd party libraries out there for .Net it's not too surprising since some of them are bound to be graphics libraries that have flood fill algorithms. Perhaps somewhere in the .Net Framework or .Net Core families there might be one I'm not aware of. Regardless, it's such a simple operation, too simple not to be able to find a decent implementation of it. So I decided to do something about that.
Most flood fill implementations you readily find online are variations of what is called the 4 way recursive flood fill. It seems to be very popular because of how extremely easy it is to understand and implement. The problem with it though is that it is extremely slow, even on moderately sized images. I certainly don't recommend it. Eventually my research led me to another variant called scanline flood fills which are known for having very decent performance under most circumstances so this is what I chose to pursue.
Finding a decent scanline flood fills algorithm online was equally problematic. The few I found were too clumsily implemented, overly complex or had many amateur mistakes. I actually saw one in C# that used Bitmap.GetPixel/Bitmap.SetPixel to read and write pixels which is insane as it will tank performance very very hard. No serious graphics algorithm should ever use SetPixel/GetPixel.
All was not lost though because I eventually stumbled upon a web page which has a decent implementation of the a scanline flood fill written in C that was fast, fairly easy to understand and translate. You can see it here at the bottom of the page:- https://lodev.org/cgtutor/floodfill.html
Here is my VB.Net version in it's entirety. Also attached to this post is a demo app where you can test it out against different graphical arrangements:-
Code:
Imports System.Drawing.Imaging
Imports System.Runtime.InteropServices
Imports System.Threading
'Algorithm based on this C code.
'Scroll to the bottom of the page:-
'https://lodev.org/cgtutor/floodfill.html
'*****************************************************************************************
'Note:
'I use the terms "span" and "scanline" in following comments. They are NOT the same thing.
'A scanline is a single row of pixels in the image.
'A span is a set or horizontal pixels of the same colour. A scanline CAN be a span but it could also
'contain multiple spans.
'*****************************************************************************************
Public Class Gfxfast
Public Shared Sub FloodFill(ByVal image As Bitmap, ByVal x As Integer, ByVal y As Integer, ByVal new_color As Color)
Dim pixels = GetPixels(image)
Dim newClr = new_color.ToArgb()
Dim oldClr = pixels(x + y * image.Width)
Dim spanAbove, spanBelow As Boolean
Dim width, height As Integer
If newClr = oldClr Then Return
'Very important optimization.
'If we instead read height and width values from the bitmap itself
'from within the loops it will tank the performance hard.
width = image.Width
height = image.Height
Dim stack As New Stack(Of Point)(4096)
stack.Push(New Point(x, y))
Do Until stack.Count = 0
Dim p As Point = stack.Pop()
Dim x1 As Integer = p.X
'Find the leftmost pixel of the current span that
'is in need of filling. This is where we start filling
'from
While x1 >= 0 AndAlso pixels(x1 + p.Y * width) = oldClr
x1 -= 1
End While
x1 += 1
spanAbove = False
spanBelow = False
While x1 < width AndAlso pixels(x1 + p.Y * width) = oldClr
'Start filling
pixels(x1 + p.Y * width) = newClr
'Check above the current pixel for a fillable pixel
If Not spanAbove AndAlso p.Y > 0 AndAlso pixels(x1 + (p.Y - 1) * width) = oldClr Then
stack.Push(New Point(x1, p.Y - 1))
spanAbove = True
'If we encounter an unfillable pixel above we set spanAbove to False to allow
'us to add another span on this same scanline if we eventually encounter
'a fillable pixel. This is what allows us to fill around islands and other
'complex arrangements
ElseIf spanAbove AndAlso p.Y > 0 AndAlso pixels(x1 + (p.Y - 1) * width) <> oldClr Then
spanAbove = False
End If
'Check below the current pixel for a fillable pixel
If Not spanBelow AndAlso p.Y < height - 1 AndAlso pixels(x1 + (p.Y + 1) * width) = oldClr Then
stack.Push(New Point(x1, p.Y + 1))
spanBelow = True
'If we encounter an unfillable pixel below we set spanBelow to False to allow
'us to add another span on this same scanline if we eventually encounter
'a fillable pixel. This is what allows us to fill around islands and other
'complex arrangements
ElseIf spanBelow AndAlso p.Y < height - 1 AndAlso pixels(x1 + (p.Y + 1) * width) <> oldClr Then
spanBelow = False
End If
x1 += 1
End While
Loop
'Write the changed pixels back to the image
WritePixels(image, pixels)
End Sub
Private Shared Function GetPixels(ByVal bm As Bitmap) As Integer()
Dim bmData = bm.LockBits(New Rectangle(0, 0, bm.Width, bm.Height),
ImageLockMode.ReadWrite,
PixelFormat.Format32bppArgb)
'For best performance we treat the image as an array of 32 bit Integers
Dim pixels As Integer() = New Integer((bm.Width * bm.Height) - 1) {}
Marshal.Copy(bmData.Scan0, pixels, 0, pixels.Length)
bm.UnlockBits(bmData)
Return pixels
End Function
Private Shared Sub WritePixels(ByVal bm As Bitmap, ByVal pixels As Integer())
Dim bmData = bm.LockBits(New Rectangle(0, 0, bm.Width, bm.Height),
ImageLockMode.ReadWrite,
PixelFormat.Format32bppArgb)
Marshal.Copy(pixels, 0, bmData.Scan0, pixels.Length)
bm.UnlockBits(bmData)
End Sub
End Class
Requirements for demo app
Visual Studio 2022
.Net Framework 4.7.2
Additional Credit
Lode Vandevenne for the original C algorithm from which my code was translated.
VBForums member .paul. for raising this discussion.
C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter
There's just no reason to use garbage like InputBox. - jmcilhinney
The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber
C++ programmers will dismiss you as a cretinous simpleton for your inability to keep track of pointers chained 6 levels deep and Java programmers will pillory you for buying into the evils of Microsoft. Meanwhile C# programmers will get paid just a little bit more than you for writing exactly the same code and VB6 programmers will continue to whitter on about "footprints". - FunkyDexter
There's just no reason to use garbage like InputBox. - jmcilhinney
The threads I start are Niya and Olaf free zones. No arguing about the benefits of VB6 over .NET here please. Happiness must reign. - yereverluvinuncleber
Reply With Quote
Re: Scanline flood fill algorithm in pure VB.Net code
