If the author is here, have you tested and can you comment on the precision of these different methods? I see the code uses some fast-math style approximations for a few operations. How does that compare to Newton-Raphson? And what was the termination criteria for Newton-Raphson… can the runtime be increased or decreased significantly by adjusting the threshold a little?
LegionMammal978•4mo ago
Newton's method isn't really so useful for cubics (outside of lucky initial guesses), given how simple the algebraic expressions are.
Meanwhile, I wonder to what extent the reported improvement over Blender's cubic solver has to do with the approximations this library makes [0]. Algebraic cubic-solving seems to be well-trodden ground (this library's formulas look similar to those in a paper by Holmes [1]), so faster approximations in a limited range can definitely be appropriate to obtain a further speedup, but I would've liked to see a more thorough accuracy analysis.
> Newton’s method isn’t really so useful for cubics (outside of lucky initial guesses), given how simple the algebraic expressions are.
Do you have a better suggestion for a baseline that compares the author’s method? To clarify, it’s clear that this is not evaluating cubics, it’s solving/inverting them, right? The known analytic methods for solving cubics do usually have some precision issues in fp32, depending on what one needs, which is why my question is about precision. (And also wouldn’t mind hearing about the Newton threshold vs perf, since the presentation doesn’t mention it.)
LegionMammal978•4mo ago
Yes, this is about inverting cubics x(t) = P(t), subject to the conditions x(0) = 0, x(1) = 1, x'(t) ≥ 0 for 0 ≤ t ≤ 1.
For Newton's method vs. algebraic methods, I was mainly looking at the "Test results" section of TFA. It looks like I actually misread the graphs somewhat, in that the "numeric solutions" (i.e., Newton's method) both seem to have better average-case performance than the "Blender" methods, but the worst-case performance would worry me. Meanwhile, I know from experience that quartic formulas are pointlessly convoluted compared to iterative methods, so that's where I'd place the threshold.
It's very annoying that the authors don't actually mention where in Blender they got that algebraic method for comparison (Blender has a sprawling codebase with multiple Bézier-curve implementations and even more cubic solvers), nor do they provide the code they used for Newton's method, nor do they fully talk in their paper about how they obtained their own formulas.
They seem not to have put any focus on precision, so I'd assume by default that there are all sorts of pasdroblematic edge cases. Really, precision issues are always a pain when solving polynomials. I can't claim to have any special knowledge about the techniques and tradeoffs in a machine-precision context, since most of what I've played with has been arbitrary-precision arithmetic.
sciencesama•4mo ago
Need a way to create letter transformation and number transformation !
dahart•4mo ago
LegionMammal978•4mo ago
Meanwhile, I wonder to what extent the reported improvement over Blender's cubic solver has to do with the approximations this library makes [0]. Algebraic cubic-solving seems to be well-trodden ground (this library's formulas look similar to those in a paper by Holmes [1]), so faster approximations in a limited range can definitely be appropriate to obtain a further speedup, but I would've liked to see a more thorough accuracy analysis.
[0] https://github.com/jurgus/EasingCubicBezier/blob/5b07bd9d316...
[1] https://users.math.msu.edu/users/newhous7/math_235/lectures/...
dahart•4mo ago
Do you have a better suggestion for a baseline that compares the author’s method? To clarify, it’s clear that this is not evaluating cubics, it’s solving/inverting them, right? The known analytic methods for solving cubics do usually have some precision issues in fp32, depending on what one needs, which is why my question is about precision. (And also wouldn’t mind hearing about the Newton threshold vs perf, since the presentation doesn’t mention it.)
LegionMammal978•4mo ago
For Newton's method vs. algebraic methods, I was mainly looking at the "Test results" section of TFA. It looks like I actually misread the graphs somewhat, in that the "numeric solutions" (i.e., Newton's method) both seem to have better average-case performance than the "Blender" methods, but the worst-case performance would worry me. Meanwhile, I know from experience that quartic formulas are pointlessly convoluted compared to iterative methods, so that's where I'd place the threshold.
It's very annoying that the authors don't actually mention where in Blender they got that algebraic method for comparison (Blender has a sprawling codebase with multiple Bézier-curve implementations and even more cubic solvers), nor do they provide the code they used for Newton's method, nor do they fully talk in their paper about how they obtained their own formulas.
They seem not to have put any focus on precision, so I'd assume by default that there are all sorts of pasdroblematic edge cases. Really, precision issues are always a pain when solving polynomials. I can't claim to have any special knowledge about the techniques and tradeoffs in a machine-precision context, since most of what I've played with has been arbitrary-precision arithmetic.