Преобразование, связанное с разложением растра изображения в шаблон дисплея называется — растровой разверткой. В отличие от дисплейного списка для векторного дисплея, который содержит информацию только об отрезках и литерах, в данном случае дисплейный список несет информацию о каждом пикселе. Эта информация организовывается и выводится со скоростью видеогенерации в порядке сканирования строк (сверху вниз и слева направо). Различают 4 способа формирования растра: растровая развертка в реальном времени, групповое кодирование, клеточное кодирование и использование памяти буфера кадра. Рассмотрим их.
1.Растровая развертка в реальном времени.
При этом способе сцена (изображение) произвольно представлена терминами визуальных атрибутов (цвет, оттенок, интенсивность) и геометрических характеристик (координаты x,y; углы наклона; текст). Последние упорядочены по координате y. При создании очередного кадра процессор сканирует эту информацию и вычисляет интенсивность каждого пиксела. Требования к памяти — min (дисплейный список + 1 сканирующая строка). Добавление или удаление информации из списка проходят легко (удобно для динамического изображения). Проблема — граничная скорость дисплейного процессора ограничивает сложность изображения. Это означает ограничение числа отрезков или многоугольников в картине, количество пересечений со сканирующей строкой, число цетов или полутонов серого.
Для определения пересечений каждого отрезка дисплейного списка со сканирующей строкой (простой случай) всякий раз при изображении строки обрабатывается весь список. На каждую строку (при регенерации) отводится 63.5 мс. Это показывает, что метод применим для несложных изображений, и тормозит работу на крупных планах. Ввиду того, что не каждый отрезок пересекает сканирующую строку, ввели понятие списка активных ребер (которых это косается), т.е. САР. Методы организации и управления САР различны. Рассмотрим 3 сканирующей строки и многоугольник ABCD (см. Рис. 7), отрезки котрого пересекаются строками 1, 2 и 3.
Для управления САР используют следующее. Отрезки сортируют по наибольшей координате Y. В полученном списке (отсортированном) используют два перемещающихся указателя (один для указания начала, другой — для обозначения конца списка). Указатель начала устанавливают на начало списка (т.е. на отрезок BC), указатель конца на тот последний отрезок в списке, который начинается выше рассматриваемой сканирующей строки (BD). При этом следует корректировать САР, т.е. перемещать указатели, чтобы охватить все строки и включить в список все отрезки (для конца — те что пересекаются или выше сканирующей строки, для начала — исключая те, что кончаются выше сканирующей строки).
Здесь b — задает начало списка, e — конец списка. Проблема заключается в том, что некоторые ребра (например BC) не покидают списка активных ребер. Это устраняется путем введения дополнительной структуры данных. Предварительно проводится групповая сортировка ребер (по координате Y) всех отрезков изображения. При этом создаются области памяти (группы) для каждой сканирующей строки (напр. 512 строк — 512 групп). И при просмотре отрезков в дисплейном списке информация о каждом помещается в группу, соответв. max координате Y. Так, для простого черно-белого контурного изображения необходимо имееть значение X (точки пересечения с групповой сканирующей строкой), DX (изменение координаты при переходе от одной сканирующей строки к другой), DY (число сканирующих строк, пересекаемых отрезком). Список активных ребер для текущей сканирующей строки формируется путем добавления информации из у-группы, соответствующей этой строке. Координаты X точек пересечения при этом сортируются в порядке сканирования, и ребра из САР преобразуются в растровую форму. После этого для каждого отрезка САР значение DY уменьшается на 1, а если DY < 0 — отрезок исключается из списка. Новая координата X точки пересечения для новой сканирующей строки получается добавлением DX. Процесс повторяется для всех сканирующих строк.
Понятно, что рассмотренный метод хорош для отрезков вертикальных или почти вертикальных. Для горизонтально ориентированных количество найденных точек будет мало. Для решения задачи определяют пересечения на двух последовательных сканирующих строках и активируют промежуточные пикселы. Для горизонтальных отрезков используют концевые точки.
