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

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).

.