Basic Line Drawing Algorithm

Basic Line Drawing Algorithm
by Amod Karve

A few days ago, I was wondering "How do those graphics wizards make such astonishing graphics, and I can't even make a simple line on the computer". I bought a book on graphics algorithms and set off to work. To my amazement I realized, that after all graphics was not such a tough cake. I also realized that behind hardcore graphics were involved some very basic concepts that we used to blindly ignore in our school days. After all, most of us ignore geometry in school.

After grasping the fundamentals behind simple line drawing, I thought why not share the knowledge with the world. The result is this article. By writing this article, I myself am ensuring that I have got a good grasp on the algorithm. OK ! Enough of this introduction work. Let's get down to some work.

What we require is to draw a line on the screen when we have been provided with the endpoints. Lets say, the endpoints provided to us are not integers but fractions ! (oh my god). What we have to do is to draw a line segment that has the two given points as its endpoints.

Before developing the algorithm let us first understand the problems we face. (Had there been no problems why would you be reading this ?). A line is a continuous object. However, the computer monitor (screen) consists of a matrix of pixels. So then, how do we represent the continous object on this discrete matrix. To understand the solution consider a staircase. (ah ! the name itself is enough). When a staircase is built, the requirement is to travel along a line. Now if we put up a slide from the starting point to endpoint can you imagine going up or down with ease. Of course NOT. To circumvent this problem, a staircase is built. It consists of discrete steps following which you reach the endpoint with ease. After moving some distance forward, you rise upwards and continue this sequence in discrete steps. The same approach has been used for drawing a line on the screen. So, keep in mind the wonderful staircase while we develop the mathematical approach to make a line.

Ok, so lets get down to some mathematics. A line can be represented by the equation:
y = m * x + b;

where 'y' and 'x' are the co-ordinates; 'm' is the slope i.e. a quantity which indicates how much 'y' increases when 'x' increases by one unit. 'b' is the intercept of line on 'y' axis (However we can safely ignore it for now).

So what's the trick behind the equation. Would you believe it, we already have the algorithm developed ! Pay close attention to the definition of 'm'. It states A quantity that indicates by how much 'y' changes when 'x' changes by one unit. So, instead of determining 'y' for every value of 'x' we will let 'x' have certain discrete values and determine 'y' for those values. Moreover since we have the quantity 'm'; we will increase 'x' by one and add 'm' to 'y' each time. This way we can easily plot the line. The only thing we are left with now, is the actual calculations.

Let us say we have two endpoints (xa,ya) and (xb,yb). Let us further assume that (xb-xa) is greater than (yb-ya) in magnitude and that (xa < xb). This means we will move from (xa) to the right towards (xb) finding 'y' at each point. The first thing however that we need to do is to find the slope 'm'. This can be done using the formulae:

m = (yb - ya) / (xb - xa)

Now we can follow the following algorithm to draw our line.

Let R represent the row and C the column
Set C = Round(xa)
Let F = Round(xb)
Let H = ya
Find the slope m
Set R = Round(H)
Plot the point at R,C on the screen
Increment C {C+1}
If C <= F continue else goto step (12)
Add m to H
Goto step (6)
STOP

See, the drawing of the line was so simple. We need to round off the coordinates because we have them as fractions and the screen coordinates are all integers. We round the numbers to find the coordinates nearest to the points. The above algorithm works fine for all those lines which have -1 < m < 1. For lines not falling into this category i.e. lines that have more rows than columns we just need to move row-wise instead of column-wise. So, if we just interchange the rows and columns in the algorithm above we can handle those lines too.

I hope the algorithm has made things quite clear. You must note here that the algorithm presented above is not an efficient way to draw lines but then it is an algorithm that is quite easy to grasp (I hope) than the efficient algorithms.

Disclaimer: The above written article is an original work by the author Amod Karve.

Discuss this article in the forums

Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General