Wu Anti-aliased Lines

Your average Breshenham line drawing algorithm draws lines quickly, but not that nicely. Your average integer line renderer produces nasty jaggedy lines that can only be drawn between integer coordinates. I saw a nice anti-aliased line drawer in one of Michael Abrash's books, and decided to improve it to handle non-integer coordinates.

A wu-line is not only better looking than a normal line, it also animates better. A normal line jumps from one position to the next in ugly, discrete jumps. A wu-line, however, drifts from one position to another with the greatest of ease.

So how does it work?

Well, lets think for a moment, what it actually means to be an anti-aliased line. What does a correct line look like? How thick is a line? What do the ends look like? A line is a one dimensional object, infinately long. it doesn't have any thickness. The ends of a line segment don't look like anything, they just end. Such a line cannot be drawn on a pixel based display.

For the purposes of computer graphics, it is usually assumed that a line segment is one pixel thick. This means it can be drawn. It also means that it's thin enough that it does not matter what the ends look like since they are smaller than a pixel, and can't be drawn.

Similar assumptions will also have to be made when designing the all new wu-line. Since this new algorithm will be able to handle non-integer end points, what should be done about lines that are less than one pixel long?

Assumptions

Assume that pixels are centered on their coordinates

Lines are one pixel thick

The shape of the end of the line is not important

It would also be nice if:

Two parallel line segments, joined end to end, are indistinguishable from a single, long line segment

The brightness/opacity of the line can be specified

What would the ultimate algorithm be?

The ultimate algorithm is quite easy to implement, but is too slow to be practical. It is also not really necessary, as it looks almost identical to the faster method. However I shall describe it just to give some grounding.

Imagine if you will, this zoomed in screen of pixels, with the line we would like to draw overlaid. The perfect line drawing algorithm would calculate the exact area of each pixel covered by the line, and increase that pixel's brightness accordingly.

Such an algorithm is easy to write, either by redrawing the relevant parts of the screen at a higher resolution, drawing the line over the top, and counting the pixels covered, or by calculating it presicely.

There is no need for such precision, however. We shall now procede to the next method.

A more sensible algorithm

This algorithm will draw pairs of pixels straddling the line. A main loop will draw pairs of pixels along the length of the line, and the pairs of pixels at the ends of the line will be handeled seperately.

Pixel Pairs

Consider again, a closeup of the screen. A nearly-horizontal line is to be drawn.

A nearly horizontal line crosses vertical columns of pixels. At each crossing, the X-coordinate is an integer, and the Y-coordinate is a non-integer.

Take an even closer look at a single crossing point:

At each crossing point, we shall consider the pair of pixels straddling the line. The intensities of the two pixels shall be selected so that they sum to exactly 1, and the centre of intensity lies exactly on the ideal line.

The intensity of the pixel above the line must be proportional to (1-a), and the intensity of the pixel below the line must be proportional to (1-b). I.E. the closer the line is to a pixel, the brighter it is.

Do this to every pair of pixels along the length of the line, and you nearly have a correctly antialiased line.

Drawing the end points

The last thing to do is draw the end points. These are tricky, and I still have not managed to get them right. If anyone knows, or figures out a better way to do then, please mail me. Anyway, here's the method I am currently using. It's not perfect, but very close. You will notice a small glitch when the line changes from being nearly vertical to being nearly horizontal, and vice versa. It really is only a small glitch, which you will only notice if the line is noving slowly past the 45 degree mark.

Take a really close look at one of the end points:

One of the vertices of the line is visible, and is denoted by a red spot. The blue spots represent the centres of the pixels. As you can see, the vertex is not centered on a pixel.

To calculate the correct brightness of the two pixels at the end of the line:

Project the line (backwards or forwards) to the nearest integer X-coordinate (p). Calculate the intensities of the pixel pair as if it were a normal part of the line. However, since the line only covers a small part of these pixels (i), the line will contribute to their brightness less. So multiply the intensities by i. Thus, as the whole line moves to the right, the distance i will get smaller and smaller, causing the pixel pair to fade out smoothly.

Special Cases

So, what should be done about lines that are less than one pixel long? Well, since they are far too small to represent accurately, you can do anything that looks resonable. In my own implementation, I scale the line so that it is one pixel long, and reduce it's brightness accordingly. So, very small lines appear dark, and, as they get longer, they get brighter, till they are one pixel long, at which point they are drawn normally.

Finally, some pseudocode

Here's a more concrete specification of the above algorithm in everyone's favourite language. For convenience and speed, I'll be using fixed point numbers here. They're particularly convenient in this situation. First, though, I'll have to define some functions:

Fixed Point functions required by WuLines: function trunc(x) return integer part of x end of function function frac(x) return fractional part of x end of function function invfrac(x) return 1 - (fractional part of x) end of function

The WuLine routine: procedure WuLine(fixpt x1, fixpt y1, fixpt x2, fixpt y2) variable declerations: fixpt variables: grad, xd, yd, length,xm,ym xgap, ygap, xend, yend, xf, yf brigheness1, brigheness2 integer variables: x, y, ix1, ix2, iy1, iy2 byte variables: c1,c2 code starts here: Width and Height of the line xd = (x2-x1) yd = (y2-y1) if abs(xd) > abs(yd) then check line gradient horizontal(ish) lines if x1 > x2 then if line is back to front swap x1 and x2 then swap it round swap y1 and y2 xd = (x2-x1) and recalc xd & yd yd = (y2-y1) end if grad = yd/xd gradient of the line End Point 1 ----------- xend = trunc(x1+.5) find nearest integer X-coordinate yend = y1 + grad*(xend-x1) and corresponding Y value xgap = invfrac(x1+.5) distance i ix1 = int(xend) calc screen coordinates iy1 = int(yend) brightness1 = invfrac(yend) * xgap calc the intensity of the other brightness2 = frac(yend) * xgap end point pixel pair. c1 = byte(brightness1 * MaxPixelValue) calc pixel values c2 = byte(brightness2 * MaxPixelValue) DrawPixel(ix1,iy1), c1 draw the pair of pixels DrawPixel(ix1,iy1+1), c2 yf = yend+grad calc first Y-intersection for main loop End Point 2 ----------- xend = trunc(x2+.5) find nearest integer X-coordinate yend = y2 + grad*(xend-x2) and corresponding Y value xgap = invfrac(x2-.5) distance i ix2 = int(xend) calc screen coordinates iy2 = int(yend) brightness1 = invfrac(yend) * xgap calc the intensity of the first brightness2 = frac(yend) * xgap end point pixel pair. c1 = byte(brightness1 * MaxPixelValue) calc pixel values c2 = byte(brightness2 * MaxPixelValue) DrawPixel(ix2,iy2), c1 draw the pair of pixels DrawPixel(ix2,iy2+1), c2 MAIN LOOP --------- Loop x from (ix1+1) to (ix2-1) main loop brightness1 = invfrac(yf) calc pixel brightnesses brightness2 = frac(yf) c1 = byte(brightness1 * MaxPixelValue) calc pixel values c2 = byte(brightness2 * MaxPixelValue) DrawPixel(x,int(yf)), c1 draw the pair of pixels DrawPixel(x,int(yf)+1), c2 yf = yf + grad update the y-coordinate end of x loop end of loop else vertical(ish) lines handle the vertical(ish) lines in the same way as the horizontal(ish) ones but swap the roles of X and Y end if end of procedure

And Finally

To prove it really works, and looks fantastic, here's a demo.

The program draws a model of a Newton's Cradle at two resolutions to show that the Wu Lines can be used to draw objects at quite small, and still look OK. You can also see how smoothly they move.