# 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? Sep 16, 2017 at 14:36
• A specific $t$ value would be fine i think! Sep 16, 2017 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. Sep 16, 2017 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. Sep 16, 2017 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. Sep 16, 2017 at 15:31

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$$.

• Your example uses T0 out of the blue, which hasn't been initialized. I think you meant that to be T1 ? Jan 18 at 1:15
• You say this method takes "a linear number of steps" - you mean it takes O(N) steps, where the input is the list of numbers A_0,A_1,...A_N? This would be a surprising and extremely useful result, if it's true, but I don't see it. It looks to me like your example visits all (N+2)(N+1)/2 nodes of the pyramid, so it takes exactly that number of steps (specifically, you wrote out the steps for N=2, and indeed the number of steps is exactly (N+2)(N+1)/2 = 4*3/2 = 6). Maybe I'm misunderstanding the claim you're making. Jan 18 at 1:27
• Linear in the number of vertices in the pyramid, which is $\Theta(N^2)$. Jan 18 at 11:29
• @alanwolfe I fail to see how this avoids temporary storage and answers the question !?
– user16034
Jan 18 at 11:36

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.