This next update to Paint.NET will fix the usual set of small bugs, introduce a new adjustment (Posterize), fix a major performance blemish related to selections, and add an Intersect selection mode.

As for the small bug fixes, turns out there’s the possibility that Paint.NET will crash if malformed data is in the clipboard from, of all things, certain WPF-based applications. For effects that use IndirectUI, there was a problem with "linked" sliders (using LinkValuesBasedOnBooleanRule). And, it was possible to get around some of the protections that IndirectUI put up to protect Paint.NET from certain types of plugin code. Currently this only seems to affect the Fern Fractal plugin. I’ve e-mailed the author and helped him to find a way to accomplish what he wanted without "breaking the rules," so to speak.

Posterize is an adjustment written by Ed Harvey. It allows you to restrict each of the red, green, and blue channels to only have between 2 to 64 discreet values. Normally each channel has up to 256 values … 0 through 255, which is the range for a byte. This can be useful to give your image a "faux-dithered" look, although of course there are many other creative ways to use it.

Selection performance has been a major sore point in Paint.NET over the last 3 years or so. The initial drawing of a selection is fine — it’s when you go to use union (add) or difference (subtract) combination modes that things get froggy. Really froggy. As in slow. Pathetically slow.

We’ve been using a very brute force algorithm that converts the selection to a bit-mask, then performs the boolean operations on each bit, and then traces the bitmask to recreate a selection path (selections in Paint.NET are stored as a a polygon list). This causes these operations to have performance that is proportional to the number of pixels in the area where the selection is located (its bounding rectangle, actually). On a large or even medium-sized image, these are immediately prohibitve to use. This algorithm was originally developed for use by the Magic Wand tool so that we could do per-pixel tolerance, and then convert back to the polygon representation that was required everywhere else in the application.

There are algorithms that have been developed with let you do boolean algebra operations on the polygons themselves, optimizing away this very hacky (albeit correct!) way of doing things. One such algorithm is detailed in a 1992 paper by Bala R. Vatti titled, "A Generic Solution to Polygon Clipping." This is the algorithm implemented in the GPC (General Polygon Clipper) library written by Alan Murta from the Computer Science department at the University of Manchester in England. There are other algorithms that have been developed since, such as the one described in a 1998 paper by Günther Greiner and Kai Hormann titled, "Efficient Clipping of Arbitrary Polygons".

I have read both papers and tried to implement both of the algorithms. I have tried this several times, and have come close to completion but never quite made the leap to full comprehension, nor a finished implementation. I never had more than an evening or two in a row to devote to this pursuit — by my estimate, I would need at least a full two or three weeks. Maybe even a full month. These papers are from the academic world, and I haven’t had much practice there for quite some time! As such, the papers are very dense (in a good way) and require many readthroughs to fully understand.

I was never able to find a good implementation of the second algorithm by Grenier and Hormann, which was desirable because it was simpler and supposedly more efficient. In the end, GPC by Alan Murta won out: like previously mentioned, it is an implementation of Vatti’s algorithm, in C. It has been around for quite awhile and has needed no major revisions in many years. So, from an integrator’s standpoint (me!), it is the simplest and safest solution. I am happy to say that I have just purchased a Commercial Use license from the University of Manchester and that the next update to Paint.NET will be using it to substantially increase performance for selections!

This is a simple case of pragmatism versus idealism: ideally, I would have the time, the patience, and the mental acuity to implement these. In practice, it would take so long to do this myself that the cost of a Commercial Use License is actually the cheaper alternative. So for everyone who has donated to Paint.NET, this is how I’m using your money :) This does affect anyone interested in using the Paint.NET source code for their own commercial purposes: if you need any of the code related to selection stuff, you will have to purchase your own Commercial Use License from the University of Manchester.

The only way to get a feel for the performance increase is to cheat a little, with the current version of Paint.NET. Boot it up and create a 1024×768 image. Now, draw a circle selection that encompasses the whole image. Next, go to the toolbar and where it says "Selection Mode:", click on the down-arrow and choose "Subtract." Next, Draw another circle that is inside of the one you just draw. It’s very very slow. Next, undo this foolish thing you just did. Set the "Selection Mode:" to be "Invert (xor)" (this is the one mode that GDI+ gives you for free!). Now draw that second circle again and notice how smooth everything is. In the next update, this performance will also be there for Add (Union) and Subtract! The usability improvement is real and honest, and I think everyone will really like it.

Next, I’ve decided to add an Intersect selection mode. I’m not sure why I never did this before, to be honest. It was trivial to do, especially since GPC supports it right out of the box. Many other drawing programs offer this — it simply makes sure that the result of combining two selections is the area in which they overlap.

Last, I’m reassigning the keyboard shortcuts for the selection modes. Before, you would hold Control for Add/union, hold the right mouse button for Subtract/difference, and Control+Right for Invert/Xor. These are kind of weird, and non-standard, and plus I needed a key for Intersect. So, in the next update the shortcuts will be Control for Add/union, Alt for Subtract/difference, Control+Right mouse button for Invert/Xor, and Alt+Right mouse button for Intersect.

I’m hoping to have a beta of v3.35 out within a few weeks, and the final release in early-to-mid July.

About these ads