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

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

Автор: Shalom

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

Редактор, разработка которого легла в основу статьи, был сделан для проекта 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. Во-первых, описанные выше случаи легки и интуитивно понятны в управлении для пользователя, во-вторых, чем больше степень кривой, тем больше вычислений требуется для нахождения точек кривой.

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

Кривая начинается в P₀ и заканчивается в P_n

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

Кривая не зависит от выбора направления движения по ней, т.е.

Прямые P₀P₁ и P_n-1P_nявляются касательными к кривой в начальной и конечной точках соответственно

Все точки кривой находятся внутри выпуклой оболочки точек, по которым построенна кривая; оболочка на рисунке ниже обозначена красным

Любую кривую можно разбить в любой точке , получив 2 кривых той же степени, которые полностью повторяют оригинальную кривую. Иными словами, найдется набор точек , для которого:

кривые стыкуются в точке, соответствующей параметру :

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

кривые и совпадают с оригинальной кривой на соответствующих отрезках:

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

На пункте 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 | Редактор функций на основе кривых Безье

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

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

Точка с заданием кривизны (Curve) - имеет направляющие (в различных редакторах - handles, tangents, direction points), управляющие формой кривой. Обычно такая точка имеет 2 направляющих.
Угловая(Corner) - вершина без направляющих.

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

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

Каждая кривая Безье строится ровно по 2 контрольным точкам. Т.е. если в редакторе мы видим кривую, содержащую 4 контрольные точки (как в примере выше) – значит, она состоит из 3 кривых Безье, 5 контрольных точек - из 4 кривых Безье и т.д. Исключением являются замкнутая кривые - для них число кривых Безье совпадает с числом контрольных точек.
Степень полинома кривой Безье определяется по типам 2 контрольных точек, для которых она построена.

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

Обе контрольные точки – Corner. В этом случае мы получаем прямую, проходящую через позиции котрольных точек т.е. линейную кривую Безье. В примере это прямая P1-P2:

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

Одна из контрольных точек – Curve, другая – Corner. Получаем квадратичную кривую Безье, построенную по позициям 2 контрольных точек и позиции конца направляющей. В примере квадратичная прямая строится для пары контрольных точек P2 (имеет направляющую с концом в точке H) и P3 (не имеет направляющей). Кривая стоится по последовательности точек P2-H-P3.

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

Обе контрольные точки – Curve. Получаем кубическую кривую, построенную по позициям 2 контрольных точек и позиций концов 2 handles. В примере кубическая кривая стоится для контрольных точек P3 и P4. Кривая стоится по последовательности точек P2-H1-H2-P3.

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

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

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

Как отрисовывать кривые – параметрическую кривую в чистом виде отрисовать сложно. Как правило, используется ее аппроксимация ломаной, вершины которой лежат на кривой. Понятно, что стоить ломаную можно множеством способов. Какой выбрать и почему?
Практически во всех векторных редакторах контрольные точки с заданием кривизны подразделяются на 3 типа (названия - из Corel Draw):
- Cusp – точка имеет 2 полностью независимых направляющих. За счет этого можно формировать острые углы с заданной кривизной
- Smooth – точка имеет 2 направляющих, которые противоположно направлены
- Symmetrical – то же самое, что и Smooth, только длины обоих направляющих всегда одинаковы.
Проблема состоит в конвертировании точек из одного типа в другой.

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

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

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

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

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

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

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

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

Если для квадратной кривой P0 P1 P2 совпадают точки P0 P1 или P1 P2 (в программной реализации – находятся на некотором малом расстоянии), квадратичная кривая сводится к линейной, и, следовательно, достаточно добавить к аппроксимирующей ломаной получившийся отрезок линейной кривой.
Если для кубической кривой P0 P1 P2 P3 совпадают точки P0 P1 или P1 P2 или P2 P3 (в программной реализации – находятся на некотором малом расстоянии), используется критерий для кубической кривой (совпадающие точки при применении критерия будут рассматриватся как одна).

Код для аппроксимации кубической кривой:

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]