What’s coming in 4.0.4

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 Smile)
  • 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 Smile 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 Smile)

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.


26 thoughts on “What’s coming in 4.0.4

  1. acemarke says:

    Absolutely interested in any details you care to share about performance optimization. Information’s always good, and never hurts to add another item to my toolbox.

  2. chesscanoe says:

    Wow, after the C# I’m lost – a general dictionary is of little use. Can you explain without needing to give a course in programming and graphics? Thanks for your efforts, even though I don’t comprehend your insights. 😦

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

    • Rick Brewster says:

      “Elision of virtual function calls (via inlining)” … normally if you have, say, an IList and you call, e.g. Add(), then that is done via virtual function dispatch. If you use this pattern that I’m referring to, then the JIT can (potentially!) inline the code for Add() and skip the virtual function pointer lookup, method call (aka branch), and stack push/pop stuff. This isn’t really the best example since Add() is probably too big to warrant inlining. However, the result of inlining methods such as get_Count and the indexer are fantastic!

      It does require a moderate bit of “bending over backward” but it can be worth it. If you’re not a .NET developer then you wouldn’t need to know any of this 🙂

      • OlivierOlivier DALET says:

        Hi, I am a .NET developer and definitely interested in more insights on your virtual calls elision if you don’t mind sharing. Anything realted to the usage of MethodImplOptions.AggressiveInlining?


      • Olivier says:

        By the way, as a .NET dev, I’m very interested in more insights about this virtual function calls elision, if you don’t mind sharing.

  3. Joao Coelho says:

    This is absolutely awesome! Wish I had 1/100th of those coding skills!
    Not sure where to leave feature requests, so here’s one that’s fast and easy: Image Trim. I use it a lot in Photoshop and seems super easy to implement. Trim by color of one of the 4 corners or by transparency. Big time saver so we don’t have to first select and then crop. Hope this is a useful request.. cheers!

  4. Razvan says:

    “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.” – would be interested to hear more

  5. grinch33 says:

    I’m really pleased with Paint.NET, but a lot of the time I simply want to capture the screen or a window and crop it. So 2 requests:
    1) Would it be possible to be able to grab a snapshot of the screen or another window from within Paint.NET?
    2) The first time after restarting my system it feels like a long time for Paint.NET to start. Is there any startup performance improvements that could be made? (I can do some time measurements if you like, but I have a CAD/CAM spec laptop with 16GB memory so I don’t think its the machine).

    • Rick Brewster says:

      1) This features isn’t necessary. Press the Print Screen button on your keyboard. Alt+Print Screen will capture only the current window. Then paste into Paint.NET and crop using Rectangle Select and Image -> Crop to Selection.

      2) Get an SSD. Paint.NET is already heavily optimized for this, but .NET still just pages in a lot of code at startup.

  6. ♪♫♪♪ says:

    When working on corners or edges of an image while being zoomed in (say 300%), I would love if you could actually move the image to the center of the screen with the pan tool instead of it being stuck to the side of your monitor.

  7. Jeff says:

    I’m interested in more detail about the C# coding pattern, performance optimization, etc. Thank you in advance and keep up the great work, Rick!

  8. Toke says:

    Another vote for more C# perf. info ! Very interesting stuff.
    I have been reading (not finished yet) Ben Watsons “Writing High-Performance .NET Code” and gotten into PerfView a bit and I wonder how’s your take on that tool compared to WPA? (As both are based on ETW and takes .etl traces, though I don’t know much about WPA.)

    • Rick Brewster says:

      I’m a bit biased since I worked on WPA for about 5 years 🙂 I definitely recommend trying it out! The ability to have an Analysis tab full of graphs with synchronized selection and timeline is worth its weight in gold.

  9. Robert says:

    +1 for sharing more info on aggressively applying a coding pattern in C# combining generics, structs, and interfaces that allows for elision of virtual function calls (via inlining).

    • Ken Koichi Smith (kenkoichismith) says:

      Like olaff said, thank you for your hard work! And great job keeping it up and not tiring of it!f I used paint.net a lot in my formative years as a student designer, now I’m using Photoshop and a big iMac, but would probably be using Paint.Net a lot if I had a Windows available.

Comments are closed.