Общий алгоритм растрового векторного изображения
Каков общий алгоритм растеризации векторного изображения? Я нашел много алгоритмов растеризации примитивов, таких как линии, круги, кривые Безье и т. Д. Но в целом, что мне делать? Проще говоря, перейти к векторной фигуре в векторном изображении, получить ее пиксели и поместить их в растровое изображение? Или что-то другое?
И еще вопрос, как я могу улучшить время обработки с использованием параллелизма? Я могу, например, разделить векторные фигуры и одновременно получить их пиксели. Но может быть есть другие способы сделать это?
1 ответ
Общий алгоритм растеризации таков для каждого многоугольника на изображении.
(Многоугольник определяется как одна или несколько замкнутых кривых, состоящих из отрезков прямых и параметрических сплайнов - в обычной практике это сплайны Безье 2-го порядка (коническое псевдоним коническое) и сплайнов Безье 3-го порядка. Эти замкнутые кривые определяются так, чтобы внутренняя сторона всегда слева, так как кривая проходит, поэтому обычные фигуры идут против часовой стрелки, а отверстия - по часовой стрелке.)
(i) (проекция) Преобразование многоугольника в ту же систему координат, что и в целевом растровом изображении. Разрешение не обязательно должно быть одинаковым, а для сглаженных изображений часто больше: например, FreeType использует 64-е пиксели.
(ii) (сделать монотонным по Y) При необходимости разделите каждый сегмент многоугольника на более мелкие сегменты, которые непрерывно идут вверх или вниз. Этот этап необходим только для изогнутых сегментов и относительно прост при использовании сплайнов Безье. Обычный метод состоит в том, чтобы разделить пополам, пока монотонность не будет достигнута. Откажитесь от всех горизонтальных сегментов.
(iii) (отметьте пределы пробега) Нарисуйте каждый сегмент во временное растровое изображение. Используйте алгоритм Брезенхэма для прямых линий; для кривых делите пополам, пока линия не будет дальше (скажем) 1/8 пикселя от реальной кривой, затем используйте прямую линию от начала до конца. При рисовании отметьте пиксели каким-либо образом, чтобы указать (а), являются ли они началом или концом прогонов - нисходящими линиями являются старты, а восходящими линиями - концы; (б) покрытие - доля пикселя, которая находится внутри фигуры. Именно здесь алгоритмы различаются в деталях, и где различаются правила намотки ( ненулевые и четные-нечетные).
(iv) (сканирование) Обходить временное растровое изображение строка за строкой. Для каждой строки сканируйте слева направо. Поддерживать состояние, которое указывает, находится ли текущая позиция внутри фигуры или нет, например, путем добавления числа, сохраненного в растровом изображении, к сохраненному числу. В простой монохромной растеризации это число, записанное на предыдущем этапе, будет равно +1 при пересечении ребра в фигуре и -1 при выходе из фигуры. Накапливать серии пикселей в том же состоянии. Отправьте прогоны в модуль рисования: например, FreeType испускает прогоны, состоящие из координаты Y, координат начала и конца X и покрытия от 0 до 255. Модуль рисования может использовать покрытие в качестве альфа-значения, примененного к текущему цвету чертежа. или в качестве маски, примененной к текстуре.
Выше приведено большое упрощение, но оно дает общее представление.
Большинство программ с открытым исходным кодом используют код растеризации, полученный из одного из следующих проектов:
FreeType - растеризатор шрифтов, который содержит модули растеризатора моно и сглаживания, которые относительно просты в использовании автономно - то есть для любой формы, а не только для шрифтов. Я успешно использовал эту систему в нескольких коммерческих портативных проектах C++.
Система FreeType была вдохновлена Libart Рафа Левиана.
Anti-Grain - еще одна популярная и влиятельная библиотека C++.
Кроме того, Kiia Kallio внедрила систему флагов границ линий сканирования, которая выглядит многообещающе и, по-видимому, быстрее, чем Anti-Grain.
Большинство, но не все из этих библиотек принимают формы, сделанные из квадратичных и кубических сплайнов Безье, а также отрезков прямых линий. Те, которые не (например, библиотека К. Каллио), берут только прямые полигоны; но довольно просто "сплющить" кривую в ряд отрезков, расположенных ближе, чем желаемое максимальное расстояние от фактической кривой. FreeType делает это внутренне, и его код может быть заимствован при необходимости.