07. Растровая развертка сплошных областей. Алгоритм с упорядоченным списком ребер. - p1xelse/CG GitHub Wiki

Увертюра

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

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

Уточнение:

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

Процесс реализации алгоритма с упорядоченным списком рёбер можно разбить на два этапа:

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

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

Чисто формальный подход. Для каждого ребра многоугольника определяются точки пересечения со сканирующими строками. Каждое пересечение заносится в список. Список сортируется по двум координатам.

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

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

Простая версия алгоритма крайне неэффективна: несколько сортировок + сортируем все точки пересечения (т.е. нужно ещё и всё это хранить => очень много памяти). Повысить эффективность алгоритма можно, повысив эффективность сортировки. Этот вывод подводит нас к более эффективному алгориму с упорядоченным списком ребер – эффективность повышается за счет введения групповой сортировки по y.

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

В нем сортировка по координате y выполняется одновременно с нахождением точек пересечения.

Память, отведенную для хранения точек пересечения, разбиваем на столько участков, сколько сканирующих строк, пересекающих ребра многоугольника. Эти участки памяти можно назвать Y-группами.

Очередную найденную точку пересечения заносим в ту Y-группу, которая соответствует сканирующей строке. То есть, первая сортировка - самая трудоёмкая, фактически отсутствует.

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

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

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

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

Самый эффективный вариант, с использованием САР и динамического списка

Вместо того, чтобы хранить точки пересечения контура со всеми сканирующими строками, можно хранить только точки пересечения контура с текущей сканирующей строкой – Список Активных Ребер. Это позволит значительно снизит требуемый объем памяти.

Ребро в списке активных ребер описывается с помощью структуры:
dY - количество сканирующих строк, пересекаемых ребром X - абсцисса точки пересечения ребра и текущей сканирующей строки dX - изменение абсциссы точки пересечения с ребром при переходе к следующей сканирующей строке

Такая структура позволяет не пересчитывать точки пересечения заново при переходе к следующей строке, а скорректировать значение в САР от предыдущей строки - это снижает вычислительные затраты.

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

Просмотр списка продолжаем до тех пор, пока не встретим ребро, которое не является активным на данной сканирующей строке. (активность определяется сравнением с Nm).

Для активных ребер определяем абсциссы точки пресечения с очередной сканирующей строкой, она хранится во 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 раз.
Данный алгоритм обрабатываем только те пиксели, которые расположены внутри области, то есть никаких лишних пикселей не закрашиваем.

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

Проблема нескольких горизонтальных рёбер, находящихся на одной строке

Пример от Курова (который он дал мне на защите лабораторной):

Нас интересует, как правильно закрасить строку, на которой находятся вершины 1 2 4 5 7 8 10. Центр координат находится в верхнем левом углу, ось y направлена вниз. Как происходит закраска (2-4) описано ниже:

Рассмотрим, что происходит ДО интересующей нас строки, на которой расположены вершины 1 2 4 5 7 8 10. На этом моменте в САР ребра (2-3) и (3-4). Будет закрашена внутренняя часть двух ребер, образованного (2-3) и (3-4).
На САМОЙ сканирующей строке ребра (2-3) и (3-4) исключены из САР (dy <= 0), а ребра (1-14), (5-6), (6-7), (8-9), (9-10) и (10-16) добавлены в САР. Именно на этом моменте произойдет разбиение по парам. Образуются следующие пары рёбер: (1-14) и (5-6), (6-7) и (8-9), (9-10) и (10-16). Начинается закраска, закрасится линия (1-5), (7-8) и вершина 10. Линия (1-5) закрашивает промежутки (1-2), (2-4) и (4-5).

Куров потом сказал, что всё можно описать боле кратко:

Не учитывается последняя точка - вершина ребра.