Whew, it’s been awhile since there was an update to paint.net 4.0. It’s finally time to start talking about the next one!

I’ve been slowly chipping away at various little things in Paint.NET, especially with respect to performance. And also some missing features and bug fixes.

Here’s a preview of what’s coming in 4.0.4:

• The ability to choose a “Fill” is coming back for the Paintbrush tool. I didn’t think many people would miss it and so I left it out of 4.0 in order to save time for other things. I was wrong on two fronts here: 1) people do need it, and 2) it only took a few minutes to implement. So, in 4.0.4, it’ll be back.
• Dramatically faster Magic Wand tool. I came up with a new algorithm to do the reverse scan-conversion that is needed here. On small images you probably won’t notice, but if you’ve ever had the Magic Wand tool “take forever” then the next update is going to be your favorite one of all time. I’ve seen the Magic Wand go from taking 60+ seconds in 4.0.3 to taking maybe 2 or 3 seconds in 4.0.4.
• The improvements to the Magic Wand tool’s reverse scan-conversion algorithm have also been applied to make aliased selections work a lot faster. (Actually I’ll tell the proper truth here: This work was originally intended as a challenge to myself to see if I could make the aliased selection rendering run a lot faster. It just so happened to be more relevant for the Magic Wand )
• Much faster performance overall. I’ve chipped away at performance in the areas of antialiased selections, selection clipping, and so on. Anything involving selections should be a lot faster. In particular, the Move Selected Pixels tool has a fantastically smoother framerate. Some of this optimization just involved a better choice of sorting algorithm (e.g. by using introspective sort instead of raw quicksort). I have also aggressively applied a coding pattern in C# which allows elision of virtual function calls (via inlining) by combining generics, structs, and interfaces. If anyone is interested in hearing the details, please let me know in the comments below, as I’m not sure this has been discussed much in the broader C#/.NET community. This pattern is responsible for the first 20% performance gain in my C# implementations of quicksort and introspective sort, so it’s nothing to sneeze at Other performance improvements came about by being smarter about how selection mask generation was parallelized with other computations, by replacing integer divisions with multiply/add/shift combinations, and so on. Windows Performance Analyzer is your friend, folks! I’ve been using it extensively to optimize paint.net 4.0 (both now and in the past).
• Other miscellaneous bug fixes, of course. The Gear shape had some glitches (oops), the Text tool produced foul output if you used its Smooth rendering mode while antialiasing was disabled, and Edit –> Clear wasn’t behaving the same as it was in v3.5 and was causing problems because of it.

“Reverse scan-conversion” is the inverse of polygon scan conversion (also known as rasterization). It’s the process of taking a list of non-overlapping rectangles with integer coordinates and extents (e.g. System.Windows.Int32Rect) and stitching them together to form a polygon (a list of points in 2D space). In Paint.NET this is used when you have chosen to use aliased selections: your selection’s polygonal outline is scan-converted (rasterized) to produce a list of integer rectangles which approximate its interior (this is a well-known algorithm in computer graphics). This list of rectangles (or “scans”) is then fed into the next algorithm which stitches the rectangles together to create a “pixelated” (or rectilinear) polygon outline. In 4.0.3 and before, each rectangle was first transformed into a closed polygon and then they were all run through GPC’s union algorithm. This ensured that any touching edges were coalesced. Unfortunately, GPC just does not like this scenario and performs excruciatingly slow, and sometimes even crashes via stack overflow.

As it turns out, this has a lot of overlap with what the Magic Wand tool does. It too needs to take a list of rectangles and transform it into a polygon, although the source is different. We start by applying ye ol’ flood fill algorithm, with tolerance thresholding, to the image in order to create a bitmask that tells us which pixels are included or not. This bitmask is then converted into a list of rectangles via a process akin to RLE compression. And then that list of rectangles must be converted into a polygon because that’s the way Paint.NET’s selection system works (it is geometry based: it needs polygons!). This is what takes up about 99% of the CPU time when you see the Magic Wand “taking forever,” and by reducing it from O(n^m) down to O(n), much time and frustration is saved. (I’m doing a little hand-waving here by not specifying what ‘n’ is. Also, I haven’t actually analyzed GPC’s code to figure out what m is, although it’s probably 2. Have you tried analyzing its code? It’s intense )

Almost all of the CPU time is now spent drawing the selection outline with Direct2D. A future update might optimize that too since Direct2D is using a general purpose algorithm, something which is overkill when all I need is to apply a 1 pixel stroke to a polygon.