Drawing 1-pixel thick, aliased lines in real-time

Question

A brief background: I'm working on a web-based drawing application and one of the tools I'm implementing is a 1-pixel thick pencil. The tool allows the user to draw 1px aliased lines on the canvas.

In order to determine where the user is drawing on the canvas, mouse coordinates are monitored. If mouse1 is held down, the pixel the cursor is over will change. Essentially it works just like the pencil tool in Photoshop.

NOTE: Bresenham's algorithm will not work for this situation. My input is submitted in real-time, so I'm not drawing a line from P0 to P1 where the distance between P0 and P1 is many pixels. In general, P1 is a neighbor of P0.

The issue I'm having is that my resulting lines do not have a perfectly clean 1px weight. Here's an example:

Note that both of the lines are hand drawn, so there is some variance. What's interesting is that Photoshop is able to make a much cleaner 1px representation of the line that I draw. The reason why my line looks dirtier is because of this:

When drawing with the tool in my application, the red pixels are filled in. In Photoshop, the red pixels are not filled in. This makes sense because in order to move from a given pixel to, say, its south-east neighbor, either the east or south neighbor will likely be passed over. There is an extremely slim chance that the cursor will pass exactly over the corner into the south-east neighbor, avoiding the drawing of the red pixel, but this usually doesn't happen.

So, the question I'm left with is how Photoshop is able to skip the red pixels that are showing up in my lines. The only thing I could think of was waiting until two pixels are queued up before drawing either of them so I would know if a "corner-neighbor" was passed over. In that case I would just not draw the first of the two pixels because it would be equivalent to a red pixel in my diagram. This runs the risk of not drawing an intended pixel if the user draws a pixel, moves the cursor one pixel south, and then one pixel east. Both of the pixels should be drawn, but the algorithm would say otherwise.

Any ideas? How might Photoshop be handling this issue?

Answer 1

Original: Have a look at Bresenham's line algorithm. It can easily extended concerning smoothing etc.

Edit: Regarding the development of the question and the discussions (especially the comments below), I'd like to extract some interesting points: Photoshop's pencil tool does also draw very similar lines with "east" and "south-east" pixels as well, if the mouse is moved relatively slowly thus providing many samples for all those pixels. As soon as the mouse is moved faster, the trajectory does not provide samples for all directly neighbored pixels. The result would then be the desired 1-pixel thick line. In conclusion, we note: There is no "magic" behind Photoshop's pencil tool; it just seems to scan fewer samples. For details see discussions/comments below.