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

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

Кемеровский Государственный Университет

кафедра математического анализа

Курсовая работа по теме:

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

Выполнил: студент М-963

Печёркин Ю. К.

Руководитель: Ким В. Б.

Кемерово 1999

Введение

Машинная графика в настоящее время уже вполне сформировалась как наука.

Существует аппаратное и программное обеспечение для получения разнообразных

изображений - от простых чертежей до реалистичных образов естественных

объектов. Машинная графика используется почти во всех научных и инженерных

дисциплинах для наглядности восприятия и передачи информации. Знание её

основ в наше время необходимо любому ученому или инженеру. Машинная графика

властно вторгается в бизнес, медицину, рекламу, индустрию развлечений.

Применение во время деловых совещаний демонстрационных слайдов,

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

конторского труда, считается нормой. В медицине становится обычным

получение трехмерных изображений внутренних органов по данным компьютерных

томографов. В наши дни телевидение и другие рекламные предприятия часто

прибегают к услугам машинной графики и компьютерной мультипликации.

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

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

На сегодняшний день создано большое количество программ, позволяющих

создавать и редактировать трёхмерные сцены и объекты. Среди наиболее

популярных можно назвать такие как 3D studio Max, которая позволяет

трёхмерные компьютерные ролики. Область её применения в основном реклама,

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

популярный пакет программ это Auto-CAD. Он применяется в основном

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

моделей. Кроме этих существует множество других специализированных

программных пакетов охватывающих практически все стороны человеческой

жизни.

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

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

мышлении человека, занимают особое место. Современные программно-

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

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

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

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

возможностей компьютеров. Это важное обстоятельство предполагает взаимно

обогащающее сотрудничество всё более совершенной техники и человека со всем

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

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

привлекательной оказывается компьютерная визуализация, особенно

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

инструмент для обучения наукам.

1. Введение в машинную графику

Современная машинная графика - это тщательно разработанная дисциплина.

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

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

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

цвет, закраска, текстура и эффекты прозрачности. Сейчас наибольший интерес

представляют именно эти разделы машинной графики.

Машинная графика - сложная и разнообразная дисциплина. Для изучения её,

прежде всего, необходимо разбить на обозримые части. Прежде всего

необходимо рассмотреть методы и алгоритмы растровой графики. Это достаточно

простой, но очень важный раздел машинной графики. В этом разделе

рассматриваются алгоритмы рисования отрезков и окружностей на экране

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

устранения ступенчатости или лестничного эффекта. Отдельно следует

рассмотреть методы отсечения изображения, т.е. отбора той информации,

которая необходима для визуализации конкретной сцены.

При построении трёхмерной сцены возникает проблема удаления невидимых

линий и поверхностей. Это одна из наиболее сложных составляющих

визуализации трёхмерных объектов. Способы достижения эффектов прозрачности,

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

частей трёхмерных объектов и, тем не менее, некоторые из них тесно связаны

с этой проблемой. Например, построение теней. Не смотря на это, в

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

построению реалистичных изображений, в котором подробно рассматриваются

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

в различных средах, тени, фактура объекта. Так же рассматриваются различные

источники света, их спектральные характеристики и форма. Сюда же относятся

цветовые эффекты, сглаживание поверхностей и многое другое.

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

объемная дисциплина, поэтому я остановлюсь лишь на некоторых её наиболее

интересных аспектах.

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

Любое изображение, в том числе и трёхмерное, состоит из графических

примитивов. Поэтому, прежде всего, необходимо знать специальные методы

генерации изображения, вычерчивание прямых и кривых линий, закраски

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

некоторые из этих методов.

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

Поскольку экран дисплея можно рассматривать как матрицу дискретных

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

непосредственно провести отрезок из одной точки в другую. Процесс

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

называется разложением в растр. Для горизонтальных, вертикальных и

наклоненных под углом 45( отрезков выбор растровых элементов очевиден. При

любой другой ориентации выбрать нужные пикселы труднее.

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

из них.

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

Один из методов разложения отрезка в растр состоит в решении

дифференциального уравнения, описывающего этот процесс. Для прямой линии

имеем:

[pic] или [pic]н

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

[pic]

где x1, y1 и x2, y2 – концы разлагаемого отрезка и yi – начальное значение

для очередного шага вдоль отрезка. Фактически уравнение (2.1.) представляет

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

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

называется цифровым дифференциальным анализатором (ЦДА). В простом ЦДА либо

[pic], либо [pic] (большее из приращений) выбирается в качестве единицы

растра. Ниже приводится простой алгоритм, работающий во всех квадрантах:

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

анализатора (ЦДА)

предполагается, что концы отрезка (x1,y1) и (x2,y2) не совпадают

Integer – функция преобразования вещественного числа в целое.

Примечание: во многих реализациях функция Integer означает взятие целой

части, т.е. Integer(( 8.5) = ( 9, а не ( 8. В алгоритме используется именно

такая функция.

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

положительного аргумента соответственно.

if abs ( x2 ( x1 ) ( abs ( y2 ( y1 ) then

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

else

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

end if

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

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

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

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

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

квадрантов

x = x1 + 0.5 * Sign ( (x )

y = y1 + 0.5 * Sign ( (y )

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

i =1

while ( i ( Длина )

Plot ( Integer ( x ), Integer ( y ) )

x = x + (x

y = y + (y

i = i + 1

end while

finish

С помощью этого алгоритма получают прямые, вполне удовлетворительного

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

точках. Во-вторых, результаты работы алгоритма зависят от ориентации

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

что заметно снижает скорость выполнения.

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

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

представления отрезка. В процессе работы одна из координат - либо x, либо у

(в зависимости от углового коэффициента) - изменяется на единицу. Изменение

другой координаты (либо на нуль, либо на единицу) зависит от расстояния

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

Такое расстояние называется ошибкой.

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

На рис.2.1 это иллюстрируется для отрезка в первом

Ѕ ( (y ( 1 (ошибка ( 0)

0 ( (y/(x < Ѕ (ошибка (x then

Врем = (x

(x = (y

(y = Врем

Обмен = 1

else

Обмен = 0

end if

инициализация [pic] с поправкой на половину пиксела

[pic] = 2 * (y ( (x

основной цикл

for i = 1 to (x

Plot ( x ,y )

While ( [pic] ( 0 )

If Обмен = 1 then

x = x + s1

else

y = y + s2

end if

[pic] = [pic] ( 2 * (x

end while

if Обмен = 1 then

y = y + s2

else

x = x + s1

end if

[pic] = [pic] + 2 * (y

next i

finish

Этот алгоритм удовлетворяет самым строгим требованиям. Он имеет

приемлемую скорость и может быть легко реализован на аппаратном или

микропрограммном уровне.

4. Алгоритм Брезенхема для генерации окружностей

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

функции. Разложению конических сечений, т. е. окружностей, эллипсов,

парабол, гипербол посвящено значительное число работ. Наибольшее внимание,

разумеется, уделено окружности. Один из наиболее эффективных и простых для

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

Брезенхему. Для начала заметим, что необходимо сгенерировать только одну

восьмую часть окружности. Остальные её части могут быть получены

последовательными отражениями, как это показано на рис. 2.3. Если

сгенерирован первый октант (от 0( до 45( против часовой стрелки), то второй

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

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

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

втором квадранте. Верхняя полуокружность отражается относительно прямой у =

0 для завершения построения. На рис.2.3. приведены двумерные матрицы

соответствующих преобразований.

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

начале координат. Заметим, что если работа алгоритма начинается в точке x =

0, у = R, то при генерации окружности по часовой стрелке в первом квадранте

у является монотонно убывающей функцией аргумента x (рис. 2.4). Аналогично,

если исходной точкой является y = 0, x = R, то при генерации окружности

против часовой стрелки x будет монотонно убывающей функцией аргумента у. В

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

0, у = R. Предполагается, что центр окружности и начальная точка находятся

точно в точках растра.

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

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

образом приближающий окружность: горизонтально вправо, по диагонали вниз и

вправо, вертикально вниз. На рис.2.5 эти направления обозначены

соответственно mH, mD, mV. Алгоритм выбирает пиксел, для

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

окружностью, т. е. минимум из

mH = | ( xi + 1 )2 + ( yi )2 – R2 |

mH = | ( xi + 1 )2 + ( yi ( 1 )2 – R2 |

mH = | ( xi )2 + ( yi ( 1 )2 – R2 |

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

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

приведенных на рис.2.6.

Разность между квадратами расстояний от центра окружности до

диагонального пиксела ( xi + 1, yi ( 1 ) и от центра до точки на окружности

R2 равна

[pic]

Как и в алгоритме Брезенхема для отрезка, для выбора соответствующего

пиксела желательно использовать только знак ошибки, а не её величину.

При ( < 0 диагональная точка ( xi + 1, yi ( 1 ) находится внутри

реальной окружности, т. е. это случаи 1 или 2 на рис.2.6. Ясно, что в этой

ситуации следует выбрать либо пиксел ( xi + 1, yi ) т. е. mH, либо пиксел (

xi + 1, yi ( 1 ), т. е. mD. Для этого сначала рассмотрим случай 1 и

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

горизонтальном и диагональном направлениях:

[pic]

При ( < 0 расстояние от окружности до диагонального пиксела

(mD) больше, чем до горизонтального (mH). Напротив, если ( > 0, расстояние

до горизонтального пиксела (mH) больше. Таким образом,

при ( < 0 выбираем mH ( xi + 1, уi )

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

При ( = 0, когда расстояния от окружности до обоих пикселов одинаковы,

выбираем горизонтальный шаг.

Количество вычислений, необходимых для оценки величины (, можно

сократить, если заметить, что в случае 1

[pic]

так как диагональный пиксел ( xi + 1, уi – 1 ) всегда лежит внутри

окружности, а горизонтальный ( xi + 1, уi ) - вне ее. Таким образом, (

можно вычислить по формуле

[pic]

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

вычитания - 2уi + 1 дает

[pic]

В квадратных скобках стоит по определению (i, и его подстановка

( = 2((i + yi) – 1

существенно упрощает выражение.

Рассмотрим случай 2 на рис.2.6 и заметим, что здесь должен быть выбран

горизонтальный пиксел ( xi + 1, уi ), так как у является монотонно

убывающей функцией. Проверка компонент ( показывает, что

[pic]

поскольку в случае 2 горизонтальный ( xi + 1, уi ) и диагональный ( xi + 1,

уi – 1 ) пикселы лежат внутри окружности. Следовательно, ( < 0, и при

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

( xi + 1, уi ).

Если (i > 0, то диагональная точка ( xi + 1, уi – 1 ) находится вне

окружности, т. е. это случаи З и 4 на рис.2.6. В данной ситуации ясно, что

должен быть выбран либо пиксел ( xi + 1, уi – 1 ), т. е. mD, либо ( xi, уi

– 1 ), т. е. mV. Аналогично разбору предыдущего случая критерий выбора

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

квадратами расстояний от окружности до диагонального mD и вертикального mV

пикселов, т. е.

[pic]

При (\ < 0 расстояние от окружности до вертикального пиксела ( xi, уi –

1 ) больше и следует выбрать диагональный шаг mD, к пикселу ( xi + 1, уi –

1 ). Напротив, в случае (\ > 0 расстояние от окружности до диагонального

пиксела больше и следует выбрать вертикальное движение к пикселу ( xi, уi –

1 ). Таким образом,

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

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

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

шаг.

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

[pic]

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

окружности, тогда как вертикальный пиксел ( xi, уi – 1 ) лежит внутри ее.

Это позволяет записать (\ в виде

[pic]

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

вычитания 2xi + 1 дает

[pic]

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

[pic]

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

вертикальный пиксел ( xi, уi – 1 ), так как y является монотонно убывающей

функцией при возрастании x. проверка компонент (\ для случая 4 показывает,

что

[pic]

поскольку оба пиксела находятся вне окружности. Следовательно, (\ > 0 и при

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

выбор mV.

Осталось проверить только случай 5 на рис.2.7, который встречается,

когда диагональный пиксел ( xi + 1, уi – 1 ) лежит на окружности, т. е. (i

= 0. Проверка компонент ( показывает, что

[pic]

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

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