Wu Anti-aliased Lines

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.