Skip to content

Draft: Improved clipping algorithm for vector shapes

Tanmay Chavan requested to merge earendil/krita:booleanopswithsub into master

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.

union operation

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.

Test Plan

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

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.
Edited by Tanmay Chavan

Merge request reports