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?
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.
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
(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 >> 256, y ^ 255); plot(x, sign(y1-y0)+(y>>256), 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.