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