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

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

Сканирующая строка - совокупность пикселей, имеющих одну и ту же координату y. (Определение Курова: сканирующая строка – это строка экрана с определённым текущим, можно сказать, значением координаты Y, то есть совокупность пикселей, имеющих одно определённое значение координаты Y)

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

УПОРЯДОЧИВАЮТСЯ РЁБРА, А НЕ ТОЧКИ ПЕРЕСЕЧЕНИЯ!!!

Процесс реализации можно разбить на две части: 1. Сортировка данных. 2. Преобразование отсортированных данных в растровую форму.

Простой алгоритм

Алгоритм "чисто формальный" (с) Куров, 228 год до н.э.

Псевдокод:

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

Алгоритм не эффективный из-за кучи сортировок. Их будет столько же, сколько сканирующих строк.

Более эффективный вариант.

ГЕНИАЛЬНОЕ РЕШЕНИЕ ПРОБЛЕМЫ!

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

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

Проблемы с памятью

Решение оказалось не таким гениальным, как оказалось...

1. Статический массив - мы не знаем, сколько пересечений изначально. Думаю, тут все очевидно: будет либо слишком много памяти, либо нехватит.

2. Динамический массив. Опять сталкиваемся с дополнительными затратами при реалоке (копирование).

РЕШЕНИЕ ВСЕХ ПРОБЛЕМ: динамический список.

• Первый элемент - номер наивысшей сканирующей строки, пересекающей данной ребро.
• Второй элемент - абсциса точки пересечения очередной сканирующей строки, с рассматриваемым ребро. В начале совпадать будет с абсцисой вершины, рассматриваемого ребро.
• Третий элемент - количество сканирующих строк, которые пересекают расматриваемое ребро. Берем по модулю: ymax - ymin. Нужна, для того чтобы определить в каком случае нужно исключать ребро. Каждый шаг уменьшаем на единицу. Как только dy < 0 - исключаем ребро (оно обработна)
• Четвертый элемент - котангенс угла наклона.
• Пятый элемент - следующий элемент списка.

Активное ребро - ребро, пересекающееся с очередной сканирующей строкой.

• При занесении этих ребер в список, мы их упорядочиваем, по убыванию наибольшего значения координаты у ребра. Тогда первым элементом списка будет элемент, хранящий информацию о ребре с наибольшим значением координаты y. Если ребро активно, переходим к рассмотрению следующего элемента списка.
• Просмотр списка продолжаем до тех пор, пока не встретим ребро, которое не является активным на данной сканирующей строке. (активность определяется сравнением с первым элементом).
• Для активных ребер определяем абсцисы точек пересечения с очередной сканирующей строкой. Хранится во 2 поле элемента списка.
• Чтобы определить абсциссу точки пересечения рассматриваемого ребра, к текущей абсциссе нужно прибавить dx, где dx = x2 - x1 / dy - контангенс угла наклона. Можно в 4 элемент списка закинуть, как я понял.
• Если ребро неактивное - удаляем.
• Опустошение списка - многоугольник закрашен.

ПСЕВДОКОДА НА ЛЕКЦИИ НЕ БЫЛО! КУРОВ СОСИ ЖОПУ

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

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

Этот алгоритм является одним из самых быстродейственных, 10 куровых из 10

Куров стр. 17

Следующий вопрос: 08. Заполнение многоугольников. Алгоритмы заполнения по ребрам, с перегородкой, со списком ребер и флагом.

Предыдущий вопрос: 06. Основные расчетные соотношения и алгоритм Брезенхема для генерации окружности.