Как преобразовать замкнутые кривые Безье в растровые изображения? - PullRequest
3 голосов
/ 11 апреля 2010

Мне нужен алгоритм для преобразования замкнутой кривой Безье (возможно, самопересекающейся) в двоичное растровое изображение: 0 для внутренних пикселей и 1 для внешнего. Я пишу код, который должен реализовывать некоторые операции на кривых Безье, кто-нибудь может дать мне несколько ресурсов или учебников по Безье? Википедия и другие ничего не сказали об оптимизации, вычитании, объединении, вставке и удалении узлов и других операциях: -)

альтернативный текст http://www.imagechicken.com/uploads/1271001073057545100.jpg

Ответы [ 2 ]

4 голосов
/ 11 апреля 2010

Эта статья Чарльза Лупа и Джима Блинна подробно описывает ваш вопрос.

Другим вариантом является тесселяция кривой Безье на отрезки и затем использование вашего любимого алгоритма заливки полигонов.

2 голосов
/ 18 августа 2010

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

Вот формула, которую я использовал для вычисления размера шага, чтобы гарантировать, что максимальная ошибка (то есть отклонение отрезков линии от истинной кривой) меньше дельты:

Пусть (x1, y1), (x2, y2), (x3, y3), (x4, y4) будут контрольными точками кривой Безье в пиксельных координатах.j

  dd0 = square(x1-2*x2+x3) + square(y1-2*y2+y3);
  dd1 = square(x2-2*x3+x4) + square(y2-2*y3+y4);
  dd = 6*sqrt(max(dd0, dd1));

Тогда dd является максимальным значением 2-й производной по кривой - поскольку 2-я производная кубической функции является линейной функцией, этот максимум должен иметь место в конечной точке. Здесь я использовал квадрат (х) в качестве сокращения для х * х.

  if (8*delta > dd) {
    epsilon = 1;
  } else {
    epsilon = sqrt(8*delta/dd);
  }

Тогда epsilon - это ваш размер шага: если вы выбираете конечные точки ваших отрезков в t = 0, t = epsilon, t = 2 * epsilon, ..., (и последнюю конечную точку в t = 1), то отрезки будут находиться в пределах дельты от исходной кривой.

Выберите delta = 0.1, и вы получите вывод растрового изображения, который визуально неотличим от исходной кривой.

...