Splitting a bezier curve

Question

I'm working on a game for iPhone which creates a path after your character as you move (movement is similar to snake but curvy in terms of steering). The way im doing it now is by just keeping all the vertices the player has been on in an array and then just draw a circle on every one of them each and every frame.

I wanna move on to using bezier curves instead. I've done a lot of reading about them and I understand them quite well, but im not really good with math. I've came to an understanding that i should use DeCasteljau's algorithm to split the curve at a specific t but i haven't found out just which formula to use and how to implement this in code.

So what I currently have is all the controlpoints for a curve at t=1. Now i just want to get all the controlpoints for t<1. Can somebody give me an easy to understand mathematical formula for this or an implementation (preferably in python or objective-c). Maybe there's even a object that you can use in iphone sdk to split curves already?

score 24 · Accepted Answer · answered Dec 06 '11 at 19:40

24

I managed to get it working, actually really simple math. Just calculate all the tangents for the bezier and you get the points.

Here's some python:

def sliceBezier(points, t):
    x1, y1 = points[0]
    x2, y2 = points[1]
    x3, y3 = points[2]
    x4, y4 = points[3]

    x12 = (x2-x1)*t+x1
    y12 = (y2-y1)*t+y1

    x23 = (x3-x2)*t+x2
    y23 = (y3-y2)*t+y2

    x34 = (x4-x3)*t+x3
    y34 = (y4-y3)*t+y3

    x123 = (x23-x12)*t+x12
    y123 = (y23-y12)*t+y12

    x234 = (x34-x23)*t+x23
    y234 = (y34-y23)*t+y23

    x1234 = (x234-x123)*t+x123
    y1234 = (y234-y123)*t+y123

    return [(x1, y1), (x12, y12), (x123, y123), (x1234, y1234)]

To call it:

sliceBezier([(point1_x, point1_y),(controlpoint1_x, controlpoint1_y),(controlpoint2_x, controlpoint2_y),(point2_x, point2_y)], 0.23);

answered Dec 06 '11 at 19:40

Jonathan

2,968
3
24
36

With your solution above, I don't understand how to merge the newly found points into the original list. If I start with a list of four points, I expect a final list of seven points after the split. However, I don't see where your return values go into that original list. – Brannon May 21 '13 at 04:11
2

@Brannon This method here returns the first part of the split (therefor only 4 points) so if you want the other part you just do the same but with t = 1-t. I think that should work. Otherwise just reversing the points order should be another way I think. Been a while since i wrote this :) – Jonathan May 21 '13 at 17:21
Yes, 1-t with the points in reverse order does work for computing the other side. I found that suggestion in a different post here on stackoverflow. – Brannon May 21 '13 at 20:14
8

you can avoid the overhead by returning [(x1,y1),(x12,y12),(x123,y123),(x1234,y1234),(x234,y234),(x34,y34),(x4,y4)] due to the symmetry in the definition of a Bezier curve. – Geoffrey Oct 09 '13 at 12:13

dr jerry · Answer 2 · 2014-01-29T13:24:10.513

3

I implemented something like that, if you have a modern browser take a look here. It's implemented in javascript, and supports also higher order beziers.

edited Jan 29 '14 at 13:24

answered Dec 05 '11 at 20:38

dr jerry

9,768
24
79
122

1

+1 for very nice visualization and explanation on your website. For me not only the solution counts. I also want to know, why the solution works. Thank you! – Jeremi Jan 25 '14 at 00:21
Thanks for the thumbs up. I also implemented an algorithm to convert a bezier to a set of vertices. (www.iscriptdesign.com/?sketch=iPath/polybezier.jsvg). I'm still looking for an implementation to convert a bezier to a set of arcs. – dr jerry Jan 29 '14 at 13:31

score 1 · Answer 3 · answered Oct 10 '19 at 15:54

Here is a solution using Apple's SIMD api. It is concise and returns both subdivided curves.

void SplitBezier(float t,
                 simd_float2 cv[4],
                 simd_float2 a[4],
                 simd_float2 b[4]) {

  a[0] = cv[0];
  b[3] = cv[3];

  a[1] = simd_mix(cv[0], cv[1], t);
  b[2] = simd_mix(cv[2], cv[3], t);

  auto b12 = simd_mix(cv[1], cv[2], t);

  a[2] = simd_mix(a[1], b12, t);
  b[1] = simd_mix(b12, b[2], t);

  a[3] = b[0] = simd_mix(a[2], b[1], t);

}

Splitting a bezier curve

3 Answers3

Linked