2
$\begingroup$

I'm working on a software program which currently utilizes cubic Bézier splines for generating continuous well-defined function output (only 1 output value per input) in the time domain with varying sample rates. Initially I utilized some root finding code using Cardano's method, in order to convert time domain (X axis) positions into Bezier curve t position values [0, 1]. However, this is proving to have been a poor choice of algorithms for my purpose due to numeric instability. Also the current solution I am using utilizes trigonometry functions, which can be costly on many computer platforms, especially embedded ones.

I am now looking into other algorithms, but it also got me thinking as to whether cubic Bézier curves are even the optimal solution, when the application is not constrained to any particular spline type.

Ideal spline solution properties:

  • Intuitive user interface control of curve segments
  • Very stable "well defined" interpolation sampled output
  • Software optimization friendly floating point algorithm for CPU and possibly FPGA or DSP embedded solutions

Cubic Bézier curve splines and their 2 non-intersecting control points are familiar in many software programs for animation and illustration. So ideally I would continue to use this type of spline (at least on the front end) and choose the optimal solution algorithm which meets these requirements. One solution I am currently working with utilizes the Newton–Raphson method in combination with a binary search to find a t [0, 1] value given an X position, such as with this project: https://github.com/gre/bezier-easing However, this was designed for rendering curves to screens and so I'm not yet sure if it will meet my numeric stability requirements. It does seem that the algorithm utilizes fairly basic math operations though, but if there is a better spline type to use in this type of situation, without having to go through this iterative approach of finding the t value for a given X, that may be a better option. Any helpful pointers would be greatly appreciated.

$\endgroup$
6
  • $\begingroup$ First of all : cubic Bezier splines constitute a good compromise. In general, there is no need to consider higher degree splines. But you do not mention (Non Uniform) Rational Bezier Splines (NURBS): does it mean you have never had a use for them ? $\endgroup$
    – Jean Marie
    Apr 20 '20 at 16:59
  • $\begingroup$ I agree that cubic splines are fine as far as accuracy. My question is what spline type and algorithm would be good for my use case. Which is good numeric stability and computationally efficient to interpolate on the X axis. I have looked into NURBS, but I don't know enough about them yet. I'm good at software logic, but get easily lost when it comes to complex math algorithms. Maybe NURBS and De Boor's algorithm would be a good solution? I will likely need to convert to/from Bezier curves though for drawing to the screen. It may be nice having control points be part of the curve as well. $\endgroup$ Apr 20 '20 at 22:52
  • $\begingroup$ Using the Newton-Raphson method and binary search for resolving curve position t given an x coordinate value is proving to be a good solution for my purpose. So far it seems more numerically stable than the previous solution based on the Cardano method. While it isn't as friendly to SIMD or vector optimizations as the previous code, there are more parameters which can be adjusted to provide a variable range of performance vs precision. I'll follow up with this as the answer, if no one else has any better ideas. $\endgroup$ Apr 24 '20 at 7:34
  • $\begingroup$ @ElementGreen are you sticking with the same answer? I'm currently going after exactly the same problem and was about to use Cardano when I found this... $\endgroup$
    – cubefox
    Nov 27 '20 at 15:42
  • 1
    $\begingroup$ @cubefox Yes, the solution I described at the end of my question is what I ended up using for my application. It works great and I managed to optimize it a bit to the point where it is fairly comparable performance wise to the heavily optimized Cardano root finding code I was using before. This solution seems very stable as well, though I have not yet done any deep analysis of its accuracy. $\endgroup$ Dec 14 '20 at 4:39
1
$\begingroup$

I ended up using the solution described at the end of my question, namely the Newton–Raphson method in combination with a binary search to find a t [0, 1] value given an X position. Code for this can be found with this project: https://github.com/gre/bezier-easing

I was also able to optimize it to the point where it is comparable in performance to the original Cardano method I was using, which was much more complex, difficult to work with, and quite numerically unstable. The performance/accuracy trade off the Newton-Raphson method can easily be tuned as well, just by adding more iterations to the loops. One downside is that it is not as conducive to SIMD optimizations, because each iteration depends on results from the previous one.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.