Fast subdivision of Bézier curves
This work addresses a computational bottleneck in geometric modeling for computer graphics and CAD, though the improvement is incremental and limited to specific scenarios.
The authors propose a faster algorithm for subdividing Bézier curves, reducing time from O(dn^2) to O(dn log n) using FFT, with a numerically stable variant. They also show O(d) updates when adding control points.
It is well-known that a $d$-dimensional polynomial Bézier curve of degree $n$ can be subdivided into two segments using the famous de Casteljau algorithm in $O(dn^2)$ time. Can this problem be solved more efficiently? In this paper, we show that it is possible to do this in $O(dn\log{n})$ time using the fast Fourier transform and its inverse. Experiments show that the direct application of the new method performs well only for small values of $n$, as the algorithm is numerically unstable. However, a slightly modified version -- which still has $O(dn\log{n})$ computational complexity -- offers good numerical quality, which is confirmed by numerical experiments conducted in \textsf{Python}. Moreover, the new method has a nice property: if a Bézier curve is extended by an additional control point, the subdivision can be updated in $O(d)$ time. A similar idea can be applied to speed up the subdivision of rational Bézier curves and rectangular Bézier surfaces, as well as to compute the derivatives of Bézier curves more efficiently.