2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Sorry. Formula was correct, but mistake in the code. Should be $P=(1+k)*B-k*A$. Fixed in the answer. I tested it, and it works for me. $\endgroup$ – bubba Jul 29 '14 at 9:51
  • $\begingroup$ Working now ??? $\endgroup$ – bubba Jul 29 '14 at 10:33
  • $\begingroup$ It works perfectly if the t_cut=0.5, otherwise, the result is not very good.. $\endgroup$ – mrazaf Jul 29 '14 at 11:11
  • $\begingroup$ I run my test on this example of Bézier curve: P = (94,242),(148,125),(700,240),(700,350) $\endgroup$ – mrazaf Jul 29 '14 at 11:13
  • 1
    $\begingroup$ Ok, the original curve: (94,242),(148,125),(700,240),(700,350), (so I expect these values after joining). So the splitting gives: A=(94,242), B=(107.5, 212.75), C=(152.125, 198), D=(211.46, 194.0468),E=(211.46, 194.046875) F=(389.5, 182.1875),G=(700, 267.5),H=(700, 350). with t = When I launch joining process: I get as result: P=(148, 125), Q=(77.7777, 2.2222) All results are good (the begin point, the end point and the first control point: P) expect Q. I don't understand. $\endgroup$ – mrazaf Jul 29 '14 at 12:37
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hello, thank you for reply. I tried this approach, it does not work. And the result does not satisfy : Q1 = A1 and Q4 = B4 (A is the first curve and B is the second). $\endgroup$ – mrazaf Jul 29 '14 at 8:31
  • $\begingroup$ @mrazaf: Can you provide a concrete example? $\endgroup$ – MvG Jul 29 '14 at 8:51
  • 1
    $\begingroup$ I chose a simple example with t_cut=0.5: Original curve = (94,242),(148,125),(700,240),(700,350) First part curve after splitting: (A1,A2,A3,A4) = ((94,242),(121,183.5),(272.5,183),(417.25,210.875)),Using the method that you suggest: the matrix: M = {{1,0,0,0},{0.5,0.5,0,0},{0.25,0.25,0.25,0},{0.125,0.375,0.375,0.125}} Inverse matrix: M^-1 = {{1., 0., 0., 0.}, {-1., 2., 0., 0.}, {0., -2., 4., 0.}, {2., 0., -12., 8.}} (Wolframe alpha engine) (P)=(Q) * M^(-1),the result: ((94, 242),(148.125),(848., 365),(256, -25)) which is different compared to the (P1,P2,P3,P4) for the original curve. $\endgroup$ – mrazaf Jul 29 '14 at 10:54
  • $\begingroup$ @mrazaf: You have a mistake in computing M: the second column of the third row is $0.5$ not $0.25$: $$M=\begin{pmatrix}1&0&0&0\\0.5&0.5&0&0\\0.25&0.5&0.25&0\\0.125&0.375&0.375&0.125 \end{pmatrix}$$ Furthermore, you have to multiply $Q$ from the right: $$M^{-1}Q=\begin{pmatrix}1&0&0&0\\-1&2&0&0\\1&-4&4&0\\-1&6&-12&8\end{pmatrix}\cdot \begin{pmatrix}94&242\\121&183.5\\272.5&183\\417.25&210.875\end{pmatrix}= \begin{pmatrix}94&242\\148&125\\700&240\\700&350\end{pmatrix}$$ As a sanity check, you can verify that both $M$ and $M^{-1}$ have rows which add to $1$. $\endgroup$ – MvG Jul 29 '14 at 12:35
  • $\begingroup$ Indeed, I forgot multiplication by 2. I will try this algorithm for other value of t_cut and I'll keep you informed.Many thanks for your help. $\endgroup$ – mrazaf Jul 29 '14 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.