stack(of ..) memory leak with points?

D

DPrometheus

Regular
Joined
Jan 7, 2009
Messages
50
Location
The Netherlands
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

Code: 
''' <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:
Code: 
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?
 
Last edited:
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
Code: 
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:
Code: 
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?
 
Last edited:
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
 
Back
Top