4
$\begingroup$

I have a cubic Bézier spline with four points: P1, C1, C2 and P2. I'm using De Casteljau method to split the spline to two parts at a given point x, 0 <= x <= 1.

The question is, can I use the same algorithm to split the spline twice? Say, that I want to split spline in points x1 = 0.25 and x2 = 0.75. First I split the spline S to S1 and S2 at the point 0.25. Next, I re-evaluate x2, since now it's on the segment [0.25, 1]. If I then subtract 0.25 from everything, I get 0.5 on [0, 0.75], which, scaled up to [0, 1] gives me x2'=0.(6). Then I split S2 on point x2 to get another two splines and the center one is the one I'm seeking.

Is the re-calculation of split point on the second spline valid? I mean, will 0.(6) on the second spline will match the original 0.75 on the initial one?

$\endgroup$

2 Answers 2

4
$\begingroup$

Your approach will work, but you can actually run two instances of the de Casteljau algorithm at the same time, which will save you some computations and make the construction clearer.

The best way to explain this is by using the concept of "blossoming". This was actually the technique used by de Casteljau himself, in the 1960s, though it didn't become popular until much later. Nowadays, it's easy to find descriptions on the internet.

Among other things, blossoming gives us a nice way to label the points that arise during the de Casteljau algorithm. The labels make it clear how the points are calculated as convex combinations of previous ones.

Here is the blossom diagram for a cubic curve, split into three pieces by splitting at the parameter values $a= \tfrac14$ and $b=\tfrac34$.

enter image description here

The original curve has control points $000, 001, 011, 111$.
The first segment has control points $000, 00a, 0aa, aaa$.
The second segment has control points $aaa, aab, abb, bbb$.
The third segment has control points $bbb, bb1, b11, 111$.

All the points in the diagram are computed as convex combinations, so ...

P_00a = (1-a)*P_000 + a*P_001
P_00b = (1-b)*P_000 + b*P_001  
P_01a = (1-a)*P_001 + a*P_011
...
P_0aa = (1-a)*P_00a + a*P_01a 
...

and so on.

$\endgroup$
1
  • $\begingroup$ Very clear answer... $\endgroup$
    – Jean Marie
    Commented Jun 16, 2021 at 14:51
3
$\begingroup$

You can use De Casteljau's algorithm, yes.

Let's say you wish to split $t_1$ to $t_2$ into a new cubic Bézier, with $0 \le t_1 \lt 1$ and $t_1 \lt t_2 \le 1$.

You first split at $t_1$, and keep the final point in the initial curve as the final point, last subdivision point at each subdivision step as the control point, and the point De Casteljau's algorithm ends up as the starting point.

That gives us the intermediate curve. We split this one, noting that the split point is not $t_2$, but $(t_2 - t_1) / (1 - t_1)$, because the split point is relative to the curve at hand; and this intermediate curve starts at $t_1$ in the original curve. (For $t_1 = 1/4 = 0.25$ and $t_2 = 3/4 = 0.75$, the second split point is at $2/3 \approx 0.667$. By $0.(6)$, OP refers to $2/3$ too, so we are in agreement.)

For the resulting curve, you use the starting point from the intermediate curve, first subdivision points as the control points, and the point De Casteljau's algorithm ends up with as the final point.


There is a direct algebraic formula for the coefficients, too, but it isn't as numerically stable as De Casteljau's algorithm. However, it can be useful in some cases.

In vector notation, a cubic Bézier curve from $\vec{p}_0$ to $\vec{p}_3$ with control points $\vec{p}_1$ and $\vec{p}_2$ for $0 \le t \le 1$ is described by the vector-valued function $$\vec{p}(t) = (1 - t)^3 \vec{p}_0 + 3 (1 - t)^2 t \vec{p}_1 + 3 (1 - t) t^2 \vec{p}_2 + t^3 \vec{p}_3$$

Let's say you wish to extract $t_1 \le t \le t_2$ from a cubic Bézier curve into a separate curve $\vec{q}(t)$. Calculate $$\begin{aligned} \vec{q}_0 &= c_{00} \vec{p}_0 + c_{01} \vec{p}_1 + c_{02} \vec{p}_2 + c_{03} \vec{p}_3 \\ \vec{q}_1 &= c_{10} \vec{p}_0 + c_{11} \vec{p}_1 + c_{12} \vec{p}_2 + c_{13} \vec{p}_3 \\ \vec{q}_2 &= c_{20} \vec{p}_0 + c_{21} \vec{p}_1 + c_{22} \vec{p}_2 + c_{23} \vec{p}_3 \\ \vec{q}_3 &= c_{30} \vec{p}_0 + c_{31} \vec{p}_1 + c_{32} \vec{p}_2 + c_{33} \vec{p}_3 \\ \end{aligned}$$ where $$\begin{aligned} c_{00} &= \displaystyle \frac{ -t_2^3 }{(t_1 - t_2)^3} \\ c_{01} &= \displaystyle \frac{ 3 t_1 t_2^2 }{(t_1 - t_2)^3} \\ c_{02} &= \displaystyle \frac{ -3 t_1^2 t_2 }{(t_1 - t_2)^3} \\ c_{03} &= \displaystyle \frac{ t_1^3 }{(t_1 - t_2)^3} \\ c_{10} &= \displaystyle \frac{ t_2^2 - t_2^3 }{(t_1 - t_2)^3} \\ c_{11} &= \displaystyle \frac{ 3 t_1 t_2^2 - t_2^2 - 2 t_1 t_2 }{(t_1 - t_2)^3} \\ c_{12} &= \displaystyle \frac{ - 3 t_1^2 t_2 + t_1^2 + 2 t_1 t_2 }{(t_1 - t_2)^3} \\ c_{13} &= \displaystyle \frac{ t_1^3 - t_1^2 }{(t_1 - t_2)^3} \\ \end{aligned} \quad \quad \begin{aligned} c_{20} &= \displaystyle \frac{ -t_2^3 + 2 t_2^2 - t_2 }{(t_1 - t_2)^3} \\ c_{21} &= \displaystyle \frac{ 3 t_1 t_2^2 - 2 t_2^2 - 4 t_1 t_2 + 2 t_2 + t_1 }{(t_1 - t_2)^3} \\ c_{22} &= \displaystyle \frac{ -3 t_1^2 t_2 + 2 t_1^2 + 4 t_1 t_2 - t_2 - 2 t_1 }{(t_1 - t_2)^3} \\ c_{23} &= \displaystyle \frac{ t_1^3 - 2 t_1^2 + t_1 }{(t_1 - t_2)^3} \\ c_{30} &= \displaystyle \frac{ -t_2^3 + 3 t_2^2 - 3 t_2 + 1 }{(t_1 - t_2)^3} \\ c_{31} &= \displaystyle \frac{ 3 t_1 t_2^2 - 3 t_2^2 - 6 t_1 t_2 + 3 t_1 + 6 t_2 - 3 }{(t_1 - t_2)^3} \\ c_{32} &= \displaystyle \frac{ -3 t_1^2 t_2 + 3 t_1^2 + 6 t_1 t_2 - 6 t_1 - 3 t_2 + 3 }{(t_1 - t_2)^3} \\ c_{33} &= \displaystyle \frac{ t_1^3 - 3 t_1^2 + 3 t_1 - 1 }{(t_1 - t_2)^3} \\ \end{aligned}$$

(Let $\vec{p}\bigl(t_1 + t (t_2 - t_1) \bigr) = \vec{q}(t)$, and solve for the corresponding coefficients of $t$; you have four unknowns and four equations. Sort the coefficients, and the above pop out. I used wxMaxima to do the grunt work.)

$\endgroup$
2
  • $\begingroup$ A single note: I mentioned 0,(6), which is 0,666666..., which is 2/3 :) $\endgroup$
    – Spook
    Commented Jun 15, 2021 at 7:07
  • $\begingroup$ @Spook: Oh! I have not seen that notation, only things like $0,6\underline{6}$. I will change the wording to match. $\endgroup$
    – Glärbo
    Commented Jun 15, 2021 at 10:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .