Anti-Aliased Line Drawing

First, let's start with an example to show why we want to use anti-aliased lines. The lines on the left are drawn with something like Bresenham's line algorithm. The lines on the right are drawn with an extended form of Bresenham's which anti-aliases. They are shown both at normal size and 4x zoom. Which do you think looks better?

bresenhams drawn line bresenhams drawn line at 4x zoom antialiased line at 4x zoom antialiased line

For MP4, you need to implement the one on the right. This tape will self-destruct in five seconds. ...four... ...three...

Just take me to the algorithm! I don't care if I understand it! Or scroll on for an explanation.

Theory Behind Anti-Aliasing

Figure A: Ideal Unit-width Line on pixel grid

There are several models one can use to draw anti-aliased lines, with differing quality results. Let's say I want to draw a line with a thickness of 1, from (1,1) to (8,4). Also, the ends should be rectangular, rather than capped with a circle. My "ideal" line would look something like Figure A.

But when I want to display that on a screen, and my units above are individual pixels, I simply cannot draw that. Although Pixels are arguably circles of light, because they go in a rectangular pattern, it is easiest to represent them as squares. (It also makes most of the math nicer, if you ask me.)

Rasterization

Figure B: y=round(f(x)) Approximation

So what should I do? The first way I can think of to do this follows the pseudocode based on the idea y=f(x):

And would result in something like Figure B.

Now, this algorithm has several downfalls:

  1. There is a multiplication and a divide for every pixel. Since they are integer mul/divs, they cannot be precalculated to save one of them.
  2. There is also a multiply when converting from (x,y) to address.
  3. This line is severely aliased. It's jaggy. It looks like a shallow staircase. (These all mean the same thing.)

What can I do about it?

There are two main categories of problems we want to address now: Speed and Appearance. First let's look at a type of line drawing algorithm called a Digital Differential Analyzer (DDA), and then we'll actually get on to how we anti-alias a line.

Digital Differential Analyzer

It's easy to come up with:

yi = f(xi)
yi = m * (xi-x0) + y0
yi = (y1-y0) * (xi-x0) / (x1-x0) + y0

You can greatly improve this algorithm, however, by realizing that you draw these lines sequentially:

yi+1 = m * xi+1+B
yi+1 = m * (xi + Δx) + B
yi+1 = yi + m * Δx

Now all you need to do is keep track of yi, and round to the nearest integer when you want to draw. So now we've got an initial calculation of m = (y1-y0) / (x1-x0), stored in some non-integer format, which we can then just add to our y for each subsequent pixel.

Bresenham's Line Algorithm

Bresenham found a way to turn the above non-integer calculations into entirely integer calculations. By tracking an integer y and an integer d (distance from the ideal line), his algorithm allows you to draw a line using only integer math. For more information on actually implementing Bresenham's Line Algorithm, see Lecture 19.

The other thing you should notice about these two algorithms is this: since they iterate across the line (think of the across x in the above example), adding to the drawn Y if we've crossed some threshold, we don't really have to store just X and Y anymore. We can store an address, to which we add 1 whenever X increases, and add WIDTH whenever Y increases. This eliminates the last multiply-per-pixel.

Okay. So the DDA and, better yet, Bresenham's Line Algorithm have really sped up our line drawing. That's problem 1. Now we can draw an ugly line really quickly. So onward to problem 2--we want our lines to look better.

Anti-Aliasing

If you look closely back at the Figure B, you'll probably start to notice a few more problems. For instance:

How can we know how much of a given pixel the line will cover? Well, we could go through a whole bunch of geometry, drawing the perpendicular from the center of the pixel to the edge of the line, and then derive some easy ways to find this.

Figure C: Pixel Color by Coverage or Alpha

But this is ECE291, so we'll just jump to the answer.

Remember how Bresenham's Line Algorithm stored d, the distance from the line to the center of the pixel, multiplied by some constant to make it usable? Well, we're about to use a variant of that to calculate distance. Once we're done, we'll get something that looks a lot like Figure C.

One word of caution: remember how I said pixels could be considered circles of light? That's going to play an important role in our calculation of coverage as a function of distance. Specifically, we want to have a relationship that looks like: coverage = k / distance2.

Why? To be honest, I haven't worked out the math to be completely sure. The Gupta-Sproull algorithm, which is the pseudocode I based this on, does a table lookup on distance to find coverage. My source didn't have the table. So I played with it, and found that using the inverse of distance squared result looks much better than the linear result. Feel free to experiment a little in your code and see what you like best. If you use something other than my values, though, know what they are and be prepared to defend them.

The Actual Algorithm

The Gupta-Sproull algorithm looks a lot like Bresenham's, with some additional fun thrown in. Like Bresenham's, we do an integer DDA, with error function d. But then we use d as part of the distance calculation.

Here's the pseudocode, shamelessly copied and slightly modified from Computer Graphics: Principles and Practice, Second Edition in C. It's on page 141 in my edition (section 3.18), if you happen to have the book and prefer a physical copy. Just be careful to note the changes!


void AALine(int x0, int y0, int x1, int y1)
{
    int addr = (y0*640+x0)*4;
    int dx = x1-x0;
    int dy = y1-y0;
    /* By switching to (u,v), we combine all eight octants */
    if (abs(dx) > abs(dy))
    {
	/* Note: If this were actual C, these integers would be lost
	 * at the closing brace.  That's not what I mean to do.  Do what
	 * I mean. */
	int du = abs(dx);
	int dv = abs(dy);
	int u = x1;
	int v = y1;
	int uincr = 4;
	int vincr = 640*4;
	if (dx < 0) uincr = -uincr;
	if (dy < 0) vincr = -vincr;
    }
    else
    {
	int du = abs(dy);
	int dv = abs(dx);
	int u = y1;
	int v = x1;
	int uincr = 640*4;
	int vincr = 4;
	if (dy < 0) uincr = -uincr;
	if (dx < 0) vincr = -vincr;
    }
    int uend = u + 2 * du;
    int d = (2 * dv) - du;	    /* Initial value as in Bresenham's */
    int incrS = 2 * dv;	/* Δd for straight increments */
    int incrD = 2 * (dv - du);	/* Δd for diagonal increments */
    int twovdu = 0;	/* Numerator of distance; starts at 0 */
    double invD = 1.0 / (2.0*sqrt(du*du + dv*dv));   /* Precomputed inverse denominator */
    double invD2du = 2.0 * (du*invD);   /* Precomputed constant */
    do
    {
	/* Note: this pseudocode doesn't ensure that the address is
	 * valid, or that it even represents a pixel on the same side of
	 * the screen as the adjacent pixel */
	DrawPixelD(addr, twovdu*invD);
	DrawPixelD(addr + vincr, invD2du - twovdu*invD);
	DrawPixelD(addr - vincr, invD2du + twovdu*invD);

	if (d < 0)
	{
	    /* choose straight (u direction) */
	    twovdu = d + du;
	    d = d + incrS;
	}
	else
	{
	    /* choose diagonal (u+v direction) */
	    twovdu = d - du;
	    d = d + incrD;
	    v = v+1;
	    addr = addr + vincr;
	}
	u = u+1;
	addr = addr+uincr;
    } while (u < uend);
}

So, what does this do? Well, in addition to the normal Bresenham's style algorithm, it calls DrawPixelD three times - one for the pixel Bresenham's would draw, and then for one each on either side (y1 for a line in x). These three pixels are all the pixels the line may cover.

Figure D: The Final Line

It passes DrawPixelD another parameter, which we shall call distance. To find distance, it sets twovdu to ddu, and multiplies it by the precomputed constant invD. Then, depending on which pixel we need the distance for, it either passes it verbatim, or takes invD2du, another precomputed constant, and either adds or subtracts it from this constant. Making a long process short, DrawPixelD sees distances ranging from 0.0 to 1.5.

And if you've been a good student and just generally gotten very lucky by getting everything to work, You'll have something that looks like a zoomed out Figure D.

DrawPixelD

Remember a few paragraphs back when I said something about considering the inverse of distance squared instead of just a linear distance? Here's where I explain how you are to do that.

DrawPixelD gets passed a distance. Since there isn't any convenient way to pass double-precision floating point numbers (qwords) on the parameter stack, I suggest passing them in on the FPU stack, as the top element. You can break it down into two dwords on the stack, but it's not fun. (It also requires you write both functions at once, as libDrawPixelD() expects to find it in st0, and correspondingly libAALine() puts it there. Yes, this is not standard C procedure calling.)

This distance ranges from 0.0 to 1.5, thanks to some nice geometrical math (I'm willing to try to explain the full reasoning to you if you catch me with the book). At 0.0, the line is fully centered around the pixel. at 1.5 it's fully centered around the far pixel. But what about in-between? What we want to do is somehow find an alpha such that:

α = f(distance)

So what's our function?

Simple. First we normalize the 0.0--1.5 to 0.0--1.0 (the normal range on alpha values). Then we subtract it from 1 to reverse the meaning to our normal meaning of alpha. (Normally an alpha of 1.0 means fully opaque, while an alpha of 0.0 means fully transparent. Our normalized distance was the reverse of that.) Next, we apply the magic step of squaring this value, which lessens almost all of the possible values (just consider the graph of x2 from 0 to 1). Finally we multiply by 255 to make it an integer, and we've got our alpha.

To summarize that paragraph as an equation:

α = 255 * (1 - (distance * 2/3))2

Which is a number from 0 to 255. Apply this to each of your channels just like you did in AlphaBlit (only don't use MMX!) and plot your pixel. Don't forget the first parameter, addr, was the address in the VideoBuf selector.

No MMX in DrawPixelD

Why not use MMX? Due to the design choices of Intel, it's extremely slow to switch between floating point and MMX instructions. Since we need floating point for most of this algorithm, it's faster to composite the four channels individually than to switch into MMX, use MMX operations on all four channels at once, and switch back to floating point.

And we've only got one pixel anyway, not two.