Общий алгоритм растрирования векторного изображения

Question

Каков общий алгоритм растеризации векторного изображения?Я нашел множество алгоритмов растеризации примитивов, таких как линии, круги, кривые Безье и т. д.Но в общем, что мне делать?Просто взять каждую векторную фигуру в векторном изображении, получить ее пиксели и поместить их в растровое изображение?Или что-то другое?

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

Answer 1

Общий алгоритм растеризации таков для каждого многоугольника изображения.

(Многоугольник определяется как одна или несколько замкнутых кривых, состоящих из сегментов прямых и параметрических сплайнов - в обычной практике это сплайны Безье 2-го порядка (квадратичный псевдоним конуса) и 3-го порядка (кубический).Эти замкнутые кривые определены так, что при прохождении кривой внутренняя часть всегда находится слева;поэтому обычные формы двигаются против часовой стрелки, а отверстия — по часовой стрелке.)

(i) (проекция) Преобразуйте многоугольник в ту же систему координат, что и целевое растровое изображение.Разрешение не обязательно должно быть одинаковым, а для сглаженных изображений часто бывает больше:например, FreeType использует 64 доли пикселей.

(ii) (сделать монотонным по Y) При необходимости разбить каждый сегмент многоугольника на более мелкие сегменты, которые непрерывно идут вверх или вниз.Этот этап необходим только для изогнутых сегментов и относительно прост при использовании сплайнов Безье.Обычный метод — многократное деление пополам, пока не будет достигнута монотонность.Отбросьте все горизонтальные сегменты.

(iii) (отметьте пределы выполнения) Нарисуйте каждый сегмент во временном растровом изображении.Используйте алгоритм Брезенхема для прямых линий;для кривых делите пополам, пока линия не окажется не дальше (скажем) 1/8 пикселя от реальной кривой, затем используйте прямую линию от начала до конца.При рисовании пометьте пиксели каким-либо образом, чтобы указать (а) являются ли они началом или концом серий: нисходящие линии — это начало, а восходящие линии — концы;(б) покрытие — доля пикселя, находящаяся внутри фигуры.Здесь алгоритмы различаются в деталях, а здесь правила намотки (ненулевой против даже странно) выделяются.

(iv) (сканирование) Обход временного растрового изображения, строка за строкой.Для каждой строки сканируйте слева направо.Поддерживайте состояние, которое указывает, находится ли текущая позиция внутри фигуры или нет, путем (например) добавления числа, хранящегося в растровом изображении, к сохраненному числу.При простой монохромной растеризации это число, записанное на предыдущем этапе, будет равно +1 при пересечении края в форме и -1 при выходе из формы.Накопите серии пикселей в одном и том же состоянии.Отправьте прогоны в модуль рисования:например, FreeType генерирует прогоны, состоящие из координаты Y, начальной и конечной координат X, а также покрытия от 0 до 255.Модуль рисования может использовать покрытие как альфа-значение, применяемое к текущему цвету рисования, или как маску, применяемую к текстуре.

Вышеупомянутое является большим упрощением, но дает общую идею.

Большинство программ с открытым исходным кодом используют код растеризации, полученный из одного из следующих проектов:

FreeType - растеризатор шрифтов, который содержит модули растеризации как моно, так и сглаживания, которые относительно легко использовать автономно - то есть для любой формы, а не только для шрифтов.Я успешно использовал эту систему в нескольких коммерческих портативных проектах на C++.

Система FreeType была вдохновлена ​​книгой Рафа Левиена. Либарт.

Антизерновой — еще одна популярная и влиятельная библиотека C++.

Существует также система флажков края линии сканирования реализованный Kiia Kallio, который выглядит многообещающе и кажется быстрее, чем Anti-Grain.

Большинство, но не все из этих библиотек поддерживают формы, состоящие из квадратичных и кубических сплайнов Безье, а также отрезков прямых линий.Те, которые этого не делают (например, К.библиотека Каллио) принимает только многоугольники с прямыми краями;но довольно легко «сгладить» кривую, превратив ее в серию сегментов, находящихся на расстоянии, превышающем желаемое максимальное расстояние от фактической кривой.FreeType делает это внутри себя, и его код можно позаимствовать при необходимости.