Xreferat.com » Рефераты по информатике и программированию » Трёхмерная компьютерная графика

Трёхмерная компьютерная графика

Проверка компонент d показывает, что

Трёхмерная компьютерная графика

поскольку в случае 2 горизонтальный ( xi + 1, уi ) и диагональный ( xi + 1, уi – 1 ) пикселы лежат внутри окружности. Следовательно, d < 0, и при использовании того же самого критерия, что и в случае 1, выбирается пиксел ( xi + 1, уi ).

Если D i > 0, то диагональная точка ( xi + 1, уi – 1 ) находится вне окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что должен быть выбран либо пиксел ( xi + 1, уi – 1 ), т. е. mD, либо ( xi, уi – 1 ), т. е. mV. Аналогично разбору предыдущего случая критерий выбора можно получить, рассматривая сначала случай З и проверяя разность между квадратами расстояний от окружности до диагонального mD и вертикального mV пикселов, т. е.

Трёхмерная компьютерная графика

При d < 0 расстояние от окружности до вертикального пиксела ( xi, уi – 1 ) больше и следует выбрать диагональный шаг mD, к пикселу ( xi + 1, уi – 1 ). Напротив, в случае d > 0 расстояние от окружности до диагонального пиксела больше и следует выбрать вертикальное движение к пикселу ( xi, уi – 1 ). Таким образом,

при d £ 0 выбираем mD в ( xi + 1, уi – 1 )

при d < 0 выбираем mV в ( xi, уi – 1 )

Здесь в случае d = 0, т. е. когда расстояния равны, выбран диагональный шаг.

Проверка компонент d показывает, что

Трёхмерная компьютерная графика

поскольку для случая З диагональный пиксел ( xi + 1, уi – 1 ) находится вне окружности, тогда как вертикальный пиксел ( xi, уi – 1 ) лежит внутри ее. Это позволяет записать d в виде

Трёхмерная компьютерная графика

Дополнение до полного квадрата члена ( xi )2 с помощью добавления и вычитания 2xi + 1 дает

Трёхмерная компьютерная графика

Использование определения D i приводит выражение к виду

Трёхмерная компьютерная графика

Теперь, рассматривая случай 4, снова заметим, что следует выбрать вертикальный пиксел ( xi, уi – 1 ), так как y является монотонно убывающей функцией при возрастании x. проверка компонент d для случая 4 показывает, что

Трёхмерная компьютерная графика

поскольку оба пиксела находятся вне окружности. Следовательно, d > 0 и при использовании критерия, разработанного для случая 3, происходит верный выбор mV.

Осталось проверить только случай 5 на рис.2.7, который встречается, когда диагональный пиксел ( xi + 1, уi – 1 ) лежит на окружности, т. е. D i = 0. Проверка компонент d показывает, что

Трёхмерная компьютерная графика

Следовательно, d > 0 и выбирается диагональный пиксел ( xi + 1, уi – 1 ). Аналогичным образом оцениваем компоненты d :

Трёхмерная компьютерная графика

и d < 0, что является условием выбора правильного диагонального шага к ( хi + 1, уi – 1 ). Таким образом, случай D i = 0 подчиняется тому же критерию, что и случай D i < 0 или D i > 0.

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

D i < 0

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

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

D i > 0

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

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

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

Легко разработать простые рекуррентные соотношения дня реализации пошагового алгоритма. Сначала рассмотрим горизонтальный шаг mH к пикселу ( хi + 1, уi ). Обозначим это новое положение пиксела как ( i + 1 ). Тогда координаты нового пиксела и значение D i равны

Трёхмерная компьютерная графика

Аналогично координаты нового пиксела и значения D i для шага mD к пикселу ( хi + 1, уi – 1 ) таковы:

Трёхмерная компьютерная графика

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

Трёхмерная компьютерная графика

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

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

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

xi = 0

yi = R

D i = 2(1 – R)

Предел = 0

Plot ( xi, yi )

if yi £ Предел then 4

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

if D i < 0 then 2

if D i > 0 then 3

if D i = 0 then 20

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

d = 2D i + 2yi – 1

if d £ 0 then 10

if d > 0 then 20

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

d = 2D i + 2xi – 1

if d £ 0 then 20

if d > 0 then 30

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

шаг mH

xi = xi +1

D i = D i +2xi + 1

goto 1

шаг mD

xi = xi +1

yi = yi – 1

D i = D i +2xi – 2yi + 2

goto 1

шаг mV

30yi = yi – 1

D i = D i – 2xi + 1

goto 1

4finish

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

До сих пор речь шла о представлении на растровом графическом устройстве отрезков прямых линий. Однако одной из уникальных характеристик такого устройства является возможность представления сплошных областей. Генерацию сплошных областей из простых описаний ребер или вершин будем называть растровой разверткой сплошных областей, заполнением многоугольников или заполнением контуров. Для этого можно использовать несколько методов, которые обычно делятся на две широкие категории: растровая развертка и затравочное заполнение.

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

сканирования строк, лежит ли точка внутри многоугольника или контура. Эти алгоритмы обычно иду от “верха” многоугольника или контура к “низу”.

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

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

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

Трёхмерная компьютерная графика

2.7 Растровая развёртка сплошной области

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

Для простого многоугольника на рис. 2.7 строка 2 пересекает многоугольник при x = 1 и x = 8.

Получаем три области:

x < 1вне многоугольника

1 £ x £ ="Times New Roman"> 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 Системы координаты строк сканирования.

Точное определение тех пикселов, которые должны активироваться, требует некоторой осторожности. Рассмотрим простой прямоугольник, изображенный на рис. 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.9 Особенности пересечения со строками сканирования.

Правильныйрезультат можно получить, учитывая точку пересечения в вершине два реза, если она является точкой локального минимума или максимума и учитывая один раз в противном случае. Определить локальный максимум или минимум многоугольника в рассматриваемой вершине можно с помощью проверки концевых точек двух ребер. Если у обоих рёбер у больше, чем у вершины, значит, вершина является точкой локального минимума. Если меньше, значит, вершина - точка локального максимума. Если одна больше, а другая меньше, следовательно, вершина не является ни точкой локального минимума, ни точкой локального максимума. На рис.2.10 точка Р1 - локальный минимум, Р3 - локальный максимум, а Р2, Р4 - ни то ни другое. Следовательно, в точках Р1 и Р3 учитываются два пересечения со сканирующими

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

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

Используя описанные выше методы, можно разработать эффективные алгоритмы растровой развертки сплошных областей, называемые алгоритмами с упорядоченным списком ребер. Эффективность этих алгоритмов зависит от эффективности сортировки. Приведём очень простой алгоритм.

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

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

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

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

Сохранить в связном списке значения: начальное значение координат 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пересечения

Заполнение:

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: