Совершенствование алгоритмов графического вывода для карт SVGA

• Автор: Митин, Владислав Анатольевич
• Шифр специальности: 05.13.13
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 207 с.

ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АЛГОРИТМЫ ВЫВОДА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
1.1 Классификация графических систем, информации, объектов и примитивов
1.1.1 Графические системы
1.1.2 Графическая информация
1.1.3 Графические объекты и примитивы
1.1.4 Обоснование выбора прямой линии в качестве основного строительного элемента
векторных изображений
1.2 Классические алгоритмы графического вывода и резервы ускорения
1.2.1 Алгебраические алгоритмы отображения прямых линий
1.2.2 Алгоритм прямой Брезенхэма (Bresenham)
1.2.3 Преобразование алгебраического алгоритма прямой в модифицированный алгоритм Брезенхэма
1.2.4 Универсальные алгоритмы отображения прямых
1.3 Исследуемые направления ускорения графического вывода и задачи диссертации
1.3.1 Привязка программных алгоритмов к специфике центрального процессора и системы ввода/вывода
1.3.1.1 Общая оптимизация алгоритмов на уровне команд
1.3.1.2 Оптимизация набора команд взаимодействия с видеопамятью
1.3.1.3 Использование полной разрядности регистров процессора и портов ввода/вывода
1.3.2 Использование аппаратных возможностей повышения производительности, реализованных в графической карте
1.3.2.1 Функции GUI Accelerator
1.3.2.2 Функции Graphics Co-Processor
1.3.2.3 Функции Zoom Window
1.3.3 Разделение множества алгоритмов вывода на уровни по степени их универсальности
1.3.4 Перенесение реализации некоторых задач с уровня прикладного программирования на уровень системных библиотек
ГЛАВА 2. ИССЛЕДОВАНИЕ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ
УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ
2.1 Блок расчета адреса в видеобуфере
2.2 Блок предустановок
2.3 Блок вертикальных линий
2.4 Блок горизонтальных линий
2.5 Блок линий малого наклона
2.6 Блок линий большого наклона
2.7 Блок завершения функции
В.А. МИТИН
СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ВЫВОДА ДЛЯ ГРАФИЧЕСКИХ КАРТ SVGA

ОГЛАВЛЕНИЕ
ГЛАВА 3. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ
УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ ЛИНИИ
3.1 Общий подход
3.2 Линии малой длины
3.3 Линии большой длины
ГЛАВА 4. ПРОГРАММНЫЕ МЕТОДЫ УВЕЛИЧЕНИЯ СКОРОСТИ
ГРАФИЧЕСКОГО ВЫВОДА
4.1 Общая оптимизация алгоритмов на уровне команд
4.1.1 Инструкция LOOP
4.1.2 Последовательность инструкций SHR
4.1.3 Инструкции MUL и IMUL
4.1.4 Вызов подпрограмм - инструкции CALL,RET
4.2 Оптимизация набора команд взаимодействия с видеопамятью
4.2.1 Инструкция STOSB
4.3 Использование регистров
ГЛАВА 5. РЕАЛИЗАЦИЯ УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ
5.1 Блок расчета адреса в видеобуфере
5.2 Блок предустановок
5.3 Блок вертикальных линий
5.4 Блок горизонтальных линий
5.5 Блок линий малого наклона
5.6 Блок линий большого наклона
ГЛАВА 6. ОЦЕНКА РОСТА ПРОИЗВОДИТЕЛЬНОСТИ
УСОВЕРШЕНСТВОВАННЫХ АЛГОРИТМОВ
6.1 Общий подход
6.2 Линии малой длины
6.3 Линии большой длины
ОСНОВНЫЕ РЕЗУЛЬТАТЫ
ВЫВОДЫ
ПРИЛОЖЕНИЕ 1. Время исполнения инструкций для процессоров семейства х86
ПРИЛОЖЕНИЕ 2. Листинги программ
ПРИЛОЖЕНИЕ 3. Сокращения и условные обозначения. Глоссарий
ПРИЛОЖЕНИЕ 4. Публикации
ПРИЛОЖЕНИЕ 5. Акты о внедрении
ПРИЛОЖЕНИЕ 6. Список использованной литературы
В.А. МИТИП СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ВЫВОДА ДЛЯ ГРАФИЧЕСКИХ КАРТ БУОА
ВВЕДЕНИЕ
ВВЕДЕНИЕ
Актуальность темы
В условиях быстрого роста парка компьютеров, одной из основных проблем взаимодействия между человеком и компьютером стала сложность программного обеспечения. Человек оказался не в состоянии быстро переключаться с одной задачи на другую и ориентироваться в море предоставляемой информации. Для того, чтобы сделать компьютер доступным каждому человеку и облегчить труд как специалиста, так и неспециалиста, стал необходим прозрачный, интуитивно понятный графический интерфейс с пользователем, в котором информация представляется в легко воспринимаемой форме, а управление программой осуществляется простыми и привычными в жизни способами, не требующими лишних действий и знаний. Да и с эргономической точки зрения, графический интерфейс, обладающий наибольшей гибкостью в формах и цветовой гамме отображаемых на экране объектов, явился оптимальным.
Однако, подобный интерфейс, особенно если применяется графика высокого разрешения и цветности, сопряжен с манипулированием большими объемами данных необходимых только для поддержания самого интерфейса и не имеющих никакого отношения к основным задачам программы. Подобные затраты на поддержание интерфейса оказались способны свести на нет всю эффективность использования выбранного типа интерфейса, замедляя вывод на экран монитора.
Решить эту проблему можно только совершенствованием методов программирования прикладных задач с использованием максимально гибких системных графических библиотек умело сочетающих аппаратные и программные ресурсы компьютера.
Помимо вновь появившихся задач графического интерфейса пользователя, всегда существовали и остаются актуальными задачи для систем с графическим ядром. К этому классу относятся системы построенные на графическом аппарате, являющемся ядром системы, а не всего лишь подсистемой отображения результатов их работы. Например, системы автоматизированного проектирования и моделирования объектов, системы визуализации в реальном времени промышленных процессов, цифровое телевидение, видеоигры и т.п
Скорость вывода графической информации, как в системах с графическим ядром, так и с графическим интерфейсом пользователя, является важным фактором, влияющим на эффективность работы этих систем. Она определяется полнотой реализации различных графических функций аппаратными средствами и эффективностью реализации программных алгоритмов обработки информации при организации графического вывода.
Как известно, наибольшего эффекта в повышении производительности можно добиться модернизацией аппаратных средств. Но это ведет к значительному удорожанию устройств (в нашем случае - графических карт) и, как правило, к потере совместимости с существующими аппаратными и программными средствами.
В подобных условиях, эффективным подходом к решению проблемы увеличения производительности графической подсистемы ПК, является совокупность модернизации аппаратуры существующих графических карт, с оптимальным программным использованием аппаратных возможностей.
Правильная программная реализация процедур обработки и вывода графической информации открывает дополнительные возможности по ускорению и повышению эффективности работы графических систем.
В.А. МИТИН
СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ВЫВОДА ДЛЯ ГРАФИЧЕСКИХ КАРТ SVGA

ИССЛЕДОВАНИЕ КЛАССИЧЕСКОЙ РЕАЛИЗАЦИИ УНИВЕРСАЛЬНОГО АЛГОРИТМА ПРЯМОЙ
Таб. 2-1. Время исполнения (в тактах) блока расчета адреса в видеобуфере для процессоров семейства х86.
8086 80286 80386 80486 Pentium
xchg r,r 4 3
add г, г 3 2
shr г, 1 2 2
shr г,1 2 2
add r,r 3 2
add г,±іат 4 3
mov г, imm 4 2
mov r,r 2 2
ret 16 11
m. 40 29
і А - 40(86), 29(286), 29(386), 19(486), 12(Р5)
Время работы этого блока не зависит ни от угла наклона ни от длины отображаемой прямой линии.
2.2 Блок предустановок
Этот блок занимается вычислениями начальных и конечных координат, размеров выводимого объекта, адреса начала отображения в видеобуфере, и другими вычислениями, на основании которых он принимает решение о том, каким именно из перечисленных ниже блоков отображать линию.
Предложенный Ричардом Уилтоном исходный текст реализации этого блока на языке ассемблера процессоров ІпТеї 8086 (см. ПРИЛОЖЕНИЕ 2, Листинг приложения 2-2) выглядит следующим образом:
Листинг 2-2. Классическая реализация блока предустановок на языке ассемблера процессоров Іпіеі 8086.
push bp preserve caller registers
mov bp, sp
sub sp, 6 stack space for local variables
push si
push di
; check for vertical line
mov si,BytesPerLine; initial y-increment
mov cx,ARGx2
sub cx,ARGxl CX :
jz VertLinel3 ; jump if vertical line
; force xl < x2
jns LOI jump if x2 > xl
neg cx ; CX :
mov bx,ARGx2 exchange xl and x2
xchg bx,ARGxl
mov ARGx2,bx
mov bx,ARGy2 exchange yl and y2
xchg bx,ARGy1
mov ARGy2,bx
; calculate dy = ABS(y2-yl)
L01: mov bx,ARGy2
sub bx,ARGyl BX :
jz HorizLinel3 ; jump if horizontal line
jns L03 jump if slope is positive
neg bx ; BX :
neg si ; negate y-increment
; select appropriate routine for slope of line
L03: push si ; preserve y-increment
В.А. МИТИН
СОВЕРШЕНСТВОВАНИЕ АЛГОРИТМОВ ВЫВОДА ДЛЯ ГРАФИЧЕСКИХ КАРТ SVGA