1.3.2. Line Rasterisation

As you know, on a paper sheet, we are able to draw easily a straight line between two points located anywhere on a paper.
On raster displays such as a screen, however, we can draw lines only between grid points. The line must be approximated by intensifying the grid-point pixels lying on it or nearest to it. (FOLEY et al. 1996)

Midpoint Line Algorithm

A simple algorithm for the line approximation may look like this (programmed in C):

Comments on the algorithm

Variables:

• dx defines the difference between the x-coordinates of the two points;
• dy defines the difference between the y-coordinates of the two points;
• m defines the slope of the line;
• "double" is a floating-point number which is a datatype. Double stands for double precision.
• "int" stands for integer which is also a datatype. Integers consist of positive natural numbers (1, 2, 3, ...).

For-Loop::

A for loop is a control structure which allows code to be executed iteratively. For loops are typically used when the number of iterations is known before entering the loop. (Wikipedia - The Free Encyclopedia)

• First Step: Set pixel x=x0, y=y0;
• Second Step: Set pixel x=x0+1, y=y0+m and round y;
• Third Step: Set pixel x=x+1, y=y+m and round y;
• ...

The following animation shows you the different steps of the algorithm in pictures. Have a look!

In the presented algorithm the x-coordinates of the missed pixels are taken as fixed integers (1, 2, 3, etc.). The y-coordinates have to be adapted by rounding them, as you saw it in the above example.
Naturally we can change the case so that the y-coordinates are fixed and the x-coordinates are rounded. The result looks like this:

As you notice, there are less pixels defining the line and the gaps between the pixels are larger. Therefore this solution is suboptimal.

But what happens if the slope of the line is greater than one? As you can see in the following examples, the results change:

x-axis

y-axis

We conclude that the decision which algorithm (e.g. x is set as fix or y is set as fix) has to be applied for a line rasterisation depends on the slope value of the line.

Since the introduced algorithm needs a lot of computing for complex applications, it is better to use a more efficient algorithm such as the "Algorithm by Bresenham". If you are interested in more information about this algorithm, have a look at (FOLEY et al. 1996, p. 74-78)