<p>Absolutely there is, the Bresenham's Algorithm, modified.</p>
<p>Instead of drawing from (x0,y0) to (x1,y1), one can use Bresenham's algorithm to draw lines from <code>(x0,y0*256)</code> to <code>(x1, y1*256)</code> still in x1-x0+1 steps, meaning that the delta_y is also multiplied by a factor of 256.</p>
<p>At each step  <code>plot(x, y &gt;&gt; 8, y ^ 255); plot(x, sign(y1-y0)+(y&gt;&gt;8), y &amp; 255);</code></p>
<p>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 <code>y &gt;&gt; 8</code> one <code>xor</code> and two pixel writings. <code>y &amp; 255</code> is typically free.</p>

CC BY-SA 4.0
2021-02-17T08:50:19.343Z
2021-12-02T16:34:26.367Z
2021-12-02T16:34:26.367Z
Aki Suihkonen
<blockquote>
  <p>Is there a similarly fast way to draw antialiased lines?</p>
</blockquote>

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

<hr>

<p>In a software rasterizer, the ubiquitous way to draw anti-aliased lines is <a href="https://en.wikipedia.org/wiki/Xiaolin_Wu&#39;s_line_algorithm">Xiaolin Wu's line algorithm</a>.  It's not hard to implement, and anyway there's unusually high-quality pseudocode at that link.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-08-13T14:05:47.160Z
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
CC BY-SA 4.0
2019-08-13T15:54:21.287Z
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
CC BY-SA 3.0
2017-06-16T16:37:17.097Z
"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
CC BY-SA 3.0
2017-06-18T23:31:25.497Z
@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.]
geometrian
CC BY-SA 3.0
2015-09-01T16:16:10.817Z
2015-09-01T16:16:10.817Z
geometrian
<p>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?</p>

CC BY-SA 3.0
2015-08-31T04:59:46.233Z
I can't mark a comment as correct, though.
Mark
CC BY-SA 3.0
2015-08-11T23:54:29.043Z
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
CC BY-SA 3.0
2015-08-11T23:56:30.247Z
@AlanWolfe, integer algorithms on the CPU -- the same environment that Bresenham's algorithm was designed for.
Mark
CC BY-SA 3.0
2015-08-12T00:33:52.797Z
https://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
CC BY-SA 3.0
2015-08-12T00:34:21.103Z
@yuriks, mind turning that into a full-fledged answer?
Mark
CC BY-SA 3.0
2015-08-12T00:35:01.630Z
I fat-fingered the enter key, so I just edited my comment. :)
yuriks
CC BY-SA 3.0
2015-08-12T03:57:05.190Z
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
CC BY-SA 3.0
2015-08-12T04:06:42.050Z
Regarding Bresenham being adapted to do AA, this page shows that with some simple code.  From the description of the xaolin wu algorithm it may be similar.  http://members.chello.at/easyfilter/bresenham.html
Alan Wolfe
<antialiasing><pixel-graphics><line-drawing>
Fast antialiased line drawing
Mark
# Fast antialiased line drawing

(Asked by: username_0 on 2015-08-11)

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?

**Tags:** antialiasing, pixel-graphics, line-drawing

> **Comments:**
> **username_1**: 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?  
> **username_0**: @username_1, integer algorithms on the CPU -- the same environment that Bresenham's algorithm was designed for.  
> **username_2**: https://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.  
> **username_0**: @username_2, mind turning that into a full-fledged answer?  
> **username_2**: I fat-fingered the enter key, so I just edited my comment. :)  
> **username_3**: 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.  
> **username_1**: Regarding Bresenham being adapted to do AA, this page shows that with some simple code.  From the description of the xaolin wu algorithm it may be similar.  http://members.chello.at/easyfilter/bresenham.html  
> **username_0**: I can't mark a comment as correct, though.  

---

## 2 answers

### Answer by username_5 on 2015-09-01. Score: 11 | Accepted answer

> 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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_7**: "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.  
> **username_5**: @username_7 [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.]  
> **username_6**: 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.)  
> **username_6**: But I do agree with @username_7, 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).  

---

### Answer by username_4 on 2021-02-17. Score: 1

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.


---

