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

Автор: Дмитрий Сапельников

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

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

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

Кривые Безье

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

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

Линейная (Linear) – построенная по 2 точкам.

Линейная кривая Безье – обычная линейная интерполяция. Формула:

Квадратичная (Quadratic) – построенная по 3 точкам.

Квадратичная кривая строится рекуррентно как линейная интерполяция 2 линейных кривых.

Если упростить выражение, получим следующую формулу:

Кубическая (Cubic) – строится по 4 точкам.

Кубическая кривая выражается через линейную интерполяцию 2 квадратичных кривых:

После упрощения получим:


Можно простроить кривую для произвольных N точек, используя соотношение:

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

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

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

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

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

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

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


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

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

Пусть у нас есть кривая, построенная по точкам 1-2-3-4

Выберем некоторый параметр 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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

Для кубической кривой:


Т.е. кривая считается «достаточно гладкой», когда углы между отрезками, соединяющих ее контрольные точки, становятся «достаточно тупыми» - в данном случае для оценки углов между ними используются 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);
 }
}

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

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 Следующая

9 августа 2011

Категории: 2D, математика