Drawing lines
Contents
Drawing lines#
One of the fundamental tasks in computer graphics is the rendering of a straight line on a display. Consider the diagram in Fig. 96 showing the rasterisation of the straight line joining the two points with pixel co-ordinates \((2, 2)\) and \((11,7)\). The pixels that are closest to the line are shaded to create a rasterised approximation of the idealised image. This is a simple task for a human since we are able to view the idealised image and determine which pixels need to be shaded. Algorithms are required to determine which pixels to illuminate in order to rasterise straight lines
Fig. 96 Rasterising a straight line#
Bresenham’s algorithm#
Fig. 97 Jack Elton Bresenham#
Bresenham’s algorithm developed by American computer scientist Jack Bresenham [1965] is a line drawing algorithm that uses integer only arithmetic and offers a vast improvement over other methods in terms of computational efficiency. Consider the Cartesian equation of a straight line joining two points with co-ordinates \((x_0, y_0)\) and \((x_1, y_1)\)
where \((x,y)\) are the co-ordinates of a point on the line and \(c\) is the point of interception between the line and the \(y\)-axis. Let \(\Delta y = y_1 - y_0\) and \(\Delta x = x_1 - x_0\) into equation (34) and rearranging gives
Let \(f(x,y) = x \Delta y - y \Delta x + c \Delta x\) then the sign of \(f(x,y)\) tells us whether the pixel at \((x,y)\) is above or below the line such that
To simplify the derivation we are going to assume that the two end points of the line at \((x_0,y_0)\) and \((x_1,y_1)\) are such that \(x_0 < x_1\) and \(y_0 < y_1\) so the line is drawn from left-to-right and top-to-bottom (remember that the \(y\)-axis increases as we move down the raster). If the pixel at \((x_i,y_i)\) has been plotted we move one pixel to the right and we a choice between two candidate pixels at \((x_i+1,y_i)\) and \((x_i+1,y_i+1)\). To decide between these two we calculate the value of \(f(x,y)\) at the midpoint between these two pixels and use its sign. Let \(d = f(x_i+1,y_i+\frac{1}{2})\) be a decision variable then
Fig. 98 The sign of the decision variable \(d\) determines which pixel is closest to the line.#
So the sign of \(d\) will tell use which of the candidate nodes to choose (Fig. 98). When \(d \leq 0\) the pixel at \((x_i+1,y_i)\) is closer to the line and if \(d > 0\) the pixel at \((x_i+1,y_i+1)\) is closest. The value of \(d\) will change as we proceed along the line, let \(\Delta d = d_{i+1} - d_i\) be the change in \(d\) from one pixel to the next then we can calculate \(d = d + \Delta d\) using
The value of \(\Delta d\) depends on which of the candidate nodes we have chosen. If \(d \leq 0\) the midpoint is beneath the line and we choose the upper pixel \((x_i+1,y_i)\) so \(y_{i+1} = y_i\) and
Otherwise if \(d > 0\) the midpoint is above the line and we choose the lower pixel \((x_i+1,y_i+1)\) so \(y_{i+1} = y_i + 1\) and
So we have way of choosing between the two candidate pixels. All we now need to do is determine the initial value of \(d\). The first endpoint \((x_0,y_0)\) is plotted so the two candidate pixels at \((x_0+1,y_0)\) and \((x_0+1,y_0+1)\) so we calculate the initial value of \(d\) using
The expression for calculating includes a floating point number \(1/2\). Floating point numbers have a much larger computational cost than integer numbers so it would be beneficial if we can only use integer numbers. Since we are only concerned with the sign of \(d\) and not its value we can multiply the expressions for calculating the initial value of \(d\) and \(\Delta d\) by 2 to give
The basic Bresenham’s algorithm is written using pseudocode in Algorithm 7.
Algorithm 7 (Bresenham’s algorithm)
Inputs A raster array \(R\), pixel co-ordinates of the endpoints of a straight line \((x_0, y_0)\) and \((x_1, y_1)\) and the colour of the line defined by the RBG triplet \(colour\).
Output A raster array \(R\).
\(x \gets x_0\) and \(y \gets y_0\)
\(\Delta x \gets x_1 - x_0\) and \(\Delta y \gets y_1 - y_0\)
\(d \gets 2 \Delta y - \Delta x\)
While true do
\(R(x,y) \gets colour\)
If \(x = x_1\) and \(y = y_1\) then
Terminate algorithm and return \(R\)
If \(d \leq 0\) then
\(d \gets d + 2 \Delta y\)
Else
\(y \gets y + 1\)
\(d \gets d + 2 \Delta y - 2 \Delta x\)
\(x \gets x + 1\)
Example 38
Use the basic Bresenham’s algorithm to determine the co-ordinates of the pixels on the straight line joining the two pixels with co-ordinates \((2, 2)\) and \((7, 5)\).
Solution
First we calculate \(\Delta x = 7 - 2 = 5\), \(\Delta y = 5 - 2 = 3\), \(d = 2(3) - 5 = 1\).
Stepping through the pixels:
\(x\) |
\(y\) |
\(d\) |
decision |
|---|---|---|---|
\(2\) |
\(2\) |
\(1\) |
update \(y\) |
\(3\) |
\(3\) |
\(1 + 2(3) - 2(5) = -3\) |
|
\(4\) |
\(3\) |
\(-3 + 2(3) = 3\) |
update \(y\) |
\(5\) |
\(4\) |
\(3 + 2(3) - 2(5) = -1\) |
|
\(6\) |
\(4\) |
\(-1 + 2(3) = 5\) |
update \(y\) |
\(7\) |
\(5\) |
terminate algorithm |
So we plot pixels at \((2, 2)\), \((3, 3)\), \((4, 3)\), \((5, 4)\), \((6, 4)\) and \((7, 5)\) are plotted.
Modified Bresenham’s algorithm#
In deriving the algorithm presented in Algorithm 7 we made the assumption that the line was drawn from left-to-right and top-to-bottom. To modify the algorithm so that it can draw lines in any direction we repeat the derivation considering steps in the \(x\) and \(y\) directions separately. This results in the modified Bresenham’s algorithm shown in Algorithm 8.
Algorithm 8 (Modified Bresenham’s algorithm)
Inputs A raster array \(R\), pixel co-ordinates of the endpoints of a straight line \((x, y)\) and \((x_1, y_1)\) and the colour of the line defined by the RBG triplet \(colour\).
Output A raster array \(R\).
\(x \gets x_0\) and \(y \gets y_0\)
\(\Delta x \gets |x_1 - x_0|\) and \(\Delta y \gets |y_1 - y_0|\)
\(d \gets 2 \Delta x - 2 \Delta y\)
\(x_{step} \gets 1\) and \(y_{step} \gets 1\)
If \(x_0 > x_1\) then
\(x_{step} \gets -1\)
If \(y_0 > y_1\) then
\(y_{step} \gets -1\)
While true do
\(R(x,y) \gets colour\)
If \(x = x_1\) and \(y = y_1\) then
Terminate algorithm and return \(R\)
\(\Delta d \gets 0\)
If \(d \geq -\Delta y\)
\(x \gets x + x_{step}\)
\(\Delta d = \Delta d - 2 \Delta y\)
If \(d \leq \Delta x\)
\(y \gets y + y_{step}\)
\(\Delta d = \Delta d + 2 \Delta x\)
\(d \gets d + \Delta d\)
Example 39
Use Bresenham’s algorithm for drawing lines in any direction to determine the co-ordinates of the pixels on the lines joining the following points:
(i) \((1,1)\) and \((5,7)\);
Solution
First calculate \(\Delta x = |5 - 1| = 4\), \(\Delta y = |7 - 1| = 6\), \(x_{step}=1\), \(y_{step}=1\) and \(d=2(4) - 2(6)= -4\). So we update \(x\) if \(d \geq -6\) and update \(y\) if \(d \leq 4\).
Stepping through the algorithm:
\(x\) |
\(y\) |
\(d\) |
decision |
|---|---|---|---|
\(1\) |
\(1\) |
\(-4\) |
update \(x\) and \(y\) |
\(2\) |
\(2\) |
\(-4-2(6)+2(4)=-8\) |
only update \(y\) |
\(2\) |
\(3\) |
\(-8+2(4)=0\) |
update \(x\) and \(y\) |
\(3\) |
\(4\) |
\(0-2(6)+2(4)=-4\) |
update \(x\) and \(y\) |
\(4\) |
\(5\) |
\(-4-2(6)+2(4)=-8\) |
only update \(y\) |
\(4\) |
\(6\) |
\(-8+2(4)=0\) |
update \(x\) and \(y\) |
\(5\) |
\(7\) |
terminate algorithm |
So we plot pixels at \((1,1)\), \((2,2)\), \((2,3)\), \((3,4)\), \((4,5)\), \((4,6)\) and \((5,7)\).
(ii) \((7,2)\) and \((3,5)\).
Solution
First calculate \(\Delta x = |3 - 7| = 4\), \(\Delta y = |5 - 2| = 3\), \(x_{step}=-1\), \(y_{step}=1\) and \(d = 2(4) - 2(3) = 2\). So we update \(x\) if \(d \geq -3\) and update \(y\) if \(d \leq 4\).
Stepping through the algorithm:
\(x\) |
\(y\) |
\(d\) |
decision |
|---|---|---|---|
\(7\) |
\(2\) |
\(2\) |
update \(x\) and \(y\) |
\(6\) |
\(3\) |
\(2-2(3)+2(2)=4\) |
update \(x\) and \(y\) |
\(5\) |
\(4\) |
\(4-2(3)+2(2)=6\) |
only update \(x\) |
\(4\) |
\(4\) |
\(6-2(3)=0\) |
update \(x\) and \(y\) |
\(3\) |
\(5\) |
\(0-2(3)+2(3)=2\) |
terminate algorithm |
So we plot pixels at \((7,2)\), \((6,3)\), \((5,4)\), \((4,4)\) and \((3,5)\).
