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?

Answer 1

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);

Answer 2

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.

Answer 3

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);

}