3
$\begingroup$

NOTE: I am only concerned with quadratic Bézier curves.

So, dividing a Bézier curve into two is remarkably easy; just interpolate between start and control points by $t$, and get the end point for $t$. To get the other side; interpolate between end and control points by $1 - t$, and get the start point for $t$.

However, I am struggling with trying to subdivide a Bézier curve into more than $2$ new curves.

I tried to do this iteratively, by adjusting the t value I want based on the original curve, multiplied by a percentage that the second of the two new curves is of the original; basically, if my new curve is $75\%$ of the original (for a starting value of $t = 0.25$), multiply the next desired $ t $ value by $0.75$ to get an adjusted t value to use for the next slice. This is not working though, and I am unsure why (whether it is a math issue, or some other underlying problem I have elsewhere).

Anyways, let's say we have a curve of the following:

p_0 = 0,0
p_1 = 10,10
p_2 = 20,10

And I want to derive three curves from this for the following values of $t$:

t = 0.33
t = 0.66
t = 1

Such that the three new curves are $0.0 - 0.33$, $0.33 - 0.66$, and $0.66 - 1$ of the original curve.

What is the correct way to do this? I hope this makes sense.

$\endgroup$
3
$\begingroup$

For a quadratic Bézier curve, you need the two endpoints as well as the middle control point (which is not part of the curve itself, while the two endpoints are). Your "algorithm" for splitting the curve into two halves actually only calculates the new endpoint in the middle, but does not provide any hints as to how the middle control points for the two halves should be calculated.

Assuming the overall Bézier curve has control points $P_0$, $P_1$ and $P_2$, the two sub-curves resulting from a split at position $z$ would have control points respectively:

$$ \begin{matrix} P_{1,0} = P_0 \\ P_{1,1} = (1-z)P_0 + zP_1 \\ P_{1,2} = (1-z)^2P_0 + 2(1-z)zP_1+z^2P_2 \end{matrix} $$

and

$$ \begin{matrix} P_{2,0} = (1-z)^2P_0 + 2(1-z)zP_1+z^2P_2 \\ P_{2,1} = (1-z)P_1 + zP_2 \\ P_{2,2} = P_2 \end{matrix} $$

I suggest that you give a look at http://pomax.github.io/bezierinfo/ for the maths of the solution above.

Edit I forgot to discuss the splitting into multiple chunks, sorry!

Now that you have a way to split a curve at an arbitrary $z$, you can proceed to do the splitting at arbitrary positions $z_1$, $z_2$ and so on, with the following algorithm ($Z$ contains the positions):

  1. sort the positions in $Z$ so that $\forall i, j:i < j \Rightarrow z_i < z_j$;
  2. compute the control points for the first sub-spline using $z_0$ (i.e. the lowest element in $Z$) and save these control points (they are part of the solution);
  3. compute the control points for the remaining sub-spline (i.e. the second part) using, again, $z_0$
    1. if there are no more elements in $Z$, save these control points (they are the last part of the solution)
    2. otherwise do the following:
      1. update all elements in Z using the following formula: $$z_i \leftarrow \frac{z_i - z_0}{1 - z_0}$$
      2. eliminate the first element of $Z$ (i.e. $z_0$)
      3. restart from step #2 with the updated $Z$

At each step, this algorithm will provide you the control points for a sub-curve, except for the last iteration that will give you two.

There might be some concerns regarding the propagation of errors at each step. You can easily modify the algorithm to (pre)calculate all the remaining parts in step #3 directly from the input Bézier curve to split (this also includes the last section), and use them at each step for calculating the updated parameters for the intermediate parts. This is left as a simple exercise for the reader 😄

$\endgroup$
  • $\begingroup$ I don't think I explained my question well unfortunately :/, as the algorithm I am using is based on De_Casteljau's algorithm, which I think is what you illustrated? What I want to do though is have "two t's". Basically, a slice out of the bezier curve using two weights; for instance, start t = 0.14, and end t = 0.43. I want a new curve who's start point is at 0.14 of the original curve, and end point is at 0.43 of the original, the unknown point being the control point. The end goal is a way to get N number of new curves from the original. $\endgroup$ – dmarra Aug 24 '15 at 23:29
  • $\begingroup$ @user984444 sorry, your question was clear but I focused only on the splitting into two parts. I added some notes about how to extend the simple splitting to N chunks. $\endgroup$ – polettix Aug 25 '15 at 2:27
  • $\begingroup$ First of all, thank you for such a detailed reply! It turns out my original implementation was this algorithm, but I calculating the new z incorrectly. Thank you so much! $\endgroup$ – dmarra Aug 25 '15 at 3:51
  • $\begingroup$ I tried to write those final steps in code but i failed miserably. I don't fully understand the maths perfectly :( $\endgroup$ – WDUK Nov 20 '18 at 0:59
  • $\begingroup$ @WDUK the split into multiple chunks works doing repetitive split into two parts. To make things simple, you first sort all your z positions in ascending order, then start splitting with the first (i.e. the lowest one). The first half is OK, the second one contains the remaining points so it has to be processed further (unless, of course, you completed the last cut). BUT the "old" remaining z positions have to be shifted and scaled, because they applied to the old "full" curve, not to the second half. $\endgroup$ – polettix Nov 21 '18 at 11:30

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.