# Fast antialiased line drawing

Bresenham's line algorithm is a way of drawing straight lines using only fast integer operations (addition, subtraction, and multiplication by 2). However, it generates aliased lines. Is there a similarly fast way to draw antialiased lines?

• A couple questions... are you doing the drawing logic on the CPU or GPU? Also, are you looking for integer based algorithms or floating point? – Alan Wolfe Aug 11 '15 at 23:54
• @AlanWolfe, integer algorithms on the CPU -- the same environment that Bresenham's algorithm was designed for. – Mark Aug 11 '15 at 23:56
• en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm is the classic one, though the wikipedia page is pretty half-baked and I don't have access to the paper. This feels like a lazy question though, since it's pretty easy to find this by doing some basic googling. – yuriks Aug 12 '15 at 0:33
• Just thinking out loud, I figure it should be easy to adapt Bresenham for drawing multi-pixel-thick lines. Then you can do antialiasing by calculating the distance of each pixel center from the mathematical ideal line, and applying some falloff function. – Nathan Reed Aug 12 '15 at 3:57
• I can't mark a comment as correct, though. – Mark Aug 31 '15 at 4:59

Is there a similarly fast way to draw antialiased lines?

No, because by definition an anti-aliased line touches more pixels. Such algorithms will be slower.

In a software rasterizer, the ubiquitous way to draw anti-aliased lines is Xiaolin Wu's line algorithm. It's not hard to implement, and anyway there's unusually high-quality pseudocode at that link.

In a hardware raster pipe, the line primitive is expanded to a screen-space quad by the default (or user-provided) geometry shader, and then drawn as two triangles, which can then be anti-aliased in the usual ways.

In a raytracer, there are a variety of options. It's worth thinking about how you actually want to draw a 1D object. Maybe as a cylinder (woo shadows!). Note that this introduces issues of perspective/foreshortening which may (or may not) be what you want. There isn't a clear generalization. Then, obviously, whatever you do, you just supersample it.

• "and anyway there's unusually high-quality pseudocode at that link", I disagree. That pseudo code is likely not a proper implementation of Wu's algorithm even though it seems to be what was used in countless places around the web. Wu's original algorithm drew from both ends inward towards the center and was actually faster than Bresenham's because it performs about half as many operations even though it writes to more pixels. I am talking about Wu's actual algorithm not the one posted in the linked wikipedia article. – Octopus Jun 16 '17 at 16:37
• @Octopus [Expresses vague skepticism, especially on the faster bit, but lacks context to refute or confirm—if this is so, sources, corrections, and edits are of course welcome.] – imallett Jun 18 '17 at 23:31
• Depends on what you count. If you draw from both ends inwards, then Wu's algorithm does half the calculations but twice as many pixel writes. See Table 1 in Wu's paper, linked on Wikipedia. So if pixel writes are expensive, as is the case when writing to a TFT on a serial connection, then Wu's algorithm is more expensive than Bresenham's. (I must admit I do not see why Bresenham's algorithm cannot use symmetry too.) – Jan-Åke Larsson Aug 13 '19 at 14:05
• But I do agree with @Octopus, even accepting "draw from one end to the other", the pseudocode is Wu's algorithm only if integer arithmetic is used throughout. Code I see online uses floating-point arithmetic, which is a significant change. In Wu's paper, the algorithm only uses integer arithmetic (or actually fixed-point arithmetic). – Jan-Åke Larsson Aug 13 '19 at 15:54