Category: компьютеры

Category was added automatically. Read all entries about "компьютеры".

Диссертация, введение.

Компьютерная графика как инструмент моделирования и визуализации научных данных появилась относительно недавно (начиная примерно с середины 60-х годов 20 века). Ее развитие было в первую очередь тесно связано с потребностью в наглядном представлении математических моделей и обуславливалось ростом мощностей электронных вычислительных машин. Однако последние два десятка лет в компьютерной графике бурно развивается отрасль игровой индустрии и симуляции. Современная компьютерная графика обладает огромным набором возможностей по визуализации фотореалистичных изображений не только в отложенных заданиях, но и в режиме реального времени. Последнее особенно важно для компьютерных игр, симуляторов и различного рода систем с интерактивной анимацией. Развитие компьютерной графики как прикладной науки внесло вклад не только в научный фонд различных алгоритмов и математических моделей, но и способствовало развитию таких технологий, как изготовление микропроцессоров для персональных компьютеров, разработка новых моделей графических ускорителей и систем виртуальной реальности. Не смотря на свой прикладной характер, компьютерная графика опирается на множество других прикладных и фундаментальных наук, таких как дискретная математика, цифровая обработка сигналов, физика, теория цепей и т.д.

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

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

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

Для того чтобы показать цели и структуру данной диссертационной работы, рассмотрим класс задач, связанных с цифровой обработкой сигналов (ЦОС) и компьютерной графикой (КГ).

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

Так же как и КГ, ЦОС зародилась относительно недавно – в середине 60-х начале 70-х годов 20 века. Выделение ЦОС в отдельную отрасль науки было связано прежде в сего с появлением цифровых компьютеров. ЦОС тесно связана со следующими науками:

  • аналоговая электроника;
  • цифровая электроника;
  • теория принятия решений;
  • аналоговая обработка сигналов;
  • теория вероятностей и математическая статистика;
  • теория чисел;
  • теория систем.

 

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

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

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

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

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

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

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

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

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

Рис. 1. Структура системы, использующей алгоритмы компьютерной графики.

 

            Рассмотрим функции каждой подсистемы.

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

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

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

            Подсистема обработки является центральной в информационной системе, использующей технологии и алгоритмы КГ. В этой подсистеме происходят различные преобразования объектов растровой или векторной графики по заданным параметрам для получения необходимого результата работы всей системы. Фактически, построение модели в случае использования данной системы в качестве инструмента моделирования осуществляется именно в подсистеме обработки. Для растровой графики данная подсистема осуществляет различные преобразования изображения, для векторной – преобразования геометрических примитивов. Результатом работы подсистемы обработки является преобразованное представление информации, полученной от подсистемы хранения или генерации. Результат обработки может быть сохранен в подсистеме хранения и использован в дальнейшем. Это показано обратной связью на рисунке. Также результат обработки может быть передан в подсистему отображения.

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

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

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

Рис. 2. Связь системы векторной и растровой графики.

 

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

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


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

 

Рассмотрим некоторые особенности представленной структуры.

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

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

ЦОС может быть использована в следующих подсистемах:

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

 

Этапы, которые проходит графическая информация при обработке на описанной информационной ситеме следующие:

  1. формирование информации или ее выборка из подсистемы хранения;
  2. предварительная обработка векторной графики;
  3. растеризация;
  4. постобработка для растровой графики.

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

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

  1. Моделирование трехмерных изображений.
  2. Генерация реалистичных ландшафтов.
  3. Генерация эффектов (облака, дым и т.д.).
  4. Процедурная генерация текстур.
  5. Обработка растровых изображений.
  6. Алгоритмы сжатия изображений и объектов векторной графики.

 

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

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

Новая классификация алгоритмов компьютерной графики


Воинов С.Б.

Научный руководитель: проф. Авдошин С.М.

«МАТИ» – Российский Государственный Технологический Университет
им. К. Э. Циолковского,

121552, Москва, Оршанская 3, e-mail: svoinov@forte-it.ru

 

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

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

            Используемые признаки классификации:

1.      по сложности:

1.1.  низкоуровневые – предназначенные для реализации графических примитивов;

1.2. высокоуровневые – алгоритмы удаления невидимых линий и поверхностей, алгоритмы оптимизации.

2.      по реализации:

2.1. реализуемые программно;

2.2. реализуемые аппаратно.

3.      по функциональному назначению:

3.1. алгоритмы рисования геометрических примитивов;

3.2. алгоритмы заливки граней;

3.3. алгоритмы удаления невидимых линий и поверхностей;

3.4. алгоритмы оптимизации;

3.5. алгоритмы текстурирования;

3.6. алгоритмы обработки вершин и пикселей выводимых треугольников (так называемые шейдеры – shaders);

3.7. алгоритмы трассировки лучей;

3.8. алгоритмы физического моделирования.

4.      по используемому математическому аппарату:

4.1. алгоритмы, использующие аппарат линейной алгебры;

4.2. алгоритмы, использующие нелинейные уравнения;

4.3. алгоритмы, использующие дифференциальное и интегральное исчисление;

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

4.5. эвристические алгоритмы.

5.      по асимптотической временной оценке сложности:

5.1. линейные, с оценкой O(n);

5.2. логарифмические, с оценкой O(n log n);

5.3. с оценкой хуже логарифмической – O(n2) и т.д.

6.      по поддержке современными графическими интерфейсами программирования:

6.1. поддерживаемые современными графическими API (GDI+, OpenGL, Direct3D, Cg);

6.2. неподдерживаемые современными графическими API.

7.      по области применения:

7.1. обработка плоских изображений;

7.2. построение реалистичных изображений;

7.3. геоинформационные системы (GIS);

7.4. системы компьютерного видения (computer vision);

7.5. физическое моделирование.

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


Разработка программных эмуляторов процессоров семейства Intel x86


С. Б. Воинов

«МАТИ» - Российский Государственный Технологический Университет

им. К. Э. Циолковского, Россия.

 

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

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

·        Детальное изучение системы команд процессоров семейства Intel x86 и особенностей её применения.

·        Изучение неоднозначности системы команд.

·        Знакомство с защищённым режимом работы процессора 80386 без дополнительных неудобств, связанных с необходимостью создания соответствующего программного окружения.

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

·        Снятие программных защит информации.

·        Исследования в области вирусологии без опасности повредить программно-аппаратные средства PC.

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

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

1.            Программная совместимость, т. е. насколько полностью эмулятором поддерживается система команд эмулируемого процессора. К программной совместимости можно также отнести особенности выполнения команд эмулятором и процессором. Например, процессор Intel 8086 выполняет с префиксом повторения только цепочечные команды (MOVS, LODS, STOS, CMPS, SCAS). Другие команды, например REP MOV AX, CX выполняются только один раз, в независимости от используемого префикса повторения.

2.            Быстродействие по сравнению с эмулируемым процессором. Как правило, по скорости выполнения различных операций процессор превосходит эмулятор. Однако это в большинстве случаев справедливо, когда эмулируемый процессор и процессор, для которого написан эмулятор, имеют быстродействие одного порядка. С учётом вычислительной мощности современных процессоров семейства Intel x86 (скажем, Pentium III, Pentium 4) эмуляция функций процессора Intel 8086 будет выполняться не только с такой же скоростью, как и у самого 8086, но даже быстрее. Быстродействие конкретного эмулятора зависит не только от аппаратной конфигурации компьютера, на котором он выполняется, но и во многом от того, как он написан.

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

4.            Поддержка устройств хранения информации. В большинстве случаев работа с эмулятором сопровождается загрузкой в память различных программ. Не смотря на то, что программы могут быть загружены в память эмулятора «вручную» (через пользовательский интерфейс эмулятора), они могут функционировать неверно из-за отсутствия операционной системы, применяемой совместно с эмулируемым процессором. Можно, конечно, эмулировать функции операционной системы (например, для DOS можно эмулировать функции прерывания INT 21H), но подобная задача значительно осложняет разработку эмулятора, и основное время фактически уходит на написание операционной системы. Для преодоления этой сложности можно написать эмулятор функций для работы с жёстким или гибким дисками (например, для IBM PC можно написать эмулятор прерывания BIOS INT 13H для работы с дисками на низком уровне). После написания такого рода эмулятора можно создать образ диска с уже установленной операционной системой и производить начальную загрузку эмулятора с этого диска.

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