Fast subdivision of Bézier curves
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914518886514688 |
|---|---|
| author | Woźny, Paweł Chudy, Filip |
| author_facet | Woźny, Paweł Chudy, Filip |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15691 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast subdivision of Bézier curves Woźny, Paweł Chudy, Filip Graphics Numerical Analysis 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. |
| title | Fast subdivision of Bézier curves |
| topic | Graphics Numerical Analysis |
| url | https://arxiv.org/abs/2509.15691 |