Internet, Technik, Software, Elbmarsch.
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 virtualdub.org 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.
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.