07. Растровая развертка сплошных областей. Алгоритм с упорядоченным списком ребер.
Растровая развёртка – генерация областей на основе простых описаний рёбер или вершин (закраска).
Особенность алгоритма: ребра многоугольника упорядочиваются по наивысшей сканирующей строке их пересекающей. Наивысшая сканирующая строка - первая строка, пересекающая ребро.
Эффективность алгоритмов с упорядоченным списком рёбер зависит от эффективности сортировки в порядке сканирования точек пересечений рёбер многоугольника со сканирующими строками.
Уточнение:
Никогда не говори Курову, что мы упорядочиваем точки пересечения в алгоритмах с упорядоченном спиком ребер.
Процесс реализации алгоритма с упорядоченным списком рёбер можно разбить на два этапа:
- Подготовка (сортировка) данных.
- Преобразование отсортированных данных в растровую форму.
Чисто формальный подход. Для каждого ребра многоугольника определяются точки пересечения со сканирующими строками. Каждое пересечение заносится в список. Список сортируется по двум координатам.
Описать алгоритм можно следующим образом:
- Нахождение всех точек пересечения всех сканирующих строк с ребрами многоугольника.
- Найденные точки пересечения сохраняем в массиве или списке.
- Точки упорядочиваем, выполняя сортировку по убыванию значений координаты 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).
Куров потом сказал, что всё можно описать боле кратко:
Не учитывается последняя точка - вершина ребра.