Трёхмерная компьютерная графика
Категория реферата: Рефераты по информатике, программированию
Теги реферата: доклад, контрольная работа 10
Добавил(а) на сайт: Nadezhda.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата
Внутренне- или гранично-определённые области могут быть 4- или 8- связными. Если область 4-связная, то любой пиксел в области можно достичь с помощью комбинаций движений только в 4-х направлениях: налево, направо, вверх, вниз. Для 8-и связной области добавляются ещё и диагональные направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но обратное не верно. Однако в ситуации, когда требуется заполнить разными цветами две отдельные 4-связные области, использование 8-связного алгоритма даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных областей, однако их легко адаптировать и для 8-связных.
Построчный алгоритм заполнения с затравкой
Используя стек, можно разработать алгоритм заполнения гранично-определенной области. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов.
Данный алгоритм применим гранично-определённым 4-связным областям, которые могут быть как выпуклыми, так и не выпуклыми, а также могут содержать дыры. В области, внешней и примыкающей к нашей, не должно быть пикселов с цветом, которым область или многоугольник заполнятся. Схематично работу алгоритма можно разбить на четыре этапа.
Построчный алгоритм заполнения с затравкой
Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы.
Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор пока не будет найдена граница.
В переменной Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала
В диапазоне Xлев £ x £ Xправ проверяются строки расположенные непосредственно над в под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если такие пикселы есть (т. е. не все пикселы граничные, или уже заполненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещается в стек.
При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека. Ниже приводится более подробное описание алгоритма на псевдокоде.
Построчный алгоритм заполнения с затравкой
Затравка ( x, y ) выдаёт затравочный пиксел
Pop -процедура, которая извлекает пиксел из стека
Push - процедура, которая помещает пиксел в стек
инициируем стек
Push Затравка ( x, y )
While ( стек не пуст )
Извлекаем пиксел из стека и присваиваем ему новое значениеPop Пиксел ( x, y )
Пиксел ( x, y ) = Нов_значение
сохраняем x- координату затравочного пиксела
Врем_х = x
заполняем интервал справа от затравки
x = x +1
while Пиксел ( x, y ) ¹ Гран_значение
Пиксел ( x, y ) = Нов_значение
x = x +1
end while
сохраняем крайний справа пиксел
Xправ = x - 1
восстанавливаем x- координату затравки
x = Врем_х
заполняем интервал слева от затравки
x = x - 1
while Пиксел ( x, y ) ¹ Гран_значение
Пиксел ( x, y ) = Нов_значение
x = x - 1
end while
сохраняем крайний слева пиксел
Xлев = x +1
восстанавливаем x- координату затравки
Рекомендуем скачать другие рефераты по теме: шпоры бесплатно, налоги и налогообложение.
Предыдущая страница реферата | 2 3 4 5 6 7 8 9 10 11 12 | Следующая страница реферата