Adam42 Posted March 16, 2014 Posted March 16, 2014 The magic wand tool performs badly on some images. Reproduction steps: 1. Create a 1000x1000 image. 2. Use the add noise effect to add some full intensity noise. 3. Select the magic want tool and pick global flood mode, 50% tolerance. 4. Click somewhere on the image, and press finish. 5. It will take about a minute, and use only one CPU core. The same steps complete in a few seconds on an 800x600 image. A 2000x2000 image doesn't finish in a reasonable amount of time. There's some sort of scaling issue here - surely the performance should be proportional to the number of pixels in the image. Note that I've seen this slow performance of the magic wand tool in an actual photo from my camera, this is just a simple way to recreate it. PC spec: Intel Core i5 2500K (3.3 GHz). 8GB RAM NVIDIA GeForce GTX 660 Windows 7 SP1 64-bit Quote
skullbonz Posted March 16, 2014 Posted March 16, 2014 With the magic wand tolerance set at 50% and global you are locking on to the color you are touching with it,, in all shades. In a 800x600 image there are less of these spots to lock on to than a 2000x2000 image. It doesn't have warp drive you know,lol. Quote http://forums.getpaint.net/index.php?/topic/21233-skullbonz-art-gallery
Adam42 Posted March 16, 2014 Author Posted March 16, 2014 An 800x600 image is just under half a million pixels. The magic wand takes about 5 seconds, which is not too bad. A 1024x1024 image is just over a million pixels. With double the pixels you might expect it to take about 10 seconds. It actually takes about 60 seconds. The 2048x2048 image is just over 4 million pixels, and I got bored waiting for it to finish. The photo I found the problem was 20MP but not as bad for performance as the random noise. Selections with the magic wand were taking over a minute though, which is a right pain when you want to play with the tolerance to find a value that works. I've just done a touch more investigation. It seems most of the time is spent in a polygon cliiper. Here's an example call stack grabbed with Process Explorer: PaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0x16abPaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0x1958PaintDotNet.SystemLayer.Native.x64.dll!gpc_polygon_clip+0xe8[Native Frame: IL Method without Metadata][Managed to Unmanaged Transition]PaintDotNet.SystemLayer.dll!PaintDotNet.SystemLayer.FastMath.CombinePolyLists+0xa92PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.Combine+0xd0PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.FromNonOverlappingScans+0x178PaintDotNet.Core.dll!PaintDotNet.Rendering.GeometryList.FromStencil+0x159PaintDotNet.exe!PaintDotNet.Tools.MagicWand.MagicWandTool.CreateSelectionGeometry+0x449PaintDotNet.exe!PaintDotNet.Tools.AsyncSelectionToolBase`2.<CreateSelectionOnBackgroundThread>b__9+0x5ePaintDotNet.Base.dll!PaintDotNet.Functional.Func.Eval+0x31PaintDotNet.exe!PaintDotNet.Tools.AsyncSelectionToolBase`2.CreateSelectionOnBackgroundThread+0x15aPaintDotNet.Core.dll!PaintDotNet.Threading.ActionWorkItemQueue.OnExecuteNextWorkItem+0x52PaintDotNet.Core.dll!PaintDotNet.Threading.MultithreadedWorkItemDispatcher.WorkThreadProc+0x345mscorlib.dll!System.Threading.ExecutionContext.RunInternal+0x285mscorlib.dll!System.Threading.ExecutionContext.Run+0x9mscorlib.dll!System.Threading.ExecutionContext.Run+0x57mscorlib.dll!System.Threading.ThreadHelper.ThreadStart+0x5d[unmanaged to Managed Transition]clr.dll!CoUninitializeEE+0x66b6bclr.dll!CoUninitializeEE+0x66be6clr.dll!CoUninitializeEE+0x66c58clr.dll!StrongNameSignatureVerification+0x12f5dclr.dll!CoUninitializeEE+0x712f4clr.dll!CoUninitializeEE+0x71282clr.dll!CoUninitializeEE+0x711f9clr.dll!CoUninitializeEE+0x71357clr.dll!StrongNameSignatureVerification+0x12e41clr.dll!GetMetaDataInternalInterface+0x1def2KERNEL32.dll!BaseThreadInitThunk+0xdntdll.dll!RtlUserThreadStart+0x21 If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind. Quote
Rick Brewster Posted March 16, 2014 Posted March 16, 2014 Yeah. It's CPU intensive. If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimiz IT IS NOT EASY TO OPTIMIZE. What algorithm do you think it's using, ffs?! I mean c'mon you're purposefully tossing it into the absolute worst case scenario possible and expecting it to not be "boring." It's definitely faster than 3.5. Quote The Paint.NET Blog: https://blog.getpaint.net/ Donations are always appreciated! https://www.getpaint.net/donate.html
midora Posted March 17, 2014 Posted March 17, 2014 If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind. It's not a big surprize that the function spends a lot of time in a polygon clipping library. Polygon clipping is one of the basic parts of a software like Paint.NET. But optimizing this part is not trivial and it is risky because there are so many boundary cases which makes it difficult to test. From the function name you can expect that Paint.NET uses the General Polygon Clipping Library from University of Manchester. Personally I switched at some point from this library to Clipper form Angus Johnson. It perfoms much better than GPL (in my test cases). This does not mean that Paint.NET should change something in this area. At least not in a Beta phase. Quote
david.atwell Posted March 17, 2014 Posted March 17, 2014 If the "GeometryList.FromStencil()" function is doing what I think it is, I suspect it would be easy to optimize - something like http://en.wikipedia.org/wiki/Marching_squares springs to mind.What is wrong with people? If you're not a programmer, you don't have a clue how easy it is. If you are a programmer, you should know better. How do you have the slightest idea what Rick's codebase looks like? If you're not happy with PdN's performance, make your own image editor. Seriously, I would like to see it. 4 Quote The Doctor: There was a goblin, or a trickster, or a warrior... A nameless, terrible thing, soaked in the blood of a billion galaxies. The most feared being in all the cosmos. And nothing could stop it, or hold it, or reason with it. One day it would just drop out of the sky and tear down your world.Amy: But how did it end up in there?The Doctor: You know fairy tales. A good wizard tricked it.River Song: I hate good wizards in fairy tales; they always turn out to be him.
Rick Brewster Posted March 17, 2014 Posted March 17, 2014 It's not a big surprize that the function spends a lot of time in a polygon clipping library. Polygon clipping is one of the basic parts of a software like Paint.NET. But optimizing this part is not trivial and it is risky because there are so many boundary cases which makes it difficult to test. From the function name you can expect that Paint.NET uses the General Polygon Clipping Library from University of Manchester. Personally I switched at some point from this library to Clipper form Angus Johnson. It perfoms much better than GPL (in my test cases). This does not mean that Paint.NET should change something in this area. At least not in a Beta phase. Interesting ... that is a library worth checking out. The speed boost seems quite nice. I've been using GPC for a long time and one of the appeals is that, well, "it still works" (it hasn't broken, hasn't caused major problems other than out-of-memory which isn't really its fault, hasn't required me to keep up on big source code updates every over release, etc) Quote The Paint.NET Blog: https://blog.getpaint.net/ Donations are always appreciated! https://www.getpaint.net/donate.html
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.