Take the 2-minute tour ×

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:

Line comparison

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:

Photoshop's line

My line

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?

share|improve this question
What happens when you move the mouse fast? Does it skip pixels? –  Hans Passant Dec 28 '10 at 22:07
@Hans Passant Yes, when drawing quickly I get lines similar to what Photoshop produces. What's odd is that you don't have to draw quickly in Photoshop to skip those unwanted pixels. –  Xenethyl Dec 28 '10 at 22:10
It stores the mouse points in a polyline. It doesn't add a new segment to it when it can simply extend the previous one. –  Hans Passant Dec 28 '10 at 22:16
@Hans Passant I'm not sure I follow completely. If I draw a line that passes though (50,50), (50,51), and (51,51), the ideal result would be skipping (50,51) because I was moving down to (51,51). But the points in the polyline would say that the line should move through (50,51)...? –  Xenethyl Dec 28 '10 at 22:20
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
I agree; look up Xiaolin Wu's line algorithm in wikipedia for example. –  WebMonster Dec 28 '10 at 21:30
@WebMonster Xiaolin Wu's line algorithm is for drawing anti-aliased lines. –  Xenethyl Dec 28 '10 at 21:32
@Xenethyl I just had a look at Photoshop's pencil tool we are talking about. It draws lines with "east" and "south-east" pixels as well that are identical looking compared to your own solution, if I move the mouse relatively slow and thus provide samples for all those pixels. As soon as I move the mouse faster and thus do not provide samples for all directly neighbored pixels, the result is indeed similar to your desired Photoshop line. Did you observe this, too? Maybe your progam is too fast and scans for too many samples... ^^ –  Flinsch Dec 30 '10 at 8:12
@Flinsch I think you may have just helped me realize an issue with my current implementation. Right now I'm firing my draw event whenever the cursor moves to a new pixel. I didn't really give this much thought, as I figured it would be more efficient (if the user doesn't move their mouse, there's nothing new to draw). If I switch to polling instead of event handling, I then have the ability to offer brushes that build up paint over time (ex. an airbrush). I'll experiment with this tomorrow, but I think polling will work nicely. I'll just have to figure out the right interval. –  Xenethyl Dec 30 '10 at 9:58
@Flinsch I just finished moving my code over to 10ms polling instead of mouse move event handling. Not only is performance better (the browser isn't dropping any mouse move events), but my lines are of much higher quality (rivaling Photoshop). I never would have thought that my original approach was accurate to the point where the quality of my lines degraded. Paint build-up was a freebie with this change too, which I'm quite happy about. If you could edit your answer to note the discussion below and/or polling I'll mark this as accepted. Thanks so much! –  Xenethyl Dec 30 '10 at 21:04
show 8 more comments

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


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

alt text

share|improve this answer
Thanks for helping out with one of my questions again. The environment that I'm running this in very much favors a preemptive solution over a reactive one ("deleting" a pixel is an involved process, especially when you consider drawing over something that already exists). The issue here is deciding whether or not that one pixel should really be deleted. What if the user intended to draw the "L" shape in your diagram? The algorithm would blindly delete it. I'd find it hard to believe Adobe's implementation is insanely complicated with prediction and trajectory tracking... –  Xenethyl Dec 28 '10 at 23:34
@Xenethyl If the user is picky about the corners in Photoshop, he will probably use another tool, and not a freehand pencil. But I agree in that PShop may have better algorithms in there. As for drawing over something pre-existent, I thought you have an "undo" command, so Unmarking != Deleting. –  belisarius Dec 28 '10 at 23:41
Agreed that user preference comes into this a little bit. Unfortunately, this issue is at the core of my drawing algorithm for any other drawing/painting tools (ie. pencil with different tips, paintbrush, etc). Every line that the user draws is treated as a 1px line, and if a tip (ex. a star) is being used it's just stamped at each pixel coordinate. Undo is not implemented yet, but the process would be similarly involved. Changing pixel data requires a copy, read, change, and write in this environment, unfortunately. –  Xenethyl Dec 28 '10 at 23:51
@Xenethyl: What does Photoshop actually do in the case where you carefully draw an L shape? I suspect you will need multiple clicks to do this (i.e. you won't be able to draw the L in Photoshop with the mouse button held down from start to finish), which would mean Photoshop is treating each segment of time during which the mouse button is depressed as a seperate entity -- something your program can do too. –  j_random_hacker Dec 29 '10 at 4:37
@j_random_hacker Actually, drawing a 3-pixel L shape in Photoshop isn't a problem -- it works fine. –  Xenethyl Dec 29 '10 at 9:49
add comment

Your Answer


