Расщепление кривой Безье

Question

Я работаю над игрой для iPhone, которая создает путь после вашего персонажа, когда вы двигаетесь (движение похоже на змею, но извилистое с точки зрения управления). Теперь я делаю это, просто сохраняя все вершины, в которых находился игрок, в массиве, а затем просто рисую окружность на каждой из них в каждом кадре.

Я хочу перейти к использованию кривых Безье. Я много читал о них и хорошо их понимаю, но я не очень хорошо разбираюсь в математике. Я пришел к выводу, что мне следует использовать алгоритм ДеКастельжау, чтобы разделить кривую при определенном t, но я не выяснил, какую формулу использовать и как реализовать это в коде.

Так что у меня есть все контрольные точки для кривой при t=1. Теперь я просто хочу получить все контрольные точки для t<1. Может кто-нибудь дать мне легкую для понимания математическую формулу для этого или реализации (желательно на python или target-c). Может быть, есть даже объект, который вы можете использовать в iphone SDK для разделения кривых уже?

Answer 1

Мне удалось заставить его работать, на самом деле очень простая математика. Просто рассчитайте все касательные для Безье, и вы получите очки.

Вот немного питона:

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

Чтобы назвать это:

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

Answer 2

Я реализовал нечто подобное, если у вас есть современный браузер, посмотрите здесь. Он реализован в javascript, и поддерживает также более высокого порядка Безье.

Answer 3

Вот решение, использующее Apple SIMD api. Он краток и отображает обе разделенные кривые.

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

}