GSoC/2021/StatusReports/TanmayChavan: Difference between revisions

From KDE Community Wiki
< GSoC‎ | 2021‎ | StatusReports
Line 24: Line 24:


=== Algorithm for Bezier curve intersection ===
=== Algorithm for Bezier curve intersection ===
* This was the exact feature which Qt lacked for boolean operations.  
* 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.
 


== Progress until now ==
== Progress until now ==

Revision as of 16:26, 13 July 2021

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.

Progress until now

Hey!


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