In my previous post, I mentioned that I had rewritten the selection renderer in Paint.NET v3.5. As a pseudo-warning, this post is pretty technical.
The selection renderer in Paint.NET v3.36 uses GDI+. It draws the outline twice: once as a dashed black line, and the second as a dashed white line. A timer fires every 50 milliseconds or so and redraws the outline with a slightly increased “dash offset.” This gives the “dancing ants” animation. Our pal Emma Roberts will demonstrate:
“Pretend I’m animated!” — Ants
There are a few major problems with this implementation. The first is that while you are drawing or modifying a selection, it is only drawn with a black outline (once you are done, it will transition to the “dancing ants” mode). This makes it wickedly difficult to figure out what kind of selection you’re drawing if the underlying area is black. Try it with a solid black image and you’ll understand immediately. I had to do a solid outline instead of a dashed one because there were some horrible artifacts and performance problems if I didn’t.
Next up, the new render cache (hopefully I’ll discuss it in an upcoming post) splits up rendering into more tiles than it did before (for several good reasons!). GDI+ does not do multithreading. At all. In fact, it actively prevents you from making GDI+ calls on more than one thread even if you are clever and “trick” it. This was resulting in selection rendering performance falling off a cliff as all sorts of “setup” work (creating brushes, clipping, etc.) was being over-executed by up to a factor of 10 (that’s an estimate). Not to mention it was a non-starter for multithreaded performance scaling anyway.
Another problem is that the “dancing ants” animation consumes a lot of CPU power. This in turn slows down the rest of the system, and drains battery power (I’m a desktop/workstation guy, but the market has been majority-owned by laptops for awhile now). There are a few optimizations in there to throttle CPU usage if it gets “too high” but it’s never really been profiled or quantitatively proven to work well. My criteria at the time was “fewer people are complaining,” and then I went and drank beer (woohoo!).
Ahem. Anyway. The animation is really there for two reasons: not only does it look cool, but it guarantees contrast between the selection outline and the underlying image. The image you’re working on can’t animate, but the selection outline does, so there you go: it will never be confused for being part of the image.
The solution? I wrote my own polygon rasterizer renderer. From scratch. There’s a good reason people use libraries like GDI+ and Cairo to render graphics for them: it’s tricky! Get someone else to do it for you! Simple implementations aren’t difficult, but the complexity skyrockets once you add things like antialiasing, clipping, blending, various types of caching, serialization (critical for undo/redo), and safe multithreading.
However, I felt it was worth it to implement just enough of a pixel-pushing geometry rasterization “library” in order to render the selection since it is so crucial for Paint.NET. It’s taken “only” 2 months to get right, and it still isn’t quite finished. (but hey, if something is a core business of yours, do it yourself!). I’m now taking polygon lists and doing my own clipping, scanline rasterization, clipping, blending, etc. It’s fun, confusing, educational, and horrifying. I should probably have a cigarette once I’m all done and calmed down.
Bresenham invented the classic aliased line rasterization algorithm, and a kid named Xiaolin Wu later invented a smart antialiased rasterization algorithm. Both are in wide use today because of their inherent and wonderful simplicity. I implemented the latter, because antialiasing is important. The selection outline now uses “XOR” blending, so contrast is guaranteed except for a few less-common scenarios (prevalent 50% grey).
Notice how in this new screenshot, the selection outline effectively changes color as it goes through parts of the image which are varying colors. Where her hair is dark, the selection is bright, and where it crosses her lighter skin tone it becomes darker:
Normally you can’t use both XOR and antialiasing. XOR is meant to be “undoable” and so applying it a 2nd time simply gives you back the original data. It’s generally fast, cheap, and simple. With a naive antialiasing implementation you end up with seams and dots all over your polygon, as endpoints of lines give you pixels that are rendered twice, and very small lines (0 to 2 pixels long) don’t really know what to do.
My solution was to do the rendering in two passes. In the first pass I accumulate coverage values into the alpha channel. I accumulate towards zero, and use the inverse of that later as my real alpha value. I can do this because I know that the pixel is fully opaque at this stage in the rendering pipeline; this is because the “checkerboard” has already been applied. Thus, the alpha channel can be used for whatever I want.
In the second pass I apply the XOR operator to every pixel along the path at full strength (yar!), and then use alpha blending between the original pixel’s color value and the XOR’d color value with respect to the accumulated alpha. Yes, I’m doing stencil buffer accumulation in software. Video games use these a lot, especially for things like shadows and dancing teddy bears (ok maybe not the second one so much).
Oh, also, the selection is no longer animated because contrast is achievable without it, and because the performance benefit is profound. It would also be much more difficult to get an animated or dotted outline with the new code. I’d need 4x the lines of code, or I’d have to employ code generators or some other form of voodoo (if this were C++, a “policy-based template something-or-other” would be employed). As it is I still have a few higher-order functions and closures in there I need to get rid of. But the performance is still great, so I have deferred those optimizations until later (alpha or beta).
Because the selection renderer is now implemented in code that is completely owned by me, all opportunities for optimization are available. This includes changing the underlying storage model that defines the selection’s polygons – I now use a List of Point arrays (List<System.Windows.Point[]>), which makes interoperating with GPC and WPF easier and faster. I can optimize my clipping and do work ahead of time to ensure that rendering is fast.
I can split work like vector/matrix multiplication across multiple threads. I can even prefetch work ahead of time using “spare” CPU cycles. For instance, whenever the selection changes (moves, rotates, or is edited using add/subtract/union/intersection), I have to recompute the scans of the selection. This is a list of rectangles that I use to fill the interior of the selection with a blue tint. Well, in between the notification of a changed selection, and actually painting it (other stuff happens in the middle), I compute these scans in a background thread. This is a future at work for you!
Also, I can make sure that these “scans” are computed and stored in sorted order with respect to their top Y coordinate. Then, when clipping the rendering of the highlighted selection interior, I can use a nicely fast binary search to figure out which “scan” to start rendering from. Later on I’ll put in logic so that the computation itself can be clipped (I never render the highlight outside of the image bounds, so why calculate that part?). Oh, and did I mention that along the way I found some code on the critical path for the Magic Wand that was using insertion sort? I didn’t? Well, it’s fixed. That was embarrassing.
Other opportunities for optimization include being smarter about which areas of the canvas are redrawn when things change. With GDI+, it was difficult to do the boolean path algebra correctly (because of bugs in GDI+) to find a minimal invalidation region, and so several heuristics were put into place. Now that I control all of the code for both rendering and computational geometry, I’ve been able to implement this better. This improves performance, and fixes some visual glitches whereby little bits and pieces of the selection outline remained when moving/rotating a selection (the heuristic to fix this was, “every 1 second, redraw everything”).
This has all also served to help reacquaint myself with the Paint.NET codebase in areas that haven’t really seen much change in at least 2 years. Therefore, I’m better prepared for more refactoring after v3.5’s release. I’m changing gears for my work on v3.5: I’m going to stop fixing/refactoring things, and move to bugfixing mode. I’ve done a lot of optimizations, and there are still many more possible ones, but I also need to release something so that you all can use it! More optimizations can be trickled out over v3.5.1 or v3.6 releases, etc.
Anyway, that’s all for now. I hope you all will like it. One of my private beta testers sure does:
“…the speed improvements in comparison to my memory of v3.36 are greatly improved on any Windows machine I throw it at. Really well done! I think that this alone will be enough to make people excited.”
paint.net blog 
Ooo…shiny. Very slick! I’m really looking forward to getting ahold of this when it’s released. 🙂
This just keeps looking better and better. I can’t wait Rick!
Awesome, can’t wait for PDN 3.5!
And lol at O(n^2) sorting 🙂
Your points are totally valid.
But dancing ants kicked ass 😉
The CPU usage of the old selection rectangle always bothered me (especially when zoomed in really far for some reason). Never enough to actually *complain*, but it was always there… at least if you minimized Paint.NET it would stop redrawing so I could do other stuff.
So yeah, this is a good change, definitely!
I really can’t wait for a final build either 🙂
When is an alpha available?
Awesome, but could you make the AA optional please? To make it easier to see exactly which pixels are selected without zooming in too much
It’s surely not a bad idea to write your own rasterizer, but it’s easier to use existing ones. Ever heard of AGG? I think it’s impossible to write something comparable and equally powerful within 2 months:
http://www.antigrain.com/
Its license is extremly liberal up to v2.4 and v2.5 is under GPL. Here is a .NET wrapper:
http://www.creativedocs.net/devs/agg
@Harold: The AA isn’t too terribly annoying. It is pretty easy to know which pixels are in the selection and which are not.
well this time I actually understood half of it. (last time only 1/10th)
no more ants
and I can’t wait to try this out. I’m going to be able to make smokin pictures really fast.
hope you bring it out soon and let us play!
ciao OMA
@MIke Ryan: even the old AA is annoying me. But mainly because it reduces the selection border to a blurry mess.
when we can try 3.5 alpha?
🙂
Selection ants (or lines) are not made to exactly represent actual selection but only to give an idea of the selection.
Indeed, selection is not just 0 or 1, it is between 0 and 255 and the ants may show an approximation of the selection as if it was 0 or 1.
Considering this, you should display ants without antialias and with animation and optimize this way. In addition, you should let us see and edit the exact selection mask.
It’s just my idea of selection.
damned — You’re not really making any sense. In Paint.NET, the selection is 0/1. A pixel is either selected or it is not. Soft selections are not possible.
D’oh ! I think it means it will still be 0 or 1 in 3.5… I was hoping for such a change.
Don’t you think drawing AA lines in order to show non AA selection is a little bit strange ? It is the opposite of what I would do.
oooh slick 😀
pdn is becoming more and more better 😀
cant wait for 3.5
I think that previous behaviour shouldn’t be dropped completely because there are still images with a lot of 50% gray in the world.
I agree with the HA! Guy. I think both should be in there, at least i hope. Or something. And once i upgrade to a mac, i’m buying VMWare fusion for paint.NET. Because it’s a great editing program.
Come on man, if I can solve it in flash (The photoshop way, really hate AA) without that much CPU footprint you should be able to create it in C# 🙂
Nice work on the editor though 🙂
Ola, you didn’t solve anything though. You just recreated Photoshop’s cheap 1990’s-era selection outline that honestly doesn’t work very well.
Rick, how come it doesn’t work? There must be a reason why adobe sticks to it? Personally I can’t find any other better way of showing a selection .. you shouldn’t re-invent the wheel when it’s not in the users favor ..
Ola, It is absolutely in the user’s favor.
There’s a lot that I dislike about Photoshop’s UI. However, that doesn’t mean the program is worthless by any means.
Thank you for being so dedicated to the development of this wonderful program! I prefer your program over Photoshop for its simplicity and UI.
Brilliant program!
One thing though. Could it be made a little easier to make the BG of pictures transparent? For eg, right now I copy the images, paste them on powerpoint, use the ‘set transparent’ image tool there, add wtv I wanted, prt screen back on P.Net and then continue simply because I find the magic wand a little difficult to use. Hope it’s possible.
Cheers!
I personally think it would be awesome if you allowed the rectangular and elliptical selection tools pan out from the start point as the center instead of only the corner.
It’ll be a shame to lose the dancing ants, but not being able to see my selection rectangle on predominantly black images is probably my biggest (and perhaps only meaningful) criticism of PDN. Can’t wait for v3.5
Re: “(for several good reasons!).”:
It’s good to see people punctuating in the literal order of precedence, as opposed to the way we’re taught in school.
People never get it when I tell them I keep the appended exclamation mark because it’s part of a literal quote or inner sub-sentence (clause/phrase), but I also keep the period as it trails the full sentence, similar to a ‘}’.
The new selection rect looks very interesting, but I wonder how well it works if you need pixel level accuracy. I do a lot of icon work in PDN, and I find the dancing ants very effective, I can easily see which areas are in my selection.
Perhaps we can have an option to use different selection rect types?
The one criticism I have of selection in the current version is trying to manipulate small areas. When you zoom into an image, the “hit area” for resizing a selection expands as well. To illustrate my point, select a 12×12 block of pixels, zoom in to 4x or 8x on an image and try to move them with the mouse, It’s really quite difficult. Can something be done about this for v3.5?
RottedFrog, the selection hit-testing is fixed for v3.5.
Just out of interest, why do you not get the hardware to draw this sort of stuff for you?
Will — The entire rendering system is based on software. To move to hardware would have benefits, but isn’t something to be done lightly. I may move to Direct2D in the future, but that will also entail cutting out XP support.
antialiasing in selections?
I can’t wait.
The progress on this looks great Rick, amazing job 😀 Like everyone else, I cannot wait until v 3.5!
ZizOiz — The selection outline is drawn with antialiasing. Always has been. The selection itself still only describes a region where pixels are either completely included or completely excluded.
I liked the ants. u__u
How about using the XOR rectangle when making a selection, then moving over to the ants?
Also, if you were to add 128, then take the mod-256, you’d get contrast on everything including 50% grey.
And I can’t say I agree with hardware rendering for a paint program. As the programmer, you lose control of the finer details of how your program creates its graphics, and, as much as they’d tell you otherwise, you can’t ensure that you’ll get the very same results on different hardware.
I still want ants.
As said before, they are extremely useful under high zooms where one is working at pixel level (the XOR doesn’t really show the selected pixels well)
why not make the animated ants more jerky? Instead of drawing it every 50ms, draw it every 100ms or 200ms. If that’s still too much CPU consumption, then make the ants stationary – at least ants still look more distinct from anything you might be drawing, than, say, XOR on a blank white document (which awfully looks like something already on the image).
jsonchiu, In the next update I have made improvements to the XOR renderer which should help. I will not be adding back the animation.
Also, I’m not disagreeing with anyone’s sentiment of liking the ants.