5

Мне необходимо реализовать соединения в виде кривых линий на C# (Unity). Хотелось бы получить результат максимально похожий на реализацию в Miro.com — см. рисунок ниже.

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

Проблема: При разделении кривой на сегменты с помощью нажатия и перетаскивания одной из синих точек сегмента (см. рисунок) он разделяется по середине на две части. В месте соединения двух сегментов образуется новая интерактивная (подвижная) точка для которой касательная и координаты контрольных точек неизвестны. Их мне и нужно находить при изменении позиций интерактивных точек (белые точки на рисунке снизу). При том кривая не должна резко изменять свое положение при разделении, не образовывать петель, иметь разные длины векторов контрольных точек (тут не уверен) и вести себя максимально адекватно (как на доске в Miro).

Черным я пририсовал известные контрольные точки, а красным те, которые мне необходимо найти. (Pn - интерактивные точки, Cn - контрольные точки)

Разделенная на сегменты кривая в Miro.com

Опробованные мною алгоритмы для их поиска дают неверные расстояния и направления контрольных точек.

Были опробованы следующие алгоритмы:

  1. Интерполяция из Tacent - скачки кривой при разделении, неподходящие направление и величина отступа контрольных точек;
  2. Алгоритм Чайкина - скачки кривой при разделении, создает петли;
  3. "Кастомная" интерполяция, основанная на догадках (учитывает расстояние до центра отрезка между начальной и конечной точки сегмента, а также направление между начальной и конечной точками) - имеет все те же проблемы, однако выглядит наиболее приближенно.
  4. Построение оптимального сплайна Безье - результат немного не соответствует ожиданиям (возможно чуть не тот наклон касательной), хотя, возможно, просто в коде автора закралась ошибка.

Решение видится мне в алгоритмах интерполяции сплайнов. Т.к. изначально я имею 1 сегмент кривой Безье, при его разделении я мог бы преобразовать исходную кривую в сплайн (Catmull-Rom ?) и далее использовать его для неограниченного кол-ва сегментов.

Также очень похоже выглядят кривые из 3DMax. В их документации нашёл лишь упоминание параметрической кривой.

Кривые в 3DMAX для примера Примерно такой же путь в референсе

Способы, которые я не использовал (или не получились):

  1. Catmull-Rom интерполяция;
  2. Интерполяция B-сплайном;
  3. Эрмитова интерполяция;
  4. Алгоритм Де Кастельжау (хотя вроде не для этого)

Буду безмерно благодарен за любую помощь, но прошу как можно подробнее.

19
  • Я в смятении: то ли плюсовать, то ли банить. Пост хорошо оформлен, тема интересная, видны попытки решить проблему. Но грёбаная реклама... Нажал на капу. 8 янв 2021 в 22:29
  • @AlexanderPetrov Ну двух ссылок многовато, да. И вообще: удалил ссылки (кому надо будет - вобьёт в браузер и посмотрит, я что-то покопался на их сайте, но сходу не нашёл где там такие кривые, всё-таки слишком оторвано от вопроса), теперь можно плюсовать за сам вопрос.
    – A K
    8 янв 2021 в 22:54
  • По первому рисунку не похоже, что синие точки разделяют кривые? Или они вообще просто так нарисованы (судя по второму снизу рисунку)?
    – MBo
    9 янв 2021 в 4:51
  • @MBo Если потянуть за синюю точку, то на её месте сразу же появляется белая
    – g0dzZz1lla
    9 янв 2021 в 12:09
  • @g0dzZz1lla К сожалению, это не добавляет ясности. Нужно более-менее математически описать, что делается. Набор сплайнов Catmull-Rom вычислить и перевести в форму Безье вполне реально.
    – MBo
    9 янв 2021 в 14:30

1 ответ 1

1

Деление кривой Безье на две кривых по параметру t (Delphi, но формулы везде одинаковые):

введите сюда описание изображения

procedure DivideBezier(var p, p1, p2: array of TPoint; t: double = 0.5);
var
  t0, t1, t2, t3, tt: double;
  xx, yy: integer;
begin
  if (t < 0) or (t > 1) then
    Exit;
  tt := 1 - t;
  t0 := tt * tt * tt;
  t1 := 3 * tt * tt * t;
  t2 := 3 * tt * t * t;
  t3 := t * t * t;
  p1[0] := p[0];
  p1[3].x := Round(p[0].x * t0 + p[1].x * t1 + p[2].x * t2 + p[3].x * t3);
  p1[3].y := Round(p[0].y * t0 + p[1].y * t1 + p[2].y * t2 + p[3].y * t3);
  p1[1].x := Round((p[0].x * tt + p[1].x * t));
  p1[1].y := Round((p[0].y * tt + p[1].y * t));
  xx := Round((p[1].x * tt + p[2].x * t));
  yy := Round((p[1].y * tt + p[2].y * t));
  p1[2].x := Round(p1[1].x * tt + xx * t);
  p1[2].y := Round(p1[1].y * tt + yy * t);
  p2[0] := p1[3];
  p2[3] := p[3];
  p2[2].x := Round((p[2].x * tt + p[3].x * t));
  p2[2].y := Round((p[2].y * tt + p[3].y * t));
  p2[1].x := Round(p2[2].x * t + xx * tt);
  p2[1].y := Round(p2[2].y * t + yy * tt);
end;

var
  p, p1, p2: array[0..3] of TPoint;
begin
  p[0]  := Point(100, 100);
  p[1]  := Point(200, 340);
  p[2]  := Point(300, 170);
  p[3]  := Point(400, 100);
  DivideBezier(p, p1, p2);
  Canvas.Pen.Color := clRed;
  Canvas.Pen.Width := 5;
  Canvas.PolyBezier(p1);
  Canvas.Pen.Color := clBlue;
  Canvas.Pen.Width := 5;
  Canvas.PolyBezier(p2);
  Canvas.Pen.Color := clLime;
  Canvas.Pen.Width := 1;
  Canvas.PolyBezier(p);  //исходная кривая рисуется поверх
6
  • Не могли бы Вы уточнить что представляют собой массивы p, p1, p2 Предполагаю, что p - точки, через которые проходит кривая, p1 - левые контрольные точки, p2 - правые контрольные точки, но тогда их бы было на 1 меньше.
    – g0dzZz1lla
    10 янв 2021 в 13:07
  • p - контрольные точки исходной кривой, p1 и p2 - контрольные точки новых кривых. Последняя точка p1 совпадает с первой точкой p2 ( p2[0] := p1[3];), это точка разделения (t=0.5 исходной кривой). Если использовать один массив, как для PolyBezier, то повтор нужно исключить.
    – MBo
    10 янв 2021 в 13:46
  • Правильно ли я понял, что если новая точка, полученная при разделении, перемещается, например, влево на -50, то нужно рассчитывать другое значение t? Годится ли этот способ для подвижных/интерактивных точек, которые пользователь мог бы перемещать не только вдоль исходной кривой?
    – g0dzZz1lla
    10 янв 2021 в 20:22
  • Новая точка лежит на кривой, т.к. Вы же писали Деление происходит при t=0,5. Деление можно делать при других значениях параметра, функция позволяет. Это стандартная задача Bezier subdivision. Но если нужна новая точка, не лежащая на исходной - то это совершенно другая задача, требуется формально определить, какие кривые будут созданы, и как они связаны (если вообще связаны) с исходной кривой.
    – MBo
    11 янв 2021 в 3:35
  • Мне казалось, что subdivision не подходит для случая с подвижными точками. При сдвиге получившегося узла соединения сегментов мне нужно как-то определить t. Также становятся неактуальны все направляюще точки в сегментах, которые связывает этот узел.
    – g0dzZz1lla
    11 янв 2021 в 17:53

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.