Results 1 to 3 of 3

Thread: Scanline flood fill algorithm in pure VB.Net code

  1. #1

    Thread Starter
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,655

    Scanline flood fill algorithm in pure VB.Net code



    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.
    Attached Files Attached Files
    Last edited by Niya; Feb 24th, 2024 at 11:05 PM.
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    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

  2. #2

    Thread Starter
    Angel of Code Niya's Avatar
    Join Date
    Nov 2011
    Posts
    8,655

    Re: Scanline flood fill algorithm in pure VB.Net code

    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.
    Treeview with NodeAdded/NodesRemoved events | BlinkLabel control | Calculate Permutations | Object Enums | ComboBox with centered items | .Net Internals article(not mine) | Wizard Control | Understanding Multi-Threading | Simple file compression | Demon Arena

    Copy/move files using Windows Shell | I'm not wanted

    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

  3. #3
    New Member
    Join Date
    Mar 2024
    Location
    Portland, Oregon
    Posts
    1

    Thumbs up Re: Scanline flood fill algorithm in pure VB.Net code

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width