1
$\begingroup$

I only realized from this question and the answers to it that quadratic Bézier curves are the envelopes of the lines used to compute them iteratively. That is, if a quadratic Bézier curve for points $P_0$, $P_1$, $P_2$ is constructed by linearly interpolating between $P_0$ and $P_1$ and between $P_1$ and $P_2$ and then again linearly interpolating along the line between the two resulting points, then the Bézier curve is the envelope of those lines.

I'm wondering whether this generalizes to higher Bézier curves. An $n$-th order Bézier curve can be analogously constructed by $n$ iterations of linear interpolation. Is it the envelope of any of the lines used in that construction? Or of the higher-order curves that are generated in the intermediate stages of the construction? Or both? If so, how can we see this most easily?

An answer for cubic Bézier curves would already be interesting, even if it doesn't generalize to higher orders.

(I tried searching for “Bézier” and “envelope” but didn't find anything useful, partly because the top hits are all about an Inkscape extension called Bezier Envelope.)

$\endgroup$
  • $\begingroup$ Yes is the answer en.wikipedia.org/wiki/Bézier_curve#Higher-order_curves $\endgroup$ – Coolwater Jun 22 '18 at 15:43
  • $\begingroup$ @Coolwater: I read that article, and I don't see where it says that. It shows that higher-order Bézier curves can be constructed by iterated interpolation, as I mentioned in the question. It doesn't mention envelopes at all, as far as I can tell. The animated diagrams certainly look as if the curves might be envelopes, but that might be a wrong impression. $\endgroup$ – joriki Jun 22 '18 at 15:49
  • $\begingroup$ You'll find more useful stuff if you search for "de Casteljau" "curve tangent" $\endgroup$ – bubba Jul 21 '18 at 7:53
1
$\begingroup$

As you said, a quadratic Bezier curve is the envelope of lines whose end-points are moving along two straight lines.

In just the same way, a cubic Bezier curve is the envelope of lines whose end-points are moving along two quadratic curves. You can see this by looking at the last linear interpolation in the de Casteljau algorithm.

And so on. In general, a Bezier curve of degree $m$ is the envelope of lines whose end-points are moving along two curves of degree $m-1$.

Here are the details for the cubic case. Suppose the cubic curve has control points $\mathbf{A}$, $\mathbf{B}$, $\mathbf{C}$, $\mathbf{D}$.

enter image description here

Then its equation is $$ \mathbf{P}(t) = (1-t)^3\mathbf{A} + 3t(1-t)^2\mathbf{B} + 3t^2(1-t)\mathbf{C} + t^3\mathbf{D} $$ In the final step of the de Casteljau algorithm, this is expressed as $$ \mathbf{P}(t) = (1-t)\mathbf{H}(t) + t\mathbf{K}(t) $$ where \begin{align} \mathbf{H}(t) &= (1-t)^2\mathbf{A} + 2t(1-t)\mathbf{B} + t^2\mathbf{C} \\ \mathbf{K}(t) &= (1-t)^2\mathbf{B} + 2t(1-t)\mathbf{C} + t^2\mathbf{D} \end{align} Clearly $\mathbf{H}$ and $\mathbf{K}$ are quadratic Bezier curves, which are shown in green and red respectively in the picture above.

Differentiating the original curve equation, and re-arranging, we get $$ \mathbf{P}'(t) = 2\bigl[(1-t)^2(\mathbf{B} - \mathbf{A}) + 2t(1-t)(\mathbf{C} - \mathbf{B}) + t^2(\mathbf{D} - \mathbf{C}) \bigr] $$ Then, a little algebra confirms that, in fact $$ \mathbf{P}'(t) = 2\bigl[\mathbf{K}(t) - \mathbf{H}(t) \bigr] $$ This shows that the line joining $\mathbf{H}(t)$ and $\mathbf{K}(t)$, which is constructed in the final step of the de Casteljau algorithm, is tangent to the cubic curve $\mathbf{P}(t)$.

There is further discussion on this page.

$\endgroup$
  • $\begingroup$ Thanks for the answer! You write: "You can see this by looking at the last linear interpolation in the de Casteljau algorithm." How can I see this? I can see that the higher-order Bézier curve is traced out by points on these lines -- but how can I see that it's the envelope of these lines? $\endgroup$ – joriki Jul 20 '18 at 15:54
  • $\begingroup$ Because the lines are all tangent to the final curve $\endgroup$ – bubba Jul 20 '18 at 16:34
  • $\begingroup$ Thanks for the nice graphic! I was apparently very unclear in formulating this question, as it keeps getting misunderstood :-) (This also happened with the deleted answer.) I'm aware that the property of being an envelope is characterized by the lines being tangent to the curve. I can also see that the lines appear to be tangent to the curve here. What I was after was a way to "see" this in the sense of proving it, not in the sense of looking at appearances on diagrams (as nice as they are). $\endgroup$ – joriki Jul 21 '18 at 5:10
  • $\begingroup$ The tangency is a basic property of the de Casteljau algorithm. In fact, one of the nice things about the de Casteljau algorithm is that it gives you a point and first derivative vector from the same calculations. A little algebra shows that the first derivative of the curve at parameter value $t$ is parallel to the line constructed in the final step of the de Casteljau algorithm. I can write out the details, if you want, but I'm sure you could do the calculations yourself. $\endgroup$ – bubba Jul 21 '18 at 7:05
  • $\begingroup$ There's an explanation here: pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/… $\endgroup$ – bubba Jul 21 '18 at 7:08
0
$\begingroup$

This answer merely elaborates on the computation shown by @bubba for cubic Bezier curves. It is an alternative derivation for the hodograph as defined in the link provided in the comments.

For a sequence of control points $a_0, a_1, \ldots$ and indices $0 \leq k \leq m$ let's write $$p(k,m; t)$$ for the Bezier curve of degree $m-k$ with control points $a_k, a_{k+1}, \ldots, a_m$. These can be defined recursively for $0\leq k < m$ by $$\begin{eqnarray} p(k, k; t) &=& a_k\\ \tag1 p(k, m; t) &=& (1-t)\, p(k, m-1;t) + t\, p(k+1, m; t) \end{eqnarray} $$

for $t\in [0,1]$. By induction on $m-k$ it follows that $$\tag2 p'(k, m; t) = (m-k) \left(p(k+1, m; t) - p(k, m-1; t)\right)$$ (where this is interpreted as simply $0$ if $k=m$). Indeed $p'(k, k; t) = 0$ and for $m > k$ by the recursive definition $(1)$ above: $$\begin{eqnarray} p'(k, m; t) &=& p(k+1, m; t) - p(k,m-1;t) + \\ && (1-t)\, p'(k,m-1; t) + t \,p'(k+1, m;t)\\ &=& p(k+1, m; t) - p(k,m-1;t) + \\ && (1-t)(m-k-1)\,(p(k+1,m-1;t)-p(k, m-2;t)) + \\ && t (m-k-1)\, (p(k+2, m;t) - p(k+1, m-1; t))\\ &=& p(k+1, m; t) - p(k,m-1;t) + \\ && (m-k-1)\,((1-t)\,p(k+1,m-1;t) + t \, p(k+2, m;t))-\\ && (m-k-1)\,((1-t)\, p(k, m-2; t) + t\, p(k+1, m-1;t))\\ &=& p(k+1, m; t) - p(k,m-1;t) + \\ && (m-k-1)\,(p(k+1, m; t)- p(k, m-1; t))\\ &=& (m-k)\,(p(k+1, m; t) - p(k,m-1;t)) \end{eqnarray} $$

Now $(1)$ and $(2)$ show that the segment $\left[p(k, m-1;t), p(k+1,m;t) \right]$ is indeed tangent to $p(k, m; s)$ at $s=t$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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