Кафедра информатики и вычислительной техники карпенко сергея михайловича исследование и разработка алгоритмов интерактивной компьютерной графики

if (y > x){ Врем = x; x = y; y = Врем; Обмен = 1; } else Обмен = 0; 3. инициализация с поправкой на половину пиксела = 2 * y  x 4. основной цикл for (i = 1;i<=x;i++) { Draw_Point ( x ,y ); While (  0 ) { If (Обмен == 1) ; x = x + s1; else y = y + s2; =  2 * x } if (Обмен == 1) y = y + s2; else x = x + s1; = + 2 * y; } Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет приемлемую скорость и может быть легко реализован на аппаратном или микропрограммном уровне. Растровая развёртка сплошных областей До сих пор речь шла о представлении на растровом графическом устройстве отрезков прямых линий. Однако одной из уникальных характеристик такого устройства является возможность представ­ления сплошных областей. Генерацию сплошных областей из простых описаний ребер или вершин будем называть растровой раз­верткой сплошных областей, заполнением многоугольников или за­полнением контуров. Для этого можно использовать несколько методов, которые обычно делятся на две широкие категории: растровая развертка и затравочное заполнение. В методах растровой развертки пытаются определить в порядке сканирования строк, лежит ли точка внутри многоугольника или контура. Эти алгоритмы обычно иду от «верха» многоугольника или контура к «низу». В методах затравочного заполнения предполагается, что извест­на некоторая точка (затравка) внутри замкнутого контура. В алго­ритмах ищут точки, соседние с затравочной и расположенные внут­ри контура. Если соседняя точка расположена не внутри, значит, обнаружена граница контура. Если же точка оказалась внутри контура, то она становится новой затравочной точкой и поиск продолжается рекурсивно. Растровая развёртка многоугольников Можно разработать эффективный метод растровой развёртки многоугольников [1], если воспользоваться тем фактом, что соседние пикселы, вероятно, имеют одинаковые характеристики (кроме пикселов граничных рёбер). Это свойство называется пространственной когерентностью. Характеристики пикселов на данной строке изменяются только там, где ребро многоугольника пересекает строку. Эти пересечения делят сканирующую строку на области. Для простого многоугольника на рис.3. строка 2 пересекает многоугольник при x = 1 и x = 8. Получаем три области: Растровая развёртка сплошной области x < 1 вне многоугольника 1  x  8 внутри многоугольника x > 8 вне многоугольника Строка 4 делится на пять областей: x < 1 вне многоугольника 1  x  4 внутри многоугольника 4 < x < б вне многоугольника б  x  8 внутри многоугольника x > 8 вне многоугольника Совсем необязательно, чтобы точки пересечения для строки 4 сразу определялись в фиксированном порядке (слева направо). Например, если многоугольник задаётся списком вершин P1, P2, P3, P4, а список рёбер  последовательными парами вершин P1P2, P2P3, P3P4, P4P5, P5P1, то для строки 4 будут найдены следующие точки пересечения с рёбрами многоугольника: 8, 6, 4, 1. Эти точки надо отсортировать в возрастающем порядке по x, т. е. получить 1,4, 6, 8. При определении интенсивности, цвета и оттенка пикселов на сканирующей строке рассматриваются пары отсортированных то­чек пересечений. Для каждого интервала, задаваемого парой пересечений, используется интенсивность или цвет заполняемого многоу­гольника. Для интервалов между парами пересечений и крайних (от начала строки до первой точки пересечения и от последней точки пересечения до конца строки) используется фоновая интенсивность или цвет. Точное определение тех пикселов, которые должны активироваться, требует некоторой осторожности. Рассмотрим простой прямоугольник, изображенный на рис. . Прямоугольник имеет координаты (1,1), (5,1), (5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами многоугольника при x = 1 и 5. Пиксел адресуется координатами своего левого ниж­него угла, значит, для каждой из этих сканирующих строк будут активированы Рис. 4. Системы координаты строк сканирования. пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. показан результат. Заметим, что площадь, покрываемая активированными пикселами, равна 20, в то время как настоящая площадь прямоугольника равна 12. Модификация системы координат сканирующей строки и теста активации устраняет эту проблему, как это показано на рис.4. ,b. Считается, что сканирующие строки проходят через центр строк пикселов, т. е. через середину интервала, как это показано на рис. ,b. Тест активации модифицируется следующим образом: проверяется, лежит ли внутри интервала центр пиксела, расположенного справа от пересечения. Однако пикселы все еще адресуют­ся координатами левого нижнего угла. Как показано на рис.,b, результат данного метода корректен. Горизонтальные ребра не могут пересекать сканирующую стро­ку и, таким образом, игнорируются. Это совсем не означает, что их нет на рисунке. Эти ребра формируются верхней и нижней стро­ками пикселов. Дополнительная трудность возникает при пересечении сканирующей строки и многоугольника точно по вершине, как это показа­но на рис.5. . При использовании соглашения о середине интерва­ла между сканирующими строками получаем, что строка у = 3.5 пересечет многоугольник в 2, 2 и 8, т. е. получится нечетное количество пересечений. Следовательно, разбиение пикселов на пары даст неверный результат, т. е. пикселы (0,3), (1,3) и от (3,3) до (7,3) будут фоновыми, а пикселы (2,3), (8,3), (9,3) окрасятся в цвет многоугольника. Если учитывать только одну точку пересечения с вершиной. Тогда для строки у = 3.5 получим правильный результат. Однако результат применения метода к строке у = 1.5, имеющей два пересечения в (5,1), показывает, что метод неверен. Для этой строки именно разбиение на пары даст верный результат, т. е. окрашен будет только пиксел (5,1). Если же учитывать в вершине только одно пересечение, то пикселы от (0,1) до (4,1) будут фоновыми, а пикселы от (5,1) до (9,1) будут окрашены в цвет многоугольника. П Особенности пересечения со строками сканирования. равильный результат можно получить, учитывая точку пересечения в вершине два реза, если она является точкой локального ми­нимума или максимума и учитывая один раз в противном слу­чае. Определить локальный максимум или минимум многоугольни­ка в рассматриваемой вершине можно с помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше, чем у вершины, значит, вершина является точкой локального минимума. Если меньше, значит, вершина - точка локального максимума. Если одна больше, а другая меньше, следовательно, вершина не является ни точкой локального миниму­ма, ни точкой локального максимума. На рис.5. точка Р1 - локальный минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое. Следовательно, в точках Р1 и Р3 учитываются два пере­сечения со сканирующими строками, а в Р2 и Р4 - одно. Алгоритм с упорядоченным списком рёбер Используя описанные выше методы, можно разработать эффективные алгоритмы растровой развертки сплошных областей [1], называе­мые алгоритмами с упорядоченным списком ребер. Эффективность этих алго­ритмов зависит от эффективности сортировки. Приведём очень простой алгоритм. Алгоритм с упорядоченным списком ребер, использующий список активных рёбер. 1. Подготовить данные: 1.1. Используя сканирующие строки, проведенные через середины отрезков, т. е. через у + ½ определить для каждого ребра многоугольника наивысшую сканирующую строку, пересекаемую ребром. 1.2. Занести ребро многоугольника в у- группу, соответствующую этой сканирующей строке. 1.3. Сохранить в связном списке значения: начальное значение координат x точек пересечения, y - число сканирующих строк, пересекаемых ребром многоугольника, и ~ x – шаг приращения по x при переходе от одной сканирующей строки к другой. 2. Преобразовать эти данные в растровую форму: 2.1. Для каждой сканирующей строки проверить соответствующую у- группу на наличие новых ребер. Новые ребра доба­вить в список активных рёбер. 2.2. Отсортировать координаты x точек пересечения из САР в порядке возрастания; т. е. х1 предшествует x2, если х1 < х2 2.3. Выделить пары точек пересечений из отсортированного по x списка. Активировать на сканирующей строке y пикселы для целых значений x, таких, что x1  x + ½  x2. Для каждого ребра из САР уменьшить у на 1. Если у < 0, то исключить данное ребро из САР. Вычислить новое значение координат x точек пересечения xнов = xстар + x Перейти к следующей сканирующей строке В алгоритме предполагается, что все данные предварительно преобразованы в представление, принятое для многоугольников. Алгоритм заполнения по рёбрам Алгоритм заполнения по ребрам, использующий список ребер и флаг, является двух шаговым [1]. Первый шаг состоит в обрисовке контура, в резуль­тате чего на каждой сканирующей строке образуются пары ограничивающих пикселов. Второй шаг состоит в заполнении пикселов, расположенных между ограничивающими. Более точно алгоритм можно сформулировать в следующем виде: Алгоритм со списком ребер и флагом 1. Обрисовка контура: Используя соглашения о середине интервала между сканирующими строками для каждого ребра, пересекающего сканирующую строку, отметить самый левый пиксел, центр которого лежит справа от пересечения; т.е. x + 1/2 > xпересечения 2. Заполнение: Для каждой сканирующей строки, пересекающей многоугольник Внутри = FALSE For( x = 0 (левая граница) ;x = xmax, (правая граница);x++) { if (пиксел в точке x имеет граничное значение) инвертировать значение переменной Внутри if (Внутри = TRUE) присвоить пикселу в x значение цвета многоугольника else присвоить пикселу в x значение цвета фона } В данном алгоритме каждый пиксел обрабатывается только один раз, так что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком рёбер, в результате чего, при его аппаратной реализации, он работает на один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер. Алгоритмы заполнения с затравкой В обсуждавшихся выше алгоритмах заполнение происходит в по­рядке сканирования. Иной подход используется в алгоритмах заполнения с затравкой [1] . В них предполагается, что известен хотя бы один пиксел из внутренней области многоугольника. Алгоритм пытается найти и закрасить все другие пикселы, принадлежащие внут­ренней области. Области могут быть либо внутренние, либо гранично-определенные. Если область относится к внутренне - опреде­ленным, то все пикселы, принадлежащие внутренней части, имеют один и тот же цвет или интенсивность, а все пикселы, внешние по отношению к области, имеют другой цвет. Это продемонстрирова­но на рис. 6. Если область относится к гранично-определенным, то все пикселы на границе области имеют выделенное значение или цвет, как это показано на рис. 7. Алгоритмы, заполняющие внутренне - определенные области, называются внутренне - заполня­ющими, а алгоритмы для гранично-определённых областей – гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно получить аналогичным образом. Рис. 6. Внутренне - определённая область Рис. 7. Гранично-определённая область Внутренне- или гранично-определённые области могут быть 4- или 8- связными. Если область 4-связная, то любой пиксел в области можно достичь с помощью комбинаций движений только в 4-х направлениях: налево, направо, вверх, вниз. Для 8-и связной области добавляются ещё и диагональные направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но обратное не верно. Однако в ситуации, когда требуется заполнить разными цветами две отдельные 4-связные области, использование 8-связного алгоритма даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных областей, однако их легко адаптировать и для 8-связных. Построчный алгоритм заполнения с затравкой Используя стек, можно разработать алгоритм заполнения гранично-определенной области [1]. Стек - это просто массив или другая структура данных, в которую можно последовательно помещать значения и из которой их можно последовательно извлекать. Как показывает практика, стек может быть довольно большим. Зачастую в нём содержится дублирующаяся информация. В построчном алгоритме заполнения с затравкой стек минимизируется за счёт хранения только затравочного пиксела для любого непрерывного интервала на сканирующей строке. Непрерывный интервал - это группа примыкающих друг к другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы для разработки алгоритма используем эвристический подход, однако также возможен и теоретический подход, основанный на теории графов. Данный алгоритм применим гранично-определённым 4-связным областям, которые могут быть как выпуклыми, так и не выпуклыми, а также могут содержать дыры. В области, внешней и примыкающей к нашей, не должно быть пикселов с цветом, которым область или многоугольник заполнятся. Схематично работу алгоритма можно разбить на четыре этапа. Построчный алгоритм заполнения с затравкой 1. Затравочный пиксел на интервале извлекается из стека, содержащего затравочные пикселы. 2. Интервал с затравочным пикселом заполняется влево и вправо от затравки вдоль сканирующей строки до тех пор пока не будет найдена граница. 3. В переменной Xлев и Xправ запоминаются крайний левый и крайний правый пикселы интервала 4. В диапазоне Xлев  x  Xправ проверяются строки расположенные непосредственно над в под текущей строкой. Определяется, есть ли на них еще не заполненные пикселы. Если та­кие пикселы есть (т. е. не все пикселы граничные, или уже за­полненные), то в указанном диапазоне крайний правый пиксел в каждом интервале отмечается как затравочный и помещает­ся в стек. При инициализации алгоритма в стек помешается единственный затравочный пиксел, работа завершается при опустошении стека.

Похожие:

	Контрольная работа №1 Тема контрольной работы №1 Базовые основы компьютерной Области применения компьютерной графики; технические средства компьютерной графики: мониторы, графические адаптеры		«Юго-Западный государственный университет» (юзгу) Кафедра программного... Цель работы: Исследование развития криптографии и способов применения шифров в деятельности человека
	Разработка и исследование интегрированных алгоритмов размещения элементов... Специальности: 05. 13. 12 – Системы автоматизации проектирования, 05. 13. 17 – Теоретические основы информатики		Факультет математики и информационных технологий Кафедра информатики и вычислительной техники Познакомить учащихся с планетами Солнечной системы, сформировать представление о них и о том, отчего на Земле сменяются день, ночь,...
	Учитель математики, информатики и вычислительной техники Образование высшее Стаж работы Урок Правила техники безопасности. Повторение курса 8 класса (двоичная система)		Программа дисциплины Современные проблемы информатики и вычислительной... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 09....
	Рабочая программа по дисциплине В. В основы компьютерной графики Дисциплина «Основы компьютерной графики» является фундаментальной дисциплиной в подготовке бакалавра. Это одна из основных дисциплин...		«Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами		Задача изучения дисциплины освоить основные понятия компьютерной... Цель преподавания дисциплины – ознакомление студентов с основами компьютерной графики и графическими программами
	Информатика и вычислительная техника Аналитический обзор по курсу «Современные проблемы информатики и вычислительной техники»		Контрольная работа выполняется в два этапа Составитель: Е. В. Моисеенко, доцент кафедры информатики, инженерной и компьютерной графики вгуэс
	Конспект урока информатики и икт (с использованием технологии сдп... Тема "Использование вспомогательных алгоритмов для рисования орнаментов в исполнителе Чертежник"		Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...
	Программа по формированию навыков безопасного поведения на дорогах... После защиты диссертации на тему «Наука компьютерной графики» Сазерленд и доктор Дэвид Эванс (David Evans) открывают в университете...		Курсовая работа по дисциплине «Информатика и программирование» Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»