Mnemonics for bezier curves

Bezier curves, triangles and patches are quite intimidating for most people for how they look, but the equations to construct them consist of really simple pieces.

Barycentric coordinates

You have a set of non-negative variables that sum to 1:

t+u = 1
t+u+v = 1
t+u+v+w = 1

Square bezier patches are obtained by combining two linear coordinates together, as shown later.

Binomial coefficients

Binomial coefficients are another strong part of the beziers.

bi(n, i, j) = n! / (i!*j!) where i + j = n
bi(n, i, j, k) = n! / (i!*j!*k!) where i + j + k = n

Note that i, j, k are again non-negative, just like t, u, v was in barycentric coordinates. These coefficients appear when you exponentiate the barycentric coordinates:

pow(t+u, n)
pow(t+u+v, n)
pow(t+u+v+w, n)

If you expand the first one in sympy, you may notice there's a factorial triangle in the coefficients as n increases:

t + u
t**2 + 2*t*u + u**2
t**3 + 3*t**2*u + 3*t*u**2 + u**3
t**4 + 4*t**3*u + 6*t**2*u**2 + 4*t*u**3 + u**4
t**5 + 5*t**4*u + 10*t**3*u**2 + 10*t**2*u**3 + 5*t*u**4 + u**5

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 A A 5 1
1 6 F K F 6 1

If you forget this coefficient from the bezier, it won't interpolate between the control points.

From these elements we already get the somewhat cryptic definition of cubic bezier triangle on the wikipedia page:

p(t,u,v) = (a*t + b*u + y*v)**3

This in fact provides the whole equation, but in somewhat clumsy format. You've got aaa denoting a corner point and aby denoting center. The bezier equations appear when you rewrite this kind of equations as a sum.

p(t, u) = (a*t + b*u)**n

sum over all combinations of i,j that you get from i+j=n
bi(n, i, j) * pow(t,i) * pow(u, j) * P[i,j]

There we have it. Equivalently bezier triangle comes out like this:

sum over all combinations of i,j,k that you get from i+j+k=n
bi(n, i, j, k) * pow(t,i) * pow(u, j) * pow(v, k) * P[i,j,k]

Bezier patches do it bit different:

bi(n0, i0, j0) * pow(t0,i0) * pow(u0, j0)
* bi(n1, i1, j1) * pow(t1,i1) * pow(u1, j1)
* P[i0,i1,j0,j1]

But essentially it's coming from a similar equation as before:

p(t0, t1, u0, t1) = (a0*t0 + b0*u0)**n0 * (a1*t1 + b1*u1)**n1

Coefficients and equivalent points:
P[0, 0]    a0**2*a1**2*t0**2*t1**2
P[0, 1]  2*a0**2*a1*b1*t0**2*t1*u1
P[0, 2]    a0**2*b1**2*t0**2*u1**2
P[1, 0]  2*a0*a1**2*b0*t0*t1**2*u0
P[1, 1]  4*a0*a1*b0*b1*t0*t1*u0*u1
P[1, 2]  2*a0*b0*b1**2*t0*u0*u1**2
P[2, 0]    a1**2*b0**2*t1**2*u0**2
P[2, 1]  2*a1*b0**2*b1*t1*u0**2*u1
P[2, 2]    b0**2*b1**2*u0**2*u1**2

Rational beziers

Rational beziers are obtained when you add a weight for every bezier coordinate you have:

(bezier(weights * points, t, u)) / bezier(weights, t, u)

Eg. P[i,j,k] becomes W[i,j,k]*P[i,j,k]. This addition produces weighted interpolation between the bezier points.

Bezier derivatives

I've derivated some of the control points separately. In my usecase I end up needing third derivatives of the beziers. It may make sense to derivate just the Bernstein basis polynomial:

b(n, i, j, t, u) = bi(n, i, j) * pow(t, i) * pow(u, j)

Since i+j=n and t+u=1, bernstein polynomial is usually just defined as:

b(n, i, t) = bi(n, i, n-i) * pow(t, i) * pow(1-t, n-i)

Therefore, if you can derive pow(t, i) * pow(1-t, n-i), then you can calculate derivation for bezier as a sum. Differentiating appears to yield:

t**u*(-t + 1)**(n - u)*(n*t - u)/(t*(t - 1))
t**u*(-t + 1)**(n - u)*(n**2*t**2 - n*t**2 - 2*n*t*u + 2*t*u + u**2 - u)/(t**2*(t - 1)**2)
t**u*(-t + 1)**(n - u)*(n**3*t**3 - 3*n**2*t**3 - 3*n**2*t**2*u + 2*n*t**3 + 9*n*t**2*u + 3*n*t*u**2 - 3*n*t*u - 6*t**2*u - 6*t*u**2 + 6*t*u - u**3 + 3*u**2 - 2*u)/(t**3*(t - 1)**3)

There appears to be some pattern here, but it's not entirely clear to me now. A quick search revealed that derivatives for bernstein polynomials can be written as linear combination of lower degree polynomials:

d b(n, i, t) / dt = n * (b(n-1, i-1, t) - b(n-1, i, t))

If you're squinting, there seems to be. n * n-1 * n-2 as derivatives are taken.. There's also: t'(n,i) = t(n-1,i-1) - t(n-1, i) So the derivative seem to in itself form some kind of triangle as well.

Oh. And if you're doing numerical integration, it's usually by weighted sum of fixed sample points. So it may be interesting to know that if you've got tabulated derivatives of bernstein polynomials, you can use it to compute derivatives at those points from any control point.

I'd believe that rule also holds true for rational beziers, but there's the f(t)/g(t) that needs to be handled.

Hmm...

It's possible I'll provide some more mathematics related articles. I feel I'm not done here.

This is going quite into anti-Bret Victor direction. I use analytic methods here for doing stuff I couldn't do otherwise.

Ironically you need analytic methods to produce really good representation of things.

Similar posts