автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Совершенствование алгоритмов графического вывода для карт SVGA

v-Ha правах рукописи

МИТИН Владислав Анатольевич

СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ГРАФИЧЕСКОГО ВЫВОДА ДЛЯ КАРТ SVGA

05.13.13 - вычислительные машины, комплексы, системы и сети

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 1998

Работа выполнена в Московском Государственном Институте Радиотехники Электроники и Автоматики (Техническом Университете).

Научный руководитель - доктор технических наук, профессор

Левин Н.А.

Официальные оппоненты: доктор технических наук, профессор

Ильин В.Д.

кандидат технических наук, доцент Руденко Ю.М.

Ведущая организация - Институт Электронных Управляющих

Машин (ИНЭУМ)

Защита состоится "16" декабря 1998г. в_ч._м. на заседании диссертационного совета Д 003.56.01 при Институте Проблем Информатики Российской Академии Наук (ИПИРАН) по адресу:

117900, Москва, ул.Вавилова, 30/6.

С диссертацией можно ознакомиться в библиотеке Института Проблем Информатики Российской Академии Наук.

Автореферат разослан " 3 " ЬОЛкуЛк/ 1998г.

Ученый секретарь диссертационного совета

доктор технических наук, профессор ^ —7 С.Н.Гринченко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

2. Исследование влияния привязки программных алгоритмов к специфике центрального процессора и системы ввода/вывода на скорость графического вывода. В частности:

a) влияние общей алгоритмической оптимизации с целью использования новых команд старших моделей процессоров на производительность алгоритмов графического вывода;

b) влияние используемой разрядности регистров процессора и портов ввода/вывода на производительность алгоритмов графического вывода;

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

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

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

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

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

7. Разработка конкретных методов оптимизации алгоритмов графического вывода по какому-либо из исследованных направлений.

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

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

Научная новизна.

1. Проанализированы графические системы двух основных видов - GKS и GUI, различные типы графической информации, принципы иерархического образования высокоуровневых графических объектов из низкоуровневых в GKS-системах, и высокоуровневых графических примитивов из низкоуровневых в GUI-системах. Составлены соответствующие классификации проиллюстрированные примерами объектов.

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

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

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

5. Произведена оптимизация универсального алгоритма прямой линии. Расчеты с помощью построенной модели показали, что в некоторых случаях удалось достичь 150%-го прироста производительности алгоритма (то есть в 2.5 раза). Полученный код на языке ассемблера представлен в приложениях к диссертации.

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

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

Практическая ценность. С помощью идей и материалов, лежащих в основе данной диссертации, в 1993 году автором была реализована графическая библиотека У1<1ео8ирроП. К моменту защиты диссертации данная библиотека в переработанном виде внедрена на четырех предприятиях города Москвы. Об этом свидетельствуют акты о внедрении, представленные в приложении к диссертации.

С помощью библиотеки УУеоБирроП в 1993 году в МКБ "ЭКАбанк" специалистами отдела сетей и отдела прикладного программного обеспечения были разработаны следующие программные продукты с графическим интерфейсом пользователя:

1. Инструментальное средство "УБОЕсШ", предназначенное для создания и редактирования специализированных графических объектов;

2. Программа статистической обработки информации о движении средств по лицевым и балансовым счетам банка;

3. Универсальная программа расчета начисления процентов по различным типам процентных ставок.

В течение 1994-1995 годов, была разработана вторая версия библиотеки \Ч<Зео5ирро11, учитывающая появившиеся новые аппаратные средства и другие аспекты, влияющие на производительность алгоритмов графического вывода.

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

1. Программное обеспечение аппаратно-программного комплекса "Cash-Desk", предназначенного для автоматизации рабочего места кассира торгового зала магазина;

2. Программа "Счета и главная бухгалтерская книга", предназначенная для

автоматизации работы бухгалтерии предприятия;

3. Информационная система "Shops".

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

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

Тогда же в "НИИ Экономики авиационной промышленности" его сотрудниками с помощью переработанной версии библиотеки VideoSupport были разработаны следующие программные продукты с графическим интерфейсом пользователя:

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

2. Автоматизированная система прогноза и анализа финансового состояния института.

В общем случае, результаты диссертации могут быть применены при по-

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

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

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

Апробация результатов работы. Работа докладывалась на семинарах кафедры №242 МГИРЭА и лаборатории №15 ИПИРАН и получила положительную оценку. Апробация работы произведена в процессе внедрения ее результатов, в частности - библиотеки графических функций VideoSupport, в организациях МКБ ЭКАбанк, московском универмаге "Вешняки", в универсаме "Вешняковский" и НИИ Экономики авиационной промышленности. Акты о внедрении приложены к диссертации.

Публикации. По материалам диссертации опубликовано пять статей в различных научно-технических журналах и сборниках статей, и издано одно учебное пособие МГИРЭА (80 стр.).

Результаты, выносимые на защиту.

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

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

3. Усовершенствованные для различных процессоров семейства х86 реализации универсального алгоритма отображения прямой линии.

Структура и объем работы. Диссертация состоит из введения, шести глав, основных результатов, выводов и шести приложений. В приложения входят: справочные таблицы, листинги программ, список сокращений и условных обозначений, список публикаций из 6-и наименований, 4 акта о внедрении, список использованной литературы из 60-и наименований.

Общий объем работы составляет 207 страниц, в них присутствуют 125 страницы текста, 176 иллюстраций (86 схем, диаграмм и рисунков, и 90 фрагментов листингов), 112 таблиц, 7 листингов программ.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава - "АЛГОРИТМЫ ВЫВОДА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ".

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

В классификации графических систем показано что они делятся на два больших класса: Системы с графическим интерфейсом пользователя (GUI -

Graphics User Interface) и Системы с графическим ядром (GKS - Graphics Kernel Systems). Здесь же дается деление классов на группы и подгруппы.

В классификации типов графической информации показано деление "на

векторное и матричное представление, динамические и статические формы информации, а также деление векторных форм информации в зависимости от передаваемого ими количества измерений и типов объектов. Особенно выделен класс GUI-элементов.

В классификации графических объектов и примитивов показаны пути образования высокоуровневых графических объектов из низкоуровневых объектов для GKS-систем, или низкоуровневых примитивов для GUI-систем.

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

Особенно стоит подчеркнуть обоснование выбора прямой линии в качестве основного строительного элемента векторных изображений. Рассматриваются типичные случаи для GUI- и GKS-систем. Все дальнейшие вопросы ускорения графического вывода рассматриваются применительно к прямой

линии.

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

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

Далее, подробно разбирается один из самых эффективных алгоритмов отображения прямой линии - базовый алгоритм прямой Брезенхэма (Bresenham), способный эффективно отображать прямые линии малого наклона (0"— 45') используя только целочисленные операций сложения и умножения. Приводится подробный вывод математических уравнений, положенных в его основу.

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

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

ного алгоритма Брезенхэма. Приводится упрощенная блок-схема алгоритмов этого класса.

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

1. Привязка программных алгоритмов к специфике центрального процессора и системы ввода/вывода.

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

3. Разделение множества алгоритмов вывода на уровни по степени их универсальности.

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

В первом из указанных направлений подробно рассмотрены три метода достижения ускорения:

1. Общая оптимизация алгоритмов на уровне команд.

2. Оптимизация набора команд взаимодействия с видеопамятью.

3. Использование полной разрядности регистров процессора и портов ввода/вывода.

Вторая глава - "ИССЛЕДОВАНИЕ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ". В ней подробно анализируется классическая реализация универсального алгоритма отображения прямой линии, блок-схема которого представлена на Рис. 1. Данный анализ проводится с целью построения математической модели для расчета времени исполнения этого алгоритма и его отдельных частей.

Глава содержит семь частей - по числу блоков на блок-схеме. В каждом из пунктов разбирается свой блок алгоритма. рис / Блок-схема универсального ал-

горитма'втображения прямой линии.

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

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

2. Блок предустановок занимается вычислениями начальных и конечных координат, размеров выводимого объекта, адреса начала отображения в видеобуфере, и другими вычислениями, на основании которых он принимает решение о том, каким именно из перечисленных ниже блоков отображать линию. Время выполнения блока предустановок зависит только от направления прямой, и не зависит от ее длины. Он работает при всех углах наклона прямой от 0° до 360°.

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

4. Блок горизонтальных линий занимается отображением горизонтальных линий. Кроме того он содержит свой внутренний блок предустановок, необходимый для подготовки параметров основного цикла отображения. Время выполнения этого блока не зависит от направления прямой, так как все необходимые приготовления, в связи с особенностями реализации алгоритма, были выполнены в блоке предустановок. Блок горизонтальных линий отображает линии длиной от 2 пикселей и больше, так как единственно возможная линия длиной в 1 Рис. 2. Разбиение угловой плоскости на пиксель отображается бло- сектора.

ком вертикальных линий.

Н - Horizontal LS - Low Slope CN - Coordinates Nonvuli/jiion V - Vertical HS - High Slope PN - Parameters Normalization

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

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

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

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

Третья глава - "ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ". В ней математический аппарат подсчета времени исполнения разных блоков алгоритма, описанный в предыдущей главе превращается в некую единую модель из 20-и уравнений. Каждое из этих уравнений позволяет подсчитать время отображения прямой линии произвольной длины при попадании ее в определенный диапазон углов наклона.

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

где / - время исполнения блока предустановок; время исполнения одного из блоков отображения; время исполнения блока завершения.

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

Например, линия длиной в один пиксель может быть только одна (Рис. 3, а), и она отображается именно блоком вертикальных линий, а не каким-либо другим. Линий длиной в два пикселя может быта целых восемь (Рис. 3, Ь) и они отображаются уже различными блоками. Однако, здесь еще не участвует

блок линий большого наклона, так как все линии с углом соответствующим 45° во всех квадрантах (см. Рис. 2) относятся к линиям малого наклона (ЬБ). Линии большого наклона (НБ) вступают в действие только для линий в три и более пикселя (Рис. 3, с, </).

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

Вот как выглядит в общем виде описываемая модель для расчета времени исполнения универсального алгоритма отображения прямой линии (для расшифровки обозначений см. Рис. 2):

1з'н + 111Н + '«

и М <*-0-) + /

/Л' С15 К

, (<Р=45°) — , л. , (<Р"*5°) . *

I, = г , + /, (^450) + и

'Н5 З'НЭ ¿'ИЗ К

-90») _

'да

'.ч'нз + V,

(р->90°)

7«

+ 1я

tLuv+tR

(„_90") _ , (,,-90°) , ,

, ((0-45°) , 45") , ,

(р=45°) _ , (р=45°) I .

4.5 -У'Ш+УШ , (д>->а°) _ , (<»-0°) ,

Ч5 - + V'« +

Ч/

+

, (^45°) , ((.»=45») ,

^ - + + /я

, (у—>45°) _ . , (р »45") . *

■+90°) _

Я5

ЯЯ

, (я>—»45°) _ , , , (<¡>—45°) ■ ,

Чу

, (¥>=45°) _ , , , ((

=45°)

а)

ЬЭ V

Н

Н'

-1---

: ь)

13 НЭ ' V '¡Э

N /

н

ЦЭ,-

\

1.5 НБ V НЭ

.....Л Л - А Ч---,

<о » Ь- к к ■

и л сл сл \/ . сл сл___с5

х х у х X

н

ш.

ппп

ячгл

ЕЕИКШВ9

ШК83

тт ши

-Т

4- г. [Л (У)

I I

IV Л---

____сл_сл______

I X

Рис. 3. Линии малой длины.

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

для случая с линиями малой длины, так и большой. Также производится расчет всех коэффициентов уравнений для каждого из пяти процессоров семейства х86 - 8086, 80286, 80386, 80486 и Pentium.

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

Четвертая глава - "ПРОГРАММНЫЕ МЕТОДЫ УВЕЛИЧЕНИЯ СКОРОСТИ ГРАФИЧЕСКОГО ВЫВОДА". В этой главе подробно разбираются программные методы увеличения скорости графического вывода, привязки алгоритмов к специфике центрального процессора и системы ввода/вывода.

1. Оптимизация алгоритмов на уровне команд.

С развитием семейства микропроцессоров х86 в более современных моделях команды стали выполняться за меньшее количество тактов. Однако, архитектурные особенности новых моделей как бы "изменили баланс" команд. Некоторые команды, выполнявшиеся медленнее других, стали выполняться быстрее. Это обстоятельство следует учитывать при перенесении алгоритмов на новые процессоры.

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

С учетом вышесказанного рассмотрены следующие команды и последовательности команд:

• Инструкция LOOP и последовательности инструкций DEC и JNZ.

• Последовательность инструкций SHR г, 1 и инструкция SHR г, п.

• Инструкции MUL и IMUL.

• Вызов подпрограмм - инструкции CALL, RET и подстановка кода.

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

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

1. Команды, выполняющие только операцию чтения.

2. Команды, выполняющие только операцию записи.

3. Команды, выполняющие последовательно операцию чтения, а затем операцию записи.

На первый взгляд кажется очевидным, что, при реализации каких-либо алгоритмов вывода на экран, команды первого типа следует использовать, ~ когда необходимо считать данные из видеопамяти в регистр центрального процессора или (и) обновить содержимое регистров-защелок (Latches). Команды второго типа следует применять, когда необходимо записать содержимое регистров-защелок (возможно скомбинировав его с содержимым регистра центрального процессора) в видеопамять. А команды третьего типа следует применять тогда, когда необходимо сделать последовательно обе эти операции.

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

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

Более подробно разбирается инструкция STOSB, являющаяся типичным представителем поточных команд, которые можно употреблять для работы с видеопамятью. Для нее показывается два возможных случая применения. По результатам анализа, в первом из них (когда STOSB используется как команда в потоке) для процессоров 8086, 80286 и ВОЗ 86 преобразование этой инструкции не целесообразно, однако, для процессоров 80486 и Pentium оно приводит к уменьшению времени исполнения на 3 и 1 такт соответственно; для второго же случая (когда STOSB используется как одиночная команда), для процессоров 8086, 80386, 80486 и Pentium замена приводит к уменьшению времени исполнения на 3,1,4 и 2 такта соответственно.

3. Использование регистров.

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

Таб. 1. Наиболее быстрые полные операции обновления байта видеопамяти.

Процессор Инструкции Колич. тактов

8086 AND М—R 16

OR М«—R 16

XOR М<—R 16

80286 AND М<—R 7

OR М—R 7

XOR М«—R 7

80386 MOV R«—М + MOV М—R 4+2=6

OR М—R 6

XOR М—R 6

80486 MOV R«—М + MOV М—R 1+1=2

Pentium MOV R—М + MOV М—R 1+1=2

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

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

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

Вот, например, какой выигрыш в производительности дает отыскание "лишнего" регистра для выполнения операции ADD г, г вместо ADD г, т:

Instructions Clock Cycles

8086 80286 ! 80386 80486 Pentium

ADD r.m 9 7 1 6 2 2

ADD г,г 3 1 2 1 2 1 1

Выигрыш 6 5 1 4 1 1

Таким образом, для процессоров 8086, 80286, 80386, 80486 и Pentium подобная замена приводит к уменьшению времени исполнения на 6, 5, 4, 1 и 1 такт соответственно.

Пятая глава - "РЕАЛИЗАЦИЯ УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ". В этой главе произведена оптимизация универсального алгоритма отображения прямой линии любого наклона методами, описанными в четвертой главе. Целью оптимизации является минимизация времени исполнения алгоритма для каждого из рассматриваемых процессоров семейства х86 - 8086, 80286, 80386, 80486 и РепПиш.

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

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

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

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

В конце каждого из пунктов приводится исходный текст соответствующего ему оптимизированного по времени исполнения блока алгоритма (см. Рис. 1. Блок-схема универсального алгоритма отображения прямой линии.).

Шестая глава - "ОЦЕНКА РОСТА ПРОИЗВОДИТЕЛЬНОСТИ УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ". В этой главе анализируется насколько возросла эффективность обсуждаемых алгоритмов по скорости в результате проведенной оптимизации.

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

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

= = -, -Ь-— х 100%

Абсолютный выигрыш по времени (1шпЛ) представляется либо константой, либо линейным уравнением. Это является следствием того, удалось ли оптимизировать основной цикл вывода того или иного блока отображения. Если удалось, то полученный абсолютный выигрыш увеличивается с выводом каждого нового пикселя, и следовательно, линейно зависит от длины отображаемой линии. Если же удалось оптимизировать только ту часть, которая занимается различного рода предустановками и не участвует в цикле вывода, то абсолютный выигрыш представляется константой и не зависит от длины линии, так как все предустановки делаются один раз перед отображением.

Таким образом, получаем два вида выражений, описывающих прирост производительности (лР) соответственно для случая с нарастающим и независимым абсолютным выигрышем по времени (А,.,„л):

Ктл 1+^1 ("-4) .„_'

др _ _ —!-IX-АР =

тпА _ а\

К» а2+Ь2(п-4)' а2 + Ь2 (п - 4)

где а/ и а2 - константы, связанные со временем предустановок, а Ъ1 и Ь2 -коэффициенты, связанные со временем циклов отображения.

Первое выражение представляет собой общий вид зависимости. При допустимых в нашем случае значениях параметра 0 < («-4) < °о, ее графическое представление имеет вид отрезка гиперболы с начальной точкой, опреде-а,

ляемои отношением

а,

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

Ь,

отношением

, так как

Нш

я, + (п - 4) _ 6,

а2+Ь2(п- 4) Ъ2

Эта зависимость монотон-

а\ ^ \

но возрастает, если —- < —- рис ^ ¡¡ид

а. ъ

^ 1 не. т. ииО зависимостей прироста произво-

*г 2 дительности от длины прямой. (Рис. 4, а), и монотонно убы-

и Ь

вает, если —!- > —!- (Рис. 4, Ь). Выражение для независимого абсолютного а2 Ь2

выигрыша ((мтА) представляет собой частный случай выражения для нарас-

■ 0. При этом — = 0, и график мо-Ъ,

тающего выигрыша с коэффициентом Ь2

нотонно убывает к асимптоте равной нулю (Рис. 4, Ь).

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

По показанным на Рис. 5 зависимостям прироста производительности для процессора Репйит видно, что только для горизонтальных линий не удалось добиться прироста производительности увеличивающегося с ростом длины линии, но и тут есть выигрыш на малых длинах. В остальных же случаях, увеличение производительности достигает 75%, 85%, 100%, 115%, 150%. То есть от 1.75 до 2.5 раз по сравнению с классическим алгоритмом.

и

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Проанализированы графические системы основных двух видов - GKS и GUI, различные типы графической информации, принципы иерархического образования высокоуровневых графических объектов из низкоуровневых в GKS-системах, и высокоуровневых графических примитивов из низкоуровневых в GUI-системах. Разработаны соответствующие классификации:

a) классификация графических систем;

b) классификация типов графической информации;

c) классификация графических объектов (для GKS-систем);

d) классификация графических примитивов (для GUI-систем).

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

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

a) привязка программных алгоритмов к специфике центрального процессора и системы ввода/вывода;

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

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

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

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

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

a) общеалгоритмическая оптимизация на уровне команд;

b) оптимизация набора команд для взаимодействия с видеопамятью;

c) использование полной разрядности регистров процессора и портов ввода/вывода.

6. На основании предложенных методов ускорения графического вывода, разработана реализация универсального алгоритма вывода прямой линии, позволяющая существенно повысить скорость графического вывода. Для процессоров Pentium из семейства Intel х86 величина этого ускорения достигает 2.5 раз.

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

8. Установлены количественные зависимости ускорения вывода достигаемого благодаря программной оптимизации для различных процессоров семейства Intel х86.

ВЫВОДЫ

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

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

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

a) использования в программных алгоритмах графического вывода имеющихся аппаратных возможностей повышения производительности;

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

c) перенесение некоторых общих задач с уровня прикладного программирования на уровень системных библиотек.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Митин В.А. Эргономические характеристики графических карт SVGA // Computer News. - 1995. -№1. - с.28,37,39

2. Митин В.А. Организация графических карт SVGA // Computer News. -1996. - №2. - с. 101-111

3. Левин H.A., Митин В.А. Принципы организации вывода графической информации в системах мультимедиа /У Системы и средства информатики. - М. - Наука - 1996. - Вып.8. - ISSN 0869-6527 - с.200-223

4. Митин В.А., Левин H.A. Современные аппаратные средства акселерации мультимедиа // Информационные технологии. - 1996. - № 5. - с.29-34

5. Митин В.А., Левин H.A. Современные программные методы акселерации мультимедиа // Информационные технологии. - 1997. - № 3. - с.26-33

6. Митин В.А. Системное программное обеспечение - Архитектура графических карт: Учебное пособие / Препринт МГИРЭА. - М., 1998. - 80с. -ISBN 5-7339-0131-4

Московский Государственный Институт Радиотехники Электроники и Автоматики

(Технический Университет)

/ V ? / ; ; • /

I

/ J

I

На правах рукописи

МИТИН Владислав Анатольевич

СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ГРАФИЧЕСКОГО ВЫВОДА ДЛЯ КАРТ SVGA

05.13.13 - Вычислительные машины, комплексы, системы и сети

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук, профессор Левин Н.А.

Москва - 1998

ОГЛАВЛЕНИЕ

ОГЛАВЛЕНИЕ.................................................................................................................................2

ВВЕДЕНИЕ........................................................................................................................................4

ГЛАВА 1. АЛГОРИТМЫ ВЫВОДА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ...........................6

1.1 Классификация графических систем, информации, объектов и примитивов..................6

1.1.1 Графические системы.......................................................................................................7

1.1.2 Графическая информация.................................................................................................8

1.1.3 Графические объекты и примитивы................................................................................9

1.1.4 Обоснование выбора прямой линии в качестве основного строительного элемента векторных изображений.................................................................................................13

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

1.2.1 Алгебраические алгоритмы отображения прямых линий...........................................16

1.2.2 Алгоритм прямой Брезенхэма (Bresenham)..................................................................17

1.2.3 Преобразование алгебраического алгоритма прямой в модифицированный алгоритм Брезенхэма.......................................................................................................19

1.2.4 Универсальные алгоритмы отображения прямых.......................................................23

1.3 Исследуемые направления ускорения графического вывода и задачи диссертации.....24

1.3.1 Привязка программных алгоритмов к специфике центрального процессора и системы ввода/вывода.....................................................................................................24

1.3.1.1 Общая оптимизация алгоритмов на уровне команд..............................................24

1.3.1.2 Оптимизация набора команд взаимодействия с видеопамятью..........................25

1.3.1.3 Использование полной разрядности регистров процессора и портов ввода/вывода..............................................................................................................26

1.3.2 Использование аппаратных возможностей повышения производительности, реализованных в графической карте.............................................................................27

1.3.2.1 Функции GUI Accelerator.........................................................................................27

1.3.2.2 Функции Graphics Co-Processor...............................................................................28

1.3.2.3 Функции Zoom Window...........................................................................................28

1.3.3 Разделение множества алгоритмов вывода на уровни по степени их универсальности..............................................................................................................29

1.3.4 Перенесение реализации некоторых задач с уровня прикладного программирования на уровень системных библиотек.................................................33

ГЛАВА 2. ИССЛЕДОВАНИЕ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ

УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ..................................34

2.1 Блок расчета адреса в видеобуфере.....................................................................................34

2.2 Блок предустановок..............................................................................................................35

2.3 Блок вертикальных линий....................................................................................................44

2.4 Блок горизонтальных линий................................................................................................48

2.5 Блок линий малого наклона.................................................................................................51

2.6 Блок линий большого наклона............................................................................................57

2.7 Блок завершения функции...................................................................................................62

ГЛАВА 3. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ

УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ..................................63

3.1 Общий подход.......................................................................................................................63

3.2 Линии малой длины..............................................................................................................63

3.3 Линии большой длины.........................................................................................................67

ГЛАВА 4. ПРОГРАММНЫЕ МЕТОДЫ УВЕЛИЧЕНИЯ СКОРОСТИ

ГРАФИЧЕСКОГО ВЫВОДА....................................................................................77

4.1 Общая оптимизация алгоритмов на уровне команд..........................................................77

4.1.1 Инструкция LOOP...........................................................................................................77

4.1.2 Последовательность инструкций SHR..........................................................................78

4.1.3 Инструкции MUL и IMUL..............................................................................................79

4.1.4 Вызов подпрограмм - инструкции CALL,RET............................................................82

4.2 Оптимизация набора команд взаимодействия с видеопамятью.......................................83

4.2.1 Инструкция STOSB.........................................................................................................84

4.3 Использование регистров.....................................................................................................85

ГЛАВА 5. РЕАЛИЗАЦИЯ УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ.....................86

5.1 Блок расчета адреса в видеобуфере.....................................................................................86

5.2 Блок предустановок..............................................................................................................89

5.3 Блок вертикальных линий....................................................................................................99

5.4 Блок горизонтальных линий..............................................................................................108

5.5 Блок линий малого наклона...............................................................................................116

5.6 Блок линий большого наклона..........................................................................................129

ГЛАВА 6. ОЦЕНКА РОСТА ПРОИЗВОДИТЕЛЬНОСТИ

УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ................................................142

6.1 Общий подход.....................................................................................................................142

6.2 Линии малой длины............................................................................................................142

6.3 Линии большой длины.......................................................................................................149

ОСНОВНЫЕ РЕЗУЛЬТАТЫ....................................................................................................173

ВЫВОДЫ.......................................................................................................................................174

ПРИЛОЖЕНИЕ 1. Время исполнения инструкций для процессоров семейства х86 ....175

ПРИЛОЖЕНИЕ 2. Листинги программ..................................................................................179

ПРИЛОЖЕНИЕ 3. Сокращения и условные обозначения. Глоссарий.............................198

ПРИЛОЖЕНИЕ 4. Публикации................................................................................................200

ПРИЛОЖЕНИЕ 5. Акты о внедрении.....................................................................................200

ПРИЛОЖЕНИЕ 6. Список использованной литературы....................................................205

ВВЕДЕНИЕ

Актуальность темы

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

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

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

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

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

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

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

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

Цель и задачи диссертации

Целью данной работы, было отыскание программных способов увеличения скорости графического вывода для карт SVGA на компьютерах класса IBM PC.

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

Для достижения поставленной цели решались следующие задачи:

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

2. Исследование влияния привязки программных алгоритмов к специфике центрального процессора и системы ввода/вывода на скорость графического вывода. В частности:

a) влияние общей алгоритмической оптимизации с целью использования новых команд старших моделей процессоров на производительность алгоритмов графического вывода;

b) влияние используемой разрядности регистров процессора и портов ввода/вывода на производительность алгоритмов графического вывода;

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

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

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

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

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

7. Разработка конкретных методов оптимизации алгоритмов графического вывода по какому* либо из исследованных направлений.

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

ГЛАВА 1. АЛГОРИТМЫ ВЫВОДА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

1.1 Классификация графических систем, информации, объектов и примитивов

История графических компьютерных систем длится уже довольно давно. Она началась еще до появления графических терминалов и мониторов - в ту эпоху, когда графическими были только специализированные устройства вывода на твердую основу. К ним относились всевозможные плоттеры, графопостроители и т.п.. Уже в 60-х годах велись работы по созданию эффективных алгоритмов отображения графической информации на подобных устройствах [4,34]. Но последние 18 лет ознаменовались настоящей революцией в этой области. Графические системы проследовали от специализированных систем до каждого персонального компьютера. Вот ретроспектива основных событий этих лет [21].

Таб. 1-1. Основные события в области графических систем с 1980 по 1998 годы.

1980 • Начаты разработки в исследовательском центре компании Xerox в Palo Alto.

• Первые продажи продукта под названием "Xerox STAR".

• Введены понятия указывать, выбирать, мышь (pointing, selection, mouse).

1984 • Популяризация графических систем компанией Apple.

• Компания Apple разрабатывает и выпускает на рынок новые графические системы "Lisa" и "Macintosh".

• "Macintosh" становится первой успешной графической системой на массовом рынке компьютеров.

1985 • Компания Microsoft выпускает версию 1.0 графической системы "Windows".

1987 • Система "X Windows System" получает широкое распространение.

• Компания IBM выпускает спецификацию "System Application Architecture".

• Появляется стандарт "Common User Access (CUA)".

• Компания IBM выпускает графический пакет "Presentation Manager".

• Появляется графическая операционная система - заменитель DOS.

1988 • Компания NeXT выпускает свою графическую систему "NeXTStep".

• Появляется первая эмуляция трехмерного экрана.

1989 • Появляются первые системы "UNIX" с графическим интерфейсом пользователя.

• Появляется система "Open Look" от компаний AT&T и Sun Microsystems.

• Инновационные разработки меняют устоявшееся общественное мнение.

• Появление интерфейса "Motif', созданного компаниями DEC и Hewlett-Packard для альянса Open Software Foundation (OSF).

• Система "Presentation Manager" изменяет вид и поведение.

• Компания Microsoft выпускает версию 3.0 графической системы "Windows".

1992 • Компания IBM выпускает продукт "OS/2 Workplace Shell".

• Компания Microsoft выпускает версию 3.1 графической системы "Windows".

1995 • Компания Microsoft выпускает графическую систему "Windows 95".

На сегодняшний день, все компании-разработчики операционных систем имеют графические варианты своих продуктов. Вот далеко не полный список графических операционных систем или надстроек над операционными системами, активно присутствующих сейчас на мировом компьютерном рынке: Macintosh™, NeXTStep™, OPEN LOOK™, DECwindows™, OSF/Motif™, OS/2 Presentation Manager™, OS/2 Workplace Shell™, OS/2 Warp™, Microsoft Windows 3.1™, Microsoft Windows 95™, Microsoft Windows NT™.

1.1.1 Графические системы

На Рис. 1-1 представлена классификация активно применяемых сегодня графических систем. Она показывает, что все графические системы делятся на два больших класса:

• Системы с графическим интерфейсом пользователя (GUI - Graphics User Interface). К этому классу относятся системы, в которых в качестве подсистемы отображения результатов работы была выбрана графическая подсистема.

• Системы с графическим ядром (GKS - Graphics Kernel Systems). К этому классу относятся системы построенные на графическом аппарате, являющемся ядром системы, а не всего лишь подсистемой отображения результатов работы.

Рис. 1-1. Классификация графических систем.

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

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

1.1.2 Графическая информация

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

Точечные

Векторная

Статические Динамические

изображения изображения

>

Двумерные Трехмерные

(20) (30)

Каркасные

Монолитные

Графическая информация

GUI-элементы

Статические изображения

Движущиеся изображения

Поверхностные

Рис. 1-2. Классификация типов графической информации.

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