Алгоритм закраски областей, заданных списком вершин

(метод построчного сканирования)

Интерполяция яркости при закраске областей

О линейной интерполяции яркости при закраски области можно говорить, если закрашиваемая фигура плоская т.е. лежит в одной плоскости, например (ХУ).

Рис. 2.9.5.

Плоскость определяется по трём точкам:

Рис. 2.9.6.

|| || - определитель матрицы;

A·x + B·y + D A В D

V = - ¾¾¾¾¾¾¾ = a·x + b·y + g, где a = - ¾, b = - ¾, g = - ¾;

C С C C

V = V₁ + α (х - х₁)+β (у - у₁), где

V – яркость в произвольной точке, V₁ – яркость известная.

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

Рис.2.9.7.

Сначала находят y_max и y_min. Далее для текущей у-координаты находят крайнее левое и крайнее правое ребро. Начинают с крайнего левого ребра: идут вправо (и закрашивают соответствующие точки) до пересечения со следующим ребром. Также необходим анализ на наличие локальных экстремумов. В этих точках режим закраски не меняется.

Алгоритм работает с помощью 2-х таблиц:

1. 1. таблица ребер (ТР);

2. 2. таблица активных ребер (ТАР);

В ТР заносятся все ребра, а в ТАР лишь те ребра, которые мы пересекаем.

Составление ТР:

Все ребра делятся на группы по нарастанию у-координаты, а внутри группы рёбра упорядочиваются в соответствии с нарастанием х_нач. Ребро в таблицу заносится только 1 раз, горизонтальные ребра игнорируются.

Таблица рёбер:

х_{КОН ¾} х_НАЧ V_{КОНЕЧ ¾} V_НАЧ

Dх = ¾¾¾¾¾¾; DV = ¾¾¾¾¾¾¾;

y_{max ¾} y_min y_{max ¾} y_min

Алгоритм

1. 1. Сформировать ТР и подготовить ТАР

2. 2. Выбор первой координаты сканируемой строки: у = min {y_min};

3. 3. Если у = у_min, то перенос группы из ТР в ТАР.

Таблица активных ребер (ТАР)

4. Упорядочивание ребер в ТАР по возрастанию х_НАЧ.

5. Сканирование (проводят сканирующую строку).
а) переключение режимов по х_НАЧ

б) учёт прохождения через вершины – локальные экстремумы. Если точка – локальный экстремум, то режим следует сохранить. Для отслеживания данной ситуации можно включить в ТР у_max, при совпадении необходим дополнительный анализ.

в) проводить линейную интерполяцию яркости при закраске от (х_НАЧ , V_НАЧ)_i до (х_НАЧ , V_НАЧ)_i+1

6. Удалить из ТАР те ребра, для которых справедливо у = у_max

7. Для всех элементов в ТАР произвести: х_НАЧ = х_НАЧ + ∆х; V_НАЧ = V_НАЧ + ∆V;

8. Переход к следующей сканирующей строке: y=y+1;

9. Проверка на окончание: если y>max{у_max}, то конец, иначе осуществить переход к п.3).