🔢 mathematics

Fast subdivision of Bézier curves

This contribution presents a numerically stable, $O(dn\log{n})$ algorithm for subdividing $d$ -dimensional polynomial Bézier curves using the fast Fourier transform, which furthermore enables efficient updates for extended curves and can be adapted to rational curves and surfaces.

Original authors: Paweł Woźny, Filip Chudy

Published 2026-05-01

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Paweł Woźny, Filip Chudy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an artist drawing a smooth, curved line on a computer screen using a series of "control points" (like invisible magnets that pull the line into shape). This is called a Bézier curve. It is the secret ingredient behind smooth fonts, car designs, and video game graphics.

Sometimes you need to split this line at a specific point into two halves so you can work on just one side. This is called Subdivision.

The Old Way: The Slow Ladder

For decades, the standard way to cut these curves was an algorithm called de Casteljau. The paper describes this as a very reliable, geometric method, but it is slow.

Imagine this as climbing a ladder where each rung requires you to do a lot of math. If your curve has $n$ control points, the time required to cut it grows like the square of $n$ ( $n^2$ ).

If you have 10 points, it takes 100 "steps" of math.
If you have 100 points, it takes 10,000 steps.
If you have 1,000 points, it takes 1,000,000 steps.

The more complex the curve becomes, the painfully slower the old method gets.

The New Idea: The Magical Fourier Machine

The authors of this paper asked: "Can we cut these curves faster?"

They found a way to do this using a mathematical tool called the Fast Fourier Transform (FFT). To use an analogy: Imagine the old method is like manually counting every single grain of sand on a beach to find a specific spot. The new method is like using a high-tech scanner that instantly maps the entire beach and tells you exactly where you are.

By transforming the problem of cutting the curve into a problem of multiplying polynomials (for which the FFT is perfectly suited), they reduced the time complexity to $n \log n$ .

For 10 points, it is about 30 steps.
For 100 points, it is about 700 steps.
For 1,000 points, it is about 10,000 steps.

This is a massive acceleration for complex curves.

The Catch: The Problem of "Shaky Craftsmanship"

However, there was a problem. When the authors tried to use this "magical scanner" directly, the results were numerically unstable.

Imagine trying to measure a tiny ant with a ruler designed for measuring mountains. The math becomes so sensitive that tiny rounding errors in the computer's memory turn into large errors. The paper noted that this new method actually gave the wrong answer for small curves because the computer was "confused" by the tiny numbers involved in the calculation.

The Solution: The "Volume Knob" (Scaling)

To fix this, the authors added a clever trick: a scaling factor.

Imagine the numbers in the calculation as a very quiet whisper. If you try to record a whisper on a loud radio, the static noise drowns it out. The authors realized they could turn up the "volume" (multiply the numbers by a certain factor) before performing the math, and then turn the volume back down afterwards.

This scaled version retained the incredible speed of the FFT method but made the numbers large enough for the computer to process them accurately.

Result: They created a new algorithm that is both fast ( $O(dn \log n)$ ) and accurate, even for curves with many control points.

Other Cool Tricks

The paper also mentions that the same idea of the "magical scanner" can be used for the following:

Rational Bézier curves: Curves where some control points are "heavier" than others (used for perfect circles and cones).
Surfaces: Cutting 3D curved surfaces (like a car hood) instead of just 2D lines.
Derivatives: Calculating how fast the curve changes at any given point (useful for knowing the direction the curve is heading).

The "Hybrid" Recommendation

The authors tested their new method against the old one using Python. They found that the best approach is not just one or the other, but a hybrid strategy that depends on how complex the curve is:

Tiny curves (2-3 points): Use a direct, simple formula (fastest for very small tasks).
Small curves (4-5 points): Stick with the old, reliable de Casteljau method.
Medium curves (6-16 points): Use the new FFT method without the volume knob (it is fast and accurate enough here).
Large curves (16+ points): Use the new FFT method with the volume knob (scaling) to achieve the best speed and accuracy.

Summary

The paper proves that we can cut complex computer curves much faster than before by using a mathematical "scanner" (FFT). While the first attempt was too shaky to be useful, a simple "volume adjustment" (scaling) fixed the errors. Now we have a tool that is significantly faster for complex designs, making computer graphics and design software more efficient.

1. Problem Statement

The paper addresses the computational problem of subdividing a $d$ -dimensional polynomial Bézier curve of degree $n$ at a specific parameter $c \in (0, 1)$ .

Standard Approach: The industry standard is the de Casteljau algorithm, which computes the control points for the left and right segments of the curve.
Limitation: The de Casteljau algorithm has a computational complexity of $O(dn^2)$ .
Goal: The authors aim to determine whether this problem can be solved more efficiently, with the specific goal of achieving a complexity better than quadratic, ideally approaching linear-logarithmic time.

2. Methodology

The authors propose a novel approach based on the Fast Fourier Transform (FFT) and its inverse (IFFT) to accelerate the subdivision process.

A. Theoretical Foundation (Theoretical Solution)

The core insight is recognizing that the formula for the new control points $V_k$ (Equation 2.2) can be rewritten as a convolution of two sequences.

The standard de Casteljau formula involves a sum of products of control points and Bernstein basis polynomials.
By defining two polynomials, $a_n(x)$ and $b_n(x)$ , whose coefficients are derived from the original control points and the parameter $c$ , the subdivision problem becomes equivalent to multiplying these two polynomials.
Polynomial Multiplication via FFT: The coefficients of the product polynomial can be computed in $O(n \log n)$ time using FFT and IFFT.
Complexity: For a $d$ -dimensional curve, the total complexity is $O(dn \log n)$ .

B. Practical Implementation (The Practical Solution)

The direct application of the theoretical FFT method suffers from numerical instability, particularly for higher degrees ( $n$ ), due to:

Rapid vanishing of input signal coefficients for high indices.
The necessity of multiplying small output coefficients by large factorials in the final step, which amplifies floating-point errors.

The Scaling Factor Solution:
To mitigate this, the authors introduce a scaling factor $s$ .

They modify the polynomial coefficients by multiplying them by powers of $s$ ( $s^i$ and $s^j$ ).
This amplifies the input signals for the FFT and keeps them within a numerically stable range.
After the IFFT, the results are rescaled by $s^{-k}$ .
This modified algorithm (Algorithm 4.1) retains the $O(dn \log n)$ complexity but offers significantly improved numerical robustness.

C. Incremental Updates

A unique property of this method is its efficiency in updating results. If a curve of degree $n$ has been subdivided and a new control point is added to generate a curve of degree $n+1$ , the new subdivision can be updated in $O(d)$ time (or $O(dm^2)$ for an increase in degree by $m$ ), rather than recalculating from scratch.

3. Main Contributions

Complexity Reduction: It has been proven that the subdivision of Bézier curves can be performed in $O(dn \log n)$ time, breaking the $O(dn^2)$ limit of the de Casteljau algorithm.
Numerical Stabilization: A scaled FFT-based algorithm has been developed, making the theoretical speed advantage practically usable for curves with medium to high degrees.
Generalization: The methodology has been extended to:
- Rational Bézier Curves: Subdivision of both weights and control points.
- Rectangular Bézier Surfaces: Acceleration of the subdivision of tensor product surfaces.
- Derivatives: More efficient computation of derivatives at the endpoints of curves ( $O(dn \log n)$ versus $O(dn^2)$ ).
Hybrid Strategy: A practical hybrid algorithm has been proposed that selects the best method based on the degree $n$ $n$ :
- $n=2, 3$ : Direct formula (Note 4.1).
- $n=4, 5$ : de Casteljau algorithm.
- $6 \le n \le 16$ : Direct convolution (Equation 3.5).
- $n > 16$ : Scaled FFT algorithm (Algorithm 4.1).

4. Experimental Results

The authors conducted extensive numerical experiments in Python (using NumPy's real FFT/IFFT) on a standard CPU.

Performance (Speed):
- At low degrees ( $n < 9$ ), the de Casteljau algorithm or direct formulas are faster due to FFT overhead.
- For $n > 9$ , the scaled FFT method (Algorithm 4.1) outperforms the de Casteljau algorithm.
- For $n > 16$ , the FFT method is significantly faster (e.g., at $n=50$ , the FFT required ~31s in their specific test setup compared to ~64s for de Casteljau).
Accuracy (Precision):
- The direct theoretical method (without scaling) showed poor numerical stability for higher $n$ .
- The scaled method maintained high precision. For $n=50$ , the mean number of exact significant decimal places remained near the limits of double-precision floating-point arithmetic, confirming its stability.
Rational Curves: The new method also demonstrated speed improvements for rational Bézier curves compared to the rational de Casteljau algorithm.

5. Significance

Theoretical Breakthrough: The paper establishes that the asymptotic lower bound for Bézier subdivision is tied to polynomial multiplication, not quadratic iteration.
Practical Utility: While the pure FFT approach was initially theoretical due to instability, the introduction of the scaling factor makes it a viable tool for high-degree curves used in CAD, CAGD, and computer graphics.
Scalability: The method is particularly valuable for applications requiring the subdivision of high-degree curves or surfaces (e.g., complex modeling, animation), where the quadratic complexity of traditional methods becomes a bottleneck.
Future Directions: The authors suggest that further research into optimizing the scaling factor $s$ based on the specific subdivision point $c$ and various FFT implementations could further improve numerical efficiency for very high degrees.