De Casteljau's algorithm without temporaries / stack

Question

De Casteljau's algorithm is a method for calculating a point on an order $N$ Bezier curve at time $t$ by performing a linear interpolation between two order $N-1$ Bezier curves at time $t$. You do this recursively until you reach order 0 which is single point / data value.

Calculating a point on an order 1 (linear) Bezier curve with control points $A$ and $B$ at time $t$ is done like this:

$\overline{AB} = A(1-t) + Bt$

Which you can see is just a linear interpolation between $A$ and $B$ at time $t$.

Calculating an order 2 (quadratic) Bezier curve with control points $A$,$B$ and $C$ is done by interpolating between $A$ and $B$, interpolating between $B$ and $C$ and interpolating between those results:

$\overline{AB} = A(1-t) + Bt$

$\overline{BC} = B(1-t) + Ct$

$\overline{ABC} = \overline{AB}(1-t) + \overline{BC}t$

Note that you could expand that out algebraically to get a polynomial in Bernstein form that doesn't use interpolation, but instead can be evaluated directly in one step:

$\overline{ABC} = A(1-t)^2 + 2B(1-t)t+Ct^2$

Calculating an order 3 (cubic) Bezier curve with control points $A$,$B$,$C$,$D$ at time $t$ would continue the pattern by doing a linear interpolation between $\overline{ABC}$ and $\overline{BCD}$ at time $t$.

When evaluating a curve using the De Casteljau algorithm, you need temporary storage. In the $\overline{ABC}$ case you need to first calculate $\overline{AB}$ and $\overline{BC}$ and then you combine those results. The storage needs get larger as the curve order increases.

My question is this:

Is there a way to reformulate the De Casteljau algorithm such that you can still use lerps to evaluate a point on the curve, but without the temporary storage needed?

Answer 1

The OP has indicated in the comments that they are only interested in a specific time $t$. De Casteljau's algorithm can be described as follows:

• Input: order $N$, points $A_0,\ldots,A_N$, time $t \in (0,1)$.
• Calculate $\overline{A_i A_{i+1}} = A_i(1-t) + A_{i+1}t$ for $0 \leq i \leq N-1$.
• Calculate $\overline{A_i A_{i+1} A_{i+2}} = \overline{A_i A_{i+1}} (1-t) + \overline{A_{i+1} A_{i+2}} t$ for $0 \leq i \leq N-2$.
• Continue similarly for $N-2$ more steps.
• Output $\overline{A_0 A_1 \ldots A_n}$.

It is not completely clear what it does it mean to "implement" De Casteljau's algorithm. However, a reasonable informal interpretation of this statement is as follows:

Schedule the computations in De Casteljau's algorithm in a way that uses the least amount of space and the least amount of computations.

Note that the two efficiency measures could potentially conflict.

There is an area of theoretical computer science covering exactly such questions, namely pebbling. See Jakob Nordström's survey-in-making. Your task exactly corresponds to pebbling a height $N$ pyramid. On the one hand, this is known to require $N+2$ pebbles (roughly temporary memory locations). On the other hand, there is a pebbling strategy using $N+2$ pebbles and a linear number of steps (a linear number of computations — we are allowing computing each node, i.e. $\overline{A_i \ldots A_j}$, more than once).

Here is how this pebbling strategy looks like in the case $N=2$:

• $T_1 \gets A_0$.
• $T_2 \gets A_1$.
• $T_3 \gets T_1(1-t) + T_2t$.
• $T_1 \gets A_2$.
• $T_4 \gets T_2(1-t) + T_1t$.
• $T_1 \gets T_3(1-t) + T_4t$.

The output is in $T_1$.

Answer 2

Direct evaluation of the Bernstein polynomials can be done in time linear in $N$, using the recurrence

$$B(t;i,N)=\frac t{1-t}\frac{N-i+1}iB(t;i-1,N),\\B(t;0,N)=(1-t)^N.$$

This can be used to compute the interpolant in time $O(N)$, with $O(1)$ temporary storage.