GSoC/2021/StatusReports/TanmayChavan

From KDE Community Wiki

Krita - Smarter boolean operations on vector shapes

In Krita, performing boolean operations on vector shapes leads to a large number of unnecessary nodes. This happens because Qt lacks a proper algorithm to find the intersection point of two Bezier curves. I plan on implementing a numerically stable as well as efficient algorithm to find the intersections of two Bezier curves.

Mentors

  • Iván Santa María
  • Dmitry Kazakov

Goals

  • Create a new algorithm to compute intersections of Bezier curves using implicitization
    • done!
  • Manage the dependencies and implement parts of Qt private modules in Krita codebase
    • done!
  • Integrate the algorithm with current intersection finding routine
    • pending
  • Implement the new routine for boolean operations
    • pending
  • Write proper documentation and unit tests for all the above goals while doing them
    • ongoing


Status Report

Algorithm for Bezier curve intersection

  • This was the exact feature which Qt lacked for boolean operations. As a result, it flattened the curves which in turn made too many nodes. I have implemented an algorithm to compute the intersection points using the implicit representation of a cubic Bezier curve. I have finished implementing curve-curve, line-curve intersections by now. The algorithm works well even with double precision. But, the curve-curve intersections can get really costly. On an average, a single curve-curve intersection-finding routine requires ~280 microseconds. However, it is reported this is the fastest method for curves with degree 5 or less. The line-line intersection point is obtained in the same manner as Qt did.
curve-curve intersection
curve-curve intersection
Line-curve intersection
Line-curve intersection

Qt private dependencies

  • As the set operations were handled by the class QPathClipper which lies behind the Qt API, I had to manage the dependencies so that the new implementation would not rely on Qt private modules. This was relatively easy as QPathClipper was fairly independent and it's dependencies didn't have too many dependencies. I also managed to get a downstream copy of the QPainterPath class, albeit had to skip some parts (the PathStroker related part) as it was too closely linked to other Qt private modules. However, it was not required for the purpose of the current tasks. So, I have managed to get the project to run without any private or additional dependencies.

Progress until now

Hey!


 
Under Construction
This is a new page, currently under construction!