Welcome to MSDN Blogs Sign in | Join | Help

You can use Visual Studio to debug itself!

How do you find out why your computer or a running program is so slow? Here’s one way.

 

Let’s attach the VS debugger to VS itself. The main executable for VS is devenv.exe.

 

Start Visual Studio 2008. This will be the “debugger”

 

Choose File->Open Project    C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE\devenv.exe

 

(You can also choose Debug->Attach to process to debug another instance of devenv.exe, or any other EXE, like Foxpro.exe or Excel.exe)

 

 

Hit F5, and a dialog pops up:

“Debugging information for ‘devenv.exe’ cannot be found or does not match. Symbols not loaded. Do you want to continue debugging?”. 

Answer yes, and Visual Studio starts. This will be the “debuggee”

 

Do anything you like in the debuggee, such as create or load a project. Hit F12 to cause an asynchronous breakpoint (or go to the debugger and choose Debug->Break All).

 

That will freeze all the debuggee threads and put you in the debugger.

 

You can then examine the Threads window (Debug->Windows->Threads) and see what threads are running.  There are several. You can dbl-click various threads and look at the Call stack for it (Debug->Windows->Call stack).

 

You’ll probably see that most threads are just waiting for something to happen.

 

Choose the main thread. When VS is idling, the stack will look like this:

 

            ntdll.dll!7c90eb94()       

            [Frames below may be incorrect and/or missing, no symbols loaded for ntdll.dll]

            ntdll.dll!7c90e9ab()       

            kernel32.dll!7c8094e2()

>          msvcr90.dll!_onexit_nolock(int (void)* func=0x0072006f)  Line 157 + 0x6 bytes    C

            00660072()       

 

Each stack entry shows the module and address that called the next stack entry. This isn’t very useful, so you need to load symbols. You can use the public Microsoft Symbol Server:

 

Tools->Options->Debug->Symbols

 

http://msdl.microsoft.com/download/symbols

 

Cache the symbols to a local dir, like C:\Symbols

 

Right click on the various modules (like ntdll.dll, kernel32.dll, msenv.dll etc.) in the call stack to load symbols. Now it’s a little more intelligible:

 

>          ntdll.dll!_KiFastSystemCallRet@0()       

            user32.dll!_NtUserKillTimer@8()  + 0xc bytes     

            msenv.dll!CMsoCMHandler::FPushMessageLoop()  + 0x36 bytes           

            msenv.dll!SCM::FPushMessageLoop()  + 0x4f bytes     

            msenv.dll!SCM_MsoCompMgr::FPushMessageLoop()  + 0x28 bytes      

            msenv.dll!CMsoComponent::PushMsgLoop()  + 0x28 bytes       

            msenv.dll!VStudioMainLogged()  + 0x19b bytes

            msenv.dll!_VStudioMain()  + 0x7d bytes

            devenv.exe!util_CallVsMain()  + 0xd8 bytes       

            devenv.exe!CDevEnvAppId::Run()  + 0x5cb bytes         

            devenv.exe!_WinMain@16()  + 0x60 bytes         

            devenv.exe!License::GetPID()  - 0x4cf9 bytes    

            kernel32.dll!_BaseProcessStart@4()  + 0x23 bytes         

 

You can see the WinMain calls a MessageLoop.

 

 

Let’s make the foreground thread busy. Create a VB console application. Add an XML literal:

 

Module Module1

 

    Sub Main()

        Dim bigxml = <xml>

 

                  </xml>

    End Sub

 

End Module

 

Make the XML literal big: open the file C:\Program Files\Reference Assemblies\Microsoft\Framework\v3.5\System.Data.Linq.xml and copy everything except the <?xml version="1.0" encoding="utf-8"?> into the literal (between the <xml> and the </xml>), so you have about 2000 lines. 

 

Start Task Manager (Ctrl-Shift->Escape, or right click on the task bar and choose Task Manager). Observe the little tray icon in the System tray. It will indicate how busy your computer is.

 

For example, if you have 2 processors and 1 thread is very busy, it’ll show 50% busy.

 

Now, if you hover your mouse over the “bigxml”, you’ll trigger VB to create a Quick Info tooltip, but it takes quite a lot of calculation to figure out the tip.

 

Do your asynchronous breakpoint trick and you’ll see something like this:

 

>          msvb7.dll!BCSYM::IsNamedRoot()          

            msvb7.dll!BCSYM::AreTypesEqual()     

            msvb7.dll!EquivalentTypes()  + 0x17 bytes        

            msvb7.dll!ClassifyPredefinedCLRConversion()  + 0x22 bytes     

            msvb7.dll!Semantics::ClassifyPredefinedCLRConversion()  + 0x28 bytes

            msvb7.dll!Semantics::ClassifyPredefinedConversion()  + 0xbf bytes      

            msvb7.dll!Semantics::ResolveConversion()  + 0x234 bytes        

            msvb7.dll!Semantics::ClassifyUserDefinedConversion()  + 0x40685 bytes          

            msvb7.dll!Semantics::ClassifyConversion()  + 0x21e31 bytes     

            msvb7.dll!Semantics::CompareParameterTypeSpecificity()  + 0x57 bytes           

            msvb7.dll!Semantics::CompareParameterSpecificity()  + 0xa3 bytes       

            msvb7.dll!Semantics::InsertIfMethodAvailable()  + 0x461 bytes  

            msvb7.dll!Semantics::CollectOverloadCandidates()  + 0x1e6 bytes         

            msvb7.dll!Semantics::ResolveOverloading()  + 0xd9 bytes         

            msvb7.dll!Semantics::ResolveOverloadedCall()  + 0x5e bytes    

            msvb7.dll!Semantics::InterpretCallExpression()  + 0x2656f bytes

            msvb7.dll!Semantics::CreateConstructedInstance()  + 0xfa bytes

            msvb7.dll!Semantics::CreateConstructedInstance()  + 0x5b bytes           

            msvb7.dll!Semantics::InterpretXmlElement()  + 0x241 bytes       

            msvb7.dll!Semantics::InterpretXmlContent()  + 0x56 bytes          

            msvb7.dll!Semantics::InterpretXmlElement()  + 0x27c bytes       

            msvb7.dll!Semantics::InterpretXmlContent()  + 0x56 bytes          

            msvb7.dll!Semantics::InterpretXmlElement()  + 0x27c bytes       

            msvb7.dll!Semantics::InterpretXmlContent()  + 0x56 bytes          

            msvb7.dll!Semantics::InterpretXmlElement()  + 0x27c bytes       

            msvb7.dll!Semantics::InterpretXmlContent()  + 0x56 bytes          

            msvb7.dll!Semantics::InterpretXmlElement()  + 0x27c bytes       

            msvb7.dll!Semantics::InterpretXmlExpression()  - 0x13d bytes   

            msvb7.dll!Semantics::InterpretXmlExpression()  + 0xb0 bytes    

            msvb7.dll!Semantics::InterpretXmlExpression()  + 0xc3 bytes    

            msvb7.dll!Semantics::InterpretExpression()  - 0x1fc bytes          

            msvb7.dll!Semantics::InterpretExpressionWithTargetType()  + 0x43 bytes           

            msvb7.dll!Semantics::InterpretInitializer()  + 0x36 bytes  

            msvb7.dll!Semantics::InterpretInitializer()  + 0x1a bytes  

            msvb7.dll!Semantics::InterpretInitializer()  + 0x127 bytes 

            msvb7.dll!Semantics::InterpretVariableDeclarationStatement()  + 0x158c bytes    

            msvb7.dll!Semantics::InterpretStatement()  + 0x7b2f bytes         

            msvb7.dll!Semantics::InterpretStatementSequence()  + 0x2f bytes          

            msvb7.dll!Semantics::InterpretBlock()  + 0x24 bytes      

            msvb7.dll!Semantics::InterpretMethodBody()  + 0x1fa bytes      

            msvb7.dll!SourceFile::GetBoundMethodBodyTrees()  + 0x126 bytes       

            msvb7.dll!CBaseSymbolLocator::GetBoundMethodBody()  + 0xb6 bytes           

            msvb7.dll!CSymbolLocator::LocateSymbolInMethodImpl()  + 0x29 bytes

            msvb7.dll!CSymbolLocator::LocateSymbol()  + 0x81f bytes       

            msvb7.dll!CIntelliSense::GenQuickInfo()  + 0x52399 bytes          

            msvb7.dll!CIntelliSense::HandleQuickInfo()  + 0x29 bytes           

            msvb7.dll!CIntelliSense::ProcessCompletionInfo()  + 0x66cda bytes       

            msvb7.dll!CIntelliSense::GenIntelliSenseInfo()  + 0x402 bytes     

            msvb7.dll!SourceFileView::GenIntelliSenseInfo()  + 0x94 bytes   

            msvb7.dll!SourceFileView::GetDataTip()  + 0x743 bytes 

            msvb7.dll!CVBLangService::GetDataTip()  + 0x11d bytes           

            msenv.dll!CEditView::GetFilterDataTipText()  + 0x37 bytes         

            msenv.dll!CEditView::HandleHoverWaitTimer()  + 0x213 bytes    

            msenv.dll!CEditView::TimerTick()  + 0x7d bytes 

            msenv.dll!CEditView::WndProc()  + 0x1685b9 bytes      

            msenv.dll!CEditView::StaticWndProc()  + 0x39 bytes     

            user32.dll!_InternalCallWinProc@20()  + 0x28 bytes        

            user32.dll!_UserCallWinProcCheckWow@32()  + 0xb7 bytes       

            user32.dll!_DispatchMessageWorker@8()  + 0xdc bytes

            user32.dll!_DispatchMessageW@4()  + 0xf bytes          

            msenv.dll!EnvironmentMsgLoop()  + 0xb6 bytes

            msenv.dll!CMsoCMHandler::FPushMessageLoop()  + 0x36 bytes           

            msenv.dll!SCM::FPushMessageLoop()  + 0x4f bytes     

            msenv.dll!SCM_MsoCompMgr::FPushMessageLoop()  + 0x28 bytes      

            msenv.dll!CMsoComponent::PushMsgLoop()  + 0x28 bytes       

            msenv.dll!VStudioMainLogged()  + 0x19b bytes

            msenv.dll!_VStudioMain()  + 0x7d bytes

            devenv.exe!util_CallVsMain()  + 0xd8 bytes       

            devenv.exe!CDevEnvAppId::Run()  + 0x5cb bytes         

            devenv.exe!_WinMain@16()  + 0x60 bytes         

            devenv.exe!License::GetPID()  - 0x4cf9 bytes    

            kernel32.dll!_BaseProcessStart@4()  + 0x23 bytes         

 

Note how it’s easy to read the stack. The bottom of the stack (the first thing put on it) is _BaseProcessStart, which starts the process. You can see that a timer tick caused GetDataTip to call GenIntelliSenseInfo, which calls GenQuickInfo, -> LocateSymbol, etc.

 

Each stack entry indicates the name of the routine being executed. The “+ 0x23 bytes” means the # of bytes into the routine that the call occurred. A low number means near the beginning of that method.

 

Because XML is a tree, and is thus a recursive data structure, you see that XMLContent can contain an XMLExpression and vice versa. The depth of the recursion reflects the actual XML being processed.

 

 

BTW, the VB background compiler thread is:

 

0          >          4620     Worker Thread   ThreadSyncManager::ThreadProc           _KiFastSystemCallRet@0            Normal  0

 

And it’s stack at idle:

 

>          ntdll.dll!_KiFastSystemCallRet@0()       

            ntdll.dll!_ZwWaitForMultipleObjects@20()  + 0xc bytes   

            kernel32.dll!_WaitForMultipleObjectsEx@20()  - 0x48 bytes        

            user32.dll!_RealMsgWaitForMultipleObjectsEx@20()  + 0xd9 bytes        

            ole32.dll!CCliModalLoop::BlockFn()  + 0x76 bytes         

            ole32.dll!_CoWaitForMultipleHandles@20()  + 0xe6 bytes           

            msvb7.dll!ThreadSyncManager::ThreadProc()  + 0x98 bytes       

            kernel32.dll!_BaseThreadStart@8()  + 0x37 bytes           

 

 

 

See also:

Dynamically attaching a debugger

Is a process hijacking your machine?

Posted by Calvin_Hsia | 2 Comments
Filed under: , ,

Stack overflow, expand your stack? Change your algorithm!

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

 

Posted by Calvin_Hsia | 1 Comments
Filed under: , ,

Area fill algorithm: crayons and coloring book

Kids know how to use crayons and a  coloring book. How do you write such a program?

 

In my last post (Which pixels do you turn on when you draw a line?) I showed how to draw a line. Now suppose you have some lines or shapes already drawn. How would you write code to fill in an area bounded by the drawn pixels?

 

IOW, imagine you’ve drawn a circle. You want to fill the circle with a color. Right click inside. What code should run? What if the figure were more complex, like a large block “W” or a curled up snake.

 

More formally: Given an array of pixels that represents the outline of a shape, and a point’s  x,y coordinate within that shape, how would you area fill that shape?

 

Perhaps you could write some code that will check all pixels to the East, North, West, South until it reached a pixel that was already painted. Then what?

 

What sort of algorithm and data structure would you use?

 

 

Below are C# and VB versions of a simple implementation that isn’t very efficient, but is quite simple.

 

The code is identical to the last post (the drawing parts) except for the areas delimited by “AREA”. This makes it easier for you to cut/paste the code.

 

Start Visual Studio 2008

Choose  File->New->Project->C# or VB->Windows Forms Application.

Choose View->Code

 

Paste in the VB or C# version of the code below, hit F5 to run it. Draw a shape, right click to fill.

 

How would you improve it? Why isn’t it efficient?

 

Try making the form bigger and paint more pixels. What happens?

 

Clue:  look at the source code for MineSweeper that I wrote to take advantage of the (then) new feature Collections. It’s part of the Task Pane for Visual Foxpro 9.0

 

See also:

Remove double spaces from pasted code samples in blog

 

 

<C# Sample>

#define AREA 

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace WindowsFormsApplication1

{

    public partial class Form1 : System.Windows.Forms.Form

    {

        Size m_numCells = new Size(350, 200);// we'll use an array of Cells

        Boolean[,] m_cells; // the array of cells: whether they've been drawn or not

        Size m_cellSize = new Size(8, 8);  // cell height & width

        Size m_Offset = new Size(0, 0);

        bool m_MouseDown = false;

        Button btnErase;

        Point? m_PtOld;

        SolidBrush m_brushMouse = new SolidBrush(Color.Red);

        SolidBrush m_brushGenerated = new SolidBrush(Color.Black);

        delegate bool DrawCellDelegate(Point ptcell, Brush br);

        Graphics m_oGraphics;

        public Form1()

        {

            this.Load += new EventHandler(this.Loaded);

        }

        void Loaded(Object o, EventArgs e)

        {

            this.Width = 600;

            this.Height = 400;

            this.btnErase = new Button();

            this.btnErase.Text = "&Erase";

            this.btnErase.Click += new EventHandler(this.btnErase_Click);

            this.Controls.Add(this.btnErase);

            this.BackColor = Color.White;

            btnErase_Click(null, null);

        }

        void btnErase_Click(object sender, System.EventArgs e)

        {

            m_oGraphics = Graphics.FromHwnd(this.Handle);

            m_numCells.Width = this.Width / m_cellSize.Width;

            m_numCells.Height = this.Height / m_cellSize.Height;

            m_cells = new Boolean[m_numCells.Width, m_numCells.Height];

            m_oGraphics.FillRectangle(Brushes.White, new Rectangle(0, 0, this.Width, this.Height));

        }

        Point PointToCell(Point p1)

        {

            Point ptcell = new Point(

            (p1.X - m_Offset.Width) / m_cellSize.Width,

            (p1.Y - m_Offset.Height) / m_cellSize.Height);

            return ptcell;

        }

        protected override void OnMouseDown(MouseEventArgs e)

        {

            if (e.Button == MouseButtons.Left)

            {

                m_MouseDown = true;

                m_PtOld = new Point(e.X, e.Y);

                CheckMouseDown(e);

            }

#if AREA

            else

            {

                AreaFill(PointToCell(new Point(e.X, e.Y)));

            }

#endif

        }

        protected override void OnMouseMove(MouseEventArgs e)

        {

            if (m_MouseDown)

            {

                CheckMouseDown(e);

            }

        }

        protected override void OnMouseUp(MouseEventArgs e)

        {

            m_MouseDown = false;

        }

        void CheckMouseDown(MouseEventArgs e)

        {

            Point ptMouse = new Point(e.X, e.Y);

            Point ptcell = PointToCell(ptMouse);

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

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

            {

                DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, new DrawCellDelegate(DrawACell));

                m_PtOld = ptMouse;

            }

        }

 

        bool DrawACell(Point ptcell, Brush br)

        {

            bool fDidDraw = false;

            if (!m_cells[ptcell.X, ptcell.Y]) // if not drawn already

            {

                m_cells[ptcell.X, ptcell.Y] = true;

                //*

                m_oGraphics.FillRectangle(br,

                    m_Offset.Width + ptcell.X * m_cellSize.Width,

                    m_Offset.Height + ptcell.Y * m_cellSize.Height,

                    m_cellSize.Width,

                    m_cellSize.Height);

                /*/

                 g.DrawRectangle(new Pen(Color.Blue,1),

                    m_Offset.Width + ptcell.X * m_cellSize.Width,

                    m_Offset.Height + ptcell.Y * m_cellSize.Height,

                    m_cellSize.Width,

                    m_cellSize.Height);

                

                  //*/

                fDidDraw = true;

            }

            return fDidDraw;

        }

        void DrawLineOfCells(Point p1, Point p2, DrawCellDelegate drawit)

        {

            // http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

            Brush br =  m_brushMouse;

            int x0 = p1.X;

            int y0 = p1.Y;

            int x1 = p2.X;

            int y1 = p2.Y;

            int x, cx, deltax, xstep,

                y, cy, deltay, ystep,

                 error;

            bool st;

 

            // find largest delta for pixel steps

            st = (Math.Abs(y1 - y0) > Math.Abs(x1 - x0));

 

            // if deltay > deltax then swap x,y

            if (st)

            {

                x0 ^= y0; y0 ^= x0; x0 ^= y0; // swap(x0, y0);

                x1 ^= y1; y1 ^= x1; x1 ^= y1; // swap(x1, y1);

            }

 

            deltax = Math.Abs(x1 - x0);

            deltay = Math.Abs(y1 - y0);

            error = (deltax / 2);

            y = y0;

 

            if (x0 > x1) { xstep = -1; }

            else { xstep = 1; }

 

            if (y0 > y1) { ystep = -1; }

            else { ystep = 1; }

 

            for (x = x0; (x != (x1 + xstep)); x += xstep)

            {

                cx = x; cy = y; // copy of x, copy of y

 

                // if x,y swapped above, swap them back now

                if (st)

                {

                    cx ^= cy; cy ^= cx; cx ^= cy;

                }

                if (drawit(new Point(cx, cy), br))

                {

                    br = m_brushGenerated;

                }

 

                error -= deltay; // converge toward end of line

                if (error < 0)

                { // not done yet

                    y += ystep;

                    error += deltax;

                }

            }

        }

 

#if AREA

 

        SolidBrush m_brushFill = new SolidBrush(Color.Blue);

        Color m_oColor = Color.Black;

        /*

        /*/

                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));

                            }

                        }

                    }

                }

        //*/

#endif

    }

}

 

</C# Sample>

 

<VB Sample>

#Const AREA = True

Public Class Form1

    Dim m_numCells = New Size(350, 300) ' we'll use an array of cells

    Dim m_cells(,) As Boolean   ' the array of cells: whether they've been drawn or not

    Dim m_cellSize = New Size(8, 8) ' cell size & width

    Dim m_Offset = New Size(0, 0)

    Dim m_MouseDown = False

    Dim WithEvents btnErase As Button

    Dim m_PtOld As Point?

    Dim m_brushGenerated = New SolidBrush(Color.Black)

    Dim m_brushMouse = New SolidBrush(Color.Red)

    Dim m_oGraphics As Graphics

    Delegate Function DrawCellDelegate(ByVal ptCell As Point, ByVal br As Brush) As Boolean

 

    Sub Form_Load() Handles Me.Load

        Me.Width = 600

        Me.Height = 400

        Me.btnErase = New Button()

        Me.btnErase.Text = "&Erase"

        Me.Controls.Add(Me.btnErase)

        Me.BackColor = Color.White

        btnErase_Click()

 

    End Sub

    Sub btnErase_Click() Handles btnErase.Click

        m_oGraphics = Graphics.FromHwnd(Me.Handle)

        m_numCells.Width = Me.Width / m_cellSize.Width

        m_numCells.Height = Me.Height / m_cellSize.Height

        ReDim m_cells(m_numCells.Width, m_numCells.Height)

        m_oGraphics.FillRectangle(Brushes.White, New Rectangle(0, 0, Me.Width, Me.Height))

 

    End Sub

    Function PointToCell(ByVal p1 As Point) As Point

        Dim ptcell = New Point( _

            (p1.X - m_Offset.Width) / m_cellSize.Width, _

            (p1.Y - m_Offset.Height) / m_cellSize.Height)

        Return ptcell

 

    End Function

    Protected Overrides Sub OnMouseDown(ByVal e As System.Windows.Forms.MouseEventArgs)

        If e.Button = Windows.Forms.MouseButtons.Left Then

            m_MouseDown = True

            m_PtOld = New Point(e.X, e.Y)

            CheckMouseDown(e)

#If AREA Then

        Else

            AreaFill(PointToCell(New Point(e.X, e.Y)))

#End If

        End If

    End Sub

    Protected Overrides Sub OnMouseMove(ByVal e As System.Windows.Forms.MouseEventArgs)

        If m_MouseDown Then

            CheckMouseDown(e)

        End If

    End Sub

    Protected Overrides Sub OnMouseUp(ByVal e As System.Windows.Forms.MouseEventArgs)

        m_MouseDown = False

    End Sub

    Sub CheckMouseDown(ByVal e As MouseEventArgs)

        Dim ptMouse = New Point(e.X, e.Y)

        Dim ptcell = PointToCell(ptMouse)

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

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

 

            DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, New DrawCellDelegate(AddressOf DrawACell))

            m_PtOld = ptMouse

        End If

    End Sub

    Function DrawACell(ByVal ptCell As Point, ByVal br As Brush) As Boolean

        Dim fDidDraw = False

        If Not m_cells(ptCell.X, ptCell.Y) Then

            m_cells(ptCell.X, ptCell.Y) = True

            m_oGraphics.FillRectangle(br, _

                    m_Offset.Width + ptCell.X * m_cellSize.Width, _

                    m_Offset.Height + ptCell.Y * m_cellSize.Height, _

                    m_cellSize.Width, _

                    m_cellSize.Height)

            fDidDraw = True

        End If

        Return fDidDraw

    End Function

    Sub DrawLineOfCells(ByVal p0 As Point, ByVal p1 As Point, ByVal drawit As DrawCellDelegate)

        Dim br = m_brushMouse

        Dim x0 = p0.X

        Dim y0 = p0.Y

        Dim x1 = p1.X

        Dim y1 = p1.Y

        Dim fSwapped = False

        Dim dx = Math.Abs(x1 - x0)

        Dim dy = Math.Abs(y1 - y0)

        If dy > dx Then

            fSwapped = True ' swap x0<=>y0, x1<->y1

            x0 = p0.Y

            y0 = p0.X

            x1 = p1.Y

            y1 = p1.X

            dx = Math.Abs(x1 - x0)

            dy = Math.Abs(y1 - y0)

        End If

        Dim err = CInt(dx / 2)

        Dim y = y0

        Dim xstep = 1

        If x0 > x1 Then

            xstep = -1

        End If

        Dim ystep = 1

        If y0 > y1 Then

            ystep = -1

        End If

        Dim x = x0

        While x <> x1 + xstep

            Dim cx = x, cy = y ' copy of x,y

            If fSwapped Then

                cx = y

                cy = x

            End If

            If drawit(New Point(cx, cy), br) Then ' if it wasn't already drawn

                br = m_brushGenerated

            End If

            err -= dy

            If err < 0 Then

                y += ystep

                err += dx

            End If

            x += xstep

        End While

    End Sub

#If AREA Then

    Dim m_brushFill = New SolidBrush(Color.Blue)

    Dim m_oColor = Color.Black

    Sub AreaFill(ByVal ptcell As Point)

        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)

                    AreaFill(New Point(ptcell.X - 1, ptcell.Y)) ' West

                    AreaFill(New Point(ptcell.X + 1, ptcell.Y)) ' East

                    AreaFill(New Point(ptcell.X, ptcell.Y + 1)) ' South

                    AreaFill(New Point(ptcell.X, ptcell.Y - 1)) ' North

                End If

            End If

        End If

    End Sub

#End If

 

End Class

 

</VB Sample>

 

Posted by Calvin_Hsia | 4 Comments
Filed under: , ,

Which pixels do you turn on when you draw a line?

When I wrote my cartoon animation program almost 30 years ago (see Cartoon animation program) I needed to know how to draw a line.

 

Of course, nowadays, we just call a library function that will draw a line given two points.

 

If you think about it, the problem is quite complex. Imagine a rectangular array of pixels. Which ones do you paint in order to “see” a straight line?

 

If the desired line is horizontal, or vertical, the problem is simple. However, choosing which pixels to draw for an oblique line is an interesting mathematical problem: see Bresenham's line algorithm - Wikipedia, the free encyclopedia

 

Even back then, I found Bresenham’s algorithm in a book and implemented it for my cartoon program.

 

Suppose you want to create a simple drawing program. When you move the mouse, you can handle the MouseMove event, and light up the pixel at the position of the mouse.

 

However, this will only create a dotted line, with fewer dots if the mouse moved quickly.

 

Let’s see if we can use Bresenham’s algorithm to light up the pixels between successive mouse events.

 

This sample uses larger “pixels”, so you can actually see them as squares. In the code I called them cells (mainly because I stole a lot of the code from my game of Life (see Cellular Automata: The Game of Life )

 

The actual mouse down causes a red pixel to be drawn, and the generated ones are black.

 

Below are C# and VB versions.

 

Start Visual Studio 2008

Choose  File->New->Project->C# or VB->Windows Forms Application.

Choose View->Code

 

Paste in the VB or C# version of the code below, hit F5 to run it.

 

Move the mouse slowly and you’ll see more red pixels. Quickly, and you’ll see more black generated pixels.

Note how the code needs to distinguish between 2 sets of x-y coordinates: actual pixels, and cell coordinates.

Try adjusting the Cell size.

 

Think about what a right click would do.

 

See also:

Comment/Uncomment code to switch versions quickly without using macros

Remove double spaces from pasted code samples in blog

 

 

<C#Sample>

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

 

namespace WindowsFormsApplication1

{

    public partial class Form1 : System.Windows.Forms.Form

    {

        Size m_numCells = new Size(350, 200);// we'll use an array of Cells

        Boolean[,] m_cells; // the array of cells: whether they've been drawn or not

        Size m_cellSize = new Size(8, 8);  // cell height & width

        Size m_Offset = new Size(0, 0);

        bool m_MouseDown = false;

        Button btnErase;

        Point? m_PtOld;

        SolidBrush m_brushMouse = new SolidBrush(Color.Red);

        SolidBrush m_brushGenerated = new SolidBrush(Color.Black);

        delegate bool DrawCellDelegate(Point ptcell, Brush br);

        Graphics m_oGraphics;

        public Form1()

        {

            this.Load += new EventHandler(this.Loaded);

        }

        void Loaded(Object o, EventArgs e)

        {

            this.Width = 600;

            this.Height = 400;

            this.btnErase = new Button();

            this.btnErase.Text = "&Erase";

            this.btnErase.Click += new EventHandler(this.btnErase_Click);

            this.Controls.Add(this.btnErase);

            this.BackColor = Color.White;

            btnErase_Click(null, null);

        }

        void btnErase_Click(object sender, System.EventArgs e)

        {

            m_oGraphics = Graphics.FromHwnd(this.Handle);

            m_numCells.Width = this.Width / m_cellSize.Width;

            m_numCells.Height = this.Height / m_cellSize.Height;

            m_cells = new Boolean[m_numCells.Width, m_numCells.Height];

            m_oGraphics.FillRectangle(Brushes.White, new Rectangle(0, 0, this.Width, this.Height));

        }

        Point PointToCell(Point p1)

        {

            Point ptcell = new Point(

            (p1.X - m_Offset.Width) / m_cellSize.Width,

            (p1.Y - m_Offset.Height) / m_cellSize.Height);

            return ptcell;

        }

        protected override void OnMouseDown(MouseEventArgs e)

        {

            if (e.Button == MouseButtons.Left)

            {

                m_MouseDown = true;

                m_PtOld = new Point(e.X, e.Y);

                CheckMouseDown(e);

            }

#if AREA

            else

            {

                AreaFill(PointToCell(new Point(e.X, e.Y)));

            }

#endif

        }

        protected override void OnMouseMove(MouseEventArgs e)

        {

            if (m_MouseDown)

            {

                CheckMouseDown(e);

            }

        }

        protected override void OnMouseUp(MouseEventArgs e)

        {

            m_MouseDown = false;

        }

        void CheckMouseDown(MouseEventArgs e)

        {

            Point ptMouse = new Point(e.X, e.Y);

            Point ptcell = PointToCell(ptMouse);

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

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

            {

                DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, new DrawCellDelegate(DrawACell));

                m_PtOld = ptMouse;

            }

        }

 

        bool DrawACell(Point ptcell, Brush br)

        {

            bool fDidDraw = false;

            if (!m_cells[ptcell.X, ptcell.Y]) // if not drawn already

            {

                m_cells[ptcell.X, ptcell.Y] = true;

                //*

                m_oGraphics.FillRectangle(br,

                    m_Offset.Width + ptcell.X * m_cellSize.Width,

                    m_Offset.Height + ptcell.Y * m_cellSize.Height,

                    m_cellSize.Width,

                    m_cellSize.Height);

                /*/

                 g.DrawRectangle(new Pen(Color.Blue,1),

                    m_Offset.Width + ptcell.X * m_cellSize.Width,

                    m_Offset.Height + ptcell.Y * m_cellSize.Height,

                    m_cellSize.Width,

                    m_cellSize.Height);

                

                  //*/

                fDidDraw = true;

            }

            return fDidDraw;

        }

        void DrawLineOfCells(Point p1, Point p2, DrawCellDelegate drawit)

        {

            // http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

            Brush br =  m_brushMouse;

            int x0 = p1.X;

            int y0 = p1.Y;

            int x1 = p2.X;

            int y1 = p2.Y;

            int x, cx, deltax, xstep,

                y, cy, deltay, ystep,

                 error;

            bool st;

 

            // find largest delta for pixel steps

            st = (Math.Abs(y1 - y0) > Math.Abs(x1 - x0));

 

            // if deltay > deltax then swap x,y

            if (st)

            {

                x0 ^= y0; y0 ^= x0; x0 ^= y0; // swap(x0, y0);

                x1 ^= y1; y1 ^= x1; x1 ^= y1; // swap(x1, y1);

            }

 

            deltax = Math.Abs(x1 - x0);

            deltay = Math.Abs(y1 - y0);

            error = (deltax / 2);

            y = y0;

 

            if (x0 > x1) { xstep = -1; }

            else { xstep = 1; }

 

            if (y0 > y1) { ystep = -1; }

            else { ystep = 1; }

 

            for (x = x0; (x != (x1 + xstep)); x += xstep)

            {

                cx = x; cy = y; // copy of x, copy of y

 

                // if x,y swapped above, swap them back now

                if (st)

                {

                    cx ^= cy; cy ^= cx; cx ^= cy;

                }

                if (drawit(new Point(cx, cy), br))

                {

                    br = m_brushGenerated;

                }

 

                error -= deltay; // converge toward end of line

                if (error < 0)

                { // not done yet

                    y += ystep;

                    error += deltax;

                }

            }

        }

    }

}

</C#Sample>

 

 

 

<VBSample>

Public Class Form1

    Dim m_numCells = New Size(350, 300) ' we'll use an array of cells

    Dim m_cells(,) As Boolean   ' the array of cells: whether they've been drawn or not

    Dim m_cellSize = New Size(8, 8) ' cell size & width

    Dim m_Offset = New Size(0, 0)

    Dim m_MouseDown = False

    Dim WithEvents btnErase As Button

    Dim m_PtOld As Point?

    Dim m_brushGenerated = New SolidBrush(Color.Black)

    Dim m_brushMouse = New SolidBrush(Color.Red)

    Dim m_oGraphics As Graphics

    Delegate Function DrawCellDelegate(ByVal ptCell As Point, ByVal br As Brush) As Boolean

 

    Sub Form_Load() Handles Me.Load

        Me.Width = 600

        Me.Height = 400

        Me.btnErase = New Button()

        Me.btnErase.Text = "&Erase"

        Me.Controls.Add(Me.btnErase)

        Me.BackColor = Color.White

        btnErase_Click()

 

    End Sub

    Sub btnErase_Click() Handles btnErase.Click

        m_oGraphics = Graphics.FromHwnd(Me.Handle)

        m_numCells.Width = Me.Width / m_cellSize.Width

        m_numCells.Height = Me.Height / m_cellSize.Height

        ReDim m_cells(m_numCells.Width, m_numCells.Height)

        m_oGraphics.FillRectangle(Brushes.White, New Rectangle(0, 0, Me.Width, Me.Height))

 

    End Sub

    Function PointToCell(ByVal p1 As Point) As Point

        Dim ptcell = New Point( _

            (p1.X - m_Offset.Width) / m_cellSize.Width, _

            (p1.Y - m_Offset.Height) / m_cellSize.Height)

        Return ptcell

 

    End Function

    Protected Overrides Sub OnMouseDown(ByVal e As System.Windows.Forms.MouseEventArgs)

        If e.Button = Windows.Forms.MouseButtons.Left Then

            m_MouseDown = True

            m_PtOld = New Point(e.X, e.Y)

            CheckMouseDown(e)

#If AREA Then

        Else

            AreaFill(PointToCell(New Point(e.X, e.Y)))

#End If

        End If

    End Sub

    Protected Overrides Sub OnMouseMove(ByVal e As System.Windows.Forms.MouseEventArgs)

        If m_MouseDown Then

            CheckMouseDown(e)

        End If

    End Sub

    Protected Overrides Sub OnMouseUp(ByVal e As System.Windows.Forms.MouseEventArgs)

        m_MouseDown = False

    End Sub

    Sub CheckMouseDown(ByVal e As MouseEventArgs)

        Dim ptMouse = New Point(e.X, e.Y)

        Dim ptcell = PointToCell(ptMouse)

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

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

 

            DrawLineOfCells(PointToCell(m_PtOld.Value), ptcell, New DrawCellDelegate(AddressOf DrawACell))

            m_PtOld = ptMouse

        End If

    End Sub

    Function DrawACell(ByVal ptCell As Point, ByVal br As Brush) As Boolean

        Dim fDidDraw = False

        If Not m_cells(ptCell.X, ptCell.Y) Then

            m_cells(ptCell.X, ptCell.Y) = True

            m_oGraphics.FillRectangle(br, _

                    m_Offset.Width + ptCell.X * m_cellSize.Width, _

                    m_Offset.Height + ptCell.Y * m_cellSize.Height, _

                    m_cellSize.Width, _

                    m_cellSize.Height)

            fDidDraw = True

        End If

        Return fDidDraw

    End Function

    Sub DrawLineOfCells(ByVal p0 As Point, ByVal p1 As Point, ByVal drawit As DrawCellDelegate)

        Dim br = m_brushMouse

        Dim x0 = p0.X

        Dim y0 = p0.Y

        Dim x1 = p1.X

        Dim y1 = p1.Y

        Dim fSwapped = False

        Dim dx = Math.Abs(x1 - x0)

        Dim dy = Math.Abs(y1 - y0)

        If dy > dx Then

            fSwapped = True ' swap x0<=>y0, x1<->y1

            x0 = p0.Y

            y0 = p0.X

            x1 = p1.Y

            y1 = p1.X

            dx = Math.Abs(x1 - x0)

            dy = Math.Abs(y1 - y0)

        End If

        Dim err = CInt(dx / 2)

        Dim y = y0

        Dim xstep = 1

        If x0 > x1 Then

            xstep = -1

        End If

        Dim ystep = 1

        If y0 > y1 Then

            ystep = -1

        End If

        Dim x = x0

        While x <> x1 + xstep

            Dim cx = x, cy = y ' copy of x,y

            If fSwapped Then

                cx = y

                cy = x

            End If

            If drawit(New Point(cx, cy), br) Then ' if it wasn't already drawn

                br = m_brushGenerated

            End If

            err -= dy

            If err < 0 Then

                y += ystep

                err += dx

            End If

            x += xstep

        End While

    End Sub

 

 

End Class

 

</VBSample>

Posted by Calvin_Hsia | 3 Comments
Filed under: , ,

Comment/Uncomment code to switch versions quickly without using macros

In a typical day, I write or debug programs in several languages: typically Foxpro, C#, VB, C++ and 32 bit assembly, with an occasional MSIL, IDL and 64 bit ASM thrown in.

 

Sometimes, I like to switch between one version of code and another. This is useful if I want to do side by side comparisons of behavior.

 

One way to do this is with preprocessor macros, like this:

 

#If  SomeValue

                <one version of code>

#else

                <another version>

#endif

 

However, that’s a fair amount of typing.

 

There’s a shortcut that works with C# and C++ style comments.

 

In these languages, a line that starts with “//” is a comment.

 

Also, a block comment (which can span multiple lines) starts with “/*” and ends with “*/”

 

 

 

//*

      int sub foo1() {

            int x = 2;

                  Console.WriteLine((new System.Diagnostics.StackTrace().GetFrames()[0].GetMethod().Name)); // shows Foo1

            return x;

      }

 

/*/

      int sub foo2() {

            int x = 3;

                  Console.WriteLine((new System.Diagnostics.StackTrace().GetFrames()[0].GetMethod().Name)); // shows Foo2

            return x;

      }

// */

 

With a single character change I can switch between foo1 and foo2: just delete the very first “/”.  That changes the single line comment into a block comment. The “*/” of the “/*/” now acts like the end of the comment block.

 

Using an editor that colors the code (like Visual Studio) shows the switch properly

 

 

 

/*

      int sub foo1() {

            int x = 2;

                  Console.WriteLine((new System.Diagnostics.StackTrace().GetFrames()[0].GetMethod().Name)); // shows Foo1

            return x;

      }

 

/*/

      int sub foo2() {

            int x = 3;

                  Console.WriteLine((new System.Diagnostics.StackTrace().GetFrames()[0].GetMethod().Name)); // shows Foo2

            return x;

      }

// */

 

This technique is useful when creating sample code for others to play with, such as in my next blog post.

 

 

 

Unorthodox chopsticks

Several years ago, my wife and I were walking through a local shopping mall. At the time, there was some sort of Asian festival. At a display booth there was a table upon which were two trays, side by side. One was empty, and the other had many beans. The sign challenged visitors to see how many beans could be moved to the empty tray with chopsticks in one minute.  A piece of paper indicated the top score so far: something like 10. I imagined how somebody could have spent 6 seconds per bean…

 

My wife, being quite adept with the tool, was able to get a respectable number of beans across, despite the difficulty of picking up a single slippery bean.

 

Then she challenged me, having used chopsticks all my life, to see if I could beat her score.

 

To her chagrin, I deftly wielded the sticks, one in each hand, horizontally in parallel to scoop up dozens of beans at a time, crushing the day’s high score. Of course this wasn’t the normal way most people use chopsticks, but then, it easily was the best solution to the problem at hand.

 

(I’m sure some of you are thinking that a better solution be to pick up the full tray and pour the beans onto the empty tray, but how hard would it be to lift the tray with chopsticks?)

 

 

 

At a recent social gathering, we were divided into groups to solve some word puzzles: given a fairly long word, how many words can be formed from the letters of the original word before the timer rang.

 

Many people would write out the given word as soon as the timer started like so:

 

            E S T A B L I S H M E N T

 

so that others in the group could think up words.

 

When it was my turn to write the word, I wrote it like this:

 

                        E S T A

                        B L I S H

                        M E N T

 

This gave our group 2 dimensions along which to see letter combinations to form words.

 

 

 

My kids had a toy recently, and it had a box into which we had to insert batteries. The box had very tiny Philips screws on it, and my kids tried various small screwdrivers, even my set of jeweler’s drivers. I could get the screws to turn, but they never came out. It turns out that the screws were decorative: just pull the top off the box<sigh>. 

 

(In the old days, no battery operated toys protected their owners from the hazardous battery voltages. Nowadays, probably due to some lawsuit, every compartment seems to need to protect kids from 1.5 volts)

 

 

I spend much of my time solving problems. Sometimes I get so involved in a problem I get stuck. Perhaps then, it is a good time to take a break, rethink the approach, use the tools a little differently or even just kick the tires. Often talking about it with someone else can give useful insights. Doing the unorthodox or unthinkable might just solve the problem!

 

 

See also:

A phone number challenge

A Discounter Introduces Reductions: Multiple Anagrams

Carburetor is a car part, but prosecutable is not

Write your own hangman game

Create your own Word Search puzzles

The Nametag Game

Create your own typing tutor!

Posted by Calvin_Hsia | 7 Comments
Filed under: ,

Cartoon animation program

A cartoon can be thought of as a series of drawings. To simulate movement, the drawings can be slightly different from each other.

 

Remember drawing simple cartoons using a pad of paper? Simply flipping through the pages made the drawings come to life.

 

This was tedious work: a computer can help.

 

Just after first IBM PC came out in Aug 81, I wrote a cartoon animation program in C++ and assembly code. The concept was very simple: just use the mouse (I had to write my own mouse driver for a RS-232 serial mouse and had to hijack the COM1 port for my DOS program) to let the user draw some lines on the screen. Then the user could save those lines as a cartoon frame, and then draw another frame. The program could then calculate multiple frames in between the user created frames, creating smooth animation.

 

That early 80's version of cartoon still runs on XP (although it writes directly to the video memory so it requires full screen mode.

It doesn't run on Vista (I think you can download a DOS compatible window to make it work.)

 

A zip file of the 80's version is available here. Unzip the contents to a folder (check out the date stamps!), then run cartoon.exe and hit Shift-A.

It includes some stored samples, like flying birds, alphabet, basketball. Because this was written before Windows, it won't work with your mouse. You can see the main menu bar at the top. The only thing you can do with this program is run the stored samples by hitting Shift-A. Q will Quit. Try typing other chars to invoke various commands.

If you get it to run on Vista, please let me know the details.

 

About 10 years ago, I wrote another version of Cartoon in Foxpro and it was modified and published as a Solution Sample.

 

Start Visual Foxpro, Task Pane, Solution Samples. In the "Search for sample" text, box, type in Animation. "Display line animation in a form"

You can run the form, or click on the button on the right of the task pane that opens  the form in the Form Designer, so you can see the source code.

 

You can also open the form in the Class Browser, then export the code into a single file using the "View Class Code" button.

 

Foxpro excerpt of the inbetween algorithm (notice how cursors (in-memory data tables) are used)

 

      SELECT (lcTable)

      DO WHILE !EOF("shadow")

            mr = recno()

            mr2 = recno("shadow")

            FOR nb = 0 TO nBetween

                  THISFORMSET.frmAnimation.cls

                  GO mr

                  IF mr2 < RECCOUNT("shadow")

                        GO mr2 IN shadow

                  ENDIF

                  nFrames1 = &lcTable..frameno

                  nFrames2 = shadow.frameno

                  SCAN WHILE &lcTable..frameno = nFrames1

                        nx1 = &lcTable..x1 + nb * (shadow.x1 - &lcTable..x1) / nBetween

                        ny1 = &lcTable..y1 + nb * (shadow.y1 - &lcTable..y1) / nBetween

                        nx2 = &lcTable..x2 + nb * (shadow.x2 - &lcTable..x2) / nBetween

                        ny2 = &lcTable..y2 + nb * (shadow.y2 - &lcTable..y2) / nBetween

                        THISFORMSET.frmAnimation.line(nx1,ny1,nx2,ny2)

                        IF !EOF("shadow")

                              SKIP IN shadow

                              IF shadow.frameno # nFrames2

                                    SKIP -1 IN shadow

                              ENDIF

                        ENDIF

                  ENDSCAN

                  SELECT shadow

                  IF !EOF()

                        SKIP

                        LOCATE REST FOR shadow.Frameno # nFrames2

                  ENDIF

                  SELECT (lcTable)

                  wait wind "" time .05

            ENDFOR

      ENDDO

      USE IN shadow

      SCAN REST

            THISFORMSET.frmAnimation.line(x1,y1,x2,y2)

      ENDSCAN

      THISFORMSET.frmAnimation.frameno = nFrames1 + 1

 

 

 

Below is a more up to date example using WPF.  The equivalent animation code is in tmr_tick().

Try running it, hitting the Demo button.

 

Start Visual Studio 2008.

Choose File->New Project->Visual Basic->WPF Application.

(This also works with Temporary projects)

Open Window1.xaml.vb. Paste in the code below, then hit F5 to run.

 

I had my wife and kids playing with it for quite a while!

 

Try adding a frame or MouseWheel while a cartoon is playing.

 

Try right click and then draw: it changes the way you draw.

 

Experiment with using a touchpad and a mouse for drawing.

 

Try using variable frame rates. Add a feature to save/restore the current cartoon.

 

Try drawing your name, or the letters of the alphabet.

 

My original had features like copy/paste from frames, color fill

 

See also:

My toys over the years

Why was the original IBM PC 4.77 Megahertz?

 

<Cartoon Code>

Class Window1

    Private WithEvents btnNewFrame As Button

    Private WithEvents btnErase As Button

    Private WithEvents btnPlay As Button

    Private WithEvents btnDemo As Button

    Private WithEvents btnReset As Button

    Private txtStatus As TextBlock

    Private _AnimControl As AnimControl

    Sub Load() Handles MyBase.Loaded

        Me.Width = 800

        Me.Height = 600

        Dim xaml = _

        <DockPanel

            xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

            xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml" LastChildFill="True">

            <StackPanel Background="Transparent" Orientation="Vertical" DockPanel.Dock="Top">

                <TextBlock>Draw to create lines for a cartoon frame. Add a new frame, hit play</TextBlock>

                <TextBlock>Rebirth of Calvin's cartoon program circa 1982

                    <Hyperlink>http://blogs.msdn.com/calvin_hsia</Hyperlink>

                </TextBlock>

            </StackPanel>

            <Border DockPanel.Dock="Bottom" Height="25">

                <StackPanel Orientation="Horizontal">

                    <Button Name="btnNewFrame" ToolTip="Add current drawing to cartoon, so you can create a new one">_New Frame</Button>

                    <Button Name="btnErase">_Erase</Button>

                    <Button Name="btnPlay" ToolTip="Animate the current frames or stop animation">_Play</Button>

                    <Button Name="btnDemo">_Demo</Button>

                    <Button Name="btnReset" ToolTip="Erase all frames">_Reset</Button>

                    <TextBox Name="txtBetween" Text="{Binding Path=txtBetween.text}"></TextBox>

                    <TextBlock Name="txtStatus"></TextBlock>

                </StackPanel>

            </Border>

            <UserControl Name="MyCtrl"/>

        </DockPanel>

 

        Dim dPanel = CType(System.Windows.Markup.XamlReader.Load(xaml.CreateReader), DockPanel)

        Dim MyCtrl = CType(dPanel.FindName("MyCtrl"), UserControl)

        _AnimControl = New AnimControl(Me)

        MyCtrl.Content = _AnimControl

        btnPlay = CType(dPanel.FindName("btnPlay"), Button)

        btnNewFrame = CType(dPanel.FindName("btnNewFrame"), Button)

        btnPlay = CType(dPanel.FindName("btnPlay"), Button)

        btnDemo = CType(dPanel.FindName("btnDemo"), Button)

        btnErase = CType(dPanel.FindName("btnErase"), Button)

        btnReset = CType(dPanel.FindName("btnReset"), Button)

        txtStatus = CType(dPanel.FindName("txtStatus"), TextBlock)

        Me.Content = dPanel

    End Sub

    Sub btnNewFrame_Click() Handles btnNewFrame.Click

        _AnimControl.NewFrame()

        RefreshStatus()

    End Sub

    Sub btnPlay_Click() Handles btnPlay.Click

        btnNewFrame_Click()   ' save any currently drawn changes first

        _AnimControl.Play()

    End Sub

    Sub btnDemo_Click() Handles btnDemo.Click

        _AnimControl.Demo()

    End Sub

    Sub btnErase_Click() Handles btnErase.Click

        _AnimControl.EraseBtn()

    End Sub

    Sub btnReset_Click() Handles btnReset.Click

        _AnimControl.Reset()

    End Sub

    Friend Sub RefreshStatus()

        Me.txtStatus.Text = String.Format("Frame count = {0} CurLineCnt = {1} CurFrame= {2} Between = {3}", _

                                          _AnimControl._UserFrameList.Count, _AnimControl._CurLineList.Count, _

                                          _AnimControl._ndxUserFrame, _AnimControl._nBetween)

    End Sub

End Class

 

Public Class AnimControl

    Inherits FrameworkElement

    Private WithEvents _timer As New System.Windows.Threading.DispatcherTimer

    Private _Window1 As Window1

    Friend _nBetween As Integer = 10 ' # of frames being calc'd between user frames

    Friend _ndxUserFrame As Integer   ' index into user created frames.

    Private _ndxBetween As Integer  ' from 0 to nBetween

    Friend _nBetweenDyn As Integer = 0 ' # to add to _nBetween for next animation: adjustable by mousewheel

    Private _ptCurrent As Point?

    Private _ptOld As Point?

    Private _fPenDown As Boolean

    Private _oPen = New Pen(Brushes.Black, 2)

    Private _PenModeDrag As Boolean = True ' Click to create line segs, or continuous drag to create multiple segs

    ' lines to draw for current image: could be while composing, or playing. Could be real frame or calc'd frame

    Friend _CurLineList As New List(Of cFrameLine)

 

    'Frames stored by user

    Friend _UserFrameList As New List(Of cCartoonFrame)   

    Sub New(ByVal w As Window1)

        _Window1 = w

    End Sub

    Sub Reset()

        Me._timer.IsEnabled = False 'stop playback, if any

        Me._UserFrameList.Clear() ' erase all user data

        Me._nBetweenDyn = 0

        EraseBtn()

    End Sub

    Sub EraseBtn() ' erase current frame

        _CurLineList.Clear()

        Me._ptOld = Nothing

        Me._fPenDown = False

        Me.InvalidateVisual()

    End Sub

    Sub Demo()

        Reset()

        Me._CurLineList.Add(New cFrameLine(New Point(10, 10), New Point(10, 300)))

        Me._CurLineList.Add(New cFrameLine(New Point(10, 300), New Point(300, 300)))

        Me._CurLineList.Add(New cFrameLine(New Point(300, 300), New Point(300, 10)))

        Me._CurLineList.Add(New cFrameLine(New Point(300, 10), New Point(10, 10)))

        Me._UserFrameList.Add(New cCartoonFrame(Me._CurLineList, 30))

        Me._CurLineList.Clear() ' reset for next frame

        Me._CurLineList.Add(New cFrameLine(New Point(10, 10), New Point(300, 10)))

        Me._CurLineList.Add(New cFrameLine(New Point(300, 10), New Point(300, 300)))

        Me._CurLineList.Add(New cFrameLine(New Point(300, 300), New Point(10, 300)))

        Me._CurLineList.Add(New cFrameLine(New Point(10, 300), New Point(10, 10)))

        Me._UserFrameList.Add(New cCartoonFrame(Me._CurLineList, 50))

        Me._CurLineList.Clear() ' reset for next frame

        Me._CurLineList.Add(New cFrameLine(New Point(10, 10), New Point(300, 10)))

        Me._UserFrameList.Add(New cCartoonFrame(Me._CurLineList, 10))

        Play()

    End Sub

    Sub NewFrame()

        If _CurLineList.Count > 0 Then

            Dim curFrame = New cCartoonFrame(_CurLineList, 10)

            _UserFrameList.Add(curFrame)

            EraseBtn()

        End If

    End Sub

 

    Friend Sub Play()

        If _UserFrameList.Count < 2 Then

            MsgBox("Need at least 2 frames to animate")

            Return

        End If

        If _timer.IsEnabled Then ' if we're already playing, stop

            _timer.IsEnabled = False

        Else

            _timer.Interval = New TimeSpan(0, 0, 0, 0, 50) ' days,hrs,mins,secs,msecs

            _timer.IsEnabled = True

        End If

        Me._fPenDown = False

        Me._ndxUserFrame = 0

        Me._ndxBetween = 1 ' 1st is drawn now, next by timer tick

        Me._CurLineList.Clear()

        Me._CurLineList.AddRange(Me._UserFrameList(0)._Lines) 'get the 1st frame

        Me.InvalidateVisual() ' show it

    End Sub

    Sub tmr_tick() Handles _timer.Tick ' let's do the animating

        If _ndxUserFrame = Me._UserFrameList.Count - 1 Then     ' we've reached the end: let's restart

            Me._ndxUserFrame = 0

            Me._ndxBetween = 0

        End If

        Me._CurLineList.Clear()

        Dim frmLeft = Me._UserFrameList(Me._ndxUserFrame) ' the frame on the left

        Dim frmRight = Me._UserFrameList(Me._ndxUserFrame + 1) ' the frame on the right

        _nBetween = Math.Max(0, frmLeft._nBetween + Me._nBetweenDyn) ' recorded value plus mousewheel adjustment

        Dim nLinesToDraw = Math.Max(frmLeft._Lines.Count, frmRight._Lines.Count) - 1

        For ndx = 0 To nLinesToDraw ' calc the lines to draw

            Dim lineLeft = frmLeft._Lines(Math.Min(ndx, frmLeft._Lines.Count - 1))

            Dim lineRight = frmRight._Lines(Math.Min(ndx, frmRight._Lines.Count - 1))

            Dim pt0 As New Point With _

                {.X = lineLeft.pt0.X + Me._ndxBetween * (lineRight.pt0.X - lineLeft.pt0.X) / (_nBetween + 1), _

                 .Y = lineLeft.pt0.Y + Me._ndxBetween * (lineRight.pt0.Y - lineLeft.pt0.Y) / (_nBetween + 1)}

            Dim pt1 As New Point With _

                {.X = lineLeft.pt1.X + Me._ndxBetween * (lineRight.pt1.X - lineLeft.pt1.X) / (_nBetween + 1), _

                 .Y = lineLeft.pt1.Y + Me._ndxBetween * (lineRight.pt1.Y - lineLeft.pt1.Y) / (_nBetween + 1)}

            Dim newLine = New cFrameLine(pt0, pt1)

            Me._CurLineList.Add(newLine)

        Next

        If Me._ndxBetween > Me._nBetween Then ' we've reached the right

            Me._ndxUserFrame += 1 ' advance to next user frame

            Me._ndxBetween = 0 ' we don't want to redraw frmRight when it becomes frmLeft

        End If

        Me._ndxBetween += 1 ' advance to next frame

        Me.InvalidateVisual()

    End Sub

    Protected Overrides Sub OnRender(ByVal drawingContext As System.Windows.Media.DrawingContext)

        drawingContext.DrawRectangle(Brushes.AliceBlue, New Pen(Brushes.Purple, 1), New Rect(0, 0, Me.RenderSize.Width, Me.RenderSize.Height))

        For Each fr In Me._CurLineList ' draw the lines in the current frame

            drawingContext.DrawLine(_oPen, fr.pt0, fr.pt1)

        Next

        If Me._fPenDown Then

            If Me._ptOld.HasValue Then

                drawingContext.DrawLine(_oPen, Me._ptOld, Me._ptCurrent)

            Else

                drawingContext.DrawLine(_oPen, Me._ptOld, Me._ptCurrent)

            End If

        End If

        _Window1.RefreshStatus()

    End Sub

    Protected Overrides Sub OnMouseDown(ByVal e As System.Windows.Input.MouseButtonEventArgs)