Растровая развертка сплошных областей и заполнение многоугольников

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

- растровая развертка;

- затравочное заполнение.

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

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

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

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

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

Для растровых графических устройств соседние пиксели на сканирующей строке, вероятно, имеют одинаковые характеристики. Это когерентность растровых строк.

Характеристики пикселей на данной строке изменяются только там, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на области.

Для простого многоугольника на рис. 7 строка 2 пересекает многоугольник при х=1 и х=8.

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

На рис.7 для строки 4 в фоновый цвет установлены пиксели: от 0 до 1, от 4 до 6, от 8 до 10, тогда как пиксели от 1 до 4 и от 6 до 8 окрашены в цвет многоугольника.

Точное определение тех пикселов, которые должны активизироваться, требует некоторой осторожности. Прямоугольник имеет координаты (1, 1), (5, 1), (5, 4), (1, 4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами многоугольника при x=1 и 5. Вспомним, что пиксель адресуется координатами своего нижнего левого угла, значит, для каждой из этих сканирующих строк будут активированы пиксели с х-координатами 1; 2; 3: 4; 5. На рис. 8, а показан результат. Заметим, что площадь, покрываемая активированными пикселями, равна 20, в то время как настоящая площадь прямоугольника равна 12.

Модификация системы координат сканирующей строки и теста активации устраняет это проблему, как это показано на рис.8, 6. Считается, что сканирующие строки проходят через центр строк пикселов, т.е. через середину интервала. Тест активизации модифицируется следующим L образом: проверяется, лежит ли внутри интервала центр пикселя, расположенного справа от пересечения. Однако пиксели все еще адресуются координатами левого нижнего угла, как показано на рисунке. Результат данного метода корректен.

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