Split a higher order Bezier curve into many cubic curves

Question

I need to display a bezier curve. The user chooses arbitrary points by clicking on the display area.

I implemented code to make a bezier curve with these points, but for higher order curves it doesn't work, once the order is equal the number of control points-1.

How can I split these control points to make a sequence of cubic bezier curves that represents the entire curve I want?

possible duplicate of [Convert a quadratic bezier to a cubic?](http://stackoverflow.com/questions/3162645/convert-a-quadratic-bezier-to-a-cubic) — Jonathan, May 02 '15 at 03:33
You seem to have two things going on. You say “I implemented a code to make a bezier curve with these points, but for higher orders it doesn`t work”. If you show us your code and tell us what's wrong with the output, maybe we can help you fix it. That may be a completely different problem than approximating a higher-order Bézier curve using cubic Bézier segments. Which problem do you really want to solve? (Note that you cannot, in general, find a set of cubic segments that contain **exactly** the same points as the original higher-order curve.) — rob mayoff, May 02 '15 at 03:40
@robmayoff The code I made uses all the points, so the order will be too high and will not work. Therefore I want to split in cubic curves. No need to be exactly the same curve, but a good enought approximation. — G_comp, May 02 '15 at 03:47
Can you explain why you think you even need to split the control points? Do you not want to approximate a high order curve with cubic curves or something? If your users place `n` points, you can quite easily draw the corresponding nth order curve (using `n+(n-1)+(n-2)+...+1 = n(n+1)/2` linear interpolations for each point on the curve you want drawn) — Mike 'Pomax' Kamermans, May 02 '15 at 04:53
@JoséAugusto can you please better explain what situation you have, and what you need to do? (some picture links would go a long way towards making your question clearer) — Mike 'Pomax' Kamermans, May 02 '15 at 18:06
@Mike'Pomax'Kamermans I want to draw a bezier curve that after I will turn in to a racing line, like this: http://devmag.org.za/blog/wp-content/uploads/2011/04/racing.png So, the user will click on the display area to choose the control points that will generate the road in the game. To high orders, however, the implementation I used is not working. So I did as the image: http://devmag.org.za/blog/wp-content/uploads/2011/04/bezier_path.png I split the control points to make a sequence of cubic curves. — G_comp, May 02 '15 at 21:03
@Mike'Pomax'Kamermans is it right ? There is a better way to compute the bezier to many control points? — G_comp, May 02 '15 at 21:14
@JoséAugusto please don't respond with "more details" as a comment, instead, update your actual question with that information, so that everyone can immediately see it =) — Mike 'Pomax' Kamermans, May 02 '15 at 21:49
as actual response: the curve you're showing is simply a sequence of connected cubic bezier curves. The part that's still missing is how you expect your users to click; are the on-curve points already fixed and they only get to pick the controls? In that case, it's pretty easy to abstract each cubic bezier section. — Mike 'Pomax' Kamermans, May 02 '15 at 21:53
@Mike'Pomax'Kamermans I am using an API to do that. The user clicks on the display area, then I save the coordinate that will be the control points. Something like that, but simpler: https://www.youtube.com/watch?v=1HCbe8yTHNw First I save all the control points, then I split them like the image to make the final bezier curve. This part seems to be working now. — G_comp, May 02 '15 at 22:26
So I understand you correctly, do your users only place "real points", only place "control points", or "all points"? Can they move those points around while they're drawing? Also, please make sure to update your original question so that it's clear what you're asking and what you have right now. If you already solved this problem, it's worth either deleting your question if you think others will never benefit from it, or post an answer to it explaining how you solved things. — Mike 'Pomax' Kamermans, May 04 '15 at 15:43

score 3 · Answer 1 · answered May 02 '15 at 12:04

I'm sure you can find good resources on "drawing smooth Bezier curves" using adaptive methods, but here is what I think is a good simple approach (if rather unoptimized):

Generate binomial coefficients. For example, a 5th degree curve can be expressed as:

The binomial coefficients are the nth row of Pascal's Triangle:
```
1, 5, 10, 10, 5, 1
```

Adaptively perform recursions at locations where successive divisions produce a significant change in the evaluated points. This happens at cusps/sharp bends where it takes many points to converge to an acceptable solution. For example:

Note that ||B(a) - B(b)|| is notation for the length
of the line between the evaluated points B(a) and B(b).

Evaluate B(t) for values of t = a, b,    c,   d,    e
                              = 0, 0.25, 0.5, 0.75, 1.

Evaluate lengths of straight line segments:
    ac = ||B(a) - B(c)||
    ce = ||B(c) - B(e)||

    Also evaluate ab, bc, cd, de.

if  ac - (ab + bc)  >  ERROR_THRESHOLD
    Split ab into two segments and split bc into two segments.
else
    We have found a good enough approximation.

Do the same as above for ce - (cd + de).

Though, as a note on programmability: you really can't draw higher order curves using the Bernstein polynomial without things becoming very expensive and even intractible; the values involved get too large to fit into floating point datatypes real fast. Using linear interpolation turns out to be just as fast for low order curves, but has the benefit of the numbers involved staying within the bounds set up by the initial control coordinates, so you can even trivially compute 6th, 10th or 40th order curve coordinates fast and accurately. — Mike 'Pomax' Kamermans, May 02 '15 at 18:04

Split a higher order Bezier curve into many cubic curves

1 Answers1