stack(of ..) memory leak with points?

[DPrometheus]

Hey there,

 

Lately I'm working on some paint program in vb.net but the floodfill algorithm (such as the bucket tool in MS paint) gives me some problems.

I do the tool as follows..

I create a new stack object, and from the point where the user clicks, it goes all the way to the top of the image, and checks colors accordingly. So it finds the boundary with another color or the boundary with the current selection. The it goes down in a while loop and checks if the right / left neighbours needs a repaint as well. If they do, we put them on the stack. The algorithm works nicely, but if I open up taskmanager the memory allocated by this component grows dramatically (sometimes over 1gb, starting from 30 mb) If I fire up CLR profiler it gives me more information and shows that the stack count with the points exceeds 4 million items.

 

The stack.Pop() function should free memory for the top most item when removing it and the stack itself has 0 items when the function finishes I really have no clue what I'm doing wrong? has someone got any idea's?

Also both the stack object and Drawing.Point don't implement IDisposable, so there is no need to call Dispose() explicitly, right? (Even if I would there ain't a member function.. )

 

thanks in advance,

 

M. Siroen

 

 

This is what I've got so far:

 

ArgbColor = custom color class with alpha, red, green and blue properties

MyImage = Drawing.Image object

MyImage.InSelection returns true if the given point is within the current selection, false otherwise

 

''' <summary>
           ''' Flood Fill function with tolerance
           ''' </summary>
           ''' <param name="point">start point</param>
           ''' <param name="newVal">new color</param>
           ''' <param name="Tolerance">Tolerance</param>
           ''' <returns></returns>
           ''' <remarks></remarks>
           Private Function InternalFill(ByVal point As Point, ByVal newVal As Color, ByVal Tolerance As Color) As Object
               ' Check if the given point is within the selection
               If Not MyImage.InSelection(point) Then Return Nothing

               ' Original color value
               Dim oldval As Color
               Dim firstRun As Boolean = False

               ' Switch cursor type to indicate we are busy
               Cursor.Current = Cursors.WaitCursor

               ' Determine the color underneath the mouse
               oldval = MyImage.GetPixel(point)
               ' If the new color and the clicked pixel are the same return
               If (ArgbColor.Compare(oldval, newVal, Tolerance)) Then Return Nothing
               ' First determine if a bitmap is loaded
               If Not (Drawing.Bitmap.Equals(MyImage, Nothing)) Then

                   ' Local variables
                   Dim c As Color
                   Dim st As Stack = New Stack()
                   Dim y1 As Int32
                   ' Flags to keep track which spans are tested
                   Dim sLeft As Boolean
                   Dim sRight As Boolean

                   ' Clear the stack
                   st.Clear()

                   ' Push cursor position onto stack
                   st.Push(point)

                   ' While there are items on the stack
                   While (st.Count() > 0)
                       ' Pop the last position
                       point = CType(st.Pop(), Point)
                       ' Retrieve the color for that position
                       c = MyImage.GetPixel(point)

                       ' Copy over y position to local variable
                       y1 = point.Y
                       ' Scan length of the line
                       While (y1 >= 0)
                           c = MyImage.GetPixel(New Point(point.X, y1))
                           If (ArgbColor.Compare(c, oldval, Tolerance) And MyImage.InSelection(New Point(point.X, y1))) Then
                               y1 -= 1
                           Else
                               Exit While
                           End If
                       End While
                       ' Scan code goes 1 to far, so correct this
                       y1 += 1
                       ' Get the pixel at the new position
                       c = MyImage.GetPixel(New Point(point.X, y1))
                       ' Reset flags
                       sLeft = False
                       sRight = False

                       ' Check if new position is within the image and the replacement color matches the color on this span
                       While (y1 < MyImage.Height And ArgbColor.Compare(c, oldval, Tolerance))
                           ' Set the pixel
                           If (MyImage.InSelection(New Point(point.X, y1))) Then
                               MyImage.SetPixel(New Point(point.X, y1), newVal)
                               '  Application.DoEvents()
                           End If

                           ' Test left neighbour and if color needs to be replaced for this span, add it to the stack
                           If (MyImage.InSelection(New Point(point.X - 1, y1))) Then
                               If Not sLeft And point.X > 0 And ArgbColor.Compare(MyImage.GetPixel(New Point(point.X - 1, y1)), oldval, Tolerance) Then
                                   st.Push(New Point(point.X - 1, y1))
                                   sLeft = True
                               Else
                                   If sLeft And point.X > 0 Then
                                       If ArgbColor.Compare(MyImage.GetPixel(New Point(point.X - 1, y1)), oldval, Tolerance) Then
                                           st.Push(New Point(point.X - 1, y1))
                                       Else
                                           If Not (ArgbColor.Compare(MyImage.GetPixel(New Point(point.X - 1, y1)), oldval, Tolerance)) Then
                                               sLeft = False
                                           End If
                                       End If
                                   End If
                               End If
                           End If

                           ' Test right neighbour
                           If (MyImage.InSelection(New Point(point.X + 1, y1))) Then
                               If Not sRight And point.X < MyImage.Width - 1 And ArgbColor.Compare(MyImage.GetPixel(New Point(point.X + 1, y1)), oldval, Tolerance) Then
                                   st.Push(New Point(point.X + 1, y1))
                                   sRight = True
                               Else
                                   If sRight And point.X < MyImage.Width - 1 Then
                                       If ArgbColor.Compare(MyImage.GetPixel(New Point(point.X + 1, y1)), oldval, Tolerance) Then
                                           st.Push(New Point(point.X + 1, y1))
                                       Else
                                           If Not ArgbColor.Compare(MyImage.GetPixel(New Point(point.X + 1, y1)), oldval, Tolerance) Then
                                               sRight = False
                                           End If
                                       End If
                                   End If
                               End If
                           End If

                           ' Go to next line
                           If MyImage.InSelection(New Point(point.X, y1 + 1)) Then
                               y1 += 1
                           End If
                           ' Retrieve new color
                           c = MyImage.GetPixel(New Point(point.X, y1))

                           If st.Count > 1500000 And firstRun = False Then
                               Dim thr As New Threading.Thread(AddressOf threadMessage)
                               thr.Start()
                               firstRun = True
                           End If
                       End While
                   End While

                   st.Clear()

                   ' Reset cursor type
                   Cursor.Current = Cursors.Default
               End If
               Return True
           End Function

 

EDIT:

As I figured out today the stack grows just too much in size.

In this part:

If sLeft And point.X > 0 Then
                                       If ArgbColor.Compare(MyImage.GetPixel(New Point(point.X - 1, y1)), oldval, Tolerance) Then
                                           st.Push(New Point(point.X - 1, y1))
                                       Else
                                           If Not (ArgbColor.Compare(MyImage.GetPixel(New Point(point.X - 1, y1)), oldval, Tolerance)) Then
                                               sLeft = False
                                           End If
                                       End If
                                   End If

 

I had to check not only the opposite direction (which would be sufficient if no selections were made) but also check the current direction and push those values onto the stack. i.e. If the stack was 'moving' left I had to check the values left of the current column as well, otherwise I'm left behind with gaps in the image.

 

If I remove this extra line however the memory leak seems to be gone (the program keeps around 31 MB). Still does someone has another workaround for those gaps? With the selections I can add or remove shapes to the current selection. Combinations of several primary shapes will make the fill tool more error-prone in words of leaving gaps.

Suggestions?

Edited January 15, 2009 by DPrometheus

[PlausiblyDamp]

When checking for gaps are you putting the same point onto the stack more than once?

 

If so this could explain the huge leap in memory.

[DPrometheus]

Yes I did.. After making some logfiles and a log scanner I found out that almost 90 % was a duplicate. So I included a check if it already exists on the stack with

st.Contains(point)

where st is the stack

this does terminate the memory leak in its whole but it lets the user wait for almost 29 seconds to fill a (relatively) small image of 440x440 pxls!

 

Therefore I started another approach.. Create a region and add a new rectangle for each pixel which needs to repaint.

At the end I simply call

graphics.FillRegion(new region)

 

But the duplicates come back even with a check to st.contains

I checked all the points where I add points to the stack in the newly created GetRegion function, and those are all variants of something like this:

If Not st.Contains(rightPoint) Then
   st.Push(rightPoint)
   writer.WriteLine(rightPoint.ToString())
   sRight = True
End If

 

The logger gives results like:

From the 8760 added points there are 8178 duplicates.

 

Any idea's how to implement a faster fill? Or what's happening in the GetRegion? How can I check for duplicate stack points if the stack.contains function checks each possible entry point to get onto the stack?

Edited January 21, 2009 by DPrometheus

[PlausiblyDamp]

Something like http://www.codeproject.com/KB/GDI-plus/queuelinearfloodfill.aspx might be worth a read.

[DPrometheus]

After a couple of hours I managed to modify that article to fit my needs.

So I would say Problem solved. :D

 

for comparison these were my test results.. If someone might want to create a floodfill, here are some speed tests for comparison:

method speed

Recursive * -

GDI+ / Image.SetPixel 5 min. - 58 min.

GDI+ / Graphics.FillRegion 6 - 48 seconds

QueueLinear 0.04 - 0.6 seconds

 

* Recursive didn't work in managed code. Almost all fills resulted into stackoverflow

 

thnX