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

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

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


Воинов С.Б.

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

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

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