Improve Performance of Liquify Transform Tool Mode

Things done:

• Speed Improvement 1.: A quadtree-like structure for points in the grid.
• Speed Improvement 2.: Areas outside of the affected-bounds are just copied over.
• Speed Improvement 3.: Polygons that are rects and the same in dst and src are just copied over instead of calculated.
• Change to Four-point interpolator to not fall apart as often as it did before.
• Added tests and benchmarks for Four Point Interpolator.
• Added benchmarks for Liquify Transform Tool.
• Added unit tests for Grid Iteration Tools.

Speed Improvement 1 and 2:

Speed Improvement 3:

Benchmarks: Note:

• smaller % = better
• initialization is much longer, but it still only takes a few ms., and it happens only once, so there's nothing to worry about.
• editing points is way faster now, and that's good, but rendering is more important
• testRunOnX makes a big Z with the liquify "brush" on the device/image. Most of the grid remains unchanged, that's why it's so much faster.
• testSmallChangeOnX makes a tiny Z, so there is even more space for optimization, hence so much different.
• the second parameter Y in testRenderingMask (X, Y) means whether it's on QImage (true) or not (false)
• typical mask contains one area with change, most of the area is unchanged - a lot of
• simpler mask changes the whole image, but all the polygons are convex (not folded one over another)
• liquify_mask_config changes the whole image and contains a lot of polygons folded one over another
• testCheckingIfPolygonsAreConvex is necessary for the last optimization that includes merging rectangles together and processing them at the end
• first commit: after all my changes
• second commit: after all changes except for checking for convex polygons and merging the rectangles (to see whether it doesn't introduce slowness, but it seems like it doesn't, except for the testSmallChange, because the 8ms suddenly matters when the whole operation is 20ms - but for normal changes it seems to improve things)
• third commit - after my changes to make sure my benchmark don't safe assert, breaking the calculations... so it's basically the starting point
• so, first column: "start-end" shows % of performance improvement over the starting commit
• second column: beforemerge-end shows % of performance improvement thanks to merging the rectangles (that's why it's all >90%)

TODO

• Ensure no leaks (and make a test for it?)

• Ensure clean up before any initialization

• Ensure 100% coverage of all functions to use the correct container

• Benchmark for "read from XML" in transform worker (note: probably doesn't matter, the mask is bottlenecked by the 3s of update delay anyway...)

• Benchmark original points container vs just getting indexes from the grid (the second for sure would be faster)

• Remove original points container (replace with smart grid indexes calculation thingy)

• Copy unchanged areas using the same function

• Fast copy QImage areas using memcpy or something?

• Add test with a selection

• Add image tests and check them

• Lynx3d's bug: rectangular selection + QRect

• Lynx3d's bug: https://bugs.kde.org/show_bug.cgi?id=507515

Test Plan

(TODO: Tell us how to test the changes you made.)

Formalities Checklist

• I confirmed this builds.
• I confirmed Krita ran and the relevant functions work.
• I tested the relevant unit tests and can confirm they are not broken. (If not possible, don't hesitate to ask for help!)
• I made sure my commits build individually and have good descriptions as per KDE guidelines.
• I made sure my code conforms to the standards set in the HACKING file.
• I can confirm the code is licensed and attributed appropriately, and that unattributed code is mine, as per KDE Licensing Policy.
• Does the patch add a user-visible feature? If yes, is there a documentation MR ready for it at Krita Documentation Repository?

Reminder: the reviewer is responsible for merging the patch, this is to ensure at the least two people can build the patch. In case a patch breaks the build, both the author and the reviewer should be contacted to fix the build. If this is not possible, the commits shall be reverted, and a notification with the reasoning and any relevant logs shall be sent to the mailing list, kimageshop@kde.org.