The following MR contains code required for the improved clipping algorithm of vector shapes for boolean operations. (project under GSoC '21)
Phabricator task: https://phabricator.kde.org/T14574
With the MR, we can calculate all intersection points between two QPainterPaths. Then it can clip the shapes, and perform boolean operations on them.
The intersection finding routine lies mainly in
KisNumericalEngine. It contains all the functions to find points of intersections accurately between curves and curves, lines and curves, and lines and lines. The curve intersections are carried out by the method of implicitization (based on the mathematical foundation here:https://scholarsarchive.byu.edu/facpub/1/). The shapes are then properly processed to insert the intersection points in the right places and to generate a QPainterPath from them.
All of the curves present are marked beforehand and are splitted about the intersection points. After recording them, the clipping is carried out by Qt's original algorithm. Then we resubstitute the curves in the clipped paths, carried out by the function
KisIntersectionFinder::resubstituteCurves() . As all clipping procedures occur only at the vertices, there is no loss of accuracy.
Currently, all three boolean operations - union, intersection, and subtraction work. However, the resubstitution algorithm still remains a bit buggy. Most of the operations on simple shapes such as rounded rectangles, ellipses, work as expected, however unexpected results may be generated when using more complex structures. Apart from this algorithm (
KisIntersectionFinder::resubstituteCurves()), most of the other functions work as expected.
The program can be tested by running the unit tests (not integrated in Krita testing files yet, as Defaulttool doesn't have tests) the working can be seen in this repository.
As code has been successfully integrated, the effect can be seen directly.
- Build this branch.
- Open Krita.
- Open a Vector layer.
- Add any vector shape(s) to it.
- Select the shapes.
- Choose one of the boolean operations (union/intersection/difference).
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.