GSoC/2021/StatusReports/TanmayChavan: Difference between revisions
| Line 25: | Line 25: | ||
=== Algorithm for Bezier curve intersection === | === 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. | * 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. | ||
* Relevant links: | |||
** https://phabricator.kde.org/T14679 | |||
== Progress until now == | == Progress until now == | ||
Revision as of 16:30, 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.
- Relevant links:
Progress until now
Hey!
| Under Construction |
|---|
| This is a new page, currently under construction! |