Лекция №1


НазваниеЛекция №1
Дата26.10.2012
Размер77 Kb.
ТипЛекция

Алгоритмические основы машинной графики

Лекция № 1



    Лекция 5. Часть II.

    Заполнение многоугольных областей



Данная лекция может содержать ошибки (как логические, так и грамматические).
Авторы будут признательны за любые сообщения об ошибках, неточностях, а также за любые комментарии и дополнения, присланные по адресу Denis@fit.com.ru (Денису Иванову).



Содержание

1. Введение 1

2. Описание алгоритмов 2

2.1 Алгоритм со списком реберных точек 2

2.2 Алгоритм со списком активных ребер 3

2.3 Алгоритм с операцией XOR 5

2.4 Исключительные случаи 6

2.5 Алгоритм 2 с операцией XOR 6


1.Введение


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

Для удобства каждое ребро многоугольника будем задавать координатами (x1, y1) и (x2, y2) его концов, так, что y2y1. Условимся также отсчитывать на экране координату x слева направо, а y – сверху вниз (таким образом, точка (x1, y1) будет верхним концом ребра, а (x2, y2) – нижним).

Большинство алгоритмов заполнения основано на том факте, что любое горизонтальное сечение контура многоугольника состоит из четного числа точек. Это утверждение неверно в двух случаях (см. рис. 1):

1) когда секущая прямая содержит горизонтальное ребро

и
2) когда она содержит вершину, а оба смежных ребра лежат выше (ниже) ее.

Рис. 1 Исключительные случаи

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

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

2.Описание алгоритмов

2.1Алгоритм со списком реберных точек


Этот алгоритм состоит из трех основных этапов.

­Этап I. Растеризуем все негоризонтальные ребра многоугольника, помещая полученные точки в списки: каждому значению y = ymin, ymin+1, …, ymax сопоставляется список x-координат всех пикселей из растеризации, находящихся на горизонтали y (здесь ymin и ymax – минимальная и максимальная y-координаты пикселей в растровом изображении многоугольника).

Формально эту процедуру можно записать так:

Для каждого ребра (x1, y1) – (x2, y2)

{

; // Округление до большего

;

;

while(y <= y2)

{

PutToList(x, y); // поместить x в список,

// соответствующий данному y

y++;

x += Δx;

}

}

Здесь Δx есть смещение по x при движении вдоль ребра, соответствующее увеличению y-координаты на 1 (см. рис. 2).

Р
ис. 2.
Смещение по горизонтали на Δx
при переходе на следующую строку

Рис. 3. Пример сечений многоугольника

Д
ля многоугольника, изображенного на рис. 3, списки будут иметь вид:

ymin:

x1, x2

ymin+1:

x1’, x2





y0:

x1’’, x2’’, x3’’, x4’’





ymax:



­Этап II. Для каждого y упорядочим список по возрастанию x.

Этап III. Для каждого y закрасим все промежутки вида . Заметим, что, согласно приведенному выше утверждению, в каждом списке содержится четное число элементов.

2.2Алгоритм со списком активных ребер


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

Перейдем к формальному описанию алгоритма.

Этап I. Для каждого ребра создадим структуру данных:

;

;

;

Все такие структуры поместим в список (далее – y-список) и упорядочим его по возрастанию y.

Этап II.

САР = пустой;

y = y_список[ первый элемент ].y;

do{

Добавить в САР все ребра из y-списка, у которых ребро.y = y,

сохраняя упорядоченность САР по возрастанию x

(при изъятии ребра удаляются из y-списка);

Закрасить промежутки (x2i-1, x2i) в строке y;

y++;

Для каждого ребра из САР по порядку

{

if(y > ребро.y2) удалить ребро из САР;

else{

ребро.x += ребро.Δx;

while(соседнее_слева_ребро(ребро).x > ребро.x)

поменять местами в САР ребро с соседним;

}

}

}while(САР не пуст);

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

Цикл while используется для сохранения упорядоченности САР, которая может нарушиться при изменении значений x на Δx. Пример такой ситуации показан на рис. 4. При ее возникновении указанный цикл выполняет локальную сортировку САР методом «пузырька».

Р
ис. 4.
Локальная сортировка САР

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

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

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

2.3Алгоритм с операцией XOR


Этот оригинальный алгоритм использует свойства операции XOR (исключающее «ИЛИ»). Напомним, что XOR – бинарная операция над битами, действующая по правилу:

a

0

0

1

1

b

0

1

0

1

a XOR b

0

1

1

0

Пусть контур многоугольника растеризован и выведен на экран. Тогда закрашивание его сводится к заполнению в каждой строке растра всех промежутков вида , где через xk обозначены x-координаты «включенных» пикселей в данной строке, упорядоченные по возрастанию (см. рис. 5, а).

Р
ис. 5.
Варианты закрашивания в отдельной строке

Через обозначим состояние пикселя с координатами (x, y): , если пиксель «включен» и в противном случае. Нетрудно убедиться, что последовательное выполнение операции

XOR

для x = 1, 2, 3, …, X–1 (где X – горизонтальный размер растра) приведет к требуемому результату с той лишь разницей, что последний пиксель в каждом промежутке закрашен не будет (рис. 5, б). Эта небольшая неточность в большинстве случаев некритична и визуально незаметна.

Формально алгоритм записывается так:

Растеризовать контур многоугольника и вывести его на экран;

for(y = 1; y <= Y; y++)

for(x = 1; x <= X - 1; x++)

I(x + 1, y) = I(x + 1, y) XOR I(x, y);

Если же требуется получить результат, соответствующий рис.5, а, то можно либо после закрашивания повторно вывести на экран контур многоугольника, либо воспользоваться следующей модификацией приведенного алгоритма (называемой «XOR с флагом»):

Растеризовать контур многоугольника и вывести его на экран;

for(y = 1; y <= Y; y++)

{

flag = 0;

for(x = 1; x <= X; x++)

{

if( I(x, y) == 1 ) flag = 1 - flag;

if( flag == 1 ) I(x, y) = 1;

}

}

Достоинством алгоритмов XOR является их предельная простота. Недостаток – невозможность работы при наличии посторонних изображений на экране.

2.4Исключительные случаи


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

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

XOR 1.

Это приведет к тому, что верхние (нижние) концы ребер, попавшие в один и тот же пиксель, не будут выведены, а значит, «одиночные» точки в строках растра будут исключены.

2.5Алгоритм 2 с операцией XOR


Алгоритм заключается в инвертировании цвета всех пикселей, расположенных левее i-го ребра, производимом последовательно для i = 1, 2, …, N (порядок нумерации ребер не имеет значения). Горизонтальные ребра при этом игнорируются. Как видно из рис. 6, в результате закрашенными окажутся все внутренние пиксели многоугольника и только они.

Р
ис. 6.
Шаги закрашивания многоугольника

К достоинствам данного алгоритма можно отнести его простоту и оригинальность, а так же отсутствие дополнительных структур данных. Недостатком является необходимость выполнения большого числа операций с пикселями (до N операций с каждым пикселем), в том числе и вне многоугольника. В частности, чем больше расстояние между многоугольником и правой границей экрана, тем больше будет совершено «лишних» операций.

О
т этого недостатка свободна модификация данного алгоритма – «XOR-2 с перегородкой». Идея ее заключается в том, чтобы инвертировать область не между ребром и правой границей экрана, а между ребром и вертикальной прямой («перегородкой»), мысленно проведенной в любом удобном месте – например, пересекающей многоугольник (см. рис. 7).

Рис. 7. Закрашивание с перегородкой



© Группа Компьютерной Графики, 2003
Лаборатория Вычислительных Методов, Мех-мат МГУ


Стр. из



Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница