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

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

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

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

Рассмотрим простой алгоритм с упорядоченным списком ребер. На первом этапе производится подготовка исходных данных. Этот этап предусматривает определение точек пересечения ребер многоугольника со сканирующими строками (рис.3.5.3). Для решения этой задачи можно использовать алгоритм ЦДА или алгоритм Брезенхема. Горизонтальные ребра не рассматриваются. Найденные точки сортируются: сначала производится сортировка по строкам, а затем для точек в пределах одной строки производится сортировка по возрастанию координаты x. Например, точка (x1,y1) предшествует точке (x2,y2), если y1> y2 или y1=y2 и x1≤x2.

На втором этапе подготовленные данные преобразуются в растровую форму: в отсортированном списке выделяются пары точек (x1,y1) и (x2,y2). Структура списка гарантирует, что y=y1=y2 и x1≤x2. Закрашиваются пикселы, лежащие на данной сканирующей строке в интервале x1≤x.≤x2.

БОЛЕЕ ЭФФЕКТИВНЫЕ АЛГОРИТМЫ С УПОРЯДОЧЕННЫМ СПИСКОМ РЕБЕР В предыдущем алгоритме формируется большой список точек пересечения, который затем необходимо полностью отсортировать. Эффективность алгоритма существенно возрастает, если повысить эффективность сортировки. Эта задача решается путем разделения сортировки по координате y и сортировки в строке по возрастанию координаты x на основе групповой сортировки по y. Алгоритм в этом случае выглядит следующим образом:

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

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

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

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

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