Draw Routine with Bresenham Algorithms

Draw Routine with Bresenham Algorithms

Written by: Mikezt
This article is dedicated to baze/3sc.

One of the most basic graphic routines is a line draw. When you try to write a draw routine you may find it a bit complicated. Don't worry, here's one way of doing it.

Bresenham algorithms have an advantage over other methods because they work with integer numbers. So they can be easily written in machine code. Before we start, get ready for some mathematical expressions. I'll write lower indexes in [].

Abscissa is defined with two points $(x_1, y_1)$ and $(x_2, y_2)$ and can be written as the expression:

$$y = k \cdot x + q$$

where $k$ is the direction and $q$ is the shift on the $y$ axis.

Direction $k$ indicates inclination of the line and divides the coordinate system into eight parts (see pic. 1). We get a situation where $k$ is positive and less than 1 ($0 < k < 1$). Let's presume that point $(x[i], y[i])$ was drawn. For each pixel we have to compute the differences from the ideal course of the line (pic. 2).

Difference of both possible points are:

$$D_1 = y - y[i] = k \cdot (x[i] + 1) + q - y[i]$$
$$D_2 = y[i] + 1 - y = y[i] + 1 - k \cdot (x[i] + 1) - q$$

Difference of these two values is equal to:

$$D = D_1 - D_2 = 2 \cdot k \cdot (x[i] + 1) - 2 \cdot y[i] + 2 \cdot q - 1$$

Along this difference we can choose the right point. It's clear that the factor of decision is its sign. A negative value will select the point $(x[i] + 1, y[i] + 1)$, and a positive one will select $(x[i] + 1, y[i])$. The disadvantage is the real character of the values. We can remove this disadvantage by multiplying the difference expression by $(x_2 - x_1)$, and we get the expression which is called the decision factor:

$$d[i] = D \cdot (x_2 - x_1) = 2 \cdot (y_2 - y_1) \cdot (x[i] + 1) - 2 \cdot y[i] \cdot (x_2 - x_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$$

and after a slight adjustment:

$$d[i] = 2 \cdot (y_2 - y_1) \cdot x[i] - 2 \cdot y[i] \cdot (x_2 - x_1) + 2 \cdot (y_2 - y_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$$

Expression $2 \cdot (y_2 - y_1) + (2 \cdot q - 1) \cdot (x_2 - x_1)$ is constant and we indicate it with $c$, so:

$$d[i] = 2 \cdot (y_2 - y_1) \cdot x[i] - 2 \cdot y[i] \cdot (x_2 - x_1) + c$$

Now this is an integer value, but it's quite complicated. If we express the decision for the next point, we can write a recursive relation. Here is the decision for the next point:

$$d[i+1] = 2 \cdot (y_2 - y_1) \cdot (x[i] + 1) - 2 \cdot y[i+1] \cdot (x_2 - x_1) + c$$

After subtracting these two decisions, we can express the decision value in a recursive form:

$$d[i+1] = d[i] + 2 \cdot (y_2 - y_1) - 2 \cdot (x_2 - x_1) \cdot (y[i+1] - y[i])$$

Expression $(y[i+1] - y[i])$ can only store values 0 and 1, and we can write modified expressions to compute the decision:

• if $d[i] < 0 \implies d[i+1] = d[i] + 2 \cdot (y_2 - y_1)$
• if $d[i] \ge 0 \implies d[i+1] = d[i] + 2 \cdot (y_2 - y_1) - 2 \cdot (x_2 - x_1)$

Last thing you need to know is the decision for the first step, and here it is:

$$d[1] = 2 \cdot (y_2 - y_1) - (x_2 - x_1)$$

So all you must do is check the decision for its sign; if it's negative, move the $y$ coordinate, compute the decision for the next step, and test if you've drawn the last point. If not, do it all again. For directions other than $0 < k < 1$, you must change the equations by deriving them yourself or you can use the next few pictures. I used them to find the right direction at the starting point of my draw routine.

A simple change to expression $(x_2 - x_1)$ by the first expression in the last compare and $(y_2 - y_1)$ by the second expression in the last compare (I think it's clear :-) ...

Some tips for speeding up your routine:

• Test if $x_2 > x_1$ (or any other one and choose variants with this comparison), and if it's true then there's no swap needed at the start and end points.
• Decision equations should be divided by 4 (two rotations) so you can store it in an 8-bit register, with no precision lost!

Uf, that's all. My routine is available (I hope) on the HighTech project (http://hightech.da.ru). I hope you understand what I've tried to say here. If not, feel free to write to me. Bye!

mike/zt/ctl
jurica@sknet.sk