Содержание к диссертации
Введение
1 Анализ алгоритмов и аппаратных средств отображения информации в растровых графических дис плеях 9
1.1 Архитектуры и аппаратные средства растровых графических дисплеев 9
1.2 Обзор и анализ алгоритмов растровой развёртки плоских кривых 12
1.2.1 Цифровые дифференциальные анализаторы 14
1.2.2 Структурные алгоритмы растровой развёртки отрезков прямых 18
1.2.3 Пошаговые алгоритмы 21
1.2.4 Повышение быстродействия растровой развёртки отрезков прямых 25
1.3 Обзор и анализ быстродействующих алгоритмов вычисления эле-ментарных функций 27
2 Разработка и исследование быстродействующих алгоритмов растровой развёртки отрезков прямых 33
2.1 Анализ интегральных характеристик погрешности растровых ап-проксимаций отрезков прямых' 36
2.2 Оценка производительности двух- и двух/трёхшагового алгоритмов 45
2.3 Оптимизация 4-шагового алгоритма Гилла 48
2.4 Наращивание длины шага 4-шагового алгоритма Гилла 59
2.5 Разработка алгоритмов с шагом переменной длины не менее N 70
2.6 Сравнительный анализ алгоритмов с постоянной и переменной дли-ной шага 77
2.7 Программная реализация и оценка производительности алгоритмов 81
3 Разработка и исследование быстродействующих алгоритмов растровой развёртки дуг окружностей 86
3.1 Анализ дискретных дефектов в растровых аппроксимациях окруж-ностей 87
3.2 Оценка производительности пошаговых алгоритмов 91
3.3 Растровая развёртка плоских кривых с использованием шага пере-менной длины 98
3.4 Разработка и анализ одно/двухшагового алгоритма 105
5 Разработка адаптивных алгоритмов 116
6 Оценка числа выполняемых операций адаптивных алгоритмов 140
4 Разработка быстродействующих алгоритмов вы-числения элементарных функций для геометрических преобразований отображаемой информации 142
4.1 Расчёт и анализ погрешности кусочно-линейных таблично-алгоритмических преобразователей с умножителем 144
4.2 Расчёт и анализ погрешности преобразователей с табличным фор мированием приращений функции - 150
4.3 Численное моделирование алгоритмов 156
Заключение 163
Список литературы 165
Приложение
- Обзор и анализ алгоритмов растровой развёртки плоских кривых
- Оптимизация 4-шагового алгоритма Гилла
- Растровая развёртка плоских кривых с использованием шага пере-менной длины
- Расчёт и анализ погрешности преобразователей с табличным фор мированием приращений функции
Введение к работе
Динамичное развитие информационных технологий, снижение стоимости, энергопотребления, массогабаритных характеристик микропроцессоров и микро-ЭВМ создаёт предпосылки для компьютеризации всех сфер человеческой деятельности. Важным направлением развития цифровой вычислительной техники является компьютерная визуализация информации или машинная графика. Совершенствование технологий производства и сравнительно низкая стоимость цифровых интегральных микросхем обеспечили массовое использование растровых графических телевизионных устройств в качестве средств отображения информации в электронных вычислительных системах различного назначения. К настоящему моменту методы и средства растровой машинной графики находят широкое применение в системах компьютерного моделирования, автоматизированного проектирования, входят в состав различных человеко-машинных интерфейсов. Например, в ряде модернизируемых и разрабатываемых перспективных радиолокационных станций средств ПВО/УВД производится замена индикатора кругового обзора на растровые графические дисплеи [1...4].
Существующие тенденции развития аппаратных средств компьютерных систем показывают, что дальнейшее улучшение технических и пользовательских характеристик растровых дисплеев связывается с увеличением их разрешающей способности и числа элементов разрешения, что приводит к пропорциональному росту затрат на формирование отображаемых образов. Возрастает число задач по обработке и отображению информации, решаемых на программно-алгоритмическом уровне, поэтому для современных растровых устройств отображения информации важное значение имеют эффективные алгоритмы и математическое обеспечение.
Разработке численных методов и алгоритмов растровой графики посвящено большое количество работ как зарубежных, так и отечественных исследователей. Известны работы Д. Брезенхэма, К. By, М. Питтэвэя, П. Стефенсона, Ю. Ситникова, Б. Мартемьянова, П. Вельтмандера и др. Вместе с тем, ряд используемых алгоритмов имеет потенциальные возможности повышения быстродействия при сохранении структуры алгоритма и точностных характеристик результата. Таким образом, в настоящее время существует актуальная научно-техническая задача - повышение эффективности алгоритмов отображения информации растровых графических телевизионных устройств, решение которой способствует улучшению их технических характеристик и условий труда операторов вычислительных систем.
Обзор и анализ алгоритмов растровой развёртки плоских кривых
Алгоритмы растровой развёртки используются при визуализации технических чертежей, цифровых карт местности, в растровых индикаторных устройствах радиолокационных станций (РЛС), системах геометрического моделирования, системах управления цифровыми плоттерами, при решении геометрических задач в устройствах числового программного управления (ЧПУ) и ряде других практических приложений.
В РЛС кругового обзора при отображении элементов радиально-кругового растра и воздушной обстановки (рисунок 1.4) используются отрезки прямых и дуги окружностей.
При визуализации цифровых карт местности в большинстве случаев используется кусочно-линейная интерполяция очертаний геодезических объектов. Анализ технических чертежей показывает, что контуры изготавливаемых деталей на 95% ограничены отрезками прямых и дугами окружностей [18]. Таким образом, в ряде важных технических приложений используется растровая развёртка отрезков прямых и дуг окружностей.
Кроме того, ряд перечисленных систем функционирует в реальном масштабе времени, что накладывает дополнительные ограничения на время выполнения алгоритмов разложения в растр. Например, в индикаторах кругового обзора РЛС необходимо обеспечить возможность одновременного сопровождения до 200 и более целей, при этом требуется отображать радиолокационные эхо-сигналы, подстилающую цифровую карту местности и другую сопутствующую информацию [1...4]. При этом число элементов разрешения используемых современных растровых графических дисплеев составляет порядка 2000x2000 и более [5].
Проведём обзор и сравнительный анализ методов и алгоритмов, используемых для растровой аппроксимации плоских кривых. В зависимости от способов программной/аппаратурной реализации и используемых особенностей растрового представления непрерывных функций, выделим структурные, пошаговые (инкрементные) алгоритмы и цифровые дифференциальные анализаторы.
При использовании цифровых дифференциальных анализаторов (ЦДА) производится дискретная аппроксимация решения дифференциального уравнения (системы параметрических дифференциальных уравнений) воспроизводимой функциональной зависимости. Основным устройством ЦДА является цифровой интегратор, выполняющий приближенное вычисление определённого интеграла по одной из формул численного интегрирования [6,7,11]. Структурная схема цифрового интегратора с параллельным переносом показана на рисунке 1.5.
В интеграторе имеются входы для приращений независимой переменной dX и зависимой переменной dY, определяющих любую функцию двух переменных. Интегратор выполняет интегрирование Y по X: Z = fYdX. Регистр Y принимаетвходные сигналы dY и суммирует их, формируя значения интегрируемой функции в данный момент времени. Регистр R, выполняющий функции накапливающего сумматора, принимает два входных сигнала Y и dX и вырабатывает произведение YdX, которое, по существу, является приращением площади под кривой Y. Далее эти приращения суммируются, но на выходе dZ сигнал появляется лишь в случае, когда сумма, накопившаяся в R, превысит некоторую заданную величину. Следовательно, dZ представляет величину переполнения регистра R. Каждому из регистров Y и R могут быть присвоены некоторые начальные значения.
Дифференциальное уравнение прямой, проходящей через точки (ха,уо) и (хьУк), имеет вид dy/dx = (yk-y0)/(xk x0) = k, где к - угловой коэффициент воспроизводимой прямой. При интегрировании указанного уравнения получаем общее решение Дх) кх + С, где, в соответствии с начальными условиями Лхо)=Уо и/[хіс)=Уь постоянная интегрирования равна С = (х/уо - У&оУіХк - хо)-Полученное частное решение можно привести к виду J(x) = к(х - хо) + уо. Так как произведение к(х - XQ) представляет площадь прямоугольника с высотой к и основанием (х - х0), найденное решение можно представить в виде определённого интеграла
Для целочисленных значений у, х0, х и единичных приращений аргумента указанный интеграл можно представить в виде xt = Xo + i, _У; = Ь й:+ l/2j + y0 О і Хк - Хо, где bd означает выделение целой части числа х. Помещая в регистр Y интегратора значение к, и задавая единичные приращения аргумента х, получаем на выходе переполнения регистра R накапливающего сумматора це
Оптимизация 4-шагового алгоритма Гилла
Разработка многошаговых инкрементных алгоритмов растровой развёртки отрезков прямых представлена в ряде работ. Разработка 4-шагового алгоритма выполнена в работе [49]. В предлагаемом алгоритме диапазон угловых коэффициентов воспроизводимых отрезков &є[0...1] разделяется на 8 поддиапазонов, в каждом из которых в результате выполнения итерации алгоритма производится выбор одной из восьми 4-х шаговых комбинаций. Несмотря на выполнение условия \Ь(хи yt)\ \/2, в случае равных значений расстояний от альтернативных точек до истинной прямой, формируемая дискретная аппроксимация отличается от (2.3).
В работе Гилла [50] предлагается методика синтеза TV-шаговых инкрементных алгоритмов формирования наилучшей дискретной аппроксимации (2.3) с использованием одношагового алгоритма Брезенхэма. В качестве примера приводится разработка четырёхшагового алгоритма. Сущность методики состоит в анализе системы неравенств, которые должны быть выполнены для выбора рассматриваемой ІУ-шаговой комбинации, в результате чего определяется диапазоны) значений оценочной функции и соответствующие диапазон(ы) угловых коэффициентов к, для которых может быть выполнена данная комбинация. В отличие от алгоритма, предлагаемого в [49], используемый диапазон угловых коэффициентов Ає [0... 1 ] разбивается на 6 поддиапазонов, в каждом из которых используется пять 4-х шаговых комбинаций, так что общее число комбинаций сокращается почти вдвое с 8x8=64 до 5x6=30.
Рассмотрим методику синтеза на примере четырёхшагового алгоритма. Из формулировки одношагового алгоритма (2.5) можно заключить, что область значений оценочной функции ограничена неравенством
В соответствии с (2.7), для выбора, например, четырёхшаговой комбинации АААА должен выполняться набор условий, который можно представить в виде следующей системы неравенств:
Очевидно, что из выполнения последнего неравенства следует истинность предыдущих трёх (если F меньше меньшего, то F меньше большего), поэтому для выбора рассматриваемой комбинации достаточно выполнение неравенства F 6ук. В свою очередь, диапазон значений оценочной функции, определяемый неравенством F 6ук, должен пересекаться с областью значений оценочной функции (2.15), что будет иметь место при выполнении неравенства -6ук infF, откуда получаем неравенство 8у 2хк, выполняя деление которого на 8 получаем к 1/4. Так как алгоритм Брезенхэма формирует дискретные аппроксимации в диапазоне є[0...1], то диапазон значений , в котором может быть выбрана рассматриваемая 4-х шаговая комбинация, 0 к 1/4.
Для выбора комбинации (ADAA) должен выполняться набор условий, представленный в виде следующей системы неравенств:
Проверка трёх неравенств (1, 3 и 4) сводится к проверке одного, если правые части двух оставшихся неравенств будут больше правой части проверяемого (если F меньше меньшего, то F меньше большего) и, таким образом, рассматриваемая система из четырёх неравенств распадается на три:1. Условие (0 2х -4п)л(0 2хА-6 ) истинно при (к 1/2)л (к 1/3),так что первоначальная система из четырёх неравенств сводится к проверке надиапазон —2ук F 0 (отсюда вытекает неравенство —2ук 0, из решения которого получаем к 0) и, чтобы указанный диапазон [ -2ук...О) пересекался с областью значений оценочной функции Fe[2(yk-Xk)...2yk), должно выполнятьсяусловие (0 infF) л ( 2ук sup F). Таким образом, получаем систему неравенств-2ук 0, 0 2(ук-хк), 2ук 2ук, решая которую, находим, что (к 0) л (к 1), так что соответствующий результирующий диапазон 0 к 1/3.2. Решение пары неравенств (2хк — 4ук 0) л(2хк — Аук 2хк 6ук) приводит к противоречивому набору условий & 1/2иЛ 0.3. Решение неравенств (2хк — 6ук 0) л (2хк — 6ук 2хк — 4ук) приводит к диапазонам к 1/3, к 0, и первоначальная система из четырёх неравенств сводится к проверке на принадлежность диапазону —2ук F 2хк- 6ук (отсюда вытекает неравенство -2 2хк- 6ук) и, чтобы указанный диапазон [-2)...2хк- 6ук) пересекался с областью значений оценочной функции, должно выполняться условие (2хк - 6ук infF) л ( 2ук sup F). Таким образом, получаем систему неравенств-2ук 2хк-6ук, 2хк-6ук 2(ук-хк), 2ук 2ук, решая которую, находим к 1/2 и к 0, так что соответствующий результирующий диапазон угловых коэффициентов 1/3 к 1/2.
Для выбора комбинации (AADD) должен выполняться набор условий, приводящий к системе неравенств:
Растровая развёртка плоских кривых с использованием шага пере-менной длины
Пусть воспроизводимая плоская кривая fix) удовлетворяет одному из следующих условий: - / (х) -\, -1 / (х) 0 0 / ( ) 1, 1 / (х) ъ. (3.9) Не ограничивая общности выводов, достаточно рассмотреть один из четырёх указанных случаев, поскольку оставшиеся приводятся к рассматриваемому с использованием ряда поворотов и/или отражений. Ограничимся случаем, когда f (x) є [0...1]. В общем случае, дискретная аппроксимация непрерывной кривой fix) на целочисленной растровой сетке состоит в выборе 4/8-связной последовательности точек {(x yi)}, наиближайших к графикуfix) на заданном интервале изменения аргумента. В качестве меры близости точки (xh yt) и функции fix) используют расстояние по нормали к графику fix), расстояние по вертикали/горизонтали и другие критерии. В частности, для окружностей это может быть разность квадратов радиусов х + у) - R2. Положим, что для наилучшей растровой аппроксимации функции fix), 0 \f (x)\ 1, на интервале хє[а...Ь], минимизируется величина И ,\ УІ)І = \/(ХІ)-Уі\ mi11 xt є [М-ІАІ] » гДе паРы ІХЬУІ} - целые числа, так что у{ = \_f(xi)+\/2J или, в случае, когда числа с дробной частью, равной 1/2, округляются к ближайшему меньшему целому, yt = [/( ,)-1/2 , следовательно, погрешность аппроксимации (д(л , ) 1/2. Используемая растровая сетка определяется как абстрактная прямоугольная координатная сетка с единичной стороной ячейки, при этом элементы растра расположены в узлах сетки. Сформулируем и докажем ряд теорем о свойствах наилучших растровых аппроксимаций для функций, удовлетворяющих условиям (3.9). Теорема 3.1. Пусть на отрезке xe[a...b], а Ь, определены непрерывные функции J[x) и g(x), имеющие на этом отрезке конечные первые производные. Тогда, если Да) = g(a) и в каждой точке интервала х є (а...6] выполняется неравенство f (x) g (x), то f(x) g(x). С другой стороны, если fib) = g(b) и в каждой точке интервала x e[a..J ) истинно неравенство f (x) g (x), то g(x) f(x). Доказательство. Рассмотрим случай Да) = g(a). Представим значение функции в точке х є (а, Ь] в виде i=i І=І А где Ax = (x a)/N. Переходя к пределу, при ЛҐ—и» и, соответственно, Ля:—(), N значение функции равно f(x) f(a) + lim &xY f{a + ibx). Записывая разность )=1 значений функций в точке х, получаем так что знаки sgn\f(x)-g(x)] = sgn [f\a + iAx)-g\a + iAx)\. Аналогичным образом рассматривается и случай f(b) = g(b). n Рассмотрим теорему, устанавливающую, в частности, наименьший размер аксиальной серии для растровой аппроксимации функции fix), производная ко торой ограничена в диапазоне f (x)e [О..Л/п] . Аксиальная серия определяется как непрерывная последовательность смежных элементов растра с одинаковой абсциссой (ординатой). Доказательство. Так как величины А/ и Аг варьируются, будем рассматри вать интервал изменения аргументал:гє[а...Ь]. Поскольку криваяДх) удалена от точки (xhyi) на расстояние -1/2 А(х,-, уі) 1/2, то, в соответствии с утвержде ниями теоремы 3.1, возможные положения кривой Дх) ограничены сверху пря мой а с угловым коэффициентом k= XIп, проходящей через точку (ХІ,УІ+ 1/2), а снизу - прямой с с угловым коэффициентом k = 0, проходящей через точку (ХІ, у І -1/2), так что max {A([X(- +1.. .xt + п], ух +1)} 1/2, а min{A([Xj +1...Xj + п],Уі)} -1/2 (рисунок 3.4). Сформулируем теорему 3.3 об ограничении на максимальную длину аксиальной серии, входящей в растровую аппроксимацию выпуклой вниз кривой Дх), первая производная которой ограничена в диапазоне f {x) є [1/и...1], п 1. Теорема 3.3. Пусть кривая Дх) непрерывна на интервале [а - Ar..b] и выполняются условия /"(х) 0, f (x)e[l/n..A], xe[a...b], где п 1 - целое число. Пусть также Д(хг-, yi;) 1/2, xt є (а — А ..і — я]. Тогда расстояние Д(х,- + п, у І ) 1/2. При этом величина А 0 зависит от функции Дх) и значения п (таким же образом рассматривается и случай, когда Дх) выпукла вверх). Рисунок 3.5 Иллюстрация к формулировке теоремы 3.3; область возможного положения fix) заштрихована Доказательство теоремы 3.3 следует из рисунка 3.5 и аналогично рассмотренному доказательству теоремы 3.2. Таким же образом рассматривается и случай, когда функцияДя:) выпукла вверх. Следствие 3.1. Из теорем 3.2 и 3.3, в частности, следует, что, если для кривой fix) выполняется условие f {a) = 1/(л +1) f\x) \jn - f (b), a b, то длина l = xic-xo+ 1 входящей в растровую аппроксимацию fix) аксиальной серии с абсциссой начальной точки х0 а - Д и абсциссой конечной точки xk b + Ar,le[n,n + 1]. При этом Ь-а + Аг + Д п + 1. Результат, аналогичный следствию 3.1, сформулирован в [40] для дискретных представлений отрезков прямых линий, а аппроксимирующие алгоритмы, использующие указанное свойство, рассмотрены в работах [42,43]. Установим минимальный размер диагональной серии, входящей в растровую аппроксимацию кривой fix), производная которой ограничена в диапазонах f (x)e[(n-V)/n..A], п 0, симметричных (относительно точки f (x) = 1/2) ранее рассмотренным диапазонам / (У)є[0..Л/я]. Диагональная серия определяется как непрерывная последовательность диагонально связанных элементов растра, лежащих на одной прямой у = [-]#. Теорема 3.4. Пусть плоская кривая fix) непрерывна на интервале хе[а - Д/...6 + Дг], а Ь, при этом f(x) є[(л-1)/л...1], xe[a...b], где п 0 - целое число, и \&{х;,у 1/2. Тогда, если Д(л:(-+7, ,-+у-1/2) 0, то Д(х(.+ m,j/.+т) 1/2, т = 1..-7 щ если Д(ж,- + j, yt + j -1/2) 0, то \А(Х( + т,у( + my \/2, m=j...ntj І.-.и. При этом xte[a А/...6-л + Дг], а величины Д/, Д_ 0 зависят от функции fix) и значения л.
Расчёт и анализ погрешности преобразователей с табличным фор мированием приращений функции
Реализация кусочно-линейной интерполяции, рассмотренная в п, 4.1, требует умножения величины Kj на младшие разряды аргумента, однако для большинства существующих микропроцессорных устройств умножение является относительно длительной/трудоёмкой операцией, поэтому целесообразно рассмотреть возможность повышения быстродействия алгоритма за счёт табличного формирования приращений функции К]х(хш2г). По-прежнему полагаем,что значения аргумента и функции нормированы и находятся в интервале [0...1), значения аргумента задаются «-разрядным линейно-нарастающим двоичным кодом, значения функции представлены с т двоичными разрядами, а код аргумента делится на группы старших и младших разрядов, число которых равно g и (л - g) соответственно (см. выр. 4.2). Тогда значения функции можно представить в видегдеДхст) - значения функции в опорных точках, определяемых старшими разрядами аргумента, а Щхш,Хмщ) - набор приращений для интерполирования функции в интервалах между соседними опорными точками. Будем использовать один и тот же набор приращений сразу для нескольких опорных точек, определяемых частью старших разрядов х , имеющих наибольший вес, число которых равно Ъ g. Таким образом, диапазон изменения аргумента разбивается на 2 групп по 2 интервалов размером 2 8, на каждую из которых приходится по одному набору приращений, аппроксимирующих функцию в пределах интервала с шагом 2 ". Аналитическую на заданном интервале аргумента функцию Дл;) можно представить в виде разложения в степенной ряд Тейлора в точкегде х 0. - точка расчёта суммы остатка ряда Тейлора для вычисления набораприращений нау -м интервале Ть\ (у —1)2 x 0j jl bJ= 1...26.
Структура устройства, реализующего вычисление функции в соответствии с выражением (4.11), представлена на рис. 4,3. Таблица значений функции в опорных точках J(xcm) и таблица приращений А/Х ,, ), имеют g и n-g + b адресных входов соответственно. В целях уменьшения погрешности т-разрядного результата, вычисления ведутся с г дополнительными двоичными разрядами.двоичных разрядов.
Рассмотрим методику расчёта таблиц и анализ погрешности воспроизведения функции для структуры на рис. 4.3. Погрешность определяется как разность между эталонным значением функции fix) и реальным значением на выходе устройства/ (х). В соответствии с (4.11), суммарное значение погрешности равногде А/, А„р - погрешности представления значений функции и приращений с конечным числом двоичных разрядов, Дг - погрешность перехода от (т + г) - разрядных вычислений к ти - разрядному результату и Д$ - погрешность метода, обусловленная отбрасыванием (g-b) старших разрядов аргумента при адресации таблицы приращений. Целесообразно выполнять округление используемых операндов таким образом, чтобы выполнялось условие симметрии максимальных/минимальных значений суммарной погрешности дискретизации операндов:
В случае, когда к (т + г) - разрядному результату суммирования j(xcm) и приращения добавляется округляющее значение 2 т , погрешность отбрасывания г разрядов результата суммирования находится в диапазоне Аге[-2 т 1..Тп 1-2 т г]; если добавляется значение 2 -2 , получаем Are[-2 m l+2 m r.. .2 т 1]. Таким образом, для выполнения условия (4.13), одно из значений Длст), Af{xcm, х ) должно округляться симметрично, а второе - по избытку или недостатку так, чтобы скомпенсировать разницу в 2Гт г между шах Аг и min Дг.
Пусть значения Дхст) усекаются до (т + г) двоичных разрядов, тогда Afe[0...2 m r). На этапе предварительных расчётов, если это не вызывает переполнения разрядной сетки результата, к полученному значению Дхст) прибавляется симметрирующая добавка для Аг, равная l "1, так что Дгє [-2 т ].. .2-m_1—2 да"г] (симметрирующая добавка 2 м-1 может добавляться какв Л ), так и в приращение функции). Значения приращений функции симметрично округляются до (т + г) разрядов, так что погрешность округления [-2- ...2- 1).
Суммируя максимальные и минимальные значения трёх составляющих, получаем величину верхней границы абсолютного значения погрешности результата:]Д/» Тт х + 2-"-"-x + тахД6. (4.14)В случае отсутствия дополнительных разрядов производим симметричное округление (или округление по избытку одного значения и недостатку - другого) приращений и значений функции в опорных точках до т разрядов, выражение для погрешности имеет вид Af (x) = Af + Д + Аь и, так какТекущее значение погрешности метода возрастает при увеличении значения хш а также по мере удаления текущей опорной точки хст от точки расчёта суммы остатка ряда х й. В соответствии с (4.11), текущее значение Аь равноПоскольку 0 хт 2 ё - 2 ", оценка верхней границы абсолютного значения погрешности Аь на всём диапазоне изменения аргумента имеет вид:Заметим, что погрешность метода равна нулю в опорных точках и монотонно изменяется по мере приближения к правой границе интервалов 2 8, поэтому значение ДА на интервале 2 8 можно скомпенсировать и, таким образом, уменьшить
