КГ Лекция 07. Растровая графика. Заполнение многоугольников.
Пиксель может иметь либо цвет фона, либо цвет закраски.
Считаем, что эти 2 цвета дополняют друг друга (инвертируют).
Для каждой сканирующей строки, пересекающей ребро многоугольника, дополнить(проинвертировать) все пиксели, расположенные правее точки пересечения.
Задается цвет фона и цвет закраски; цвет закраски = !(цвет фона), цвет фона = !(цвет закраски) (инверсия/дополнение).
В алгоритме заполнения по ребрам в отличие от предыдущего не требуется создавать и сортировать списки различных данных. Он очень прост:
- Необходимо для каждой строки сканирования, пересекающей ребро многоугольника, ограничивающего закрашиваемую область, в точке с координатами
(X1, Y1) - Активизировать все пиксели, которые лежат справа от
(X1, Y1)и для которых справедливо неравенство :X + 1/2 > X1.
К каждому ребру многоугольника алгоритм применяется индивидуально. Пересечения строк сканирования осуществляется аналогично алгоритму с упорядоченным списком ребер, то есть определяются точки пересечений со сканирующими строками, проведенными через середины интервалов (Y + 1/2). Рекомендуется использовать этот алгоритм совместно с дисплейным файлом, что позволяет выбирать и обрабатывать ребра в любом порядке. Ибо тогда при обработке ребра многоугольника обрабатываются пиксели из дисплейного файла, соответствующие точкам пересечения ребра со строкой сканирования.
После обработки всех ребер многоугольника, ограничивающего закрашиваемую область, дисплейный файл выводится в порядке сканирования на экран графического дисплея.
Примечание: Если брать не выпуклый многоугольник, то цвет каждого пикселя может изменяться многократно! Если пиксель изменяет свой цвет четное кол-во раз, то получим фоновый цвет. Если нечетное => цвет закраски.
- Оценка эффективности алгоритма (по времени)
- Многократной обработкой одного и того же пикселя в случае областей закрашивания сложной формы(столько раз, сколько изменяем цвет пикселя);
- Приходится обрабатывать не только те пиксели, которые находятся внутри многоугольника, но и пиксели за его пределами.
- Зависимостью алгоритма от операций ввода/вывода.
Алгоритм крайне неэффективный!
Кратко: Ребра никак не упорядочиваются, сортировка не происходит. В этом алгоритме ребра могут обрабатываться в произвольном порядке. Алгоритм прост, но требует больших временных затрат, поскольку некоторые пиксели могут обрабатываться несколько раз.
Количество обработок пикселя определяется количеством ребер, расположенных левее этого пикселя.
Для сокращения числа обрабатываемых пикселей используется "перегородка".
Перегородка – воображаемая вертикальная прямая, которую мы проводим с целью уменьшения количества раз изменения цвета каждого пикселя.
В этом случае алгоритм модифицируется следующим образом: анализируется каждая точка пересечения каждого ребра многоугольника со строкой сканирования. Эффективность повышается за счет введения перегородки. Если текущая точка пересечения находится слева от перегородки, то активизируются все пиксели, центры которых лежат справа от точки пересечения ребра со строкой сканирования и слева от перегородки. Если же точка пересечения находится справа от перегородки, то активизируются пиксели, центры которых расположены слева или на пересечении строки сканирования с ребром многоугольника и справа от перегородки. Рекомендуется проводить перегородку через одну из вершин многоугольника и реализовывать данный алгоритм совместно с использованием дисплейного файла.
Дополнить цвет пикселей, расположенных правее точки пересечения сканирующей строки с ребром многоугольника, но левее перегородки, если пересечение расположено левее перегородки.
- Для каждой сканирующей строки, пересекающей ребро многоугольника:
- Если пересечения находится слева от перегородки, то дополнить (проинвентировать) все пикселы, центры которых лежат справа от пересечения сканирующей строки с ребром и слева от перегородки.
- Если пересечение находится справа от перегородки, то дополнить все пикселы, центры которых расположены слева или на пересечении сканирующей строки с ребром и справа от перегородки.
- Алгоритма заполнения с перегородкой все же остается неоднократная обработка части пикселей.
Для того, чтобы избавиться от этого, разработан модифицированный алгоритм заполнения сплошной области со списком ребер и флагом. Алгоритм со списком ребер и флагом - двух-шаговый алгоритм:
- Во-первых, обрисовывается контур, ограничивающий область, в результате чего на каждой строке сканирования определяются пары ограничивающих пикселей - т.е. очерчивание границ многоугольника;
- Во-вторых, активизируются пиксели, расположенные между вычисленными на предыдущем шаге ограничивающими пикселями - т.е. заполнения многоугольника.
Вводится в рассмотрение еще и флаг - признак расположения очередного пикселя внутри или вне многоугольника.
- Флаг = истина, если пиксель расположен внутри многоугольника;
- Флаг = ложь, если пиксель расположен вне многоугольника.
1. Обрисовка контура:
Используя соглашения о середине интервала между
сканирующими строками для каждого ребра, пересекающего сканирующую строку,
отметить самый левый пиксел, центр которого лежит справа от пересечения,
т.е. X + 1/2 > X_пересечения.
2. Заполнение:
Для каждого сканирующей строки, пересекающей многоугольник (Цикл от Ymax до Ymin)
2.1) f = 0, если пиксель находится вне области
(f - промежуточная переменная,
показывающая расположение очередного пиксела:
fl=0 - пиксел лежит вне области заполнения,
fl=1 - пиксел лежит внутри заполняемой области);
2.2) X = Xl (Xl - левая граница)
2.3) пока (X <= Xr) (Xr - правая граница) выполнить следующие действия:
Если пиксель (цвет) (X, Y) = граничному значению (цвету), тогда инвертировать флаг
(f = 1, если было f = 0)
(f = 0, если было f = 1)
Если f = 1, тогда присвоить пикселю (X, Y) цвет многоугольника
Иначе присвоить пикселю (X, Y) цвет фона
X = X + 1
Y = Y + 1
При реализации данного алгоритма каждый пиксель обрабатывается только один раз, следовательно временные затраты на выполнение операций ввода/вывода значительно меньше, чем в простом алгоритме заполнения по ребрам или в алгоритме с перегородкой. Существует аппаратная реализация алгоритма со списком ребер и флагом, в этом случае его скорость выполнения увеличивается на несколько порядков по сравнению с упорядоченным списком ребер (при программной реализации скорость выполнения алгоритмов отличается незначительно, в чем предлагается убедиться при выполнении лабораторной работы).
На стадии отрисовки границ, два ребра могут сливаться в одно. Как вариант – отрисовывать границу с использованием инверсного цвета пера. Либо же, первое ребро отрисовывается, при отрисовке последующих – если точку надо поставить в ту точку, которая уже подсвечена, то поставить её рядом.
Также извечный вопрос строки, проходящей через вершины. Также, использовать обычный способ отрисовки отрезков нельзя – может возникнуть разбиение; точек пересечения со сканирующей строкой может оказаться несколько.