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

bezier-curvecomputer sciencediscrete mathematicsgeometryplane-curves

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.

Best Answer

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. enter image description here

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
Related Question