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?
$\begingroup$
$\endgroup$
9
-
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 WolfeCommented Aug 11, 2015 at 23:54
-
5$\begingroup$ @AlanWolfe, integer algorithms on the CPU -- the same environment that Bresenham's algorithm was designed for. $\endgroup$– MarkCommented Aug 11, 2015 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$– yuriksCommented Aug 12, 2015 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 ReedCommented Aug 12, 2015 at 3:57
-
2$\begingroup$ I can't mark a comment as correct, though. $\endgroup$– MarkCommented Aug 31, 2015 at 4:59
|
Show 4 more comments
2 Answers
$\begingroup$
$\endgroup$
4
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.
-
1$\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$– OctopusCommented Jun 16, 2017 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$ Commented Jun 18, 2017 at 23:31
-
$\begingroup$ 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.) $\endgroup$ Commented Aug 13, 2019 at 14:05
-
1$\begingroup$ 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). $\endgroup$ Commented Aug 13, 2019 at 15:54
$\begingroup$
$\endgroup$
Absolutely there is, the Bresenham's Algorithm, modified.
Instead of drawing from (x0,y0) to (x1,y1), one can use Bresenham's algorithm to draw lines from (x0,y0*256) to (x1, y1*256) still in x1-x0+1 steps, meaning that the delta_y is also multiplied by a factor of 256.
At each step plot(x, y >> 8, y ^ 255); plot(x, sign(y1-y0)+(y>>8), y & 255);
This is similarly fast, as it would use Bresenham's middle point algorithm with better error handing than Wu's algorithm (given that it suffers from error accumulation due to DDA) while also calculating the distance properly rounded. This approach of course adds one shift y >> 8 one xor and two pixel writings. y & 255 is typically free.
