МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Трехмерная компьютерная графика

    Аналогичным образом оцениваем компоненты (\:

    [pic]

    и ( < 0, что является условием выбора правильного диагонального шага к ( хi

    + 1, уi – 1 ). Таким образом, случай (i = 0 подчиняется тому же критерию,

    что и случай (i < 0 или (i > 0.

    Подведем итог полученных результатов:

    (i < 0

    ( ( 0 выбираем пиксел ( хi + 1, уi ) ( mH

    ( > 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

    (i > 0

    (\ ( 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

    (\ > 0 выбираем пиксел ( хi , уi – 1 ) ( mV

    (i = 0 выбираем пиксел ( хi + 1, уi – 1 ) ( mD

    Легко разработать простые рекуррентные соотношения дня реализации

    пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу (

    хi + 1, уi ). Обозначим это новое положение пиксела как ( i + 1 ). Тогда

    координаты нового пиксела и значение (i равны

    [pic]

    Аналогично координаты нового пиксела и значения (i для шага mD к пикселу (

    хi + 1, уi – 1 ) таковы:

    [pic]

    То же самое для шага mV к ( хi, уi – 1 )

    [pic]

    Реализация алгоритма Брезенхема для окружности приводиться ниже.

    Пошаговый алгоритм Брезенхема для генерации окружности в первом квадранте

    все переменные целые

    xi = 0

    yi = R

    (i = 2(1 – R)

    Предел = 0

    1. Plot ( xi, yi )

    if yi ( Предел then 4

    выделение случая 1 или 2, 4 или 5, или 3

    if (i < 0 then 2

    if (i > 0 then 3

    if (i = 0 then 20

    определение случая 1 или 2

    2. ( = 2(i + 2yi – 1

    if ( ( 0 then 10

    if ( > 0 then 20

    определение случая 4 или 5

    3. ( = 2(i + 2xi – 1

    if ( ( 0 then 20

    if ( > 0 then 30

    выполнение шагов

    шаг mH

    10. xi = xi +1

    (i = (i +2xi + 1

    goto 1

    шаг mD

    20. xi = xi +1

    yi = yi – 1

    (i = (i +2xi – 2yi + 2

    goto 1

    шаг mV

    30 yi = yi – 1

    (i = (i – 2xi + 1

    goto 1

    4 finish

    5. Растровая развёртка сплошных областей

    До сих пор речь шла о представлении на растровом графическом устройстве

    отрезков прямых линий. Однако одной из уникальных характеристик такого

    устройства является возможность представления сплошных областей. Генерацию

    сплошных областей из простых описаний ребер или вершин будем называть

    растровой разверткой сплошных областей, заполнением многоугольников или

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

    которые обычно делятся на две широкие категории: растровая развертка и

    затравочное заполнение.

    В методах растровой развертки пытаются определить в порядке

    сканирования строк, лежит ли точка внутри многоугольника или контура. Эти

    алгоритмы обычно иду от «верха» многоугольника или контура к «низу».

    В методах затравочного заполнения предполагается, что известна

    некоторая точка (затравка) внутри замкнутого контура. В алгоритмах ищут

    точки, соседние с затравочной и расположенные внутри контура. Если соседняя

    точка расположена не внутри, значит, обнаружена граница контура. Если же

    точка оказалась внутри контура, то она становится новой затравочной точкой

    и поиск продолжается рекурсивно.

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

    Можно разработать эффективный метод растровой развёртки

    многоугольников, если воспользоваться тем фактом, что соседние пикселы,

    вероятно, имеют одинаковые характеристики (кроме пикселов граничных рёбер).

    Это свойство называется пространственной когерентностью.

    Характеристики пикселов на данной строке изменяются только там, где

    ребро многоугольника пересекает строку. Эти пересечения делят сканирующую

    строку на области.

    Для простого многоугольника на рис. 2.7 строка 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.

    При определении интенсивности, цвета и оттенка пикселов на сканирующей

    строке рассматриваются пары отсортированных точек пересечений. Для каждого

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

    цвет заполняемого многоугольника. Для интервалов между парами пересечений и

    крайних (от начала строки до первой точки пересечения и от последней точки

    пересечения до конца строки) используется фоновая интенсивность или цвет.

    Точное определение тех пикселов, которые должны активироваться,

    требует некоторой осторожности. Рассмотрим простой прямоугольник,

    изображенный на рис. 2.8. Прямоугольник имеет координаты (1,1), (5,1),

    (5,4), (1,4). Сканирующие строки с 1 по 4 имеют пересечения с ребрами

    многоугольника при x = 1 и 5. Пиксел адресуется координатами своего левого

    нижнего угла, значит, для каждой из этих сканирующих строк будут

    активированы пикселы с x-координатами 1, 2, 3, 4 и 5. На рис. 2.8 показан

    результат. Заметим, что площадь, покрываемая активированными пикселами,

    равна 20, в то время как настоящая площадь прямоугольника равна 12.

    Модификация системы координат сканирующей строки и теста активации

    устраняет эту проблему, как это показано на рис. 2.8,b. Считается, что

    сканирующие строки проходят через центр строк пикселов, т. е. через

    середину интервала, как это показано на рис. 2.8,b. Тест активации

    модифицируется следующим образом: проверяется, лежит ли внутри интервала

    центр пиксела, расположенного справа от пересечения. Однако пикселы все еще

    адресуются координатами левого нижнего угла. Как показано на рис.2.8,b,

    результат данного метода корректен.

    Горизонтальные ребра не могут пересекать сканирующую строку и, таким

    образом, игнорируются. Это совсем не означает, что их нет на рисунке. Эти

    ребра формируются верхней и нижней строками пикселов.

    Дополнительная трудность возникает при пересечении сканирующей строки и

    многоугольника точно по вершине, как это показано на рис. 2.9. При

    использовании соглашения о середине интервала между сканирующими строками

    получаем, что строка у = 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) будут окрашены в цвет

    многоугольника.

    Правильный результат можно получить, учитывая точку пересечения в

    вершине два реза, если она является точкой локального минимума или

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

    максимум или минимум многоугольника в рассматриваемой вершине можно с

    помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше,

    чем у вершины, значит, вершина является точкой локального минимума. Если

    меньше, значит, вершина - точка локального максимума. Если одна больше, а

    другая меньше, следовательно, вершина не является ни точкой локального

    минимума, ни точкой локального максимума. На рис.2.10 точка Р1 - локальный

    минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое.

    Следовательно, в точках Р1 и Р3 учитываются два пересечения со сканирующими

    строками, а в Р2 и Р4 - одно.

    7. Алгоритм с упорядоченным списком рёбер

    Используя описанные выше методы, можно разработать эффективные

    алгоритмы растровой развертки сплошных областей, называемые алгоритмами с

    упорядоченным списком ребер. Эффективность этих алгоритмов зависит от

    эффективности сортировки. Приведём очень простой алгоритм.

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

    Подготовить данные:

    Используя сканирующие строки, проведенные через середины отрезков, т.

    е. через у + Ѕ определить для каждого ребра многоугольника наивысшую

    сканирующую строку, пересекаемую ребром.

    Занести ребро многоугольника в у- группу, соответствующую этой

    сканирующей строке.

    Сохранить в связном списке значения: начальное значение координат x

    точек пересечения, (y - число сканирующих строк, пересекаемых ребром

    многоугольника, и ~ (x – шаг приращения по x при переходе от одной

    сканирующей строки к другой.

    Преобразовать эти данные в растровую форму:

    Для каждой сканирующей строки проверить соответствующую у- группу на

    наличие новых ребер. Новые ребра добавить в список активных рёбер.

    Отсортировать координаты x точек пересечения из САР в порядке

    возрастания; т. е. х1 предшествует x2, если х1 < х2

    Выделить пары точек пересечений из отсортированного по

    x списка. Активировать на сканирующей строке y пикселы для целых

    значений x, таких, что x1 ( x + Ѕ ( x2. Для каждого ребра из САР

    уменьшить (у на 1. Если (у < 0, то исключить данное ребро из САР.

    Вычислить новое значение координат x точек пересечения xнов = xстар +

    (x

    Перейти к следующей сканирующей строке

    В алгоритме предполагается, что все данные предварительно преобразованы

    в представление, принятое для многоугольников.

    8. Алгоритм заполнения по рёбрам

    Алгоритм, использующий список ребер и флаг, является двух шаговым.

    Первый шаг состоит в обрисовке контура, в результате чего на каждой

    сканирующей строке образуются пары ограничивающих пикселов. Второй шаг

    состоит в заполнении пикселов, расположенных между ограничивающими. Более

    точно алгоритм можно сформулировать в следующем виде:

    Алгоритм со списком ребер и флагом

    Обрисовка контура:

    Используя соглашения о середине интервала между сканирующими строками

    для каждого ребра, пересекающего сканирующую строку, отметить самый

    левый пиксел, центр которого лежит справа от пересечения;

    т.е.

    x + 1/2 > xпересечения

    Заполнение:

    Для каждой сканирующей строки, пересекающей многоугольник

    Внутри = FALSE

    for x = 0 (левая граница) to x = xmax, (правая граница)

    if пиксел в точке x имеет граничное значение

    then инвертировать значение переменной Внутри

    if Внутри = TRUE then

    присвоить пикселу в x значение цвета многоугольника

    else

    присвоить пикселу в x значение цвета фона

    end if

    next x

    В данном алгоритме каждый пиксел обрабатывается только один раз, так

    что затраты на ввод/вывод значительно меньше, чем в алгоритме со списком

    рёбер, в результате чего, при его аппаратной реализации, он работает на

    один-два порядка быстрее чем алгоритм с упорядоченным списком рёбер.

    9. Алгоритмы заполнения с затравкой

    В обсуждавшихся выше алгоритмах заполнение происходит в порядке

    сканирования. Иной подход используется в алгоритмах заполнения с затравкой.

    В них предполагается, что известен хотя бы один пиксел из внутренней

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

    пикселы, принадлежащие внутренней области. Области могут быть либо

    внутренние, либо гранично-определенные. Если область относится к внутренне

    - определенным, то все пикселы, принадлежащие внутренней части, имеют один

    и тот же цвет или интенсивность, а все пикселы, внешние по отношению к

    области, имеют другой цвет. Это продемонстрировано на рис. 2.10. Если

    область относится к гранично-определенным, то все пикселы на границе

    области имеют выделенное значение или цвет, как это показано на рис. 2.11.

    Алгоритмы, заполняющие внутренне - определенные области, называются

    внутренне - заполняющими, а алгоритмы для гранично-определённых областей –

    гранично-заполняющими. Далее будут обсуждаться гранично-заполняющие

    алгоритмы, однако соответствующие внутренне заполняющие алгоритмы можно

    получить аналогичным образом.

    Внутренне- или гранично-определённые области могут быть 4- или 8-

    связными. Если область 4-связная, то любой пиксел в области можно достичь с

    помощью комбинаций движений только в 4-х направлениях: налево, направо,

    вверх, вниз. Для 8-и связной области добавляются ещё и диагональные

    направления. Алгоритм заполнения 8-связной области заполнит и 4-связную, но

    обратное не верно. Однако в ситуации, когда требуется заполнить разными

    цветами две отдельные 4-связные области, использование 8-связного алгоритма

    даст не верный результат. Далее речь пойдёт об алгоритмах для 4-связных

    областей, однако их легко адаптировать и для 8-связных.

    10. Построчный алгоритм заполнения с затравкой

    Используя стек, можно разработать алгоритм заполнения гранично-

    определенной области. Стек - это просто массив или другая структура данных,

    в которую можно последовательно помещать значения и из которой их можно

    последовательно извлекать. Как показывает практика, стек может быть

    довольно большим. Зачастую в нём содержится дублирующаяся информация. В

    построчном алгоритме заполнения с затравкой стек минимизируется за счёт

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

    сканирующей строке. Непрерывный интервал - это группа примыкающих друг к

    другу пикселов (ограниченная уже заполненными или граничными пикселами). Мы

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

    возможен и теоретический подход, основанный на теории графов.

    Данный алгоритм применим гранично-определённым 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- координату затравки

    x = Врем_х

    проверим, что строка выше не является ни границей многоугольника, ни

    уже полностью заполненной; если это не так, то найти затравку, начиная

    с левого края подинтервала сканирующей строки

    x = Xлев

    y = y +1

    while x ( Xправ

    ищем затравку на строке выше

    Флаг = 0

    while ( Пиксел ( x, y ) ( Гран_значение and

    Пиксел ( x, y ) ( Нов_значение and x < Xправ )

    Страницы: 1, 2, 3, 4, 5, 6


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.