Hi there,
I am dealing with some urgent stuff at work, but had some time to look at the code today - here's the URL I used if others want to review it too. https://gitlab.com/moazin/inkscape/-/compare/85e35906c09996116f4c86e698192a8...
I mainly have some a bunch of coding style comments: - You don't need a semicolon after a method body. - You don't need explicit initializers for fields that have default constructors, example: https://gitlab.com/moazin/inkscape/-/compare/85e35906c09996116f4c86e698192a8... _pt() and _q() are unnecessary. - You don't need to explicitly define a trivial destructor. - Don't define a virtual destructor unless the type is actually designed for being derived from. PathSimplifier::FitPoint shouldn't have one. - clang-format is your friend, please use it. It's much easier to follow the style guide this way. - There are some constness problems. For example, both the Curve and Line parameters to PathFlattener::approximatesEnough should be const references rather than mutable references. - In several places, you pass Geom::CubicBezier by value, which creates unnecessary copies. - Characters are free, but time is scarce - readable names are important. For example: https://gitlab.com/moazin/inkscape/-/compare/85e35906c09996116f4c86e698192a8... I guess "stP" stands for "start point" and "enP" for "end point", and in this case it's easy to see where the values originate, but in general, cryptic names like this should be avoided. I also recommend using the more descriptive function "distance" instead of the function "L2". - The breakLine method: https://gitlab.com/moazin/inkscape/-/compare/85e35906c09996116f4c86e698192a8... This function follows the pattern: "if (a boolean flag), do the interesting operation, then do something very simple". This is not the best way to factor code into functions. Instead, the function should only do the thing inside the if statement, and the if statement should be outside (potentially in another helper function). - The structure of breakCubicInternal is rather messy, with the level <= 0 exit condition being checked in multiple places and the entire code being duplicated. You should rewrite this so that there is only one copy of the subdivision code.
Besides the above, I recommend writing some tests for your code. Writing tests is the only way to ensure that your code actually works and continues working. Another reason is that if a design is easy to test, it is often also easy to understand and modify. If you haven't used it yet, take some time to learn GTest - 2Geom already has some unit tests based on it.
I see that your code uses recursive subdivision for flattening. There is an alternative approach which uses parabolic approximation and produces fewer segments, described in this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.5344&rep=re...
Let me know if you have any questions. Best regards, Krzysztof
pt., 12 cze 2020 o 12:03 Moazin Khatri moazinkhatri@gmail.com napisał(a):
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:
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.
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).
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.
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`)
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