Xiaolin Wu's line algorithm

Xiaolin Wu's line algorithm is a method of drawing antialiased lines in raster graphics. It was presented in the article An Efficient Antialiasing Technique in the July 1991 issue of Computer Graphics and in Fast Antialiasing in the June 1992 issue of Dr. Dobb's Journal. Bresenham's algorithm draws lines extremely fast but does not antialias them and cannot handle endpoints that do not fall exactly on integer pixel positions. Wu's method is comparatively fast, though still slower than Bresenham's. Like Bresenham's, it steps along one axis and considers the two nearest pixels to the ideal line, but instead of choosing the nearer one it draws both, with intensities proportional to their distance from the true line, which produces smoother lines. Pixels at the line ends are handled separately and lines shorter than one pixel are a special case. Wu also presented a matching circle-drawing extension in the book Graphics Gems II.