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

Article
03/30/2009

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.

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)

{

// https://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>

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>

Comments

Anonymous
March 31, 2009
Like Steven B said in your original blog entry, it's amazing to see how such a little bit of VFP code translates into so much more C# and VB lines. This is progress?
Anonymous
April 30, 2009
Kids know how to use crayons and a coloring book. How do you write such a program? In my last post (
Anonymous
June 07, 2009
PingBack from http://greenteafatburner.info/story.php?id=3715

Partager via

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

Comments

Ressources supplémentaires