In the last post, Area fill algorithm: crayons and coloring book, I showed a program that emulates a kid drawing in a coloring book.

 

However, the algorithm wasn’t very efficient, and would explode even if you had a simple drawing: it was using the stack to store where to go.

 

The heart of the routine:

                void AreaFill(Point ptcell)

                {

                    if (ptcell.X >= 0 && ptcell.X < m_numCells.Width)

                    {

                        if (ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)

                        {

        //                    System.Threading.Thread.Sleep(100);

                            if (DrawACell(ptcell, m_brushFill))

                            {

                                m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));

                                m_brushFill = new SolidBrush(m_oColor);

                                AreaFill(new Point(ptcell.X - 1, ptcell.Y));

                                AreaFill(new Point(ptcell.X + 1, ptcell.Y));

                                AreaFill(new Point(ptcell.X, ptcell.Y + 1));

                                AreaFill(new Point(ptcell.X, ptcell.Y - 1));

                            }

                        }

                    }

                }

 

 

It just checks boundaries, Draws the current point, then calls itself to draw the points North, South, East and West. Doing this for thousands of pixels eats up the current thread’s stack very fast.

 

One way to fix this is to expand the stack size.

 

You can examine the default stack size of an executable (EXE or DLL) by opening a Visual Studio command prompt (Start->Programs->VS2008->VSToos->VSCommand prompt), then type

link /dump /headers d:\dev\cs\Fill\bin\Debug\Fill.exe

 

Microsoft (R) COFF/PE Dumper Version 9.00.21022.08

Copyright (C) Microsoft Corporation.  All rights reserved.

 

 

Dump of file Fill.exe

 

PE signature found

 

File Type: EXECUTABLE IMAGE

 

FILE HEADER VALUES

             14C machine (x86)

               3 number of sections

        4A1ECBC2 time date stamp Thu May 28 10:37:06 2009

               0 file pointer to symbol table

               0 number of symbols

              E0 size of optional header

             10E characteristics

                   Executable

                   Line numbers stripped

                   Symbols stripped

                   32 bit word machine

 

OPTIONAL HEADER VALUES

             10B magic # (PE32)

            8.00 linker version

            2000 size of code

             800 size of initialized data

               0 size of uninitialized data

            3E7E entry point (00403E7E)

            2000 base of code

            4000 base of data

          400000 image base (00400000 to 00407FFF)

            2000 section alignment

             200 file alignment

            4.00 operating system version

            0.00 image version

            4.00 subsystem version

               0 Win32 version

            8000 size of image

             200 size of headers

               0 checksum

               2 subsystem (Windows GUI)

             540 DLL characteristics

                   Dynamic base

                   NX compatible

                   No structured exception handler

          100000 size of stack reserve

            1000 size of stack commit

          100000 size of heap reserve

            1000 size of heap commit

 

This is a little misleading, because the default stack size is 100000 Hex, which is 1,048,576, or about 1 Megabyte.

 

You can change the stack size using Editbin.exe

 

D:\dev\cs\Fill\bin\Debug>link /dump /headers Fill.exe | find "stack"

          100000 size of stack reserve

            1000 size of stack commit

 

D:\dev\cs\Fill\bin\Debug>editbin /stack:10000,1000 Fill.exe

Microsoft (R) COFF/PE Editor Version 9.00.21022.08

Copyright (C) Microsoft Corporation.  All rights reserved.

 

D:\dev\cs\Fill\bin\Debug>link /dump /headers Fill.exe | find "stack"

            2710 size of stack reserve

             3E8 size of stack commit

 

 

 

A better way to fix this is to use heap memory , rather than the stack:

 

 

        //* More efficient algorithm: don't use the stack to store state

        void AreaFill(Point ptcell)

        {

            Queue<Point> queueCells = new Queue<Point>();

            queueCells.Enqueue(ptcell);

            while (queueCells.Count > 0)

            {

                ptcell = queueCells.Dequeue();

                if (ptcell.X >= 0 && ptcell.X < m_numCells.Width)

                {

                    if (ptcell.Y >= 0 && ptcell.Y < m_numCells.Height)

                    {

                        //                    System.Threading.Thread.Sleep(100);

                        if (DrawACell(ptcell, m_brushFill))

                        {

                            m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));

                            m_brushFill = new SolidBrush(m_oColor);

                            queueCells.Enqueue(new Point(ptcell.X - 1, ptcell.Y));

                            queueCells.Enqueue(new Point(ptcell.X + 1, ptcell.Y));

                            queueCells.Enqueue(new Point(ptcell.X, ptcell.Y + 1));

                            queueCells.Enqueue(new Point(ptcell.X, ptcell.Y - 1));

                        }

                    }

                }

            }

        }

 

This solution is almost the same as the first: however, instead of recurring to go North, etc, the routine just puts the points to work on into a queue.

 

The VB solution is analogous:

    Sub AreaFill(ByVal ptcell As Point)

        Dim queueCells = New Queue(Of Point)

        queueCells.Enqueue(ptcell)

        While queueCells.Count > 0

            ptcell = queueCells.Dequeue()

            If (ptcell.X >= 0 And ptcell.X < m_numCells.Width) Then

 

                If (ptcell.Y >= 0 And ptcell.Y < m_numCells.Height) Then

                    '                    System.Threading.Thread.Sleep(100);

                    If (DrawACell(ptcell, m_brushFill)) Then

                        Me.m_oColor = Color.FromArgb((((Me.m_oColor.ToArgb And &HFFFFFF) + 140) And &HFFFFFF) Or &HFF000000)

 

                        '    m_oColor = Color.FromArgb((int)(((((uint)m_oColor.ToArgb() & 0xffffff) + 140) & 0xffffff) | 0xff000000));

                        m_brushFill = New SolidBrush(m_oColor)

                        queueCells.Enqueue(New Point(ptcell.X - 1, ptcell.Y))

                        queueCells.Enqueue(New Point(ptcell.X + 1, ptcell.Y))

                        queueCells.Enqueue(New Point(ptcell.X, ptcell.Y + 1))

                        queueCells.Enqueue(New Point(ptcell.X, ptcell.Y - 1))

                    End If

                End If

            End If

        End While

    End Sub

 

 

 

 

See also:

Tail Recursion

Cartoon animation program

Comment/Uncomment code to switch versions quickly without using macros

 

http://msdn.microsoft.com/en-us/library/8cxs58a6.aspx

http://bytes.com/groups/net-c/229335-stack-size