Hello again! Following is an update on my progress of the second phase of the project.
Current progress: Most of the work was full of algorithm choices. This was something new for me, as until now, I was used to writing code and implementing algorithms which already had been done. In this case, there were implementations, but none specific to the purpose of this project. Most of the Greiner-Hormann implementations did not deal with degenerices. Although there were methods to deal with them, even they weren't perfect, and had to be solved by further processing. The main problem in this case was self-intersections. The algorithm works in such a way that it needs a pointer to the intersection point in the second shape. However, this poses a problem for self-intersections, as there will be a pointer in the same shape. We could probably tackle this by splitting the computation into two at that point, but this will lead to the effort increasing exponentially. Apart from this, these are the problems that I am aware of; There might be several more which will reveal themselves after the implementation. I tried mailing some people who had written research papers for this particular algorithm and some library owners, but I couldn't get a response.
There is also a way to use the scanline-based approach of Qt with curves. However, as it uses the winding number method, we need to allot the line (or curve) a direction: upward or downward. We can't do that with Bezier curves, as ours are not monotonous (I guess this is why CGAL had the condition of monotonocity of curves for set operations). However, I had an idea. Since we store the parametric equations of the curves, we could just as well differentiate it to obtain maxima and minima. this could allow us to split the curve into (maximum) three smaller monotonic curves, and then give it a direction. Alas, this little process is too costly. However, the code for the purpose exists in the files, and can be easily implemented.
This made me think the flattening after intersection approach to be better. basically, we initially find all the points of intersection. After this, we use the QWingedEdge structure which Qt provides. The idea is that after flattening it at that point, we won't lose any precision on the intersection points. This implies there will be no implicit perturbation (as with Qt's flattening approach and original Greiner-Hormann). Even if we flatten it now, the edges shall be considered only for selecting the fill areas. This makes it the more robust approach. We get to use all the processing done by Qt, thus reducing possible regressions. And the implementation is also heavily optimized, so there will be less overhead.
I have been working mostly on this third approach. A lot of time was spent into figuring out how Qt handles it. The code is intertwined and also lacks documentation, making it difficult to figure out where and how exactly does it do it's work. Also it contains implicit conversions, where they use bitwise operators for simple integer and boolean operations, which really confused me. However, after spemding some time, I understood that and removed a pretty significant yet trivial bug from my code, and finally managed to get it to work (partially).
After isolating the intersection-finding routine from the clipping portion, I am trying to get the curves flattened (done) and to unflatten them later. I'm currently working on this, and it would have been done by now, if it weren't for my exams. Due to the prevalent uncertainty of will this pandemic end, and my university's inclination towards trying to conduct offline exams (which was shattered by the second wave), I hadn't anticipated it before the GSoC period. I should have had better foresight, and I guess I should have improvised when I knew about it. However, my exams will be done by 10th, so I will start working at full efficiency by the next two days. I believe the part after the clipping will be fairly straightforward; as all of the dependencies are the same, and I only need to modify a few lines in the original Krita codebase. I believe i can get most of it done in the next few days, and will try my level best for that.