Animated Bézier Curves (2010)(jasondavies.com)
jasondavies.com
Animated Bézier Curves (2010)
https://www.jasondavies.com/animated-bezier/
3 comments
Bezier curves are usually defined as polynomials. It would be interesting to see some algebraic derivation showing how the polynomial form of the curve follows from the construction in the visualization.
It's a lerp of a lerp of a lerp. The algorithm shown is de Castlejau's.
You get the higher order terms by repeatedly substituting the interpolated control points.
Iteration 1 generates 3 interpolated points pi' from 4 control points pi:
E.g. p0' = t * p0 + (1-t) * p1 <- LERP (Linear Interpolation)
p1' = t * p1 + (1-t) * p2
p2' = t * p2 + (1-t) * p3
Iteration 2 generates 2 interpolated points pi'' from 3 interpolated points pi':
p0'' = t * p0' + (1-t) * p1'
p1'' = t * p1' + (1-t) * p2'
Iteration 3 generates 1 interpolated point p0''' (which is the point on the Bezier for that value of t) from 2 interpolated points pi'':
p0''' = t * p0'' + (1-t) * p1''
Expanding out this final equation by substituting in p0'', then p0', etc.:
p0''' = t * p0'' + ...
= t * (t * p0' + (1-t) * p1') + ...
= t^2 * p0' + t * p1' - t^2 * p1' + ...
= t^2 * (t * p1 + (1-t) * p2) + t * p1' + ...
So all those polynomial powers of t are generated by repeatedly multiplying by t and 1-t.
This just suddenly clicked for me a couple of months a ago as I was doing a deep dive on SVG.
TAKEAWAY: Bezier curves are just recursively-applied linear-interpolation. There's nothing magical about them. You or I could have thought them up -- it's the obvious thing to do.
NOTE: The primes here don't mean differentiation. It's just a way of numbering the recursion.
EDIT> spacing, prime comments
You get the higher order terms by repeatedly substituting the interpolated control points.
Iteration 1 generates 3 interpolated points pi' from 4 control points pi:
E.g. p0' = t * p0 + (1-t) * p1 <- LERP (Linear Interpolation)
p1' = t * p1 + (1-t) * p2
p2' = t * p2 + (1-t) * p3
Iteration 2 generates 2 interpolated points pi'' from 3 interpolated points pi':
p0'' = t * p0' + (1-t) * p1'
p1'' = t * p1' + (1-t) * p2'
Iteration 3 generates 1 interpolated point p0''' (which is the point on the Bezier for that value of t) from 2 interpolated points pi'':
p0''' = t * p0'' + (1-t) * p1''
Expanding out this final equation by substituting in p0'', then p0', etc.:
p0''' = t * p0'' + ...
= t * (t * p0' + (1-t) * p1') + ...
= t^2 * p0' + t * p1' - t^2 * p1' + ...
= t^2 * (t * p1 + (1-t) * p2) + t * p1' + ...
So all those polynomial powers of t are generated by repeatedly multiplying by t and 1-t.
This just suddenly clicked for me a couple of months a ago as I was doing a deep dive on SVG.
TAKEAWAY: Bezier curves are just recursively-applied linear-interpolation. There's nothing magical about them. You or I could have thought them up -- it's the obvious thing to do.
NOTE: The primes here don't mean differentiation. It's just a way of numbering the recursion.
EDIT> spacing, prime comments
The algebra does seem more transparent when you use an infix lerp operator: a [t] b meaning (1-t) a + t b. I also tweaked the notation further with (a..b) to mean (b-a) but thought of as "the vector from a to b". Then, for example, a quadratic spline:
d/dt ((a [t] b) [t] (b [t] c)) = 2 (a..b) [t] (b..c)
There is no "usual": you can define them geometrically (as lerps of lerps), symbolically (as polynomials), or even algebraically (as power matrix operations). All three are covered over on https://pomax.github.io/bezierinfo which was on HN yesterday =D
I feel like there are some really neat insights and visuals the can be made combining this with the fourier transform but I can't quite pin it down.
I feel like there's a pun here.
For functions of an interval (in the case of polynomial spline segments, usually {x(t), y(t)} for 0 ≤ t ≤ 1), what you want for an analog of a Fourier transform is to use Chebyshev polynomials. You can use a discrete cosine transform to convert between values at n points appropriately spaced (w/r/t the parameter) along the curve to and from coefficients of the Chebyshev basis polynomials of the form f(x) = cos(n arccos x), in just the same way you would use a discrete Fourier transform to convert back and forth between equispaced points on a periodic interval [0, 2π) and coefficients of trigonometric polynomials. All the same FFT speedup tricks apply, so you only need O(n log n) floating point operations for a polynomial of degree n.
See http://www.chebfun.org/ATAP/atap-first6chapters.pdf
See http://www.chebfun.org/ATAP/atap-first6chapters.pdf
A Primer on Bézier Curves (with interactive animation) -
https://news.ycombinator.com/item?id=14191577