10.7. Заполнение полигонально-определенных областей Области часто определяют через полигоны, и разработано много эффективных алгоритмов для их заполнения сплошным цветом или узором. В некоторых графических пакетах предусмотрены свои собственные эффективные подпрограммы закрашивания. Рассмотрим, как происходит заполнение в одном из таких пакетов.
Предположим, что область, подлежащая закрашиванию, представляет собой полигон Р, описанный совокупностью адресов пикселов р{ - (xt, yt), i - 1,…, N, которые определяют вершины полигона Р. На рис. 10.29 приведен пример для полигона, заданного семью вершинами. Для заполнения полигона Р мы проходим буфер кадров по строкам развертки, закрашивая необходимые участки каждой строки. Как показано на рисунке, нужные участки определяются при нахождении пересечений каждой строки развертки, скажем, у » 3, со всеми ребрами полигона Р. Те серии пикселов, которые лежат между парами ребер, должны лежать внутри Р и закрашиваются желаемым цветом.
Ниже приводится псевдокод, описывающий процесс закрашивания:
for (each scan line L)II для каждой строки развертки L
{Find intersections of L with all edges of P II находим пересечения L со всеми ребрами Р
10.7. Заполнение полигонально-определенных областей
Sort the intersections by increasing x-value II сортируем пересечения по возрастанию х
Fill pixel runs between all pairs of intersections //закрашиваем серии пикселов между всеми парами пересечений }
Например, на рисунке строка развертки при у = 3 пересекает четыре ребра е2, е3, еА, е5. Четыре абсциссы точек пересечения округляются до ближайшего целого, как описывается ниже, и сортируются; в результате получается последовательность 1, 2, 7, 9. Затем закрашиваются следующие две серии: первая от столбца 1 до столбца 2 и вторая от столбца 7 до столбца 9.
Рис. 10.29. Закрашивание нужных участков строки развертки Заметим, что при группировании отсортированных пересечений ребер в пары используется вариант теста «внутри-снаружи» (inside-outside test). В процессе движения вдоль строки развертки мы при каждом пересечении попадаем или внутрь полигона Р, или наружу от него, причем это состояние все время меняется. (Иногда в данном контексте пребывание внутри называют четностью (parity), тогда можно говорить об изменении четности при каждом пересечении.) Если мы попадаем внутрь, то эта последовательность пикселов будет закрашиваться; если попадаем наружу, то нет. Если полигон Р целиком лежит по правую сторону от начала каждой строки развертки, то начальная четность равна out (вне). Отметим, что в данном алгоритме используется связность интервала (span coherence) - стремление нескольких соседних пикселов вдоль строки развертки лежать рядом с внутренним пикселом. Таким образом, целая серия может быть закрашена при минимуме вычислений.