КГ Лекция 06. Растровая графика. Растровая развертка сплошных областей.

Растровая развёртка сплошных областей (заливка).

Генерация сплошных областей на базе простых описаний вершин или рёбер многоугольника.

В растровых методах делается попытка определить в порядке сканирования строк принадлежность точки внутренней области контура или многоугольника. Эти алгоритмы обычно просматривают многоугольники (контуры) от верхней точки до нижней. Методы растровой развертки применимы обычно и к векторным дисплеям, в которых они используются для штриховки или закраски контуров.

В методах затравочного заполнения предполагается, что известна некоторая точка (затравка), лежащая внутри замкнутого контура. В алгоритмах затравочного заполнения ищут точки, соседние с затравочными и расположенные внутри контура. Если точка оказывается внутри контура, то она становится новой затравочной точкой и поиск продолжается рекурсивно. Если же точка расположена не внутри контура, то это означает, что обнаружена граница контура. Затравочные алгоритмы применимы только к растровым дисплеям.

Растровая развёртка(заполнение многоугольников или заполнение контуров) – генерация областей на основе простых описаний рёбер или вершин (закраска).

Две категории методов – растровая развёртка и затравочное заполнение. При разработке более эффективных методов учитывается тот факт, что соседние пикселы скорее всего имеют одинаковые характеристики, за исключением пикселов, лежащих на границе. Это свойство принято называть свойством пространственной когерентности.

Алгоритм заполнения с упорядоченным списком ребер

Уточнение:

Никогда не говори Курову, что мы упорядочиваем точки пересечения в алгоритмах с упорядоченном спиком ребер.

Это быстродействующий алгоритм, суть которого состоит в сортировке в порядке сканирования точек пересечений ребер многоугольника, ограничивающего заданную область, со сканирующими строками.

Процесс реализации алгоритма можно разбить на два этапа:

• подготовка (сортировка) данных
• преобразование отсортированных данных в растровую форму.

Описать алгоритм можно следующим образом:

1. Нахождение всех точек пересечения всех сканирующих строк с ребрами многоугольника.
2. Найденные точки пересечения сохраняем в массиве или списке.
3. Точки упорядочиваем, выполняя сортировку по убыванию значений координаты y.
4. Сортируем точки пересечения, расположенные на одной сканирующей строке. Упорядочиваем их по возрастанию абсциссы.
5. Массив точек пересечения, расположенных на одной сканирующей строке, разбиваем на пары и производим закраску пикселей внутри этих интервалов. На этом этапе нужно обработать экстремумы. В случае прохождение очередной сканирующей строки через вершину многоугольника в массиве будут найдены точки с одинаковым значением абсциссы.

Подробнее

При реализации данного алгоритма большое время уходит на подготовку данных, для этого необходимо определить для каждого ребра многоугольника точки пересечений со строками сканирования, проведенными через середины интервалов, используя уже реализованные алгоритм Брезенхема или Цифровой Дифференциальный Анализатор (ЦДА). Горизонтальные ребра не могут пересекать сканирующую строку и, следовательно, игнорируются. Но при синтезе изображения они, естественно, присутствуют, ибо формируются верхней и нижней строками пикселей. Каждое пересечение (X, Y + 1/2) заносится в список. Затем список отсортировывается по строкам и по возрастанию абсциссы oX в строке, то есть точка с координатами (X1, Y1) будет предшествовать точке с координатами (X2, Y2) в том случае, если Y1 > Y2 или при равных ординатах точек - X1 <= X2.

После подготовки данных, они преобразуются в растровую форму, для этого из отсортированного списка выделяются пары точек (X1, Y1) и (X2, Y2) ( они соответствуют условию предыдущего абзаца) и на сканирующей строке инициализируются точки с целыми значениями X, которые соответствуют неравенству: X1 <= X + 1/2 <= X2. При реализации данного алгоритма дополнительные трудности возникают при пересечении сканирующей строки и многоугольника точно по вершине. При использовании соглашений о середине интервала между строками сканирования возможен случай, когда получится нечетное количество пересечений. и, следовательно, разбиение пикселей на пары даст неверный результат.

Правильный результат в этом случае получается, если учитывать точку пересечения в вершине два раза в том случае, если она является точкой локального минимума или максимума, и один раз в противном случае. Локальный максимум или минимум многоугольника в исследуемой вершине определяется с помощью проверки концевых точек ребер, соединенных в данной вершине. Если у обоих конечных точек ординаты 'Y' больше, чем у вершины, значит вершина является точкой локального минимума. Если одна больше, а другая меньше, значит вершина - точка локального максимума. Если же одна ордината больше, а другая меньше, значит вершина не является ни точкой локального минимума, ни точкой локального максимума (V1 - локальный максимум, V3 - локальный минимум, тт. V2,V4 не являются ни локальным минимумом , ни локальным максимумом; то есть при пересечении в тт. V1, V3 учитывается два пересечения со строками сканирования, а в тт. V2 и V4 - одно).

Более эффективный алгоритм с упорядоченным списком ребер

В предыдущем алгоритме формируется большой список точек пересечения, который затем необходимо полностью отсортировать. Эффективность алгоритма существенно возрастает, если повысить эффективность сортировки. Эта задача решается путем разделения сортировки по координате y и сортировки в строке по возрастанию координаты x на основе групповой сортировки по y.

Алгоритм в этом случае выглядит следующим образом:

1. Подготовка исходных данных.
   • Определение для каждого ребра многоугольника точек пересечения со сканирующими строками. Для решения этой задачи используется алгоритм Брезенхема или ЦДА. Горизонтальные ребра не рассматриваются.
   • Размещение координат X найденных точек пересечения в группе, соответствующей y координате сканирующей строки.
   • Сортировка для каждой Y-группы координат X точек пересечения в порядке возрастания, т.е. X1 предшествует X2, если X1 <= X2.
2. Преобразование данных в растровую форму.
   • Выделение для каждой сканирующей строки из списка координат X точек пересечения пар точек пересечений. Закраска пикселов, имеющих X-координаты, лежащие в интервале X1 <= X <= X2.

В данном алгоритме сортировки по координате X и координате Y разделены, поэтому растровую развертку можно производить, не дожидаясь завершения всего процесса сортировки. В данном алгоритме легче также добавлять или удалять информацию из дисплейного списка. Необходимо только добавить или удалить информацию из соответствующей Y-группы, следовательно, заново сортировать требуется только эти Y-группы.

Проблемы с распределением памяти

Проблемы, возникающие при использовании массивов:

• Если используется статический массив, то у нас нет предварительно никаких сведений о том, сколько точек пересечений у нас будет находиться на каждой сканирующей строке. В отсутствии какой-либо информации мы отведенный участок памяти можем равномерно поделить на столько участков памяти, сколько есть сканирующих строк, пересекающих многоугольник. Отведенного участка памяти может не хватить, или его будет слишком много.

• Можно использовать динамический массив. При увеличении размеров динамического массива память выделяется заново, а раннее содержимое массива должно быть скопировано в новый участок памяти, т. е. мы сталкиваемся с дополнительными расходами памяти и времени на копирование элементов массива.

Самый эффективный вариант, с использованием САР (решение проблемы с памятью)

Несмотря на то, что при использовании Y-группы задача сортировки упрощается, при реализации модифицированного алгоритма с упорядоченным списком ребер требуется резервировать большое количество памяти (значительная часть которой не будет использована) или ограничивать число пересечений с данной сканирующей строкой. Эти недостатки легко преодолеваются благодаря введению добавочной структуры данных(в виде списка активных ребер, как это предлагалось для растровой развертки в реальном времени) - связанного списка активных ребер (САР)

В этом случае значительно сокращается потребность в памяти, а точки пересечения со строками сканирования вычисляются в пошаговом режиме. В процессе подготовки данных в алгоритме с упорядоченным списком ребер, использующем список активных ребер необходимо определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую данным ребром.

Это удобно сделать анализируя строки сканирования, проведенные через середины отрезков (через Y + 1/2). Затем ребро многоугольника сохраняется в Y-группе, соответствующей этой сканирующей строке и формируется связанный список, в который заносятся следующие значения:

• начальное значение абсцисс точек пересечения - X;
• число сканирующих строк, пересекаемых ребром многоугольника - Y;
• шаг приращения по оси абсцисс при переходе от одной строки сканирования к другой - X.

В процессе преобразования подготовленных данных в растровую форму для каждой строки сканирования осуществляется проверка соответствующей y-группы на наличие новых ребер, в случае их обнаружения, соответствующие значения заносятся в САР. После чего координаты абсцисс точек пересечения из связанного списка отсортировываются в порядке возрастания (то есть X1 <= X2) и из него выделяются пары точек, с помощью которых активизируются пиксели на строке сканирования для целых значений X аналогично двум предыдущим случаям.

Затем для каждого ребра из САР число сканирующих строк, пересекаемых данным многоугольником - Y, уменьшается на 1. Если в результате, y становится меньше 0, то данное ребро исключается из САР и вычисляется новое начальное значение координаты абсцисс точек пересечения xn = x + x. Затем переходят к новой строке сканирования и этапы реализации алгоритма повторяются. Так как в данном алгоритме минимизированы операции ввода/вывода, то при реализации можно сделать его независящим от устройств.

В итоге алгоритм с упорядоченным списком ребер, использующий список активных ребер, выглядит следующим образом:

1. Подготовка исходных данных.
   • Определение для каждого ребра многоугольника наивысшей сканирующей строки, пересекаемой ребром.
   • Занесение ребра многоугольника в y-группу, соответствующую этой сканирующей строки.
   • Сохранение в связном списке следующих значений: начального значения координаты X точек пересечения;
   • delta_Y - числа сканирующих строк, пересекаемых ребром многоугольника;
   • delta_X - шага изменения координаты X при переходе от одной сканирующей строки к следующей строке.
2. Преобразование этих данных в растровую форму.
   • Проверка для каждой сканирующей строки y-группы на наличие новых ребер. Добавление новых ребер в САР.
   • Сортировка x-координат точек пересечения из САР в порядке возрастания, т.е. X1 предшествует X2, если X1 <= X2.
   • Выделение пар точек пересечений в отсортированном списке.
   • Закрашивание пикселов на очередной сканирующей строке со значениями x-координаты, лежащей в интервале X1 <= X <= X2.
   • Уменьшение на единицу количества пересекаемых строк для всех ребер из САР: delta_Y = delta_Y - 1. Исключение ребра из САР при delta_Y < 0.
   • Вычисление нового значения координаты X точки пересечения со сканирующей строкой X = X + delta_X.
   • Переход к следующей сканирующей строке.

Примечания

• Для активных ребер определяем абсциссы точки пресечения с очередной сканирующей строкой, она хранится во 2ом поле элемента списка.
• Если ребро перестает быть активным, то удаляем элемент списка.
• Опустошение списка => весь многоугольник закрашен.

Псевдокод алгоритма (написанный старшим курсом самостоятельно)

// подготовка
Для всех рёбер:
Заносим в поле x минимальное значение х ребра
Заносим в поле n значение вершины ребра (наивысший у)
Заносим в поле dy модуль разности y-координат концов (кол-во строк)
Заносим в поле dx разность x-координат делёную на разность y-координат
Поле next = NULL

// сортировка
Сортируем рёбра в порядке убывания поля n

// алгоритм
Обнуляем САР
помещаем в переменную у наивысшую используемую строку (y = edges[0].n)
позиция = 0
пока y > 0:
	если просмотрели все рёбра и САР пуст, то завершаем (позиция == кол-во рёбер)
	для всех рёбер после текущей позиции (int j = позиция; j < count_edges; j++):
если поле n == y и поле x > 0 (вершина ребра в текущей сканируемой строке):
			вносим ребро в САР
			позиция = j + 1 (чтобы не проверять уже используемые рёбра)
	заполняем необходимые пиксели (описано ниже)
	y-- (переход на новую строку)
	корректируем все рёбра (dy -= 1, x -= dx)
	удаляем из САР рёбра, для которых поле dy обнулилось

// заполнение пикселей
Из САР заносим все текущие координаты x рёбер в массив/вектор
Сортируем по возрастанию
Высвечиваем все промежутки, номер которых (0 - n) не кратен 2 (каждый чётный промежуток)

Оценка алгоритма по времени:

• В процессе закрашивания цвет пикселей не анализируем, принадлежность пикселей внутренней области многоугольника определяем путем нахождения точек пересечения сканирующих строк с ребрами многоугольника. То есть 0 раз анализируем текущий цвет каждого пикселя.
• В данном алгоритме каждый пиксель изменяет свой цвет ровно 1 раз.
• Данный алгоритм обрабатываем только те пиксели, которые расположены внутри области, то есть никаких лишних пикселей не закрашиваем.

Таким образом, алгоритм с упорядоченным списком ребер является одним из самых быстродействующих.