3 Bresenham’s Line drawing procedure

T. Raghuveera

Learning Objectives:

Understand the theory behind Bresenham’s Line drawing procedure
Prove the advantages of Bresenham’s procedure over DDA procedure
Solve example problem for better understanding of the concepts

In this module, let’s focus on Bresenham’s line drawing procedure which is superior to DDA procedure as this avoids floating point calculations and gives a better approximation for the theoretical line.

Bresenham is a scientist and is popular for his contributions to line drawing and circle drawing procedures, and few others, which are not of our interest.

Assume a line with slope <1, the same discussion that we had during DDA procedure is still valid here, i.e. sample the line along x-axis at unit x-intervals if the line slopes are <=1 otherwise sample the line along y-axis.

Let’s start our assumptions with a line whose slope <1 i.e. the line is more inclined towards x-axis, so it is obvious to sample the line along x-axis at unit x-intervals and compute the corresponding y values. Also that to compute next points on a line, we always starts with a known point on the line and tries computing the next unknown point on the line using recursive equations.

So the next x i.e. xk+1=xk+1 and the next y i.e. yk+1 is to be computed. Let the known plotted point on the line be (xk,yk).

Before we get into the derivation lets understand the underlying principle of Bresenham’s procedure. To compute the next point on the line (Xk+1, Yk+1), a value called ‘decision parameter’ is computed. Based on the result a pixel is chosen for plotting.

As shown in the figure above let the line shown be the theoretical line and we need to find the best possible approximation for this by computing Bresenham’s line. For the next X position, Xk+1, the corresponding Y value could not be plotted as the position (Xk+1, y) does not exist on the monitor. We have to choose between Yk and Yk+1. i.e. next position to be plotted is either (Xk+1, Yk) or (Xk+1, Yk+1). Now how do we decide among the two choices. The answer is, compute the vertical difference between the possible pixel position and the position on the true theoretical line which is.

Let dlower be the vertical difference between the position (y) on theoretical line and the lower pixel (yk) and dupper be the vertical difference between the position (y) on theoretical line and the upper pixel (yk+1). As evident if dlower is < dupper the theoretical line is closer to the lower pixel so choose position (Xk+1, Yk) otherwise choose position. The difference between dlower and dupper is considered as ‘decision parameter’, as the sign of the difference operation helps us decide what y coordinate position is to be chosen for the next x.

‘Decision parameter’ referred to as pk helps us decide which of the pixels is to be chosen
Whichever pixel position is close to the theoretical line, that pixel is chosen.

i.e. next X is Xk+1 = Xk+1, and next Y is Yk+1=Yk or Yk+1 depending on the sign of pk.

Let’s derive those recursive equations of the Bresenham’s procedure. To start with we use slope-intercept form of line equation. Having known the position (xk,yk) on the line, the next x position would be xk+1. From the slope-intercept form of line equation, for the next x position we have