2. Процедуры машинной графики

2.4. Алгоритмы заполнения областей, ограниченных полигонами

 

 

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

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

Заполнения проводят под углами, кратными 45°, поскольку только в этом случае отсутствуют “точки-просечки”. Последние имеют место за счет смещения начала вектора, что приводит к пропуску точек области при формировании диагональных шагов (см. рис.2.6). 

Рис. 2.6. Появление точки-просечки

Задачу заполнения решают различными способами, которые делят на два больших класса.

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

Рис. 2.7. Заполнение области, ограниченной контуром, по мере его формирования

Заполнение области по мере формирования контура, который ее ограничивает, состоит в следующем (рис.2.7):

1.  Проводят условную базисную линию, которая, как правило, делит область на 2 части.

2.  Формируют точки траектории контура до появления шагового приращения в направлении базисной линии.

3.  От базисной линии проводят вертикальный (горизонтальный) вектор к установленной ранее точке траектории (возможно также заполнение вектором с углом наклона 45º). Для каждой точки вектора устанавливают цвет.

4.  Действия 2-3 повторяют до момента заполнения первой части области.

5.  Действия 2-3 выполняют для нижней части контура.

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

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

Алгоритмы заполнения области, в которых применяют проверку на четность, базируются на том, что произвольная прямая пересекает замкнутую кривую четное количество раз. Если известно, что первая точка соответствующей линии лежит за контуром, то, выполнив обход этой линии, путем вычислений количества пересечений можно определить, какие отрезки размещены в области. Если число сечений нечетно, то соответствующий отрезок размещен в внутренней области (отрезки AB и CD на рис.2.8), в другом случае – вне области (отрезок BC). 

Рис. 2.8. Определение границы контура по критерию четности

Как правило, вводят вспомогательную переменную с нулевым начальным состоянием. При каждом пересечении контура со сканирующим отрезком прямой состояние переменной меняют на противоположное (рис.2.9). 

Рис. 2.9. Формирование состояний переменной Т при сканировании области.

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

В этом случае можно выполнить анализ по двум вспомогательным прямым ДП1 и ДП2 (рис.2.10), размещенными над и под сканирующим отрезком ОП, которые используют для проверки на четность. Если ни одна с этих прямых не пересекает контур возле точки пересечения, то это означает, что отрезок ОП есть касательным. 

Рис. 2.10. Определение наличия касательных к контуру

Определить "критические" ситуации возможно также по количеству пересечений сканирующего отрезка прямой с контуром (рис.2.11). Если количество пересечений l для соседних строк не совпадает, то необходимо выполнить дополнительный анализ на предмет обработки нештатной ситуации. 

Рис. 2.11. Определение критических ситуаций по количеству пересечений контура со сканирующим отрезком прямой.

Рассмотрим метод и соответствующий ему алгоритм заполнения области, ограниченной сторонами многоугольника, который использует принцип четности. Будем считать, что стороны многоугольника заданы координатами вершин многоугольника хi, уi, которым соответствует максимальное значение у или минимальное значение х, если сторона горизонтальна, а также приращения Dx, Dу для определения координат другой вершины.

Первый шаг алгоритма состоит в сортировке сторон в соответствии с максимальными значениями уi, а при их равенстве – по минимуму хi. В случае равенства и хi используются значения Dх, а затем Dу. При этом выбирается сторона с наименьшим алгебраическим значением. В результате получаем упорядоченный список сторон контура – список очередности.

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

Метка M1 определяет число границ, передаваемых из списка очередности в текущий список: две – если точки соответствуют максимуму; одна – если она не является максимумом; больше двух, если одному значению у соответствует более одного максимума.

Метка М2 служит для введения в текущий список следующей пары границ при переходе в следующий слой. Ее значение отвечает значению y, при котором этот переход должен состояться. Указанными метками метятся первые стороны из списка очередности, с которыми пересекаются прямые, проведенные через вершины многоугольника, являющиеся локальными максимумами. 

Рис. 2.12. Формирование списка очередности. 

Метка М3 определяет число новых границ, к которым производится обращение при завершении работы с текущей границей. Табл.2.1 иллюстрирует формирование списка очередности и меток для получения текущего списка на примере фрагмента области, приведенной на рис.2.12.

Таблица 2.1. Описание границ

Сторона:

Х

І

Х

Y

Метка 1

Метка 2

Метка 3

АВ

ха

YA

XB-XA

Yb-Ya

2

YD

1

АСС

ХА

YA

XC-XA

Yc-Ya

1

0

DC

ХD

YD

XC-XD

Yc-Yd

2

0

DE

xd

YD

XE-XD

Ye-Yd

1

1

EF

хе

Y

XF-XE

Yf-Ye

1

1

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

Заполнение области по критерию связности требует наличия пиксела-затравки, который размещен внутри контура.

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

Простейший рекурсивный алгоритм состоит в рассмотрении четырех соседних к затравочному пикселу элементов на предмет их принадлежности контуру (рис.2.13). Пиксели, которые не принадлежат контуру, в свою очередь могут использоваться в качества затравочных. 

Рис. 2.13. Заполнение области рекурсивным алгоритмом. 

Рассмотренный алгоритм при своей внешней простоте требует значительного объема вычислений. Это связано в первую очередь с дублированием рассмотрения соседних элементов для соседних затравочных пикселей.

Альтернативный нерекурсивный алгоритм состоит в следующем. Начиная с затравочного пиксела (рис.2.14) проводится анализ на принадлежность пикселей контуру, которые находятся влево, а затем вправо от затравочного с одновременным закрашиванием. Дальше осуществляется переход на нижнюю сторону с повторением рассмотренной процедуры. Этот процесс продолжается до полного заполнения нижней от затравочного пиксела части области. Затем проводится заполнение верхней части области.

Рис. 2.14. Заполнение области, ограниченной контуром, по критерию связности 

В случае заполнения невыпуклых областей необходимо реализовать стек, в котором сохраняют пиксели, расположенные вблизи максимумов и минимумов контура. Указанные пиксели используются в качества затравочных. Их последовательно считывают со стека. Очевидно, что задача вычисления этих пикселей не составляет особых проблем.

На рис.2.15 приведен пример задания нескольких затравочных пикселей для невыпуклых контуров. 

Рис. 2.15. Задание точек-«затравок» для невыпуклого контура

Контрольные  вопросы.

1.  В чем причина появления «точек-просечек»?

2.  Как находят касательные к контуру?

3.  Сравните быстродействие алгоритмов по критерию связности и парности.

4.  В каких случаях необходимо несколько «точек-затравок»?

     Содержание