Animated Bézier Curves (2010) | Hacker News Reader

Animated Bézier Curves (2010)

jasondavies.com

106 pointsarm9 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.

http://mae.engr.ucdavis.edu/~farouki/bernstein.pdf

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-19.html

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-34.html

http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-169.html

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

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 are some convenient laws to keep the intermediate steps visualizable.) From this it's clear that the tangents to the start and the end of the curve (at a and c) intersect at b: at t=0 it goes through a with derivative 2(a..b), and at t=1 it goes through c with derivative 2(b..c). Compare https://en.wikipedia.org/wiki/B%C3%A9zier_curve#Quadratic_B.... in the usual notation.

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.

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

I feel like there's a pun here.

A Primer on Bézier Curves (with interactive animation) - https://news.ycombinator.com/item?id=14191577

Reply on news.ycombinator.com