Заполнение областей (многоугольника, контура)

vОбщие замечания

Ø Алгоритм заполнения с упорядоченным списком ребер

Ø Особенности алгоритмов затравочного заполнения

§ Простой алгоритм заполнения с затравкой для четырехсвязной гранично-определенной области

§ Построчный алгоритм заполнения с затравкой для четырехсвязной гранично-определенной области

Общие замечания

В компьютерной графике заполнением многоугольника (или заполнением контура) называют процесс генерации сплошной области, т.е. заполнение этой области определенным цветом. Фигура, ограничивающая область, может быть непосредственно многоугольником или замкнутой кривой, которая при разложении в растр представляется многоугольником. Задать ограничивающий многоугольник можно координатами вершин или описаниями его ребер. Впрочем, граница области может быть определена как-либо иначе, например, совокупностью пикселей, образующих ограничивающий область контур.

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

Общие принципы работы алгоритмов растровой развертки можно описать следующим образом. Для всех ребер многоугольника, за исключением горизонтальных, так или иначе, определяются точки их пересечения с осями сканирующих строк, сдвинутыми по оси y в координатной сетке растра на 1/2 вверх относительно координат адресуемых точек соответствующих рядов пикселей. Независимо от действий конкретного алгоритма результат получается следующим: на каждой сканирующей строке, имеющей такие пересечения, цветом многоугольника заполняются интервалы между парами пересечений, встречающимися на сканирующей строке при следовании вдоль нее от начала к концу; крайние интервалы (от начала строки до первого пересечения и от последнего пересечения до конца строки) и интервалы между этими парами пересечений заполняются фоновым цветом.

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

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

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

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

§ занести каждое пересечение (x, ) в список;

§ отсортировать список по строкам (сверху вниз) и по возрастанию x в строке – (,) предшествует (,), если или и ;

§ выделить из отсортированного списка пары элементов (,) и (,); при этом структура списка будет гарантировать, что в таких парах и ;

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

При работе подобного алгоритма по заполнению, например, приведенного на рис.8.1 пятиугольника на оси сканирующей строки будут выделены две пары точек: с и ; с и . На данной строке заполнятся пиксели с координатами адресуемых точек (1, 3), (2, 3), (5, 3) и (6, 3), т.к. для первых двух пикселей выполняется условие: 1.5 £ x + 0.5 £ 3.25, а для вторых двух: 5 £ x + 0.5 £ 6.75. Рис.8.1 иллюстрирует также полный результат работы алгоритма.

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

Особенности алгоритмов затравочного заполнения

При организации работы конкретных алгоритмов затравочного заполнения учитывается специфика геометрии генерируемой области, а также способ задания ее границы. Различают гранично-определенные и внутренне-определенные области. Для гранично-определенной области граница задается контуром, содержащим пиксели одного цвета, причем ни один из пикселей самой области не может иметь этот цвет, а пиксели, внешние по отношению к границе, могут. Пиксели, расположенные на границе внутренне-определенной области, могут иметь разные цвета, за исключением цвета самой области. Алгоритмы, заполняющие гранично-определенные области, называются гранично-заполняющими, а алгоритмы, работающие с внутренне-определенными областями – внутренне-заполняющими. Гранично- и внутренне-определенные области могут быть четырехсвязными или восьмисвязными. Четырехсвязной называется область, в которой от каждого пикселя можно «добраться» до любого другого, переходя от пикселя к пикселю в двух горизонтальных и двух вертикальных направлениях, т.е. вправо, влево, вверх и вниз. В восьмисвязной области это же можно сделать, добавив к указанным направлениям переходов еще четыре диагональных: вправо и вверх, вправо и вниз, влево и вверх, влево и вниз. Рис.8.2 иллюстрирует изложенные положения: на нем приведены примеры четырехсвязной гранично-определенной (рис.8.2а) и восьмисвязной внутренне-определенной (рис.8.2б) областей. Отметим также то, что граница четырехсвязной области является восьмисвязной, а граница восьмисвязной области – четырехсвязной.

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

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

Последовательность действий обозначенного в заголовке данного раздела алгоритма такова:

§ поместить координаты адресуемой точки затравочного пикселя в стек;

§ пока стек не пуст:

извлечь данные о пикселе из стека; если ему уже присвоено требуемое значение цвета – проигнорировать, если нет, тогда:

присвоить пикселю требуемое значение цвета;

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

Проследим действия такого алгоритма при заполнении области, представленной на рис.8.3. Выберем в качестве затравки пиксель с координатами адресуемой точки, например, (4, 4 ). Данные об этом пикселе помещаются на 1 уровень стека, извлекаются оттуда, и пиксель заполняется, т.е. ему присваивается требуемое значение цвета. Проверка соседних пикселей приводит к помещению в стек на уровни 1, 2 и 3 пикселей, расположенных правее, выше и левее текущего, т.е. (5, 4 ), (4, 5 ) и (3, 4 ) соответственно. Пиксель ниже текущего принадлежит границе, поэтому в стек не попадает. Далее с 3 уровня стека извлекается и заполняется пиксель (3, 4 ). В результате проверки соседних пикселей на освободившийся 3 уровень стека попадает пиксель (3, 5 ), а на 4 уровень – пиксель (2, 4 ). Последующие шаги алгоритма очевидны. На рис.8.3 последовательность заполнения пикселей обозначена стрелками, а уровни стека, на которые попадают данные о пикселях – числами на изображениях пикселей. Поясним только некоторые специфичные случаи в работе алгоритма. После извлечения с 15 уровня стека и заполнения пикселя (3, 1) выясняется, что все соседние с ним пиксели либо уже заполнены, либо принадлежат границе, поэтому ни один из них в стек не помещается. Из стека, с 14 его уровня, извлекается пиксель (7, 1), после чего заполняется данный пиксель и еще три, расположенные выше него. Проверка пикселей, соседних с последним из заполненных, т.е. с пикселем (7, 4 ), снова не приводит к пополнению стека, который на данный момент имеет тринадцать уровней данных. Последующее извлечение с 13 и 12 уровней стека данных о пикселях соответственно (7, 2) и (7, 3) не приводит к каким-либо последствиям. Последним в области заполняется пиксель (6, 5 ), извлеченный перед этим с 11 уровня стека. После проверки соседних с ним пикселей стек, имеющий десять уровней, не пополняется. Далее происходит последовательное извлечение данных с десяти оставшихся уровней стека без какого-либо заполнения. После опустошения стека алгоритм завершает работу.

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

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

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

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

Работу такого алгоритма для случая гранично-определенной области схематично можно описать так:

vпоместить координаты адресуемой точки затравочного пикселя в стек;

vпока стек не пуст:

Ø извлечь данные о пикселе из стека; если ему уже присвоено требуемое значение цвета – проигнорировать, если нет, тогда:

Ø присвоить пикселю требуемое значение цвета;

Ø заполнить интервал с текущим пикселем вправо и влево от него вдоль сканирующей строки до обнаружения границ;

Ø переменным х_лев и х_пр присвоить значения горизонтальных координат адресуемых точек соответственно крайнего левого и крайнего правого пикселей интервала;

Ø в диапазоне х_лев £ х £ х_пр проверить строки, расположение непосредственно над и под текущей строкой; если в них есть еще не заполненные интервалы (т.е. не все пиксели граничные или уже заполненные), то в указанном диапазоне данные о крайнем правом пикселе на каждом интервале поместить в стек.

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

Действие этого алгоритма можно просмотреть на примере, программа которого составлена студентами и сотрудниками МИРЭА.