Разбить кубическую кривую Безье на несколько точек

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

SubdivPoints subdivideBezier(Vector2 p0, Vector2 p1, Vector2 p2, Vector2 p3, float t)
{
    Vector2 p11 = (p1 - p0) * t + p0;
    Vector2 p21 = (p2 - p1) * t + p1;
    Vector2 p31 = (p3 - p2) * t + p2;

    Vector2 p12 = (p21 - p11) * t + p11;
    Vector2 p22 = (p31 - p21) * t + p21;

    Vector2 p13 = (p22 - p12) * t + p12;

    return SubdivPoints(p11, p12, p22, p31, p13);
}

У меня вопрос, есть ли простой способ расширить это для разделения несколько раз? Я представляю, что после каждого разделения я хочу пересчитать значения t; Мне интересно, будет ли здесь работать простая арифметика. Например, допустим, у меня есть значения t 0,2 и 0,6. Я разделил кривую при t = 0,2, дав мне две кривые. Вторая кривая покрывает значения t 0,2

Источник

2 ответа

Решение

Очень трудно сказать, даже если ваш нынешний подход работает, поскольку мы не видим, что стоит за SubdivPoints, Я могу думать о 2 подходах для этого:

  1. алгебраическая

    если вы посмотрите на свою проблему в качестве параметра t масштабирование полинома тогда стало понятнее. Например, вы хотите контрольные точки для части t=<0.25,0.5>, Это означает, что нам нужно сформировать новые контрольные точки, представляющие одну и ту же кривую с параметром u=<0.0,1.0>, Как это сделать?

    1. написать БЕЗЬЕ как многочлен

    каждая ось может быть сделана отдельно таким же образом s позволяет нам сосредоточиться на xось только. У нас есть 4 контрольных точки BEZIER с координатами X (x0,x1,x2,x3), Если мы применяем полиномы Бернштейна для формирования кубического полинома, мы получим:

    x(t)=      (                           (    x0))
    +    t*(                  (3.0*x1)-(3.0*x0))
    +  t*t*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +t*t*t*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
    1. масштабировать параметр путем подстановки

    Для этого используйте линейную интерполяцию:

    t0=0.25 -> u0=0.0
t1=0.50 -> u1=1.0
t=t0+(t1-t0)*(u-u0)/(u1-u0)
t=0.25+0.5*u

    Теперь переписать полином с помощью u вместо т

    x(t)=             (                           (    x0))
    +(0.25+u/2)  *(                  (3.0*x1)-(3.0*x0))
    +(0.25+u/2)^2*(         (3.0*x2)-(6.0*x1)+(3.0*x0))
    +(0.25+u/2)^3*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))
    1. измените полиномиальную форму, чтобы снова соответствовать уравнению БЕЗЬЕРА

    Теперь нужно разделить термины полинома для u^0,u^1,u^2,u^3 и реформируйте каждый, чтобы соответствовать стилю БЕЗЬЕ (с # 1). Из этого извлекают новые контрольные точки.

    Например, термин u ^ 3 выглядит следующим образом. Единственная возможность получить и ^ 3 от

    (1/4+u/2)^3= (1/8)*u^3 + (3/16)*u^2 + (3/32)*u + (1/64)

    так разделены u^3 срок будет:

    u*u*u*((    x3)-(3.0*x2)+(3.0*x1)-(    x0))/8

    остальные будут немного сложнее, так как вам нужно объединить все линии вместе... После упрощения вам нужно будет разделить новые координаты. Как вы можете видеть, это небольшое безумие, но есть алгебраические решатели, такие как Derive для Windows...

    Извините, у меня нет времени / настроения / желудка, чтобы сделать полный пример всех терминов, но вы увидите, что это будет полиномиальное безумие...

  2. подбор кривой

    это основано на том, что вы находите координаты своих контрольных точек и проверяете, как далеко они находятся от желаемой кривой. Таким образом, проверьте "все возможные" точки и запомните закрытое совпадение между исходной кривой на целевом диапазоне и новой. Это было бы неразрешимо, поскольку существует бесконечное число возможных контрольных точек, поэтому нам необходимо сократить их до приемлемого размера, используя что-то. Например, теперь у нас контрольные точки не будут далеко от исходных контрольных точек, поэтому мы можем использовать их для ограничения области для каждой точки. Вы можете использовать поиск аппроксимации для этого или любого другого метода минимизации.

    Вы также можете получить намного лучшую начальную точку для этого, если используете интерполяционную кубику. Смотрите BEZIER против интерполяционных кубиков. Так:

    1. вычислите 4 новые кубические контрольные точки интерполяции из вашей кривой BEZIER

      так что если у нас есть те же диапазоны, что и раньше, то

      X0 = BEZIER(t0-(t1-t0))
X1 = BEZIER(t0)
X2 = BEZIER(t1)
X3 = BEZIER(t1+(t1-t0))

      это интерполяционные кубические контрольные точки, а не безье. они должны быть равномерно распределены. X1,X2 являются конечными точками кривой и X0,X3 до и после них, чтобы максимально сохранить локальную форму и линейность параметра

    2. transfrom (X0,X1,X2,X3) вернуться в контрольные точки BEZIER (x0,x1,x2,x3)

      Вы можете использовать мою формулу по ссылке выше:

      // input: X0,Y0,..X3,Y3  ... interpolation control points
// output: x0,y0,..x3,y3 ... Bezier control points
    double x0,y0,x1,y1,x2,y2,x3,y3,m=1.0/9.0;
    x0=X1;             y0=Y1;
    x1=X1+((X1-X0)*m); y1=Y1+((Y1-Y0)*m);
    x2=X2+((X2-X3)*m); y2=Y2+((Y2-Y3)*m);
    x3=X2;             y3=Y2;

      Как видите, каждая ось вычисляется одинаково...

    3. применить поиск приближения для контрольных точек BEZIER

      новый (x0,x1,x2,x3) пока не точны, так как, изменяя контрольные точки вслепую, мы можем немного пропустить некоторую локальную крайность искривления кривой Поэтому нам нужно искать настоящие. К счастью, новые контрольные точки (x0',x1',x2',x3') будет очень близко к этим точкам, поэтому теперь мы должны искать каждую точку только рядом с ее противоположной частью с некоторым разумным радиусом вокруг (как ограничивающая рамка size/8 или что угодно... вы увидите результаты и сможете настроить...

[заметки]

Если вам нужен точный результат точности, тогда можно использовать только подход № 1. Подход № 2 всегда будет иметь какую-то ошибку. Если форма не должна быть точной, иногда кубической интерполяции, преобразованной в BEZIER без окончательной подгонки, будет достаточно (если форма не слишком сложна в / рядом с вырезанными областями).

Как я уже писал ранее, не зная, какой принцип используется в вашем SubdivPoints невозможно ответить, каков будет результат его повторного использования...

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

Источник

Поскольку ваша функция subdivideBezier() действительно следовала алгоритму де Кастельжау, я предполагаю, что она работает для разделения кубической кривой Безье с параметром t. Так что, да, чтобы продолжить деление на другой параметр (скажем, t2), все, что вам нужно сделать, это выяснить, на какую подразделяющуюся подразделяющуюся кривую t2, вычислить новое t2* по этой кривой и поделить. В вашем примере, где вы хотите подразделить при t=0,2 и 0,6, новый параметр для 0,6 должен быть (0,6-0,2)/(1-0,2) = 0,5. Таким образом, вы можете просто подразделить 2-ю кривую при t=0,5.

Источник
Другие вопросы по тегам