2025/09/19 by Paweł Woźny, Woźny, Paweł, Filip Chudy +1 · 1 citation
Engineering · #3D Shape Modeling and Analysis #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Graphics (cs.GR) #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2509.15691
openalex publication_date 2025/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(dn2) time. Can this problem be solved more efficiently? In this paper, we show that it is possible to do this in O(dnlogn) 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(dnlogn) computational complexity -- offers good numerical quality, which is confirmed by numerical experiments conducted in \textsfPython. 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.