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



страница1/4
Дата23.10.2016
Размер0,71 Mb.
  1   2   3   4

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гродненский государственный университет им. Я. Купалы»

Математический факультет

Кафедра информатики и вычислительной техники

КАРПЕНКО СЕРГЕЯ МИХАЙЛОВИЧА


ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ ИНТЕРАКТИВНОЙ КОМПЬЮТЕРНОЙ ГРАФИКИ

Дипломная работа

студента 5-го курса


Научный руководитель:

Переверзева Н.А.

зам. декана по научной работе,

доцент, канд. тех. наук

Допущен к защите: Рецензент

«____» ___________ 2003 г.

________________________

Зав. кафедрой


Гродно


2003

РЕФЕРАТ




Структура и объем работы. Данная работа состоит из введения, двух глав, заключения и трех приложений. Общий объем работы – 82 с. (основная часть – 68 с.), библиография содержит 11 наименований, из них 3 – Internet-источники, 1 – публикации автора. В работе приведено 36 иллюстраций.

Ключевые слова: АЛГОРИТМ, РАСТОВАЯ ГРАФИКА, АЛГОРИТМ ХУДОЖНИКА, ТРАССИРОВКА ЛУЧЕЙ, BSP-ДЕРЕВО, ПОВЕРХНОСТЬ, ПОРТАЛ, ПРИМИТИВ, СЕКТОР, СЦЕНА, Z-BUFFER.

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

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


Содержание

Введение

4

1. Задачи проекта

6

2. Растровая графика

7

2.1. Алгоритмы вычерчивания отрезков

7

2.1.1. Цифровой дифференциальный анализатор

7

2.1.2. Алгоритм Брезенхема

9

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

12

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

13

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

16

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

17

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

18

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

19

3. Удаление невидимых линий и поверхностей

20

3.1. Алгоритм плавающего горизонта

22

3.2. Алгоритм Робертса

29

3.3. Алгоритм художника

41

3.4. Алгоритм использующий Z-буфер

42

3.5. Z-отсечение

43

3.6. Алгоритм определения видимых поверхностей путём трассировки лучей

45

3.7. Алгоритм секторов и порталов

52

3.8. BSP – деревья

57

3.9. Shadow Volumes или стенсельные тени

59

4. Заключение

67

Литература

68

Приложение 1. Исходный текс программы трассировки лучей

69

Приложение 2. Краткое руководство пользователя к 3D-движку

75

Приложение 3. Слайды работы программ

76

Введение

Машинная графика в настоящее время уже вполне сформировалась как наука. Существует аппаратное и программное обеспечение для получения разнообразных изображений - от простых чертежей до реалистичных образов естественных объектов. Машинная графика используется почти во всех научных и инженерных дисциплинах для наглядности восприятия и передачи информации. Знание её основ в наше время необходимо любому ученому или инженеру. Машинная графика властно вторгается в бизнес, медицину, рекламу, индустрию развлечений. Примене­ние во время деловых совещаний демонстрационных слайдов, под­готовленных методами машинной графики и другими средствам автоматизации конторского труда, считается нормой. В медицине становится обычным получение трехмерных изображений внутренних ­органов по данным компьютерных томографов. В наши дни телевидение и другие рекламные предприятия часто прибегают к услугам машинной графики и компьютерной мультипликации. Использование машинной графики в индустрии развлечений охватыва­ет такие несхожие области как видеоигры и полнометражные художественные фильмы.

На сегодняшний день создано большое количество программ, позволяющих создавать и редактировать трёхмерные сцены и объекты. Среди наиболее популярных можно назвать такие как 3D studio Max, которая позволяет трёхмерные компьютерные ролики. Область её применения в основном реклама, мультипликация и оформление телевизионных передач. Другой не менее популярный пакет программ это Auto-CAD. Он применяется в основном инженерами и проектировщиками для создания чертежей и пространственных моделей. Кроме этих существует множество других специализированных программных пакетов охватывающих практически все стороны человеческой жизни.

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

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

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

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

Как видно из выше сказанного компьютерная графика это достаточно объемная дисциплина.


1. Задачи проекта

Исследовать и реализовать алгоритмы создания трехмерных изображений (сцен), таких как, Z-Buffer, определение видимых поверхностей путём трассировки лучей, секторов и порталов, BSP – деревьев, теней.

В ходе работы над проектом были реализованы следующие программы:


  • отображение сцен с использованием алгоритма определение видимых поверхностей путём трассировки лучей;

  • отображение теней;

а так же трехмерный движок, который поддерживает:

  • отображение сцен с использованием алгоритма порталов;

  • поддержку трехмерных объектов в формате .3ds, которые могут содержать в себе анимацию;

  • использование как динамического, так и статического света;

  • спецэффекты, такие как прозрачность и хромовые покрытия;

  • проигрывание музыки в формате mp3;

  • звуковые спецэффекты с использованием технологии A3D;

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




  1. Растровая графика

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



    1. Алгоритмы вычерчивания отрезков

Поскольку экран дисплея можно рассматривать как матрицу дискретных элементов (пикселов), каждый из которых может быть подсвечен, нельзя непосредственно провести отрезок из одной точки в другую. Процесс определения пикселов, наилучшим образом аппроксимирующих за­данный отрезок, называется разложением в растр. Для горизонтальных, верти­кальных и наклоненных под углом 45 отрезков выбор растровых элементов очевиден. При любой другой ориентации выбрать нужные пикселы труднее.

Существует несколько алгоритмов выполняющих эту задачу. Рассмотрим два из них.




      1. Цифровой дифференциальный анализатор

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

или н

Решение представляется в виде




    (1)

где x1, y1 и x2, y2 – концы разлагаемого отрезка и yi – начальное значение для очередного шага вдоль отрезка. Фактически уравнение (1) представляет собой рекуррентное соотношение для последовательных значений y вдоль нужного отрезка. Этот метод, использу­емый для разложения в растр отрезков, называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо , либо (большее из приращений) выбирается в качестве единицы растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:




Процедура разложения в растр отрезка по методу цифрового дифференциального анализатора (ЦДА)
1. предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают
Intфункция преобразования вещественного числа в целое.

Примечание: во многих реализациях функция Integer означает взятие целой части, т.е. Int( 8.5) = 9, а не 8. В алгоритме используется именно такая функция.

Sign функция, возвращающая 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.

if (abs ( x2 x1 )  abs ( y2  y1 ) )

Длина = abs ( x2  x1 )



else

Длина = abs ( y2  y1 )

2. полагаем большее из приращений x или y равным единице растра

x = ( x2 x1 ) / Длина

y = ( y2  y1 ) / Длина

3. округляем величины, а не отбрасываем дробную часть



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

x = x1 + 0.5 * Sign ( x )

y = y1 + 0.5 * Sign ( y )

4. начало основного цикла

i =1

while ( i  Длина )

{

Draw_Point ( Int ( x ), Int ( y ) );

x = x + x;

y = y + y;

i = i + 1;



}

С помощью этого алгоритма получают прямые, вполне удовлетворительного вида, но у него есть ряд недостатков. Во-первых, плохая точность в концевых точках; во-вторых, результаты работы алгоритма зависят от ориентации отрезка; вдобавок предложенный алгоритм использует вещественную арифметику, что заметно снижает скорость выполнения.




      1. Алгоритм Брезенхема

Алго­ритм Брезенхема [1] выбирает оптимальные растровые координаты для представления отрезка. В процессе работы одна из координат - либо x, ли­бо у (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между действительным положени­ем отрезка и ближайшими координатами сетки. Такое расстояние называется ошибкой.

Алгоритм построен так, что требуется проверять лишь знак этой ошибки. На рис.1. это иллюстрируется для отрезка в первом



½  y  1 (ошибка  0)


0  y/x < ½ (ошибка <0)
Инициировать ошибку в – ½

ошибка = ошибка + y/x



  1. Основная идея алгоритма Брезенхема

октанте, т. е. для отрезка с угловым коэффициентом, лежащим в диапазоне от нуля до единицы. Из рисунка можно заметить, что если угловой коэффициент отрезка из точки (0,0) больше чем 1/2, то его пересечение с прямой x = 1 будет расположено ближе к пря­мой у = 1, чем к прямой у = 0. Следовательно, точка растра (1,1) лучше аппроксимирует ход отрезка, чем точка (1,0). Если угловой коэффициент меньше 1/2, то верно обратное. Для углового коэффициента равного 1/2 нет какого-либо предпочтительного выбора. В данном случае алгоритм выбирает ­точку (1,1).

Быстродействие алгоритма можно существенно увеличить, если использовать только целочисленную арифметику и исключить деление. Т.к. важен лишь знак ошибки, то приняв



можно добиться хорошей скорости выполнения алгоритма.

Ч


    1. Разбор случаев для обобщённого алгоритма Брезенхема.



тобы реализация алгоритма была полной необходимо обрабатывать отрезки во всех октантах. Когда абсолютная величина углового коэффициента больше 1, y постоянно изменяется на единицу, а критерий ошибки Брезенхема используется для принятия решения об изменении величены x. Выбор постоянно изменяющейся (на +1 или –1) координаты зависит от квадранта (рис. 2.).

Рис. 2. Разбор случаев для обобщенного алгоритма Брезенхема


Алгоритм Брезенхема может быть оформлен в следующем виде.



Обобщённый целочисленный алгоритм Брезенхема квадрантов
предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают и все переменные  целые.

Функция Sign возвращает 1, 0, 1 для отрицательного нулевого и положительного аргумента соответственно.
1. инициализация переменных

x = x1;

y = y1;

x = abs ( x2  x1 );

y = abs ( y2  y1 );

s1 = Sign ( x2  x1 );

s2 = Sign ( y2  y1 );

2. обмен значение x и y в зависимости от углового коэффициента наклона отрезка



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. Растровая развёртка сплошных областей

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

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

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

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



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

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

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

Для простого многоугольника на рис.3. строка 2 пересекает многоугольник при x = 1 и x = 8.
Получаем три области:


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

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) будут окрашены в цвет многоугольника.



П

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


    1. Поделитесь с Вашими друзьями:
  1   2   3   4


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница