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