# De Casteljau's algorithm without temporaries / stack

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?

• Are you interested in a single time $t$ or in a continuous algorithm? – Yuval Filmus Sep 16 '17 at 14:36
• A specific $t$ value would be fine i think! – Alan Wolfe Sep 16 '17 at 14:37
• You can reduce space from roughly $N^2$ to roughly $N$ by doing the calculations in the best possible order. This is like pebbling the pyramid graph. – Yuval Filmus Sep 16 '17 at 14:43
• Thanks. What I'm really looking for is some way to have a single "accumulation" register if possible, which is affected by lerps (maybe modified t values or modified control points used) if possible. Maybe a tall order. – Alan Wolfe Sep 16 '17 at 14:45
• There is a pebbling lower bound showing that you need memory $N$ if you want to use this recursive approach. Perhaps it's better to expand things out like you did in your example. – Yuval Filmus Sep 16 '17 at 15:31

## 1 Answer

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 meant 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_0t$.
• $T_1 \gets T_3(1-t) + T_4t$.

The output is in $T_1$.