enter image description here

Using the diagram above, calculating a point on a quadratic Bezier curve at time $t=0.6$ using the De Casteljau Algorithm is done like this:

  1. Linearly interpolate between $P_0$ and $P_1$ for time $t=0.6$ to get a point $Q_0$.
  2. Linearly interpolate between $P_1$ and $P_2$ for time $t=0.6$ to get a point $Q_1$.
  3. Lastly, linearly interpolate between $Q_0$ and $Q_1$ for time $t=0.6$ to get the point on the curve $R$, where the black dot on the blue line is.

Is there any value or meaning in using different $t$ values for each linear interpolation instead of using $t=0.6$ for each of them?

For instance, one modification could be to square the weight when interpolating between $Q_0$ and $Q_1$. It would still have the property of going from 0 to 1, but would do so non linearly.

Other modifications may include using $1-t$, using a constant, or maybe using $t*0.5+0.5$.

Is there any value to doing this which a regular bezier curve couldn't give you? Is there a more generalized term which includes this type of a curve or modified version of De Casteljau's Algorithm?

In short, I'm just wondering if this sort of thing is a known thing with a known name, and what sort of functionality it can get you.

Thanks!

Exploration: $1-t$

As an alternative to this algorithm, you can also write an equation to evaluate Bezier curve points in Bernstein form like the below, where $s = 1-t$, and $A,B,C$ are the control points of the curve:

$P = As^2 + 2Bt + Ct^2$

Which can also be seen mathematically as a linear interpolation between two linear interpolations, just like the De Casteljeau algorithm, of course.

If using $(1-t)$ instead of $t$ for the lerp between $Q_0$ and $Q_1$, and arrange it back into Bernstein form I get the below:

$P = Bs^2 + (A+C)st + Bt^2$

That indicates that at least for this modification, the result is still a Bezier curve of the same degree, but the starting and ending control point both have the value of B, while the middle control point has a value of (A+C).

Exploration: $t=0.7$

On the other hand, if i use a constant value of $t = 0.7$ for the last interpolation I get this:

$P = 0.3As - (0.4B - 0.7C)t + 0.7B$

Which puts us at a linear interpolation (a linear Bezier curve), plus a constant.

Exploration: $t^2$

If i use $s^2$ and $t^2$ instead of $s$ and $t$ for the last interpolation, then put it back in Bernstein form, I get the below, which is a cubic Bezier curve with control points: $A$, $B/3$, $B/3$, $C$.

$P = As^3 + B/3 * 3s^2t + B/3 * 3st^2 + Ct^3$

up vote 4 down vote accepted

If you use a different value in each linear interpolation step, you get the "blossom" or "polar form" of the curve. The basic idea is to replace a degree $n$ function of one variable (the original Bezier curve) with a symmetric multi-affine function of $n$ variables. This is a very powerful idea indeed, and makes many of the facts about Bezier and b-spline curves plainly obvious. Among other things, the blossoming idea gives us a very good way to label the intermediate points that arise in the de Casteljau and de Boor algorithms.

The main theorem is as follows: for each polynomial $f$ of degree $n$, there exists a symmetric multi-affine function $F$ (called the polar form of $f$) such that $F(x,\ldots,x) = f(x)$ for all $x$.

Some examples are:

  • If $f(t) = t^2$, then $F(u,v) = uv$
  • If $f(t) = 2t$, then $F(u,v) = u + v$
  • If $f(t) = (1-t)^3$, then $F(u,v,w) = (1-u)(1-v)(1-w)$

This is just standard algebra, though the concept and the terminology are no longer part of the standard curriculum. Usage in CAD actually goes back to de Casteljau himself. He wrote some internal Citroen papers on the topic in the 1960's, using the term "courbes à pôles". His work was unknown until much later, which is why Bezier usually gets all the credit. His "poles" are what we would call "control points", today. It was re-invented in the 1980's by Lyle Ramshaw who coined the term "blossomimg".

There is a good description of all of this in this book by Gallier.

There is a book by de Casteljau, available either in English or French. If you can read French, I recommend that version. In the English version, the translation is not very good, and the typesetting is horrible. In either language, the text is difficult to understand, because the approach is so unconventional, by today's standards.

Lyle Ramshaw's original report is available here.

See also the answers to this question.

  • Very interesting thank you! This makes me wonder if all polynomials (or maybe just many) can be broken down into some combination of linear interpolations? – Alan Wolfe Dec 2 '16 at 14:44
  • It's interesting to see that Ramshaw describes turning a quadratic into a bilnear map in the abstract. As this is relevant to the discussion, I self published a computer graphics paper on using the bilinear texture interpolation feature of modern GPUs to calculate Bezier curves when storing only the control points in the texture. It extends to higher orders, piecewise curves and more. blog.demofox.org/2016/02/22/… – Alan Wolfe Dec 2 '16 at 14:52
  • 1
    > wonder if all polynomials (or maybe just many) can be broken down into some combination of linear interpolations -- Yes, every polynomial has a polar form. – bubba Dec 3 '16 at 1:59
  • Hey bubba, I've been reading the sources and I see that this is useful for labeling, splitting and joining curves. Do you know if it has uses outside of curves? Eg. Is there anything meaningful to say about making a symmetric multiaffine function and then evaluating the function off of the diagonal? – Alan Wolfe Dec 5 '16 at 16:11
  • 1
    Yes, the off-diagonal values are the coordinates of various "control" points, like the Bezier control points and the deBoor points used to define b-splines. – bubba Dec 12 '16 at 1:04

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.