11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Alan Wolfe Aug 11 '15 at 23:54
  • 5
    $\begingroup$ @AlanWolfe, integer algorithms on the CPU -- the same environment that Bresenham's algorithm was designed for. $\endgroup$ – Mark Aug 11 '15 at 23:56
  • 3
    $\begingroup$ 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. $\endgroup$ – yuriks Aug 12 '15 at 0:33
  • 2
    $\begingroup$ 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. $\endgroup$ – Nathan Reed Aug 12 '15 at 3:57
  • 2
    $\begingroup$ I can't mark a comment as correct, though. $\endgroup$ – Mark Aug 31 '15 at 4:59
9
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Octopus Jun 16 '17 at 16:37
  • $\begingroup$ @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.] $\endgroup$ – imallett Jun 18 '17 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.