Alans Blog

Internet, Technik, Software, Elbmarsch.

How to Include Clipping in Bresenham's Line generation algorithm

Dieser Artikel wird zunächst auf Englisch veröffentlicht, eine deutschsprachige Übersetzung folgt später.

One of the best-known algorithms to draw a line on a pixel display is the Bresenham algorithm. It is extremely fast (and extremely simple) and can easily be integrated into simple hardware because it doesn't need floating point calculations, divisions or multiplications.

I will not explain the details of this algorithm here, if you are interested, the (German) Wikipedia article is a good start. The English Wikipedia article is unfortunately rather poor.

I stumbled across a problem with this algorithm when I started programming on the Commodore Amiga again after more than 20 years. In fact, I wanted to draw lines and wanted to clip them at the display border to avoid writing into memory which is used for other purposes (mainly the code). I thought, someone should have solved this problem after almost 30 years of Amiga, but - NO?!

I stumbled across three articles on the net. One is about subpixel-correct line drawing (and polygon filling) on the Amiga, but it didn't go too much into detail, especially because it didn't consider clipping. I also found a very interesting discussion on which contained some hints, but unfortunately no solution. Additionally, I found a scientific article from 1995 which combined Clipping with the Bresenham algorithm, but this article is not publicly available so I could not read it. All other links I found were not helpful. But those three links seemed to point in the right direction: it should be possible to draw correctly clipped lines on the Amiga (or on any other hardware or software based on the Bresenham algorithm).

Taking a closer look on the registers used for line drawing on the Amiga, more specifically the Blitter in the custom chip "Agnus", made it perfectly clear to me: the error term is placed in the register APTR (details can be found in the Amiga Hardware Reference Manual (AHRM)). The formula for APTR is: 4 * dY - 2 * dX, the other values which must be provided are AMOD = 4 * (dY - dX) and BMOD = 4 * dY. Another basic rule for the Blitter is: dX >= dY, and both dX and dY values must be positive (line drawing in the other octants is performed by selecting the octant in another register, but this is described in the AHRM above). This results in AMOD always being <=0 and BMOD being >= 0 which is important to notice for the next steps.

The Amiga Blitter plots a line using the Bresenham algorithm, and obviously it does so by adding a specific value to APTR after each step in the long x-direction (dX > dY). As long as APTR is <0, the Blitter takes a step "right" and then adds BMOD (thus increasing or not changing APTR, because BMOD >=0). If APTR becomes >=0 in the previous calculation step, the Blitter takes a step "up and right" instead of right and then adds AMOD (which is <=0) to APTR, decreasing APTR again. This is repeated until the end of the line is reached (dX+1 steps).

If we now want to write correct values into the Blitter registers for an x-position which is not the start position, we only need to calculate the APTR value for this x-position. To make a long story short, the formula is

APTR = (2 * dX + 4 * x * dY) modulo (abs(4 * dY - 4 * dX) + abs(4 * dY)) + (4 * dY - 4 * dX)

In this formula, 4 * dY - 4 * dX happens to be the value of APTR, and 4 * dY is the value of BPTR, and we have to calculate them anyway for the line function of the Blitter, so the short form of the formula is (remember: AMOD <=0, BMOD >=0):

APTR = (2 * dX + 4 * x * dY) modulo (BMOD - AMOD) + AMOD

For clipping, we also need the y-position of the clip start, and, big surprise, this is the truncated value of the result of the division for which we need to calculate the modulo above. So it makes sense to use the DIVU function of the 68000 processor of the Amiga, which provides us with the truncated value and the modulo in one step, even if it is a very costly (slow) function. Calculation of only the modulo could have been done quicker, but we need the full result anyway.


To calculate the values of APTR and y-position for clipping a line at position x (0 <= x <= dX), we can use the formulas

APTR = (2 * dX + 4 * x * dY) modulo (BMOD - AMOD) + AMOD

for the APTR, and

y = (2 * dX + 4 * x * dY) DIV (BMOD - AMOD)

for the y-position.

Working code may follow later. I declare these formulas for Open Source acording to the BSD 3-clause license or the Creative Commons license CC BY-SA 4.0, whichever suits your purpose.