Войти
ПрограммированиеСтатьи2D графика и изометрия

Редактор функций на основе кривых Безье

Автор:

Статья о кривых Безье и о проблемах, с которыми можно столкнуться при написании редактора скалярных функций на базе кривых Безье.

Редактор, разработка которого легла в основу статьи, был сделан для проекта Filter Forge. Чтобы не быть голословным, покажу конечный результат работы:

FFCurveEditor | Редактор функций на основе кривых Безье

Кривые Безье
Как связать формулы с тем, что мы видим в редакторах векторной графики
Создание 2d редактора Безье: стандартные проблемы.
  Решение проблемы построения ломаной по кривой Безье
  Конвертирование контрольных точек из одного типа в другой
Создание скалярной функции на базе кривой Безье: проблемы
  Решение проблемы единственности значения для функции
  Решение проблемы нахождения значения функции
  Ограничения для точек и направляющих в интерфейсе.
Заключение
Ссылки

Кривые Безье

Почему именно кривые Безье? В первую очередь из-за своей привычности для пользователей. Я не встречал ни одного 2d векторного редактора, за основу которого были взяты другие методы аппроксимации кривой по контрольным точкам. Безье – де-факто стандарт среди подходов к векторной графике.

Кривая Безье - это полином K степени, построенный по K + 1 точкам. Точки лежат в N-мерном пространстве. В дальнейшем для выкладок будем использовать N=2 – редактор-то у нас двумерный. Наиболее распространены для использования следующие кривые:

Линейная (Linear) – построенная по 2 точкам.
Linear bezier curve | Редактор функций на основе кривых Безье
Линейная кривая Безье – обычная линейная интерполяция. Формула:
f_01_linear_bezier | Редактор функций на основе кривых Безье


Квадратичная (Quadratic) – построенная по 3 точкам.
quadratic_bezier_curve | Редактор функций на основе кривых Безье
Квадратичная кривая строится рекуррентно как линейная интерполяция 2 линейных кривых.
f_02_quadratic_bezier | Редактор функций на основе кривых Безье
Если упростить выражение, получим следующую формулу:
f_03_quadratic_bezier_simpl | Редактор функций на основе кривых Безье


Кубическая (Cubic) – строится по 4 точкам.
cubic_bezier_curve | Редактор функций на основе кривых Безье
Кубическая кривая выражается через линейную интерполяцию 2 квадратичных кривых:
f_04_cubic_bezier | Редактор функций на основе кривых Безье
После упрощения получим:
f_04_cubic_bezier_simpl | Редактор функций на основе кривых Безье

Можно простроить кривую для произвольных N точек, используя соотношение:
f_06_bezier_common | Редактор функций на основе кривых Безье
Но на практике чаще всего используют 1<=N<=3. Во-первых, описанные выше случаи легки и интуитивно понятны в управлении для пользователя, во-вторых, чем больше степень кривой, тем больше вычислений требуется для нахождения точек кривой.


Все кривые Безье независимо от степени имеют следующие важные свойства:


На пункте 5 остановимся подробнее. Алгоритм разбиения кривой называется разбиением de Casteljau. Рассмотрим алгоритм для кубической кривой Безье (для кривых других порядков он работает аналогично).

Пусть у нас есть кривая, построенная по точкам 1-2-3-4
cubic_bezier_subdiv | Редактор функций на основе кривых Безье

Выберем некоторый параметр t* (для рисунка t* = 0.5) и найдем точки на отрезках 1-2, 2-3 и 3-4, соответствующие линейной интерполяции с параметром t. Назовем точки 12, 23, 34 соответственно. Затем повторим операцию на отрезках 12-23, 23-34, найдя точки 123 и 234. И, наконец, построив линейную интерполяцию по t для отрезка 123-234, получим точку 1234, лежащую на кривой Безье, а кривые, построенные по точкам 1-12-123-1234 и 1234-234-34-4, повторяют оригинальную кривую. Упрощенный код:

struct CubicPoints 
{
 Vec2 p1;
 Vec2 p2;
 Vec2 p3;
 Vec2 p4;
};

void split_curve(
 const CubicPoints& in_points, const double t, CubicPoints& out_points1, CubicPoints& out_points2)
{
 const Vec2 p12 = lerp(in_points.p1, in_points.p2, t);
 const Vec2 p23 = lerp(in_points.p2, in_points.p3, t);
 const Vec2 p34 = lerp(in_points.p3, in_points.p4, t);
 const Vec2 p123 = lerp(p12, p23, t);
 const Vec2 p234 = lerp(p23, p34, t);
 const Vec2 p1234 = lerp(p123, p234, t);
 
 out_points1.p1 = in_points.p1;
 out_points1.p2 = p12;
 out_points1.p3 = p123;
 out_points1.p4 = p1234;
 
 out_points2.p1 = p1234;
 out_points2.p2 = p234;
 out_points2.p3 = p34;
 out_points2.p4 = in_points.p4;
}
Аналогичные построения для кубической кривой:
quaratic_bezier_subdiv | Редактор функций на основе кривых Безье
Повторюсь, что можно t* взять произвольный, чтобы разбить кривую в любой точке.

Это алгоритм очень важен для рендеринга кривых в редакторе. На его базе, как правило, строят адаптивную ломаную, приближающую форму кривой. Эту ломаную используют для отрисовки кривой.

Как связать формулы с тем, что мы видим в редакторах векторной графики


В векторных редакторах никаких формул нет. Есть кривые, построенные по контрольным точкам:

complex_bezier | Редактор функций на основе кривых Безье

Существует 2 основных типа контрольных точек, использующихся в редакторах –

Фактически, контрольная точка с заданием кривизны предоставляет информацию о 2 точках, по которым в дальнейшем будет строится кривая Безье. Это позиция самой точки и позиция конца ее направляющей.
Линейная контрольная точка предоставляет лишь 1 точку для построения кривой Безье.

Соотнести изображение с формулами кривых Безье не очень сложно.


В зависимости от комбинации типов контрольных точке получаем следующие случаи построения кривых Безье:



Создание 2d редактора Безье: стандартные проблемы.


Стандартных проблем две:

Решение проблемы построения ломаной по кривой Безье


Решение «в лоб» – «пройтись» по кривой, изменяя параметр t с некоторым шагом, получив таким образом набор точек, лежащих на кривой. Эти точки образуют искомую ломаную.
Недостаток данного метода состоит в том, что кривая будет плохо приближаться на участках с большой кривизной. Подробнее останавливаться не буду, хорошие примеры есть в начале данной статьи

Для качественной аппроксимации кривой лучше использовать адаптивный метод. Метод основывается на рекурсивном разбиении кривой на участки, пока на каждом участке мы не достигнем требуемой нам гладкости кривой. Главная загвоздка кроется как раз в критерии для «достигнем требуемой нам гладкости». О тяжких поисках такого критерия можно почитать в статье по ссылке выше, но критерии автора мне не очень понравились из-за своей неустойчивости и множества частных случаев.

Использованный мной критерий порога кривизны, как мне кажется, прозрачнее и устойчивее описанного в статье.
Для квадратичной кривой:
quadratic_bezier_curve | Редактор функций на основе кривых Безье
quad_curve_smooth_criteria | Редактор функций на основе кривых Безье

Для кубической кривой:
cubic_curve | Редактор функций на основе кривых Безье
cubic_curve_smooth_criteria | Редактор функций на основе кривых Безье
Т.е. кривая считается «достаточно гладкой», когда углы между отрезками, соединяющих ее контрольные точки, становятся «достаточно тупыми» - в данном случае для оценки углов между ними используются cos, посчитанные через скалярное произведение нормализованных векторов отрезков. На практике хорошие результаты давали значения tolerance = 1E-4..1E-2.

Критерий не работает, если какие-либо из соседних (т.е. например, P0 и P1, P1 и P2) контрольных точек совпадают. Эти частные случаи решаются следующим образом:



Код для аппроксимации кубической кривой:
void create_cubic_curve_linear_approx(
 std::vector<Vec2>& result_points, const CubicPoints& curve_points, const double angle_threshold)
{
 result_points.push_back(points1.point1);
 add_points_recursive(result_points, curve_points, angle_threshold);
 result_points.push_back(points1.point4);
}

void add_points_recursive(
 std::vector<Vec2>& result_points, const CubicPoints& curve_points, const double angle_threshold)
{
 // Минимальная допустимое расстояние между соседними конрольными точками 
 static const double LEN_THRESHOLD = 1E-06;
 
 const Vec2 seg1 = curve_points.p1 - curve_points.p2;
 const double seg1_len = seg1.get_length();

 const Vec2 seg2 = curve_points.p2 - curve_points.p3;
 const Vec2 seg2_inv = curve_points.p3 - curve_points.p2;
 const double seg2_len = seg2.get_length();

 const Vec2 seg3 = point4 - point3;
 const double seg3_len = seg3.get_length();

 bool need_subdivision = false;
 // Если средний сегмент больше минимальной длины
 if (seg2_len > LEN_THRESHOLD)
 {
  if ((seg1_len > LEN_THRESHOLD && seg1.dot(seg2_inv) > -(1.0 - angle_threshold) * seg1_len * seg2_len) ||
   (seg3_len > LEN_THRESHOLD && seg3.dot(seg2)   > -(1.0 - angle_threshold) * seg3_len * seg2_len))
  {
   need_subdivision = true;
  }
 }
 else
 {
  // Случай вырожденного среднего сегмента
  if (seg1_len > LEN_THRESHOLD && 
   seg3_len > LEN_THRESHOLD &&
   seg1.dot(seg3) > -(1.0 - angle_threshold) * seg1_len * seg3_len)
  {
   need_subdivision = true;
  }
 } 

 if (need_subdivision)
 {
  CubicPoints out_points1;
  CubicPoints out_points2;
  split_curve(curve_points, 0.5, out_points1, out_points2)
 
  add_points_recursive(result_points, out_points1, angle_threshold); 
  add_points_recursive(result_points, out_points2, angle_threshold); 
 }
 else
 {
  const Vec2 point = get_cubic_curve_point(curve_points, 0.5);
  result_points.push_back(point);
 }
}

Конвертирование контрольных точек из одного типа в другой


Для конвертации нет строгих правил, я использовал эвристики из Corel Draw:


  Конечный тип

  Начальный тип

Corner

Cusp

Smooth

Symmetrical

Corner

-

Строим направляющие как 1/3 длины векторов в направлении соседних точек

Corner->Cusp->Smooth

Corner->Cusp->Smooth->Symmetrical

Cusp

Удаляем направляющие

-

Поворачиваем направляющие таким образом, чтобы они легли на биссектрису меньшего угла между старыми направляющими

Сusp->Smooth->Symmetrical

Smooth

Удаляем направляющие

Делаем направляющие независимыми

-

Для обоих направляющих задаем длину как среднее арифметическое их длин старых направляющих

Symmetrical

Удаляем направляющие

Symmetrical->Smooth->Cusp

Убираем ограничение на равенство длин направляющих

-


Псевдокод для не совсем очевидных случаев:
struct ControlPoint
{
 Vec2 position;
 Vec2 handle1;
 Vec2 handle2;
 
 void corner_to_cusp_handles(const ControlPoint* left_adjacent_point, const ControlPoint* right_adjacent_point)
 {
  if (left_adjacent_point != 0)
   handle1 = (left_adjacent_point->position - position) / 3.0;

  if (right_adjacent_point != 0)
   handle2 = (right_adjacent_point->position - position) / 3.0;

  if (left_adjacent_point == 0)
   handle1 = Math::Vector2(-handle2.x, -handle2.y);

  if (right_adjacent_point == 0)
   handle2 = Math::Vector2(-handle1.x, -handle1.y);
 }

 void cusp_to_smooth_handles(void)
 {
  static const double LEN_THRESHOLD = 1E-06;

  const double h1_len = handle1.get_length();
  const double h2_len = handle2.get_length();

  if (h1_len > LENGTH_THRESHOLD && h2_len > LENGTH_THRESHOLD)
  {
   const Vec2 h1_norm = handle1 / h1_len;
   const Vec2 h2_norm = handle2 / h2_len;

   const Vec2 new_handles_dir = h1_norm.dot(h2_norm) > 0.0 ? h1_norm + h2_norm : h1_norm - h2_norm;
   new_handles_dir.normalize();

   handle1 = new_handles_dir * h1_len;
   handle2 = -new_handles_dir * h2_len;
  }
 }

 void smooth_to_symmetrical_handles(void)
 {
  const Vec2 new_handle = (handle1 - handle2) * 0.5;
  handle1 = new_handle;
  handle2 = -new_handle;
 }
};

Страницы: 1 2 Следующая »

#2D, #математика

9 августа 2011

Комментарии [12]