Растр — совокупность цветов и оттенков в виде прямоугольной матрицы. Их количество, для конкретной графической системы, зависит от видеоадаптера, установленной палитры и др. факторов. Матрица может быть сеткой или целочисленной решеткой. Большинство графических библиотек обладают набором простейших алгоритмов (преобразование идеального объекта в растровый образ, обработка растра), однако этого недостаточно. Связность — возможность соединения двух пикселов растровой линией в виде последовательного набора. Остается уточнить — когда два пиксела (x1, y1) и (x2, y2) будут связными. Связность классифицируют на: — 4-х связность (для пикселов, у которых координаты по “x” и по “y” отличаются в сумме на 1. Т.е. верно соотношение: (1) |x1 — x2| + |y1 — y2| ? 1.; — 8-и связность (для пикселов, у которых координаты по “x” или по “y” отличаются не более чем на 1. Для них справедливо: (2) |x1 — x2| ? 1, |y1 — y2| ? 1. Четырехсвязность более сильное понятие, чем восьмисвязность, т.е. любой 4-х связный объект будет и 8-ми связным (но не наоборот). Заключение поясняет Рис.1. Рассмотрим алгоритмы построения отрезка.
Формирование растра.
Преобразование, связанное с разложением растра изображения в шаблон дисплея называется — растровой развёрткой. В отличие от дисплейного списка для векторного дисплея, который содержит информацию только об отрезках и литерах, в данном случае дисплейный список несет информацию о каждом пикселе. Эта информация организовывается и выводится со скоростью видеогенерации в порядке сканирования строк (сверху вниз и слева направо). Различают 4 способа формирования растра: растровая развертка в реальном времени, групповое кодирование, клеточное кодирование и использование памяти буфера кадра.
1.Растровая развертка в реальном времени. При этом способе сцена (изображение) произвольно представлена терминами визуальных атрибутов (цвет, оттенок, интенсивность) и геометрических характеристик (координаты x,y; углы наклона; текст). Последние упорядочены по координате y. При создании очередного кадра процессор сканирует эту информацию и вычисляет интенсивность каждого пиксела. Требования к памяти — min (дисплейный список + 1 сканирующая строка). Добавление или удаление информации из списка проходят легко (удобно для динамического изображения). Проблема — граничная скорость дисплейного процессора ограничивает сложность изображения. Это означает ограничение числа отрезков или многоугольников в картине, количество пересечений со сканирующей строкой, число цветов или полутонов серого. Для определения пересечений каждого отрезка дисплейного списка со сканирующей строкой (простой случай) всякий раз при изображении строки обрабатывается весь список. На каждую строку (при регенерации) отводится 63.5 мс. Это показывает, что метод применим для несложных изображений, и тормозит работу на крупных планах. Ввиду того, что не каждый отрезок пересекает сканирующую строку, ввели понятие списка активных ребер (которых это касается), т.е. САР. Методы организации и управления САР различны.
2. Групповое кодирование. В основу метода положен принцип, утверждающий, что в изображении имеются достаточно большие однородные области, характеризующиеся одинаковой интенсивностью или цветом. При простейшем групповом кодировании определяется только интенсивность и количество последовательных пикселов этой интенсивности, находящиеся на текущей сканирующей строке. Кодируемые данные следует рассматривать группами по 2-м (4-м) значениям в виде схем: | Интенсивность| Длина участка | где длина участка — число последовательных пикселов. | R | G | B | Длина участка | — для цветных изображений (R,G,B — интенсивности компонентов). Преимущества метода: 1) позволяет сжимать данные. Коэффициент сжатия еще выше для сплошных фигур. Величина коэффициента может для изображений группами может приближаться к соотношению 10:1. Это существенно для передач фото по каналам связи. 2) экономия занимаемой памяти (вытекает из первого). Недостатки метода: 1) трудно выполнять действия по изображению отрезка или текста; 2) большие потери времени на выполнение процедур удаления из-за последовательной схемы хранения длин участков. 3) При использовании коротких участков одинаковой интенсивности памяти требуется больше, чем при попиксельном хранении (например, для зон изображения, состоящих из чередующихся фрагментов одинаковой длины, но разной интенсивности).
3. Клеточное кодирование. Если в методе группового кодирования изображение рассматривалось, как линейная или одномерная совокупность пикселов, то при клеточном кодировании сделана попытка с помощью min информации представить целые области изображения, т.е. клетки.
В алфавитно-цифровых дисплеях зоны дисплея разбиваются на клетки, или области, достаточные для содержания одной литеры; составлены из пикселов, хранящихся в ПЗУ. Метод клеточного кодирования можно применить и для вычерчивания линий. При этом надо в ПЗУ хранить и шаблоны сегментов отрезков.
Для произвольной клетки размером n x n существует всевозможных шаблонов отрезков, составленных из пикселов. Например, при n = 8 получим 264. Однако не все шаблоны предоставляют реально возможные сегменты. Так, для алгоритма Брезенхема построения отрезков с tg угла наклона между 0 или 1 существует не более 2n-1 шаблонов, представляющих сегменты отрезков. Применение клеточного кодирования особенно эффективно в случая, когда для дисплейного файла (упорядоченного сверху вниз и слева направо) используется связный список. Однако уровень интерактивности низок (процесс идет автоматически).
4. Буфер кадра. Буфер кадра можно реализовать с помощью сдвиговых регистров. Сдвиговый регистр можно считать стеком FIFO (доступ в порядке очередности). При заполненном стеке, при добавлении вершин новых битов происходит выталкивание ранних битов со дна. Выталкиваемые биты можно интерпретировать, как интенсивность пикселов сканирующей строки. Буфер кадра на сдвиговых регистрах можно реализовать используя по одному регистру на пиксел в сканирующей строке, при длине регистра равному числу строк. Другой вариант заключается в том, чтобы использовать регистр с длиной, равной произведению числа пикселей сканирующей строки и числа строк.
