anthrotype
commented
8 years ago Thomas Sederberg, in "Computer Aided Geometric Design", describes a so-called "Horner's algorithm" for evaluating Bezier curves more efficiently than the De Casteljau algorithm, or the lerp approach currently used in cu2qu.
One first has to convert the coefficients of the Bernstein-Bezier polynomial to power (or monomial) form. Then one can evaluate a power basis polynomial of degree n using only n multiplies and adds. This is described by the author as
the fastest algorithm for evaluating a power basis polynomial at a single point.
Sederberg also describes a variant of the same Horner algorithm which works directly on the Bernstein-Bezier polynomial, and hence doesn't require to convert coefficients to power basis.
In my tests, both Horner's schemes are between 2 to 3 times faster than De Casteljau's. I don't have code to show right now, but I might try to apply Horner's scheme to cu2qu and see if it speeds things up.
Of course, an alternative would be to have a C extension module do the expensive job. That would not be so bad. I recently discovered CFFI, and I find it relatively easier than using the CPython API.
behdad
jamesgk
I'm guessing that handcoding cubic_bezier_at() and quadratic_bezier_at() will give a good boost.