Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Шпоры по компьютерной графике (по билетам) - файл Шпоры КГ.doc


Шпоры по компьютерной графике (по билетам)
скачать (207.5 kb.)

Доступные файлы (1):

Шпоры КГ.doc787kb.02.01.2007 18:03скачать

содержание
Загрузка...

Шпоры КГ.doc

  1   2   3   4   5
Реклама MarketGid:
Загрузка...
(Билет 1)1. Предмет КГ. Области применения КГ. Совр. Тенденции развития КГ.

Компьютерная графика (КГ) – это область информатики, включающая все аспекты формирования изображений с помощью компьютеров. В том случае, если пользователь может управлять характеристиками объектов, говорят об интерактивной компьютерной графике.

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

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

Основная задача распознавания образов состоит в преобразовании уже имеющегося изображения на формально понятный язык символов. Распознавание образов, или система технического зрения (COMPUTER VISION), – совокупность методов, позволяющих получить описание изображения, поданного на вход, либо отнести заданное изображение к некоторому классу. Одной из задач COMPUTER VISION является так называемая «скелетизация» объектов, при которой восстанавливается некая основа объекта, его «скелет».

Обработка изображений (IMAGE PROCESSING) рассматривает задачи, в которых и входные, и выходные данные являются изображениями, например, передача изображения с устранением шумов и сжатием данных, переход от одного вида изображения к другому (от цветного к черно-белому) и т.д.

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

Области применения компьютерной графики:

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

  1. 2. Проектирование.

    1. – Системы CAD/CAM используются сегодня в различных областях инженерной конструкторской деятельности: от проектирования микросхем до создания самолетов.

    2. – Архитектура. Есть ряд эффектных применений КГ в области проектирования стадионов и дизайна спортивного инвентаря.

    3. – Медицина.

3. Моделирование. Моделирование реальной обстановки (симуляторы), построение фотореалистических изображений, формирование виртуальной реальности (VR – virtual reality).

  1. 4. Пользовательский интерфейс, например MS Windows, X-Windows, Mac OS и др.

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

2D-графика достигла максимальной скорости (для классических задач и разрешений). Все поставляемые сегодня ПК имеют возможности 3D-графики.

Активно развивается «новое» направление КГ – обработка видеоинформации.

^ 13. Аффинные преобразования на плоскости.
Допустим, на плоскости введена прямолинейная координатная система. Тогда каждой точке М ставится в соответствие упорядоченная пара чисел (х, у) ее координат (рис. 1). Вводя на плоскости еще одну прямолинейную систему координат, мы ставим в соответствие той же точке М другую пару чисел - (х*, у*).

Переход от одной прямолинейной координатной системы на плоскости к другой описывается следующими соотношениями:

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



Формулы (*) можно рассматривать двояко: либо сохраняется точка и изменяется координатная система (рис. 2) – в этом случае произвольная точка М остается той же, изменяются лишь ее координаты, либо изменяется точка и сохра­няется координатная система (рис. 3) – формулы (*) задают отображение, переводящее произвольную точку M(x,y) в точку М*(х*, у*), координаты которой определены в той же координатной системе.



Рис. 1



Рис. 2



Рис. 3

В дальнейшем мы будем рассматривать формулы (*) как правило, согласно которому в заданной системе прямолинейных координат преобразуются точки плоскости.

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

  1. Поворот вокруг начальной точки на угол  описывается формулами:



  1. Растяжение (сжатие) вдоль координатных осей можно задать так:

х* = х, у*=у, а > 0, > 0 .

Например, растяжение (сжатие) вдоль оси абсцисс обеспечивается при условии, что  > 1 (0 <  < 1).

  1. Отражение (относительно оси абсцисс) задается при помощи формул:

х* = х, у* = -у.

  1. Параллельный перенос обеспечивают соотношения

x* = x + ,

у* = у + ..

Выбор этих четырех частных случаев определен двумя обсто­ятельствами.

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

  2. Любое преобразование вида (*) всегда можно представить в виде последовательного исполнения простейших преобразований.

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

, ,

Этого можно достичь, например, так: перейти к опи­санию произвольной точки плоскости тройкой чисел.

Билет 2



^ 2. История развития КГ. Современные тенденции развития КГ.
История компьютерной графики (КГ) тесно связана с этапами развития аппаратного обеспечения вычислительной техники.

Первые системы компьютерной графики появились вместе с первыми цифровыми компьютерами. Началом эры КГ можно считать проект 1950 года WHIRLWIND ("вихрь"). Его система уже имела дисплей. «Вихрь» стал основой создания опытного образца системы воздушной защиты как средства преобразования данных, полученных от радара, в наглядную форму.

Середина 1960-х – период плодотворной работы и в промышленных приложениях КГ. Сначала появилась цифровая электронная чертежная машина фирмы Itek. В 1964 году появилась DAC-1 – система автоматизированного проектирования, разработанная совместно с IBM. Первые запоминающие электронно-лучевые трубки появились в 1968 году, когда фирма Computer Displays создала систему ARDS, а Computek – свою серию 400.

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

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

Развитие систем CAD/CAM начиналось с мэйнфреймов, работающих с каркасными моделями. К середине восьмидесятых рабочие станции стали уже обычным средством.

В 1984 году появилась модель Apple Macintosh с графическим интерфейсом пользователя. Первоначально областью применения ПК были не графические приложения, а работа с текстовыми процессорами и электронными таблицами.В конце 80-х рабочие станции приобрели возможности вывода фотореалистических изображений в реальном масштабе времени. Манипулятор "мышь" стал естественным графическим устройством ввода, наряду с сенсорными системами, которые также нашли свое место в числе оборудования КГ.

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

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

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

2D-графика достигла максимальной скорости (для классических задач и разрешений). Все поставляемые сегодня ПК имеют возможности 3D-графики.

Активно развивается «новое» направление КГ – обработка видеоинформации.
^ 12. Аффинные преобразования, их свойства, однородные координаты.
Для решения таких задач, как движение объектов и их частей, управления камерой применяются аффинные преобразования (АП), рассмотрим их основные свойства:

1) точки, лежащие на одной прямой, после преобразования лежат на одной прямой;

2) пересекающиеся прямые остаются пересекающимися, а параллельные – параллельными;

3) при АП пространства пересекающиеся плоскости остаются пересекающимися, параллельные – параллельными, а скрещивающиеся – скрещивающимися;

4) при АП сохраняются отношения площадей двух квадратов на плоскости и отношение объемов двух кубов в пространстве.

Пусть М - произвольная точка плоскости с координатами х и у, вычисленными относительно заданной прямолинейной координатной системы. Однородными координатами этой точки называется любая тройка одновременно неравных нулю чисел x1, x2, x3, связанных с заданными числами x и y следующими соотношениями:

x


Однородные координаты
1/x3=x, x2/x3=y.

При решении задач компьютерной графики однородные коорди­наты обычно вводятся так: произвольной точке М(х, у) плоскости ста­вится в соответствие точка М*(х,у,1) в пространстве. Произвольная точка на прямой, соединяющей начало координат, точку 0(0, 0, 0) с точкой М*(х, у, 1), может быть задана тройкой чисел вида (hx, hy, h).

Будем считать, что h0. Вектор с координатами hx, hy, h является направляющим векто­ром прямой, соединяющей точки 0(0, 0, 0) и М*(х, у, 1). Эта прямая пересекает плоскость z = 1 в точке (х, у, 1), которая однозначно определяет точку (х, у) коорди­натной плоскости ху.

При помощи троек однородных координат и матриц третьего порядка можно описать любое аффинное преобразование плоскости. В самом деле, считая h = 1, сравним две записи: помеченную символом * и матричную:



Нетрудно заметить, что после перемножения выражений, стоя­щих в правой части последнего соотношения, мы получим обе форму­лы (*) и верное числовое равенство 1 == 1. Тем самым сравниваемые записи можно считать равносильными.

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

1. Матрица вращения (rotation)

;

2. Матрица растяжения (сжатия)

(dilatation)

;

3. Матрица переноса (translation)

;

4. Матрица отражения (reflection)







Билет 3



^ 3. Основные понятия КГ. Аппаратное обеспечение КГ. Принципы формирования изобр.
Компоненты графической системы – практически все, что только есть в компьютере:

1) процессор общего назначения; 2) память;3)видеоадаптер; 4) устройства ввода;

5) устройства вывода.

Электронный луч можно направить в желаемое место на экране в одном из двух режимов: векторном и растровом. В векторном режиме движение луча определяется координатами точек рисуемой фигуры. Координаты могут быть заданы и математическими формулами. Для представления дисплейных примитивов векторная графика требует мало памяти, сами примитивы четко изображаются, оператор может непрерывно менять изображения в реальном времени. Главным недостатком векторной графики является то, что с ее помощью нельзя изобразить сплошные области, любые объекты могут быть представлены лишь в виде проволочных каркасов. В растровом режиме луч отклоняется не в соответствии с контурами рисунка, а, как в бытовом телевизоре, 25 раз в секунду высвечивается растр (кадр),состоящий из строк. Управлять в растровом режиме можно только яркостью луча при прохождении им

активных точек строки. ^ Векторная графика – представление графического изображения в памяти компьютера в виде координат отдельных точек. Растровая графика – представление графического изображения как единого целого, а в памяти компьютера как копии всего экрана. Цифровое изображение – набор точек (пикселей) изображения; каждая точка изображения характеризуется координатами x и y и яркостью V(x, y), это дискретные величины, обычно целые. В случае цветного изображения каждый пиксель характеризуется координатами x и y и тремя яркостями яркостью красного, синего и зеленого (VR , VB , VG). Комбинируя эти три цвета, можно получить большое количество различных оттенков. Максимальное количество цветов, одновременно отображаемых на экране, определяется количеством битов, выделенных для каждого пикселя в видеобуфере. В полноцветных системах каждому пикселю отводится 24 бита цветовой информации: по байту на каждый компонент VR , VB , VG. Как правило, чем больше пикселей на экране, тем выше качество изображения. Один из путей, позволяющих скомпенсировать нехватку имеющихся цветов, – это псевдотонирование компьютерного изображения. Существует много вариантов псевдотонирования, но все они основаны на одном принципе – замене пикселей с цветами, отсутствующими в палитре, конфигурациями пикселей с цветами из палитры. Псевдотонирование основывается на том, что человеческий глаз смешивает цвета двух рядом находящихся пикселей, воспринимая некий третий цвет. В зависимости от разрешающей способности они подразделяются на CGA, EGA, VGA, SVGA и др. Каждой точке экрана, называемой пикселем, соответствует определенное место в памяти, называемое видеопамятью. Обычно она располагается на видеоадаптере, который управляет работой дисплея, циклически отображая на экране содержимое видеопамяти.

Режимы видеоадаптеров:

MDA (монохромный) режим. Позволяют получать разрешение до 1280х1024

CGA (Color Graphic Adapter) имеет характеристики 320 х 200 при 4-х цветах.

EGA (Enhanced Graphic Adapter) имеет разрешение 640 х 350, но при этом доступны всего лишь 4 цвета (16 цветов – при 320х200).

VGA (Video Graphic Array) режим основан на подаче аналогового сигнала, что позволяет получать до 16 цветов (из 256) при разрешении 640х480.

Перечисленные дисплеи называются иначе цифровыми, поскольку на экран поступает цифровой RGB сигнал из 3 пушек (Red, Green, Blue). Развитием данного режима является стандарты SVGA, позволяющие получить 32-битный цвет при разрешениях, зависящих от

возможностей аппаратного обеспечения.

Устройства вывода можно классифицировать следующим образом:

1. По принципам записи (обновления) изображения:

− с произвольным сканированием луча, при котором изображение формируется при перемещении луча по экрану в соответствии с координатами строящихся элементов изображения (каллиграфические, штриховые устройства);

− с растровым сканированием луча, при котором изображение представляется в виде матрицы точек; изображение на экране формируется при перемещении луча в соответствии с разверткой слева-направо по строке и сверху-вниз по строкам с подсветкой требуемых точек; 2) по принципам отображения:

− периодическая регенерация информации на экране из неотображающей памяти;

− использование отображающего устройства сохранения изображения;

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

^ Электронно-лучевые трубки:

электронно-лучевая трубка (ЭЛТ), используемая в видеомониторах. Катод нагревают до тех пор, пока возбужденные электроны не создадут расширяющегося облака. Эти электроны притягиваются к сильно заряженному положительному аноду. На внутреннюю сторону расширенного конца ЭЛТ нанесен люминофор. Облако электронов с помощью электронных линз фокусируется в узкий, строго параллельный пучок. Теперь сфокусированный электронный луч дает одно яркое пятно в центре ЭЛТ. Луч отклоняется или позиционируется влево или вправо от центра и выше или ниже центра с помощью усилителей горизонтального и вертикального отклонения. В цветной растровой ЭЛТ находятся три электронные пушки, по одной на каждый основной цвет: красный, зеленый и синий. Для того чтобы электронные пушки возбуждали только соответствующие им точки люминофора (например, красная пушка возбуждала только точку красного люминофора), между электронными пушками и поверхностью экрана помещена перфорированная металлическая решетка. Это так называемая теневая маска стандартной цветной ЭЛТ с теневой маской. Процесс преобразования хранящейся в буфере кадра растровой картинки в упорядоченный набор точек на телеэкране называется растровой разверткой. Минимальной скоростью вывода или изменения изображения является 25 кадров в секунду при условии, что минимальная скорость регенерации или воспроизведения в два раза больше, т. е. 50 кадр/с.

^ ЖК дисплеи:

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

Экран на динамическом рассеивании:

Две прозрачные пластинки, между ними жидкие кристаллы. Подано напряжение. Часть света отражается, и образуются цвета. Кристаллы выстраиваются определенным образом, создавая на экране изображение.

^ Экран на основе твист-эффекта:

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

Для решения проблемы быстродействия были разработаны ЖК-дисплеи с активной матрицей, в которых каждый пиксель снабжен независимо управляемым тонкопленочным транзистором (TFT).

Плазменные дисплеи:

принцип работы: с двух сторон располагаются металлизированные полоски, В середине – диэлектрик с отверстиями. В отверстиях – газ. Все это склеивают. Одна пластинка служит катодом (К), другая – анодом(А).
^ 15. Проецирование. Общий вид преобразований в пространстве. Виды проекций.
Трехмерных объекты, на бумаге и на экране дисплея, вычерчиваются при помощи двухмерных проекций. В плоской проекции каждая точка предмета отображается определенным образом на плоскость проекции, и её образ называется точкой проекции. Если линии, соединяющие точки предмета с соответствующими точками отображения, параллельны, то мы имеем плоскую параллельную проекцию. Если же линии сходятся в одной общей точке, то получаемое изображение называется центральной проекцией, или перспективным изображением предмета.

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




где a, d, е – масштабирование:

m, n, l – смещение;
p, q, r – проецирование;
s – комплексное масштабирование;
х – вращение.

Параллельные проекции можно разделить на следующие группы:

1) ортографическая проекция (параллельно одной из координатных плоскостей) координатная плоскость параллельна или совпадает с одной из координатных плоскостей. Если она параллельна, то необходимо координаты исходной точки умножить на матрицу сдвига с параметром m или n или l <>0.

2) аксонометрическая проекция (проектирующие прямые перпендикулярны картинной плоскости):

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

  • диметрическая (два угла между нормалью картинной плоскости и координатными осями равны);

– изометрическая (три угла между нормалью картинной плоскости и координатными осями равны); Каждый из трех видов аксонометрических проекций получается комбинацией поворотов, за которой следует параллельное проектирование. Например, поворот вокруг оси ординат, оси абцисс и проектирование вдоль оси аппликат.

3) Проекции, для получения которых используется пучок прямых, не перпендикулярных плоскости экрана, называют косоугольными.

  • Свободная-;кабинетная.Среди перспективных проекций выделяются:-одноточечная (r  0);-двухточечная (p, q  0);-трехточечная (p, q, r  0).

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

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

В OpenGL ортографическая проекция задается функциями:

  • glOrtho(left, right, bottom, top, near, far), где near >0, far >0.

  • glOrtho2D(left, right, bottom, top), где near=0, far=1.

В OpenGL перспективная проекция задается функциями:

  • glFrustum(left, right, bottom, top, near, far), где near >0 , far >0;

  • gluPerespective(fovy,aspect,near,far) – параметр fovy задает угол видимости в направлении оси OY в градусах, центрированный относительно этой оси.

Используемый в OpenGL и других графических API подход базируется на методике нормализации проецирования (projection normalization), которая предусматривает сведение всех типов проекций к ортогональной, для чего выполняется предварительной искажение исходных объектов.


Билет 4
^ 4. Архитектура рабочих станций. Графический ускоритель. АРI.
Видеокарта предназначена для преобразования информации, хранящейся и обрабатываемой ПК в визуальную форму, пригодную для воспроизведения на мониторе. Комплект “видеокарта-монитор” – это интерфейс между человеком и ПК.

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

В настоящий момент в видеоакселерации можно выделить следующие направления:

1) 2D – ускорители (прорисовка окон при открытии и свертывании, аппаратный курсор, постоянно видимый при перемещении указателя, аппаратная поддержка примитивов линий, окружностей, шрифтов, закраска областей на экране, заливка градиентов и т.д.);

2) обработка видеопотоков (компрессия/декомпрессия в реальном времени);

3) 3D – ускорители.

API

Интерфейс между прикладной программой и графической системой – это множество функций, которые в совокупности образуют графическую библиотеку. Спецификация этих функций и есть то, что мы называем интерфейсом прикладного программирования (API –Appli cation programmer’s interface). Для программиста, занимающегося разработкой прикладной программы, существует только API, таким образом, он избавлен от необходимости вникать в подробности работы аппаратуры и программной реализации функций графической библиотеки. Программируемый интерфейс приложений (API) состоит из функций, управляющих 3D-конвейером на программном уровне, но при этом может использовать преимущества аппаратной реализации 3D при наличии этой возможности. Если имеется аппаратный ускоритель, API использует его преимущества, если нет, то API работает с оптимальными настройками, рассчитанными на самые обычные системы. Таким образом, благодаря применению API любое количество программных средств может поддерживаться любым количеством аппаратных 3D-ускорителей.

^ 14. Аффинные преобразования в пространстве. Использование матричного представления. Составные аффинные преобразования в пространстве.
Поступая аналогично тому, как это было сделано в размерности два, заменим координатную тройку (х, у, z), задающую точку в про­странстве, на четверку чисел (x, y, z, 1) или, более обобщенно, на (hx, hy, hz), h0. Каждая точка пространства (кроме начальной точки О) может быть задана четверкой одновременно не равных нулю чисел; которая определена однозначно с точностью до общего мно­жителя. Предложенный переход к новому способу задания точек позволяет воспользоваться матричной записью и в более сложных, трехмерных задачах.

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

1. Матрицы вращения в пространстве

вокруг оси абсцисс на угол :



вокруг оси ординат на угол :



2. Матрица растяжения (сжатия):

,

где, используются следующие коэффициенты растяжения(сжатия):

 > 0 - вдоль оси абсцисс;

 > 0 - вдоль оси ординат;

 > 0 - вдоль оси аппликат.


3. Матрицы отражения

относительно плоскости ху

;

относительно плоскости уz

;

относительно плоскости zx

.

4. Матрицы переноса (здесь ,, - координаты вектора переноса)

.


Билет 5
^ 5. Архитектура графических рабочих станций. Технологии 3D графики.
Часть вычислительных операций, связанных с отображением и моделированием трехмерного мира, переложено теперь на 3D-акселератор, который является сердцем 3D-видеокарты. Для достижения реалистичности отображения поверхностей применяется текстурирование . Так, фасад здания потребовал бы отображения множества граней для моделирования множества кирпичей. Однако текстура (изображение, накладываемое на всю поверхность сразу) дает больше реализма, но требует меньше вычислительных ресурсов, так как позволяет оперировать всем фасадом как единой поверхностью. Перед тем, как поверхности отображают на экране, они текстурируются и затеняются. Все текстуры хранятся в памяти, обычно установленной на видеокарте. Когда поверхности текстурируются, необходим учет перспективы. Она гарантирует, что битмэп (массив пикселей) правильно наложится на разные части объекта – и те, которые ближе к наблюдателю, и на более далекие. Для подавления эффектов мерцания и пробелов между битмэпами применяется фильтрация (обычно би- или трилинейная). Чтобы избежать непредвиденных изменений (depth-aliasing – неверное наложение текстуры на удаленные полигоны), большинство управляющих графикой процессов создают серии предфильтрованных битмэпов текстур с уменьшенным разрешением, этот процесс называется mip mapping. Затем графическая программа автоматически определяет, какую текстуру использовать, основываясь на деталях изображения, которое уже выведено на экран. Соответственно, если объект уменьшается в размерах, размер его текстурного битмэпа тоже уменьшается: 0 – сама текстура, 1 – уменьшенная в два раза и т.д. В момент нахождения объекта в переходном состоянии от одного mip-map-уровня к другому появляется особый тип ошибок визуализации, известных под названием mip-banding (мип-бендинг) – полосатость или слоеность, т.е. явно различимые границы перехода от одного mip-map-уровня к другому.

^ Билинейная фильтрация – метод устранения искажений изображения. При медленном вращении или движении объекта могут быть заметны перескакивания пикселей с одного места на другое, что и вызывает мерцание. Для снижения того эффекта при билинейной фильтрации для отображения точки поверхности берется взвешенное среднее четырех смежных текстурных пикселей. Трилинейная фильтрация – для получения каждого пикселя изображения берется взвешенное среднее значение результатов двух mip-уровней билинейной фильтрации. Полученное изображение будет еще более четким и менее мерцающим, что позволяет решить проблему mip-banding. Одной из альтернатив трилинейной фильтрации является анизотропная фильтрация. Анизотропная фильтрация может быть реализована с помощью использования выборки по шаблонам, в качестве которых могут выступать текстели. Для наложения текстуры на пиксель используется больше текстелей, причем количество используемых текстелей зависит от применяемого алгоритма. Для борьбы с рваными краями изображения применяется anti-aliasing. Это способ обработки (интерполяции) пикселей для получения более четких краев изображения.

Z-буферизация – это самый распространенный метод удаления скрытых поверхностей. В Z-буфере хранится значение глубины всех пикселей (z-координаты).

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

Прозрачность – способ передачи информации о прозрачности полупрозрачных объектов. Эффект полупрозрачности создается путем объединения цвета исходного пикселя с пикселем, уже находящимся в буфере. В результате цвет точки является комбинацией цветов переднего и заднего плана.
^ 16. Этапы создания графического объекта. Преобразование положения объекта. Понятие камеры. Особенности матричных преобразований.
Задание 3D объекта и его создание разбивается на несколько этапов, в процессе которых последовательно преобразуется система координат. Изначально объект задается в некоторой своей локальной системе координат, которая затем размещается в мировой системе координат. Далее определяем видовую систему координат, задавая картинную плоскость, положение глаза (камеры) и систему координат камеры.

Основной задачей проектирования является перевод 3-х мерного объекта, заданного в видовой системе координат, в 2-х мерный объект нормализованной системы координат устройства.

При проектировании отсекаются объекты, которые не попадают в область видимости, а также определяется множество значений z (zÎ[near; -far]), для которого точки, имеющие значения координаты z, принадлежащие этому множеству, являются видимыми, а точки, находящиеся слишком близко () или слишком далеко () – невидимыми.

Преобразования над объектами по функциональному признаку можно разделить на следующие группы:

- моделирующие преобразования (аффинные преобразования);

- видовые преобразования (положение, направление камеры и т.д.);

- задание проекции;

- задание области видимости.

Моделирующие преобразования определяют положение объекта в мировом пространстве. Изначально матрица видового преобразования строится на основе информации о параметрах камеры (положении направлении камеры, положительного направления) и положении мира относительно камеры.

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

- координаты камеры;

- направление обзора;

- координаты вектора;

- определяющего вертикальное направление.

Серия преобразований может быть свернута в одну матрицу преобразований:

  • композиция преобразований не является коммутативной;

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

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

  • преобразования обратимы, (для переноса на вектор (a,b,c) – это перенос (-a,-b,-c));

  • преобразования могут восприниматься как изменения в системе координат;

  • преобразования, необходимые для перевода точки из КС2 в КС1, можно получить как обратную последовательность кадров, переводящих КС1 в КС2.


Билет 6
^ 7. Общие положения алгоритмов сжатия изображений.
Изображения – это своеобразный тип данных, характеризуемый тремя особенностями:

1) Изображения занимают намного больше места в памяти, чем текст.

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

3) При создании алгоритма компрессии графики мы используем особенности структуры изображения – изображение в отличие, например, от текста обладает избыточностью в 2-х измерениях. Т.е., как правило, соседние точки, как по горизонтали, так и по вертикали в изображении близки по цвету.

Для того, чтобы говорить об алгоритмах сжатия изображений, решить несколько важных вопросов:

1) Какие классы изображений существуют?

2) Какие классы приложений, использующие алгоритмы компрессии графики, существуют, и какие требования они предъявляют к алгоритмам?

3) Какие критерии мы можем предложить для сравнения различных алгоритмов?

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

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

1. Изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом. Плавные переходы цветов отсутствуют. (Графики, диаграммы).

2. Изображения с плавными переходами цветов, построенные на компьютере (графика презентаций, эскизные модели в САПР, изображения, построенные по методу Гуро)

3. Фотореалистичные изображения, например отсканированные фотографии.

4. Фотореалистичные изображения с наложением деловой графики, например реклама.

Рассмотрим следующую простую классификацию приложений, использующих алгоритмы компрессии:

1. Характеризуются высокими требованиями ко времени архивации и разархивации.

2. Характеризуется высокими требованиями к степени архивации и времени разархивации.

3. Характеризуются очень высокими требованиями к степени архивации.

Требования к алгоритмам компрессии:

1. Высокая степень компрессии. Некоторые алгоритмы дают лучшее соотношение качества к размеру файла при высоких степенях компрессии, однако проигрывают другим алгоритмам при низких степенях.

2. Высокое качество изображений.

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

4. Высокая скорость декомпрессии.

5. Масштабирование изображений (легкость изменения размеров изображения до размеров окна активного приложения).

6. Возможность показать изображение низкого разрешения, используя только начало файла.

7. Устойчивость к ошибкам. Данное требование означает локальность нарушений в изображении при порче фрагмента передаваемого файла.

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

9. Редактируемость. Под редактируемостью понимается минимальная степень ухудшения качества изображения при его повторном сохранении после редактирования.

10. Небольшая стоимость аппаратной реализации. Эффективность программной реализации.

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

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

2. Класс изображений, на который ориентирован алгоритм.

3. Симметричность. Отношение характеристики алгоритма кодирования к аналогичной характеристике при декодировании. Характеризует ресурсоемкость процессов кодирования и декодирования. Симметричность по времени – отношение времени кодирования ко времени декодирования. Иногда потребуется симметричность по памяти.

4. Наличие потерь качества. Способы изменения коэффициента архивации.

5. Характерные особенности алгоритма и изображений, к которым его применяют.
^ 17. Понятие растрового алгоритма. Понятие связности. Основные требования предъявляемые к растровым алгоритмам.
Так как в подавляющем большинстве графические устройства являют­ся растровыми, то есть представляют изображение в виде прямоуголь­ной матрицы пикселов (растра), то, возникает необходимость в растровых алгоритмах.

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

• переведение идеального объекта (отрезка, окружности и др.) в их растровые образы;

обработка растровых изображений.

Достаточно важным понятием для растровой сетки является связ­ность - возможность соединения двух пикселов растровой линией, то есть последовательным набором пикселей. При этом возникает воп­рос, когда пикселы (х11)и (х2,y2) можно считать соседними.

Вводится два понятия связности:

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

x1-x2+ y1-y21,

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

x1-x21, y1-y21,

Понятие 4-связности является более сильным, чем 8-связность: любые два 4-связных пиксела являются и 8-связными, но не наоборот.

т.к. понятие линии базируется на понятии связанности, то естественным образом возникает понятие 4- и 8-связных линий. Поэтому когда идет речь о растровом представлении, например, отрезка, то следует ясно понимать, о каком именно представлении идет речь. При этом нужно иметь в виду, что растровое представление объекта не является единственным и возможны различные способы построения.

Билет 7
6. Архитектура графических рабочих станций. Принципы конвейерной архитектуры.
Описывая технологии, применяемые в 3D-графических акселераторах, попробуем разобраться, каким же образом применение всех эффектов позволяет получить целостную картину. 3D-графика реализуется с помощью многоступенчатого механизма, называемого конвейером рендеринга.

Конвейерная обработка позволяет ускорить выполнение расчетов за счет того, что вычисления для следующего объекта могут быть начаты до окончания вычислений предыдущего. Конвейер рендеринга может быть разделен на 2 стадии: геометрическая обработка и растеризация.

1) Подготовка отсечения

Масштабирование

Освещение

Разбиение на примитивы

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

Z-Buffer, текстурирование

Туман

Прозрачность

Сглаживание

Pixel

Графический конвейер на стадии геометрической обработки выполняется преобразование координат (вращение, перенос и масштабирование всех объектов), отсечение невидимых частей объектов, расчет освещения, определение цвета каждой вершины с учетом всех световых источников и процесс деления изображения на более мелкие формы. Для описания характера поверхности объекта она делится на всевозможные многоугольники. Наиболее часто используется деление на треугольники и четырехугольники. Координаты объектов переводятся из вещественного в целочисленное представление для ускорения вычислений. На этапе рендеринга применяются эффекты в следующей последовательности: удаление скрытых поверхностей, наложение с учетом перспективы текстур с использованием z-буфера, применение эффектов тумана и полупрозрачности. После этого очередная точка считается готовой к помещению в буфер со следующего кадра. В отличие от геометрического этапа, зависящего от вычислительной мощности процессора, выполняющего все вычисления, этап рендеринга интенсивно использует ресурсы памяти. Для каких целей используется память, установленная на плате 3D-акселератора. В ней дополнительно хранятся текстуры, z-буфер и буфер следующего кадра.


^ 18. Растровое представление отрезка: постановка задачи, простейший алгоритм, алгоритм ЦДА.
"дискретная плоскость" – множество всех точек с целочисленными координатами на обычной плоскости. Дискретную плоскость часто называют целочисленной решеткой. Нельзя провести непрерывный отрезок прямой линии из одной точки экрана в другую. Можно только подсветить ближайшие к прямой пикселы. Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением отрезка в растр.

Отрезки должны удовлетворять следующим требованиям:

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

  2. Яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.

  3. Алгоритмы рисования должны быть простыми , т.е. отрезок “рисоваться” должен быстро.

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

Следует отметить, что постоянная яркость будет у горизонтальных, вертикальных отрезков и под углом 450, причем у отрезков под углом 450 яркость будет меньше чем у вертикальных и горизонтальных отрезков.

Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки (x1, y1) и (x2, y2). Для простоты будем считать, что 0y2-y1x2-x1. Тогда отрезок описывается следующим уравнением:

или у = kx+b .

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

Другим простейшим алгоритмом разложения отрезка в растр является алгоритм, построенный по методу цифрового дифференциального анализатора (ЦДА).

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

^ 1) Осуществляется аппроксимация длины отрезка (float len)

2) Полагаем большее из приращений Dy или Dx равным единице растра

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

^ 4) Начало основного цикла

i=1;

while (i<= Len)

{ PutPixel (Int(x), Int(y), Color);

x = x + Dx;

y = y + Dy;

i = i + 1;}

Недостатки алгоритма разложения отрезка в растр, основанного на методе ЦДА:

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

  2. Может быть активизирован пиксел, стоящий за концом отрезка, и если рисуется ломаная, то данный пиксел будет высвечиваться 2 раза.

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



Билет 8
Технические средства отсутствуют


^ 20. Растровое представление отрезка: построение сглаженной линии (метод Флойда-Стейнберга, модификация алгоритма Брезенхейма, сглаживание всей сцены).
Основной причиной лестничного эффекта является то, что отрезок или ребро какой-либо фигуры непрерывны для того, чтобы соответствовать дискретным пикселам экрана дисплея.

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

В результате простой модификации алгоритма Брезенхейма можно получить аппроксимацию площади части пиксела, находящейся внутри многоугольника. Эту аппроксимацию можно использовать для модуляции интенсивности. При пересечении пиксела и отрезка с тангенсом угла наклона m (0 <= m <= 1) может быть задействован либо один, либо два пиксела. Если пересекается только один пиксел, то площадь правее и ниже отрезка равна уi+ m/2. Если же надо рассмотреть два пиксела, то площадь нижнего пиксела составляет 1 - (1 - yi)2/2m, а верхнего - (yi-1+m)2/2m. Суммарная площадь для двух пикселов равна уi + m /2.


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

Если к ошибке в исходном алгоритме Брезенхейма добавить величину w = 1 - m, т.е. ввести преобразование e' = e + w, то 0<=e'<=1. Теперь ошибка е' - это мера площади той части пиксела, которая находится внутри многоугольника, т. е. уi+m/2. В связи с этими модификациями начальное значение ошибки равно 1/2, поэтому для первого пиксела алгоритм, приводившийся на первом рисунке, всегда будет выдавать значение интенсивности, равное половине максимальной. Более реалистичное значение для первого пиксела дает перемещение оператора активирования пиксела на другое место. Более того, можно получить непосредственно значение интенсивности, а не десятичную дробь от ее максимума с помощью умножения на максимальное число доступных уровней интенсивности I следующих величин: тангенса угла наклона (m), весового коэффициента (w) и ошибки е'.

Билет 9


^ 8. Алгоритмы архивации без потерь: RLE, LZ/LZW, Хаффман.
Алгоритм RLE.

Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных. В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного файла. Оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сжимаем в 32 раза. Алгоритм рассчитан на деловую графику – изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка, например, при обработке цветных фотографий. Для того чтобы изображение увеличилось в два раза, в нем значения всех пикселей должны быть больше двоичного 11000000 и подряд попарно не повторяться. Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл. Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта. В лучшем случае этот алгоритм сжимает файл в 64 раза, в худшем увеличивает на 1/128.

Алгоритм LZ/LZW.

Сжатие в нем в отличие от RLE осуществляется уже за счет одинаковых цепочек байт. Существует довольно большое семейство LZ-подобных алгоритмов. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что во входном потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> пропускаемых байт и сами значения байтов. При разархивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений “пропускаемых” байт просто копируются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера при поиске одинаковых подстрок. В результате сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на <счетчик> и на <смещение> будет выделено по 2 байта (старший бит старшего байта счетчика – признак повтора строки / копирования потока), даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб. В пределе, поскольку максимальное сжатие мы получаем, превращая 32Кб буфера в 4 байта, а буфер такого размера будет накоплен не сразу. Однако минимальная подстрока для которой выгодно проводить сжатие, должна состоять в общем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма.

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

Алгоритм Хаффмана – один из классических алгоритмов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины, и, напротив, встречающимся редко – цепочку большей длины. Для сбора статистики требует двух проходов по изображению. Классический алгоритм Хаффмана требует записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек.

^ 19. Растровое представление отрезка: постановка задачи, алгоритм Брезенхейма.
Процесс определения пикселов, наилучшим образом аппроксимирующих заданный отрезок, называется разложением отрезка в растр.

Идея алгоритма состоит в том, что в процессе построения отрезка одна из координат - либо “х”, либо “y” (в зависимости от углового коэффициента) - изменяется на единицу. Изменение другой координаты (либо на нуль, либо на единицу) зависит от расстояния между “теоретическим” положением отрезка и ближайшими координатами сетки (такое расстояние в алгоритме называется “ошибкой”).

При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксел. При этом из двух точек А и В выбирается та, которая ближе к исходной прямой (в данном случае выбирается точка А, так

как а < b).

При совмещении начала координат с одним из концов отрезка, имеем три возможные оси симметрии, и достаточно рассмотреть половину одного квадранта, например ту, для которой dx >= dy >= 0.

Уравнение прямой, описывающее отрезок:



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

Пусть E = y*dx - x*dy. (1)

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

Движение A: увеличение x

x = x + 1; в результате согласно (1) ошибка уменьшается на величину dy:

E = E - dy;

Движение B: увеличение x и y

x = x + 1;

y = y + 1;

приводит в соответствии с (1) к возрастанию E на величину (dx - dy), имеющую положительное значение в рассматриваемой половине квадранта:

E = E + dx - dy;

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

Этот алгоритм имеет два недостатка:

  1. первое движение выбирается произвольно

  2. ошибка изменяется от dx-dy до -dy и случайным образом большинство точек может расположиться выше или ниже истинного отрезка.

Обе проблемы отпадают, если центрировать функцию ошибки относительно нуля, начиная с величины (dy -dx/2):

E = dy - dx/2.

Билет 10
^ 9. Алгоритмы архивации с потерями, проблемы алгоритмов архивации с потерями. Основные идеи алгоритмов JPEG, фрактальный, волновой.
Несжимаемость многих изображений привела к созданию нового типа алгоритмов – сжимающих с потерей информации. Коэффициент архивации и степень потерь качества в них можно задавать. При этом достигается компромисс между размером и качеством изображений.

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

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

JPEG – один из самых новых и достаточно мощных алгоритмов. Разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. Оперирует алгоритм областями 8х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при разложении матрицы такой области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.

^ Фрактальная архивация основана на том, что изображение представляется в более компактной форме – с помощью коэффициентов системы итерируемых функций (IFS). IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х-координата, у-координата, яркость). Фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.

^ Рекурсивный (волновой) алгоритм исходит из идеи использования когерентности областей. Ориентирован алгоритм на цветные и черно-белые изображения с плавными переходами. Идея алгоритма заключается в том, что в файле сохраняется разница – число между средними значениями соседних блоков в изображении, которая обычно принимает значения, близкие к 0. К достоинствам этого алгоритма можно отнести то, что он очень легко позволяет реализовать возможность постепенного “проявления” изображения при передаче его по сети.

^ 21. Растровое представление окружности: постановка задачи, простой алгоритм, алгоритм Брезенхейма.
Из геометрии мы знаем, что окружность с центром в точке (xc,yc) и радиусом r, задается параметрически с помощью системы уравнений:



Отсюда не сложно получить алгоритм генерации окружности:

  1. Полагаем А=0.

  2. Если А больше либо равно 2, то окружность отрисована.

  3. Вычислим x=Trunc(xc+r*cos(A)), y=Trunc(yc+r*sin(A))

  4. Screen[x,y]=Color

  5. Увеличим A на d и перейдем к шагу 2.

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

Если точка (x,y) лежит на окружности с центром в точке (0,0), то и точка (x,-y), так же лежит на этой окружности. Последнее утверждение можно развить, а именно: если точка (x,y) лежит на окружности с центром в точке (0,0), то и точки (x,-y);(-x,-y);(-x,y);(y,x),(y,-x);(-y,-x);(-y,x), так же лежат на этой окружности. Координата x увеличивается на единицу на каждом шаге. Так же координата y либо уменьшается на единицу, либо остается без изменений. Нужно выбрать, куда переходить из точки (xi,yi) либо в точку (xi+1,yi), либо в точку (xi+1,yi-1). Для того, чтобы осуществить выбор рассмотрим две невязки:

di1=(xi+1)2+yi2-r2

di2=(xi+1)2+(yi-1)2-r2

А так же будем следить за их суммой:

di=di1+di2

Рассмотрим несколько вариантов расположения "вещественной" окружности относительно "целых" точек:

Случай 1. di1 < 0, di2 < 0, и следовательно di < 0.
Случай 2. di1= 0, di2 < 0, и следовательно di < 0.
Случай 3. di1 > 0, di2 < 0, и следовательно имеем два варианта для di:
Случай 3.1. |di1| < |di2| и следовательно di < 0.
Случай 3.2. |di1| > |di2| и следовательно di > 0.
Случай 4. di1 > 0, di2=0, и следовательно di > 0:
Случай 5. di1 > 0, di2 > 0, и следовательно di > 0:

В случае, если di < 0 надо активировать точку (xi+1,yi), а в случае, если di > 0 надо активировать точку (xi+1,yi-1). di=di1+di2=(xi+1)2+yi2-r2+(xi+1)2+(yi-1)2-r2=2xi2+2yi2+4xi-2yi+3-2r2

Теперь получим выражение di+1 через di .

di+1=2xi+12+2yi+12+4xi+1-2yi+1+3-2r2=di+4(xi-yi)+10

Осталось получить значение d1 в начальной точке (x1=0,y1=r):

d1=3-2r

Если x > y, то выходим.

1. Screen[x+xc,y+yc]:=Color;

2. Screen[x+xc,-y+yc]:=Color;

3. Screen[-x+xc,y+yc]:=Color;

4. Screen[-x+xc,-y+yc]:=Color;

5. Screen[y+xc,x+yc]:=Color;

6. Screen[y+xc,-x+yc]:=Color;

7. Screen[-y+xc,x+yc]:=Color;

8. Screen[-y+xc,-x+yc]:=Color;

Если d < 0, то d:=d+4*x+6, переходим на Шаг 13

d:=d+4(x-y)+10; y:=y-1;

Билет 11
^ 10. Геометрическое моделирование и решаемые им задачи…
Модель – это представление некоторых, необязательно всех, свойств объекта, либо конкретно существующего, либо абстрактного, его особенностей.

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

1. Физическое подобие означает, что изображение по основным физическим характеристикам повторяет оригинал. Подобие считается физически полным, если характеристики оригинала и изображения полностью подобны или строго пропорциональны.

2. Психофизическое (физиологическое) – соответствие на уровне зрительных ощущений, например фотореалистичная графика.

3. Психологическое – предполагает лишь некоторую схожесть между объектом и изображением: чертежи, проволочные модели и т.п

геометрические модели – это модели состоящие из след компонентов:

- пространственное расположение и форма – геометрия объекта; некоторые атрибуты: цвет, текстура;

- топология (связность с другим объектом).

^ Способы представления объектов:

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

^ Координатные модели – это наборы точек, принадлежащих объектам, которые задаются координатами.

У координатных моделей могут быть разновидности:

- координатно-разностные модели, где вместо координат их разности;

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

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

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

Декартова система координат – основа численного моделирования объектов.

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

В задании объекта могут также участвовать логические параметры. Эти параметры не влияют на параметрические числа объектов и можно ограничиться числами 0 и 1 или же установить параметр по знаку числа. Так же очень важно задавать направление вычерчивания, которое необходимо для определения видимости сторон. Для этого используют касательные векторы, или векторы направления.
^ 22. Алгоритм закраски области, заданной цветом границы.
Рассмотрим область, ограниченную набором пикселей заданного цвета, и точку (x, у), лежащую внутри этой области, называемую затравкой.

Задача заполнения области заданным цветом в случае, когда область не является выпуклой, может оказаться довольно сложной.

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

1. Поместим затравочную точку на стек.

2. Извлекаем координаты точки с вершины стека в переменные (x, y).

3. Заполняем максимально возможный интервал, в котором находится точка, вправо и влево вплоть до достижения граничных точек.

4. Запоминаем крайнюю левую xl и крайнюю правую xr абсциссы заполненного интервала.

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

6. Если стек не пуст, то переходим к пункту 3.

Этот алгоритм эффективно работает даже для областей с дырками.

Билет 12



^ 11. Представление геометрических моделей. Полигональные сетки и способы …
Наиболее распространённые представления графических объектов:

1. Пространственное подразбиение.

Если в трёхмерном пространстве есть тело, то это пространство можно разбить на кубики (воксели). Для каждого кубика b(i, j, k) можно указать, пересекается ли он с телом, то есть лежит ли он внутри, на границе – 1 или вне тела – 0. В некоторых случаях удобно применять некоторые промежуточные значения, задавая тем самым плотность в данной точке пространства.

Характеристики воксельного представления:

• Только приближение реального объекта. Поверхности, не параллельные осям координат, представляются приблизительно. Качество приближения зависит от относительного размера вокселей.

• Требует больших размеров памяти для хранения, и эти требования резко возрастают при увеличении разрешения (растет как куб от разрешения).

• С таким представлением хорошо работают в основном пространственные алгоритмы, такие как вычисление объема объекта, нахождение центра масс и т.д.

• Можно проводить набор операций: пересечение, объединение, вычитание. 2. Граничное (поверхностное). Тела задаются ограниченными фрагментами поверхностей.

3. Конструктивное.

При конструктивном представлении вводятся примитивы тел. Конструируя эти объекты и применяя теоретико-множественные операции, можно получить более сложное тело.

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

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

  1   2   3   4   5



Скачать файл (207.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации