Over the last few days I’ve let my progress on this project run ahead of my documentation, so let’s try to catch up. Tonight, I’d like to briefly discuss how to draw lines – and why you might not have to care.
So far, my approach has been to not care – I’m using the AmigaOS graphics.library functions Move() and Draw() to render the actual lines of my shapes. There’s a good reason for that: I’m lazy. Besides, graphics.library is probably well-optimized, and it can take advantage of some of that snazzy Amiga custom hardware.
The Blitter, like the Copper I talked about last time, is one of the Amiga’s graphics coprocessors, and it’s part of the Fat Agnus chip. Basically, a blitter just moves data from one part of memory to another. It’s good for copying stuff into a bitmap, or moving an image around. The Amiga’s Blitter also has some special functions – it can draw lines into bitmap memory directly, and even draw filled polygons (we’ll get to that in another entry).
On the stock Amiga, the Blitter can do all this much more quickly than the CPU can. For one thing, it doesn’t have to keep fetching instructions to run – you just set up its registers and let it go, and it’ll move data around as quickly as possible.
Additionally, blits can take place asynchronously while the CPU is doing something else. It’s not exactly multiprocessing, but it’s definitely an advantage. The graphics.library functions don’t give me complete control over when to wait for the Blitter and when not to, but for example I can use the Blitter to clear the framebuffer while the CPU is computing the transformation matrices to use while drawing the next frame.
The take-home here is that the graphics.library functions for drawing lines are easy to use, fast, and actually work. You might do better if you’re writing your own assembly routines that set up the Blitter directly, but I’m not getting into that at this stage.
However, I was kind of interested in writing my own line-drawing routine, just to see how a software solution compared speed-wise. The best known algorithm for drawing lines (at least, for drawing lines without antialiasing) is Bresenham’s algorithm. In this algorithm, you iterate from the start of the line to the end of the line in the positive-x direction, drawing a pixel at each x coordinate and using a magic “error” value to figure out when to increment the y coordinate. For “steep” lines, you can do the same basic thing, but swap the roles of x and y. An important part of the algorithm’s performance is that its main loop only uses integer addition and subtraction.
(Okay, the error value isn’t actually magic – it increments by Δx and decrements by Δy to basically count out the slope of the line – but it is pretty clever. You can read the details over at Wikipedia.)
My first attempt at implementing a line-drawing algorithm was so slow that I didn’t even want to measure it, and for good reason. Calculating the x and y coordinates was fast enough, but figuring out which bit of memory to change to plot those values took way too much time – and it required an expensive integer division. The solution was to figure out the memory location for the first point in the line – which byte of the bitplane, and which bit of that byte – and then incrementally change those values as I drew the line. So if the first pixel was at bit 1 of byte 0x0000ccc5, the pixel to its right was bit 0, and one to the right of that was bit 7 of byte 0x0000ccc6. Going down or up meant adding or subtracting the number of bytes in one row of the bitmap.
Once I did that, I was back to using integer addition and subtraction for all the operations. There were, of course, a few glitches along the way – you can see a couple of them at the top of this post. One thing that messes with my head is that bytes are arranged from left to right in each row of the bitmap, but the bits of each byte run from right to left. That right-hand picture shows me getting things backwards.
So how fast did my heavily-optimized software line drawing routine go? I am pleased to report that it took about 2.75 times as long as the Blitter to do the same amount of work. It was a fun exercise, but I’ve reverted back to using the graphics.library routines for real work – and we’ll get into more of that tomorrow.