Трёхмерная компьютерная графика
Категория реферата: Рефераты по информатике, программированию
Теги реферата: доклад, контрольная работа 10
Добавил(а) на сайт: Nadezhda.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
Алгоритм с упорядоченным списком ребер, использующий список активных рёбер.
Подготовить данные:
Используя сканирующие строки, проведенные через середины отрезков, т. е. через у + ½ определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром.
Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке.
Сохранить в связном списке значения: начальное значение координат x точек пересечения, D y - число сканирующих строк, пересекаемых ребром многоугольника, и ~ D x – шаг приращения по x при переходе от одной сканирующей строки к другой.
Преобразовать эти данные в растровую форму:
Для каждой сканирующей строки проверить соответствующую у- группу на наличие новых ребер. Новые ребра добавить в список активных рёбер.
Отсортировать координаты x точек пересечения из САР в порядке возрастания; т. е. х1 предшествует x2, если х1 < х2
Выделить пары точек пересечений из отсортированного по
x списка. Активировать на сканирующей строке y пикселы для целых значений x, таких, что x1 £ x + ½ £ x2. Для каждого ребра из САР уменьшить D у на 1. Если D у < 0, то исключить данное ребро из САР. Вычислить новое значение координат x точек пересечения xнов = xстар + D x
Перейти к следующей сканирующей строке
В алгоритме предполагается, что все данные предварительно преобразованы в представление, принятое для многоугольников.
Алгоритм заполнения по рёбрам
Алгоритм, использующий список ребер и флаг, является двух шаговым. Первый шаг состоит в обрисовке контура, в результате чего на каждой сканирующей строке образуются пары ограничивающих пикселов. Второй шаг состоит в заполнении пикселов, расположенных между ограничивающими. Более точно алгоритм можно сформулировать в следующем виде:
Алгоритм со списком ребер и флагом
Обрисовка контура:
Используя соглашения о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксел, центр которого лежит справа от пересечения; т.е.
x + 1/2 > xпересечения
Заполнение:
Для каждой сканирующей строки, пересекающей многоугольник
Внутри = FALSE
for x = 0 (левая граница) to x = xmax, (правая граница)
if пиксел в точке x имеет граничное значение
then инвертировать значение переменной Внутри
if Внутри = TRUE then
присвоить пикселу в x значение цвета многоугольника
else
присвоить пикселу в x значение цвета фона
end if
next x
В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком рёбер, в результате чего, при его аппаратной реализации, он работает на один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер.
Алгоритмы заполнения с затравкой
В обсуждавшихся выше алгоритмах заполнение происходит в порядке сканирования. Иной подход используется в алгоритмах заполнения с затравкой. В них предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внутренней области. Области могут быть либо внутренние, либо гранично-определенные.
Рис. 2.10. Внутренне - определённая область
Рис. 2.11. Гранично-определённая область
Если область относится к внутренне - определенным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрировано на рис. 2.10. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 2.11. Алгоритмы, заполняющие внутренне - определенные области, называются внутренне - заполняющими, а алгоритмы для гранично-определённых областей – гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно получить аналогичным образом.
Рекомендуем скачать другие рефераты по теме: шпоры бесплатно, налоги и налогообложение.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата