Retrieve the initial cubic Bézier curve subdivided in two Bézier curves

Question

I have a cubic Bezier curve subdivided to two cubic Bezier: Assuming that "t_cut" is the t value where this initial Bezier is cut: example of function subdivision(BezierCurve initialCurve, Beziercurve b1, BezierCurveb2, float t_cut)

I want to retrieve the initial Bezier curve (so, its P1 and P2 control points, because P0 and P3 are known, using this function for example: BezierCurve merge(bezier1, bezier2, t_cut)). I can fix my problem if t_cut is always 0.5 (see my first question about merging two Bezier curves: Merge two or more cubic Bézier curves for optimization) but with other value of t_cut, I am not really satisfied by the result because I work with 10^-5m.

But, If someone could help me to retrieve this value of t_cut, on where the initial curve is cut, I can use this to merge the 2 curves and get an almost perfect approximation of the original curve. The merge function:

void BezierCurve::merge(QVector<BezierCurve> b_cContainer)
{
if(b_cContainer.empty()== false && b_cContainer.size() < 2)
{
QMessageBox::warning(0, "Warning", "2 or more curves are required to be merged");
}

auto leftCurve = b_cContainer[0];
auto rightCurve = b_cContainer[1];
auto A = leftCurve.getOrigin();
auto B = leftCurve.getC1();
auto C = leftCurve.getC2();
auto D = leftCurve.getEnd();

auto E = rightCurve.getC1();
auto F = rightCurve.getC2();
auto G = rightCurve.getEnd();

// origin and end do not changed: i-e A and G
origin = leftCurve.getOrigin();
end = rightCurve.getEnd();

auto k = (float)(norm(E-D))/(float)(norm(D-C));
c1 =(1+k)*B - k*A; //C1 is the first control point.
c2 =((1+k)*F - G)/k; // C2 is the second control.
}

Thank's for help.

Answer 1

If you know that the two curves you have resulted from splitting a single initial curve, then you don't need both these curves; knowing either and the cut position is enough to restore the full initial curve.

Have a look at this post on Stack Overflow. It discusses how you cut a curve. What you want to do is do the reverse. To find control points $Q_i$ for the segment between $t_0$ and $t_1$ (with $u_0=1-t_0$ and $u_1=1-t_1$) of a Bézier curve, you do the following computation:

\begin{align*} Q_1 &= u_0u_0u_0\,P1 + (t_0u_0u_0 + u_0t_0u_0 + u_0u_0t_0) P_2 + (t_0t_0u_0 + u_0t_0t_0 + t_0u_0t_0) P_3 + t_0t_0t_0\,P_4 \\ Q_2 &= u_0u_0u_1\,P1 + (t_0u_0u_1 + u_0t_0u_1 + u_0u_0t_1) P_2 + (t_0t_0u_1 + u_0t_0t_1 + t_0u_0t_1) P_3 + t_0t_0t_1\,P_4 \\ Q_3 &= u_0u_1u_1\,P1 + (t_0u_1u_1 + u_0t_1u_1 + u_0u_1t_1) P_2 + (t_0t_1u_1 + u_0t_1t_1 + t_0u_1t_1) P_3 + t_0t_1t_1\,P_4 \\ Q_4 &= u_1u_1u_1\,P1 + (t_1u_1u_1 + u_1t_1u_1 + u_1u_1t_1) P_2 + (t_1t_1u_1 + u_1t_1t_1 + t_1u_1t_1) P_3 + t_1t_1t_1\,P_4 \end{align*}

If you know all the $t_i$ and $u_i$ then this is simply a linear transformation, which you can express by a $4\times 4$ matrix. This matrix will turn a set of $P_i$ into a set of corresponding $Q_i$. So if you want to do the reverse operation, you need the inverse of that matrix. Compute that, feed in the $Q_i$ control points of one part of the split curve, and you obtain the control points of the full curve.

Note that if you consider the first part of the original curve, from $t=0$ to $t=t_{\text{cut}}$, then you have

$$t_0=0\quad u_0=1\quad t_1=t_{\text{cut}}\quad u_1=1-t_{\text{cut}}$$

If you don't know $t_{\text{cut}}$, then you will need to obtain that from the curve. In that case I suggest you extend one of your curves until it reaches the endpoint of the other. If you plug the $x$ coordinate of one endpoint into the equation of the cubic Bézier curve, then this is a cubic equation which will have up to three possible solutions. Try these three $t$ values and see for which the $y$ coordinate matches as well. You might want to enforce $t>1$ as well, so you really extend the curve. Then use this $t$ as $t_1$ and with $t_0=0$ do the above (forward, not inverse) computation to compute the control points of the full curve from those of the first part.

Answer 2

Let's make sure we understand splitting, before we talk about joining. To subdivide a Bézier curve into two, you use the deCasteljau algorithm, as illustrated in the figure below.

Suppose we are given a curve defined by four control points $A$, $P$, $Q$, $G$, and a splitting parameter value $u \in [0,1]$ (which you called $t_{\text{cut}}$). To split the curve, we repeatedly divide edges in the ratio $u:v$, where $v=1-u$. So, we divide the edge $AP$ in the ratio $u:v$ to get point $B$, divide $QG$ to get $F$, and so on. The division is done using convex combinations of points, so, for example, $B = uP + vA$, and $F = uG+vQ$. This process generates the points $B$, $C$, $D$, $E$, $F$, as shown. The two curves resulting from the splitting are shown in pink and blue in the picture. The pink curve has control points $(A,B,C,D)$, and the blue one has control points $(D,E,F,G)$.

Now let's talk about how we might "undo" this splitting process. So, we are given the points $A$, $B$, $C$, $D$, $E$, $F$, $G$, and we want to get the points $P$ and $Q$. We simply have to run the deCasteljau "dividing" steps in reverse.

First we find the splitting parameter $u$ (your $t_{\text{cut}}$). We calculate $k = DE/CD$. Then $E-D = k(D-C)$, and a little arithmetic shows that $$ D = \frac{1}{1+k}E + \frac{k}{1+k}C $$ But if $D$ was produced by the deCasteljau algorithm, we also know that $D = uE + vC$, so we have $u = 1/(1+k)$ and $v=k/(1+k)$.

Next, we find $P$ so that $B$ divides $AP$ in the ratio $u:v$. This means that $B = uP + vA$, which implies that $$ P = \frac{1}{u}B - \frac{v}{u}A = (1+k)B - kA $$ Similarly, since $F = uG+vQ$, we have $$ Q = \frac{1}{v}F - \frac{u}{v}G = \frac{1+k}{k}F - \frac{1}{k}G $$ The $u$ and $v$ are just to relate all this to the deCasteljau algorithm, for purposes of understanding. In code, you can forget about $u$ and $v$, and just use $k$. The (pseudo) code is:

k = Length(E-D)/Length(D-C)
P = (1+k)*B - k*A
Q = ((1+k)*F - G)/k

Of course, you can execute this code with any two Bézier curves as input, regardless of whether they were produced by splitting. I think the output curve will then be a reasonable approximation of the two input ones, which gives another answer to a question you asked elsewhere.

If we use the input data

A = ( 94     , 242)
B = ( 121    , 183.5)
C = ( 272.5  , 183 )
D = ( 417.25 , 210.875)
E = ( 562    , 238.75 )
F = ( 700    , 295 )
G = ( 700    , 350 )

Then the output is

k = 1
P = 2*B - A = (242,367) - (94,242) = (148,125)
Q = 2*F - G = (1400, 590) - (700,350) = (700,240)

Another example, as given in the comments. The input data is:

A = ( 94 , 242 )
B = ( 107.5 , 212.75 )
C = ( 152.125 , 198 )
D = ( 211.46875 , 194.046875 )
E = ( 389.5 , 182.1875 )
F = ( 700 , 267.5 )
G = ( 700 , 350 )

This gives the following output, which is easy to check by hand calculations:

k = 3
P = (4*B - A)   = (148 , 125)
Q = (4*F - G)/3 = (700 , 240)

So, actually, this is the same curve as in the previous example, but it is split at $u = 1/(1+k) = 0.25$ rather than at $u = 0.5$.

I don't know what is wrong with the code given in the question, but I suspect the calculation of "c2" in the last line is not working correctly. Maybe this is because division of a vector by a scalar is not properly supported. I suggest rewriting it as

r = 1.0/k
c2 = (1+r)*F - r*G