Hi everyone,
I would like to provide a status update on the Path Library Improvement project. Since this is my first report to the list (the last one wasn't public), I'd like to discuss everything done so far. This report is huge and quite technical, so if you want a short version, it is this:
"I have successfully written a relatively short piece of code that creates simplification results totally identical to the livarot version. The algorithm is the same as livarot and is nearly as fast. I'm about to start cleaning it, documenting it and integrating it with simplify, lpe-simplify and pencil tool. This will be done within the next two days."
Now the detailed version:
According to the original schedule, I was supposed to work on the Path Simplification feature and that is what I have been doing. I started with writing some boilerplate code that will allow me to trigger my own Path Simplification code in Inkscape. This is so that I can compare its results with livarot based simplification quickly.
I started exploring the simplification algorithm of lightvarot and wrote some path flattening (the process of approximating a path by line segments) myself. I integrated these in Inkscape and the algorithm produced pretty satisfying results but it was too slow. In a "Release" build, the performance might be okay for a "Path > Simplify" but would do pretty bad in live path effects. For what it's worth, I also created an animation explaining this algorithm. You can find it here: https://moazin.github.io/simplification-algos.html
Disappointed by its performance, I replaced the main part of the algorithm with its equivalent from livarot (that's explained in the link attached under the title "Livarot / Simplifying the curve". The performance improved but there were significant differences between the results. I had a choice here, I could either just rewrite a cleaner version of livarot's code or understand what's causing the differences and fix those. I chose to do the latter.
I started following the procedure "draw paths -> trigger both algorithms -> debug both simultaneously -> understand and fix the differences -> repeat". Going down this route, I understood almost all the parts of livarot and was even able to discover/fix bugs in both livarot and lightvarot. Here are the reasons behind the differences:
1. The codes for flattening the paths were different so obviously there were differences in the results. I simply implemented livarot's algorithm for splitting cubic beziers to solve this problem.
2. There is an iteration of Newton-Raphson method. (I'll probably add what this iteration is and what it does in the link attached above soon, it's mostly math stuff). I suspect that the code for this iteration in lightvarot is mathematically incorrect, so I fixed it. I will do the derivation again to be sure if it's really a bug though. Anyways, I fixed it by replacing the constants from my derivation (which are identical to the livarot version).
3. There is a special portion in livarot code which fixes what livarot calls the "splotch" problem. When the number of points you're fitting are few, you can sometimes get a fit which fits the points correctly but overall doesn't fit the polyline properly. There is some special code that calculates error differently to take into account this situation and thereby avoid bad fits. My code was missing this code, so I wrote it.
4. There is a slight optimization in livarot that reuses some calculations and I suspect it compromises on the accuracy of the fits. I need to investigate more to be sure. I fixed it in livarot by simply using the non-optimized version. (There are two `AttemptSimplify`)
5. There were some silly bugs in livarot's non-optimized `AttemptSimplify`. A minus was replaced by a plus and a weight factor was commented. Fixed both of those on the livarot side.
After doing all of these changes, both versions are producing totally identical results. The computation time is also mostly identical. There is a very minor difference in the flattening part which I'm working on.
The code can be found at: https://gitlab.com/moazin/inkscape/-/tree/integrating-livarot-low-redesign My code lives in `src/path/PathSimplifier(.h/.cpp)` and `src/path/PathFlattener(.h/.cpp)`. The temporary verb "Path > MyOperation" triggers code in `src/path/path-myoperation(.h/.cpp)`.
The commit history is pretty much garbage since I have been experimenting a lot. Over the weekend I'll be cleaning this code, documenting it properly and integrating it in lpe-simplify and the pencil tool. I'll add the final resulting code "cleanly" on a fresh branch.
An interesting part of this project is the "design" of whatever code I write. But I think it's too early for me to start thinking about it because as I move towards Boolean Operations, a lot of new things will be discovered and whatever "design" I decide on would change. So, IMHO, this can be discussed later once I am done with Boolean Operations.
Please feel free to ask any questions that you may have or provide feedback.
Thank you, Moazin