Как преобразовать замкнутые кривые Безье в растровые изображения?

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

http://www.imagechicken.com/uploads/1271001073057545100.jpg


algorithm math bezier
person sorush-r    schedule 11.04.2010    source источник

Ответы (2)


arrow_upward
4
arrow_downward

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

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

person brainjam    schedule 11.04.2010
comment
Увы, ссылка не работает, Джим. Это то же самое: research.microsoft.com/en-us /um/люди/cloop/loopblinn05.pdf - person Pierre; 12.09.2013

arrow_upward
2
arrow_downward

Хочу добавить, что вариант тесселяции очень эффективен и дает отличные результаты. Звучит неправильно аппроксимировать кривую Безье отрезками, потому что вы думаете, что результат будет выглядеть как многоугольник. Хитрость заключается в том, чтобы сделать сегменты линий достаточно короткими, чтобы ошибка была очень маленькой (скажем, менее 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);
  }

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

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

person Peter Selinger    schedule 18.08.2010