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
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
_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
- 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:
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
- The breakLine method:
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:
Let me know if you have any questions.
Best regards, Krzysztof
pt., 12 cze 2020 o 12:03 Moazin Khatri <moazinkhatri(a)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:
> 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
> 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
> 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
> 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:
My code lives
in `src/path/PathSimplifier(.h/.cpp)` and `src/path/PathFlattener(.h/.cpp)`. The temporary
verb "Path > MyOperation" triggers code in
> 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,