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

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 "corne开发者_高级运维r-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?

The difference between both lines is basically that Photoshop is re-considering the n-1 pixel drawn AFTER drawing the pixel n, and erasing it if it gives positive with one of the following masks:

 x 1 x       x 1 x
 1 o x   or  x o 1
 x x x       x x x

or

 x x x       x x x
 1 o x   or  x o 1
 x 1 x       x 1 x

x= Don't mind
o= The n-1 pixel
1= Marked pixel after drawing pixel n

Or written as logic:

Suppose pixel n-1 is at a[i,j], so, after marking the pixel n, check:

If ( (a[i-1,j  ]==1 && a[i  ,j-1]==1) ||
     (a[i-1,j  ]==1 && a[i  ,j+1]==1) ||
     (a[i  ,j-1]==1 && a[i+1,j  ]==1) ||
     (a[i  ,j+1]==1 && a[i+1,j  ]==1))
Then
     Unmark a[i,j];

You may want your to draw your line delayed one pixel just for not showing your "disappearing" pixels (although I doubt it'll be noticeable at that scale).

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.

I guess you finally solved your question (6 years have passed...), but I just wanted to say your application seems to work actually better than Photoshop in this particular case. Although I think I know what your aim was (avoiding those pixel clusterings), the "constant thickness" is better achieved with your App (despite those unwanted groupings), while Photoshop makes a "sausage rope" pattern which may be smarter, but no so width-constant and, thus, not so "real". It's likely due to a different handling of decimal values (rounding) and selecting which pixels to fill or skip. But again, this is an old topic.