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

опо.

КИНЖТЕРСТЮ ПРС№ШШИ гаэдоап ФЕДЕРАЦИИ

ДЕПАРТАМЕНТ РАДЙОПРЕШЕННОСТИ Бсесомзний НИИ Радиоаппаратуры

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

чкрихса C.B.

Ш 681.322.012

АЯГОРИШ И СРУХТУРЫ ГЕНЕРАЦИИ Г£ХАЛЬНЫХ КРИЫ НА РАСТРОМ ГРАФИЧЕСКИХ ВИДЕОТЕРМИНАЛАХ

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

системы и сети"

АВТОРЕФЕРАТ диссертация на соискание ученей степени кандидата технических наук

V

Санкт-Петербург - 1992

•Л--' /V/

Работа выполнена во Бсесовзном КИИ радиоаппаратуры

Научный руководитель -

доктор технических наук, профессор Громов Г.Н.

Руководитель-консультант -

кандитат технических наук Галтааез Т. Т.

Официальные оппоненты -

доктор технических наук, профессор Байкоз В.Д. кандидат технических наук, доцент Стародубцев З.В.

Ведущая организация - ЖТ5 ШП "Светлана".

Защита состоится "" " 1992 г. в____часов

на заседании специализированного совета К 053.2i.04 Ленинградского института точной механики и оптики по адресу:

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан

Ученый секретарь / |

специализированного совета К . Т . Н . ' /Ь ПОЛЯКО В В.

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

Актуальность проблема. Стреттельный прогресс в кикропро-цесссрной технике и развитие СБИС-технологии привел* к широкому распространении! микропроцессорных систем и персональных ЭВМ, на основе которых создается системы управления (СУ) различного назначения, САПР для различных отраслей промышленности, гибкие автоматизированные производства (ГАП) и автоматизированные системы научных исследований (ЙСНЙ), разрабаткзаятся комплексы моделирования сложных технических систем и природных явлений.

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

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

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

1. Математическое описание изображения в виде набора типовых линий и поверхностей (графических примитивов вывода - ГПВ), которые кодируются в дисплейном файле.

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

Первый этап визуализации выполняется прикладной программной пользователя, моделирующей визуализируемый геометрический объект. Второй этап выполняется средства™ СО или растрового графического видеотерминала (РГТ). При этом, чем больше вычислительные возможности РГТ, тем выше уровень интерфейса между прикладной программой и дисплейным процессором (¿Л), выполняющим геометрические

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

В зависимости от технических требований, ДП может иметь различный уровень сложности, от простого контроллера на одной СБИС до многопроцессорной специализированной "геометрической машины", реализованной на базе транспьютеров.

Бее существуйте графические контроллеры поддержизамт визуализации на плоских кривых небольшой сложности - векторы, окружности. Однако современные методы построения реалистических изображений требует генерировать образ не только в 30 координатном пространстве, но и в пространстве цвета и яркости, что ставит задачу генерации сложной кривой б многомерном пространстве (Х,У,2 - координаты 5И и его яркость по трем основным цветам, итого - б пространства вести измерений!.

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

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

С этой цель» в работе формулируются и резаатся следующие

задачи:

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

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

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

странстве;

синтез и исследование структуры генератора кривых Безье, завимости характеристик генератора от порядка кривой Безье и размерности пространства;

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

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

мжропоограмкная реализация генератора геометрически заданных конических дуг, реализованного з дисплейном процессоре (ЙЛК 1802,1604) высокопроизводительного комплекса отобрагешя информации "ЗЕНИТ", предназначенного для использования в системах упраз-ления навигацией и посадкой летательных апларатоз.

¡Методы исследований. В работе использозан аппарат аналитической геометрии, математического анализа, теории сплайнов, комбинаторной математики.

Научная новизна. При решении поставленных задач получены следуед<ее научные результаты.

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

2. Предложены и исследованы иерархические вычислительные структуры генераторов кривых, состояние из однотипных вычислительных элементов дзух видоз - линейного и конического интерполяторов;

3. Разработана нозая методика синтеза генераторов растровых образов кусочных тригонометрических полиномов, кризах Безье и обобщенных лекальных кривых в многомерном пространстве;

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

Достоверность полученных результате^ подтверждается де-

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

Практическую ценность работы составляет:

разработанное программное и математическое обеспечение, представленное в виде пакета прикладных программ (микропрограмм) реализующих быструю генераций растровых образов конических кривых для разрядно-модульного микропроцессора, реализованного на базе ¡"¡ПК 1802,1604.

Реализация и внедрение. Исследования проводились в рамках НИР, выполняемых во БНЙИРн в течении ряда лет для заказов связанных с управлением и посадкой летательных аппаратов.

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

Атробация результатов работы. Основные результаты работа докладывались и обсуждались на секции НТС ВНИИРА.

Публикации. Результаты выполненных теоретических и зкспе-рементальных исследований опубликована в семи печатных работах и отражены в отчетах по НИР.

Структура и обьем работы: диссертация состоит из введения, нести разделов, заключения, списка литературы из 121 наименований и приложения. Рабата содержит 180 страниц основного текста, и 47 иллюстраций.

С0ДЕР1АНЙЕ РАБОТЫ.

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

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

Отмечается, что все алгоритма поточечной генерации кривых является целочисленными и требуй/ едстазления генерируемой кривой в виде непаракетрического уравнения Ф!Х,У)=0, причем эти алго-

ритмы выполняет генерация лишь плоских 2) кризах, в то время, как современные метода построения реалистических изображений требуют выпшмэния генерации кривой п пространстве шести измерений (Х,У,г-ксординаты элемента изображения (ЗИ) и й,б,В - его яркостные со-ставляздиа по трем основным цветам).

Отмечается, что среди множества алгоритмов генерации 2В векторов и округлостей наибольшим быстродействием обладают алгоритма Брезенхема. Зти алгоритмы выбраны 8 качестве эталоноз и быстродействие и урозЕНь аппаратных затрат, разрабатываемых а данной работа алгоритмов и структур, оценивается гл отношения к аналогична характеристикам алгоритмов Брезенхема.

Предлагается в качестве обобщенных ГПБ выбрать выбрать следукщкэ геометрически задаваемые кривые:

1. Вписанная в произвольней треугольник коническая дуга.

2. Кризая Безье.

3. Тригонометрический полином.

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

На основании изложенного орсрмулирсзана цель и оснсзные задач и работы.

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

п(хг+ у2) -2. т ху + 2тЯ(х у)-(2т+п)£о?

где П. - эксцентриситет конической кривой,

В процессе работы УКй вырабатывает упразляэд® команды Ех,Еу € {0,1), которые подается на зход двух линейных интерполяторов составляяих гаянкй уровень генератора конических дуг. Пои получении на вход ненулевой управлявшей команды каждый

ЛИ, состояний их набора параллельно и независимо (рунсцианяруи^их /¡И, инициирует выполнение одной итерации алгоритма генерации составляющей вектора (алгоритма Брезенхема для векторов) каждого 1С ЛИ.

ОМС VECTOR (Р1-Р0)

Рис. i. Функциональная схема генератора 30 конических дуг, где CONIC - упраалявд-й конический интерполятор (УКИ), VECTOR - 3D линейный интерполятор (3D ЛИ), Line - ID линейный интерполятор UD ЛИ).

В результате выполнения одной итерации каждый ii> ЛИ еы-рабатызает приращение соответствующей координаты конической кривой. Это приращение может быть нулевым или единичным {-1,0,+1). Генерация конической дуги предложенным методом заключается в организации одновременной генерации двух векторов, скорость генерации которых будет зависеть от частоты подазаемых на вход ЛИ управлявших команд и от длин векторов задающих положение треугольника в который будет вписана генерируемая дуга.

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

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

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

Показано, что разработанный генератор конических дуг можно использовать для аппроксимацш криз ой Безье последовательностью сопряженных парабол. 3 основе алгоритма параболической аппроксимации кривой Безье лежат процедуры расщепления и понижения порядка кризах Безье. Показано что пои расцеплен;® кризой Безье пополам и выполнении процедура понижен;« порядка абсолютная погрешность аппроксимации не шеБьсит величины // йп /[¿^ I где

К"0

- координаты к-той управлявшей точки кризой Безье.

Поскольку координаты управляющих точек-ориетрирсв кривой Безье являятся цел™ числами, то условие ¡/¿¡^//<1/2 быстро достигается при выполнении лсь нескольких итераций процедура расщепления, после чего понижение порядка расщепленной кривой уже не вносит заметной погрешности. В конечном, счете кривая Безье представляется набором вписанных в треугольники парабол и может быть визуализируема с помощью разработанного в данной работе генератора конических дуг.

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

Рассматриваемая вычислительная структура представляет

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

Парабола

Сумматор

кис. 2. Функциональная схема генератора кривых Безье 3-го и 4-го порядков.

Проведенный анализ показал,что структура, имеющая а резней ней организации способна выполнять генерация степенного полинома 2,г> степени. Таю® образом, одноуровеная организация генератора обеспечивает генерацию парабол, двухуровневая - позволяет генерировать степенные полиномы 3-го и 4-го порядков, а генератор

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

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

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

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

В ходе исследования было показано, что генератора кривых следует реализовыаать в виде некоторой вычислительной структуры, имеющей иерахическца организация и состоящую из однотипных вычислительных элементов - УКИ и 1В Ж

В четвертом разделе предложена и исследована вычисли-льная структура, выполняющая аппроксимация тригонометрического полинома. Предложенная вычислительная структура имеет двухуровневую иерархическую организацию. Верхний убавляющий уровень состоит из многомерного управляющего /¿1, который при функцио»^озании вырабатывает единичные команды, служащие для управления коническими ¡круговыми) интерполяторами, причем частота инициализации круговых иктерполторов пропорциональна круговой частоте генерируемой гармоники тригонометрического полинома.

Из проведенного анализа следует, что управлявший круговой интерполятор отслеживает дискретную окружность не с постоян-\ скоростью, и при суммировании нескольких, генерируемых па-

раллельно с разящи скоростями гармоник, неизбежна отклонение от теоретического тригонометрического полинома. Однако, если круговые частоты яаляятся целыми числами, то генерируемые гармоники будут иметь точные значения при углах кратных ТГ/4 , а наибольшее угловое уклонение не превысит 3 градусов.Таким образом, предложенная вычислительная структура не будет генерировать тригонометрический Полинам, но будет генерировать кривую интерполируздув этот полином в точках, соответствующих ¥¿1/ кратным значениям угла. пО М Окр. 1 Сумматор

! * !

Ока. 2

Окр. п

2п

йх,бу

Ркс.З. Функциональная схема генератора тригонометрических полиномов (п - колическтао гармоник, - управлявшие векторы).

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

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

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

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

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

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

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

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

Показано, что для пересчета управляющих точек разномерного сплайна в последовательность наборов управлявших точек-ори-е.чтироа кривых Безье, составляя^;« этот сплайн, необходимо выполнить п-ъ матричных преобразований (п - количество управляющих тачек сплайна, а - степень сплайна) над последовательными наборами упрвлякщих точек сплайна.

Разработан целочисленный алгоритм формирования рациональной матрицы пересчета для равномерных сплайнов любой конечной степени (и для неравномерных сплайнов 2-й и 3-й степеней). Расчм-таны и приедены в приложении к диссетрации матрицы пересчета для равномерных сплайнов до 7-й степени включительно.

Предложен целочисленный алгоритм построения равномерного интерполяционного сплайна третьей степени и показано что размерность представления числовых величин накладывает ограничения на количество интерполируемых предложенным методом точек (8 точек при 16-разрядном представлении и 13 точек при 32-разрадном представлении). Расчитаны и приведена в приложении к диссертации матрицы пересчета интерполируемых точек в управляющие точки сплайна до 7-ми ж величительно.

Рассмотрена микропрограммная реализация генератора конических дуг, реализованного в дисплейном процессоре (КПК 1602,1804) высокопроизводительного комплекса отображения знакографической информации ЗЕНИТ, предназначенного для использования в системах управления посадкой летательных аппаратов.

ОСНОБШЕ РЕЗУЛЬТАТЫ РАБОТЫ.

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

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

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

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

5. На оснозе предложенных в данной работе алгоритмов в разработанном во БНИИРА комплексе отображения информации "ЗЕНИТ" микропрограммно реализован генератор конических дуг.

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

ПУБЛИКАЦИИ ПО ТЕ(1£ ДИССЕРТАЦИИ.

1. С.В.Чириков. Исследование возможности использования параметрических сплайнов в качестве графического примитива в устройствах отображения растрового типа. // Вопросы радиоэлектроники. Сер. ОБР. - 1988. - Вып. 14. С.86-96.

2. С.В.Чириков. Исследование возисвясти создания микропрограммного генератора тригонометрических полиномов для устройств отображения растрозого типа. // Вопросы радиоэлектроники. Серия ОВР. - 1589. - Бич. 10. С.бЬ-78.

3. С.В.Чирикоа. ¡•¡сгальзозание алгоритма понижения порядка кривых Бвзье для раскиран-ия возможностей генератора параметрических сплайнов. /7 Вопросы радиоэлектроники. Серия СВР. - 19ь9. -Вып. 15. С. ¿¿-72.

4. С.Б.Чириков. Использование генератора кривых Лиссажу для генерации параметрических сшайноа. // Вопросы радиозл£ктрс««и. Серия 03?. - 1990. - Был. 9. С.93-97.

5. С.Ё.Чирикоз. Целочисленный алгоритм поточечной генерации эллипсов, парабол и гипербол - основа генератора графических примитивов для устройств отображения растрового типа. // Вопросы радиоэлектроники. Серия ОБР. - 1990. - Вып. 21. С.69-97.

6. С.Б.Чириков. Целочисленный алгоритм аппроксимации лекальной кривой равномерным сплайном и представление его в виде последовательности сопряженных кривых Бэзье. // Вопросы радиоэлектроники. Серия ОВР. - 1991. - Был. 3. С.85-92.

7. С.В.Чириков. Целочисленный алгоритм поточечной генерации геометрически заданных конических дуг - основа генератора графических примитивов для устройств отображения растрового типа. // Вопросы радиозлекронжи. Серия ОВР. - 1991. - Вып. 7. С.85-93.