An update on my tale

Posted by Tanmay Chavan on July 13, 2021 · 3 mins read

Hello there! Has been some time since I've updated this blog, apologies for that. I have no idea how time flied so quickly! Anyway, I had been at work all the while, writing code, maintaining a diary on the side, and I'll be posting my updates over here now.

Week 3: I started writing the code for finding the intersection points between two curves. As expected, there were several problems at first, and the code did not work. However after some debugging I managed to get it to run. Also, started to look into how to approach set operations on shapes.

Week 4: Now I was busy porting the C++ code to work with Qt frameworks. This was a bit trickier than I had originally thought, with slight differences between the STL implementation and Qt implementation causing subtle bugs (std::vector vs QVector). Had to spend most of the time to sort that out. Also, unit testing is really useful, and definetely not as easy as taught in college :P

Week 5: Well, the code to find points of intersection finally was complete (Woohoo :) ).Lesson learnt: don't try to unnecesarily make your code run faster without having the basic code ready :P. Now, I was deep enough into the boolean/set operation research to know it was going to be a bit problematic. Qt's internal approach relies heavily on using line segments and uses Kd-tree for that, and the code is rather complex, intertwined. But, where there's will, there's way :)

Week 6: My code was finally presentable. Spent some time optimizing it. Spent most of the time incorporating my mentor's suggestions in my codebase, and writing better documentation for the functions and classes. At this point, added additional functions to verify the validity of intersection points returned, just to cover all the corner cases.

Week 7: Went knee deep into the clipping algorithm code. the Qt code as is could be potentially used for boolean operations as we have functions for pairwise intersections ( optimized for vertical and horizontal lines with curves, which is what is required by Vatti), however there is a potential overhead as we will have to abandon Kd-tree for R-tree. Then, there's Greiner-Hormann algorithm, which could be just what we need, but again, there is no proper implementation for the variant which handles curves. Also, one supposedly cool thing about Greiner-Hormann is not requiring to find points of self intersections. Now this would ordinarily be alright, but as we're dealing with cubic bezier curves, they might self-intersect, and given a 2D representation, it could lead to unexpected behaviors and possible regressions. But, I guess I've came up with a nice way to work with Vatti algorithm without much overhead (more on that later), let's see how it goes :D