Алгоритм заполнения по ребрам

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

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

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

1) подготовить данные:

- определить для каждого ребра многоугольника точки пересечения со сканирующими строками, проведенными через середины интервала, (можно использовать алгоритм Брезенхема или ЦДА); горизонтальные ребра игнорируются;

- занести каждое пересечение (X,Y+1/2) в список. Отсортировать список по строкам и по возрастанию X в строке; т.е. X1, Y1 предшествуют X2, Y2, если Y1 > Y2 или Y1 = Y2 и X1 £ X2;

2) преобразовать эти данные в растровую форму:

- выделить из отсортированного списка пары элементов (X1, Y1 ) и (X2, Y2); структура списка гарантирует, что Y = Y1 = Y2 и X1 < X2;

- активизировать на сканирующей строке Y пиксели для целых значений X, таких, что X1 £ X +1/2 £ X2.

Алгоритм с упорядоченным списком ребер очень мощный. Каждый пиксель изображения активизируется только один раз, следовательно, минимизированы операции ввода-вывода. Главный недостаток алгоритма состоит в больших накладных расходах, связанных с поддержкой и сортировкой различных списков. В другом методе растровой развёртки сплошных областей большинство из этих списков устранено. Этот метод называется алгоритмом заполнения по ребрам.

Алгоритм заполнения по ребрам

Для каждой сканирующей строки, пересекающей ребро многоугольника в (X1, Y1), дополнить, т.е. активизировать, подсветить все пиксели, у которых центры лежат справа от (X1, Y1), т.е. для (X1,Y1), X+1/2>X1.

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

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

Главный недостаток – для сложного изображения каждый пиксель может обрабатываться много раз. Следовательно, эффективность алгоритма ограничена скоростью ввода/вывода.

Число обрабатываемых пикселов можно сократить, если ввести так называемую перегородку.

Алгоритм заполнения с перегородкой

Для каждой сканирующей строки, пересекающей ребро многоугольника:

- если пересечение находится слева от перегородки, то дополнить все пиксели, центры которых лежат справа от пересечения сканирующей строки с ребром и слева от перегородки;

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

Обычно перегородка проходит через одну из вершин многоугольника, и снова удобнее всего применять данный алгоритм с буфером кадра. Недостаток – неоднократная активизация части пикселов.