Scanline flood fill algorithm in pure VB.Net code

https://www.vbforums.com/images/ieimages/2024/02/20.png

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.

Enjoy. :wave:

Here's the original C code in case that page gets lost to time before VBForums:-

Code:

---

void floodFillScanlineStack(int x, int y, int newColor, int oldColor)
{
  if(oldColor == newColor) return;

  int x1;
  bool spanAbove, spanBelow;

  std::vector<int> stack;
  push(stack, x, y);
  while(pop(stack, x, y))
  {
    x1 = x;
    while(x1 >= 0 && screenBuffer[y * w + x1] == oldColor) x1--;
    x1++;
    spanAbove = spanBelow = 0;
    while(x1 < w && screenBuffer[y * w + x1] == oldColor)
    {
      screenBuffer[y * w + x1] = newColor;
      if(!spanAbove && y > 0 && screenBuffer[(y - 1) * w + x1] == oldColor)
      {
        push(stack, x1, y - 1);
        spanAbove = 1;
      }
      else if(spanAbove && y > 0 && screenBuffer[(y - 1) * w + x1] != oldColor)
      {
        spanAbove = 0;
      }
      if(!spanBelow && y < h - 1 && screenBuffer[(y + 1) * w + x1] == oldColor)
      {
        push(stack, x1, y + 1);
        spanBelow = 1;
      }
      else if(spanBelow && y < h - 1 && screenBuffer[(y + 1) * w + x1] != oldColor)
      {
        spanBelow = 0;
      }
      x1++;
    }
  }
}

---

It was way too difficult to find an implementation this simple while also being decently fast. I'd like it to be preserved as long as possible. ;)

Thank you!! I really, really needed this and was hoping not to become an expert in implementing a VB.NET flood fill algorithm from scratch.