Xiaolin Wu's Line Algorithm Article Index for
Xiaolin 		Website Links For
Line 		 

Information About

Xiaolin Wu's Line Algorithm
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Bresenham's Algorithm draws lines extremely quickly, but it cannot perform anti-aliasing. In addition, it cannot handle the case where the line endpoints do not lie exactly on integer points of the pixel grid. A naïve approach to anti-aliasing the line would take an extremely long time, but Wu's algorithm is quite fast (It is still slower than Bresenham's, though). The basis of the algorithm is to draw pairs of pixels straddling the line, coloured according to proximity. Pixels at the line ends are handled separately. Lines less than one pixel long should be handled as a special case.

Here is Pseudocode for the nearly-horizontal case (\Delta x > \Delta y). To extend the algorithm to work for all lines, swap the x and y coordinates when near-vertical lines appear (for reference, see Bresenham's Line Algorithm ).


function plot(x, y, c) '''is'''
plot the pixel at (x, y) with brightness c (where 0 ≤ c ≤ 1)

function ipart(x) '''is'''
return ''integer part of x''

function round(x) '''is'''
return ipart(x + 0.5)

function fpart(x) '''is'''
return ''fractional part of x''

function rfpart(x) '''is'''
return 1 - fpart(x)

function drawLine(x1,y1,x2,y2) '''is'''
if x2 < x1
swap x1, x2
swap y1, y2
end if

dx = x2 - x1
dy = y2 - y1
gradient = dy / dx

''// handle first endpoint''
xend = round(x1)
  • (xend - x1)

    • xgap = rfpart(x1 + 0.5)

xpxl1 = xend '' // this will be used in the main loop''
ypxl1 = ipart(yend)
  • xgap)

  • xgap)

    • intery = yend + gradient ''// first y-intersection for the main loop''


''// handle second endpoint''
xend = round(x2)
  • (xend - x2)

    • xgap = rfpart(x2 - 0.5)

xpxl2 = xend '' // this will be used in the main loop''
ypxl2 = ipart(yend)
  • xgap)

  • xgap)


''// main loop''
for x '''from''' xpxl1 + 1 '''to''' xpxl2 - 1 '''do'''
plot(x, ipart(intery), rfpart(intery))
plot(x, ipart(intery) + 1, fpart(intery))
intery = intery + gradient
repeat
end function


An extension to the algorithm for circle drawing was presented by Xiaolin Wu in the book ''Graphics Gems II''. Just like the line drawing algorithm is a replacement for Bresenham's line drawing algorithm, the circle drawing algorithm is a replacement for Bresenham's circle drawing algorithm.


REFERENCES



EXTERNAL LINKS