автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Инструментальные средства интеграции и оптимизации представления графической информации в базах данных САПР

Министерство науки, высшей школы и технической политики Российской Федерации

Московский ордена Трудового Красного Знамени горный институт

ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ИНТЕГРАЦИИ И ОПТИМИЗАЦИИ ПРЕДСТАВЛЕНИЯ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ В БАЗАХ ДАННЫХ САПР

Специальность 05.13.12 — «Системы автоматизации проектирования (промышленность)»

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

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

КОМИССАРОВ Михаил Юрьевич

УДК 681.3.082.

Москва 1992

/

Работа выполнена в Московском ордена Трудового Красного Знамени горном институте.

Научный руководитель академик АЕН РФ ГОРБАТОВ В. А.

Официальные оппоненты: проф., докт. техн. наук ИВАННИКОВ А. Д., доц., канд. техн. наук КРЕ'ПКОВ И. М.

Ведущая организация — Московский инженерно-физический институт. ••

Защита диссертации состоится « у< . » ОК.Т. 1992 г.

в . . . час. на заседании специализированного совета Д-053.1'2.12 Московского ордена Трудового Красного Знамени горного института по адресу: 117935, Москва, Ленинский .проспект, 6., . А -55о

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

Автореферат разослан « Р. . » Ученый секретарь специализированного совета

доктор техн. наук ТОРХОВ В. Л.

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

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

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

Большой вклад в теоретические основы построения САПР, базы данных и машинную графику для САПР внесли В.И.Гольдфарб, В.А.Горбатов, А.Д. Иванников, В.П.Корячко, В.М.Курейчик, А.Н.Мелихов, И.П.Норенков, В.А.Осипов, B.C. Полозов, Д.А.Поспелов, В.П.Чистов и др. Проектные объекты и их элементы имеют, как правило графические образы. Хранение их как самостоятельных объектов, принятое в настоящее время, может вызвать весьма неприятные последствия. Дело в том, что это про/иворечит одному из основных принципов организации баз данных - интегрированное™. Оказывается, что одни и те желанные о проектном объекте в разных своих аспектах хранятся, по крайней мере, два раза. Один раз - в виде геометрических характеристик для геометрического моделирования, другой раз - в виде графического файла для визуализации. Такое положение потенциально опасно вследствие нарушения целостности или, по крайней мере, чревато постоянными изменениями одного представления (геометрического или графического) при обновлении другого. При изменении геометрических характеристик необходимо осуществлять перестройку графического образа, что является трудоемким процессом и для режима реального проектирования практически невозможно. При изменении же графического образа в режиме графического редактирования реализация соответствующих обновлений в числовых значениях геометрических характеристик может оказаться просто невыполнимой.

Таким образом, для успешного функционирования САПР безусловно необходимо решение задачи интеграции графической информации в базе данных САПР. Как показало изучение состояния исследований в области БД САПР, актуальной научной задачей, имеющей существенное значение для САПР, является разработка инструментальных средств ( как языковых, так и модельных), связанных с интегрированным представлением графической информации.

На основании проведенного анализа состояния вопроса в области реализации графических аспектов в БД САПР в настоящей работе поставлена цель - разработать языковые средства , методы и программные средства оптимального представления графической информации в базах данных САПР.

Для реализации этой цели необходимо:

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

• разработать методы и алгоритмы оптимального представления графической информации в БД САПР ;

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

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

Работа выполнялась в рамках темы 12.9.1.1.15 "Создание элементов автоматизированного проектирования и управления горнодобывающими предприятиями " программы АН СССР исследований в области естественных наук до 2000г., раздела 6. "Разработка теоретических основ проектирования и переработки твердых полезных ископаемых" программы Гособразования СССР "Экологически чистое горное производство", проблемы 1.2.7. "Совершенствование системы образования на основе применения проблемы НТП СЭВ, темы 0.80.03.16.А. "Создание и введение в о ^гнуюэкст 1 гацию открытых горных разработок" ..ограмм" Г СССР на 1986

- 1990г. Выполнение работы производилось в рамках трех хоздоговорных тем ( NN гос.рег. 01850056506 ,01890057107 , 019000004417).

Научная ноничнп работы зпкипчпется в:

• разработке оригинальных языковых средств графической интерпретации данных(П1Д), предназначенных для интеграции графической информации в базе данных САПР;

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

• решении задачи оптимизации представления графической информации на уровне метафайла на основе использования группового и упорядоченного доступа к объектам БД, методов теоретико-графовой оптимизации.

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

• создании программных средств поддержки языка ГИД и формировании оптимального представления на языковом уровне и на промежуточном уровне - уровне графического метафайла;

• разработке методики использования инструментальных средств поддержка языка ГИД.

Результаты работы внедрены в практику автоматизации проектных работ в ПО "Точмащ" ("Комплексы инструментальных средств поддержки баз данных для персональных рабочих станций "ИНФО-САПР", "ИНФО-ОПТ") , в НИР/ОКР НПО "Компас", по темам связанным с разработкой специализированных интегрированных САПР/АСТПП приборостроительного профиля (Инструментальные средства информационной технологии: комплексы "ИНФО-САПР","ИНФО-ОПТ" , СУБД "ИС-МИК-РО").

Апробапия работы. Содержание и основные результаты работы доложены и обсуждены на VIII Международной конференции по системам управления и информатике (Бухарест, 1991), XI,XII,XIII,XIV Всесоюзных симпозиумах "Логическое управление с использованием ЭВМ" и X,XI,XII, XIII Координационных совещаниях "Математическое обеспечение интеллектуальных систем САПР-ГАП" (Орджоникидзе, 1988 г.; Симферополь,1989 г.; Симеиз, 1990 г.; Новый Свет, 1991 г.), 5-й Всесоюзной конференции по машинной графике "Машинная графика-89" (Новосибирск , 1989 г.). Всесоюзной научно-технической конференции "Интегрированные системы автоматизированного проектирования" (Вологда , 1989 г.), 24-й Всесоюзной школе "Автоматизация научных исследований" (Апатпты , 1990 г.), научно-технической конференции "Разработка и внедрение САПР И АСТПП в машиностроении" (Ижевск , 1990 г.) , школе-семннаре молодых ученых "Проблемы кибернетики" (Киев , 1990 г.).

Публикации. Основное содержание работы отражено в 10 публикациях.

Объем и структура пигсетгпшии. Диссертация состоит из введения, четырех глав и заключения. Она содержит 142 страниц машинописного текста, включает 37 рисунков, 3 таблицы и список литературы из 93 наименований.

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

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

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

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

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

На основании проведенного анализа состояния вопроса интеграции средств информационного обеспечения и машинной графики в САПР в диссертации сформулированы концепции разработки языковых средств графической интерпретации данных для объектно- ориентированных САПР:

- интеграция графической информации с информацией моделирования;

- независимость от устройств ввода/вывода;

- ушгверс—.ность;

- переносимость (соотнесите стандартам ОКБ и йх! -Ашосас1);

- простота описания нзобралений;

- компактность при создании версий изображений.

При этим учитывались основные требования к графически:. ■ обеспечению САПР: ||с.:.и.|1сим0сть пг строп*Ц..1 ьви.'м/'иывода; гибкость модели проектируемого объекта;

С

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

ЯЗЫК ГРАФИЧЕСКОЙ ИНТЕРПРЕТАЦИИ ДАННЫХ

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

Основные конструкции языка ГИД.

Построенное в терминах языка ГИД изображение называется ФОРМУЛОЙ. Формула имеет уникальное имя. Формула состоит из ВЫРАЖЕНИЯ или последовательности СЕГМЕНТов.

Формула ::» "Имя ( Выражение )" I "Имя ( Сегмент)"

Формула может быть визуализирована при помощи процедур языка управления визуализацией ГИД/УВ. Семантически формула попадает под стандартное определение изображения - совокупности графических примитивов и/или сегментов, которая может быть одновременно выведена на носитель изображения.

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

Графическое ВЫРАЖЕНИЕ задает способ построения формулы из Фрагментов при помощи теоретико-множественных операций объединения, пересечения, разности, дополнения и сложения по модулю два.

Выражение ::= Фрагмент I Фрагмент Операция Фрагмент...

Таким образом, определяется механизм сборки изображения из примитивов (составных элементов ). Символически это можно записать:

Выражение ::™Операнд1 51 Операнд2 Э2 ...5п-1 Операнды ,

где Б1, 52,...,Зп-1 - теоретико-множественные операции.

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

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

Фрагмент ::= Интерпретация I Координатное_преобра.юванне( Фрагмент ) I выражение )

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

Интерпретация ::= (. 11нтерпре1аит1_|рафически10_об1,екга[; Графическнй_а1рпи> г 1 <

Термин "графические атрибуты " в языке ГИД соответствует понятию "атрибуты примитивов вывода" стандарта GKS.

Графический_атрибут [Тип_линии;1 [Толщина_линии;] [ Цвет;) [ Тип_марке-ра;] [ Масштаб_маркера;1 [Шрифт;] [ Вид_заполнения ;] [ Вид_Штриховки ]; [ Цвет_заполнителя ;] [ Граница ;] [ Цвет_границы ;] [ Атрибуты_текста] Идентификация геометрической информации. Параметры, идентифицирующие геометрическую информацию, могут быть: числовыми константами; указателем геометрической информации; макроподстановкой; указателем массива координат.

Числовые константы подставляются непосредственно в запись изображения на языке ГИД: ...LN(0,0,;1;1)... Координаты_точки ::« Аргумент,Аргумент Аргумент ::- Число I Указатель_геометрической_информации I

(Аргумент) I Макроподстановка Указатель_геометрической_информации используется для идентификации геометрической информации в базе данных или является арифметическим выражением ,в результате вычисления которого получается значение одной из координат.

Указатель_геоме1р)1ческон_Ш1формации^" Арифмегачеш)е_выражеш1е I Запрос к базе донных Операнды арифметического выражения в свою очередь могут быть числовыми константами, указателем геометрической информации или макроподстановкой.

Связь с базой данных. Связь с базой данных организована с помощью языка запросов SQL/ERA (Sequel for Entity-Relation-Association dala model), ориентированного на инструментальный пакет "Инфо-САПР", поддерживающий модель данных "Сущность-Связи-Ассоциация" , разработанный на кафедре "Вычислительные машины" Московского горного института. Запрос информации из базы данных на SQL/ERA подобен запросу на языке Sequel. 3anpoc_SQL/ERA :r=Bi iyrpeimce_iiMS (Услоапе_поиоса [Лоп1чеасая_опера1щяУсловне_поиска.-]) Например:

...LN(0,0;0,(#C.dlc(rIc10.25))/2;#C.llc(Mq),My;Mx,#C.d2c(r2=12)+My;...

Язык упп.чялрния визуализацией. Язык управления визуализацией (ЯУВ/ГИД) включает в себя следующие наборы функций: управление видовым конвейером; управление устройствами ввода/вывода; управление таи.ицами состояния; обработка ошибок; формирование метафайла CKSM (или DXF-Autocad).

Таким образом , предложено универсальное и удобное средство доя создания сложных изображений в различных предметных областях САПР.

МЕТОДЫ ОПТИМИЗАЦИИ ГРАФИЧЕСКОГО ПРЕДСТАВЛЕНИЯ ДАННЫХ.

Исследование модели визуализации выражения языка "ГИЛ".

В языке графической интерпретации данных, предложенном в данной работе, изображение J рассматривается как поименованная упорядочегная совокупность независимых фрагментов еч ,е2 ,...ел и множества операций @ "{ft ,U ,XOR,~,/) 0 - Name <е4 & еа ^ ... п), (1)

где каждый фрагмент е в свою очередь может быть совокупностью фрагмеи ¡ -в :

eL-<&X . га« 0iG 0

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

При проектировании САПР в базу данных помещается структура изображения моделируемого объекта , описанная на языке ГИД. При визуализации текущей версии изображения происходит подстановка результатов запросов к БД в выражение, записанное на языке ГИ Д, и затем отрабатывают процедуры, реализующие атгорнтмы машинной графики. Основной недостаток структурного представления изображения заключается в значительных затратах времени на вычисления. При позиционном представлении изображения время визуализации ограничено только скоростью перезаписи массив! информации с внешнего накопителя ( диска ) в память платы видеоадаптера дисплея, что с точки зрения пользователя САПР происходит мгновенно.

Как правило, в техническом задании на САПР оговорено время отклика Т. (обычно не больше 2-4 секунд; обработка сложных запросов - 10 секунд; более 20 секут - система не считается интерактивной).

Таким образом, время визуализации Tv должно быть: Т,< Т„ . (2)

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

Исходя из вышеизложенного и учитывая, что :

1) запись изображения на языке ГИД одинакова для различных версий объекта к

2) возможность языка ГИД в качестве фрагментов е использовать матрицу ячеек (подизображение, заданное позиционным представлением),

следует, что, выделив общие для различных версий участки изображения к задзг эта фрагменты в виде матрицы ячеек, можно существенно уменышгтъ время визуали luubi Т„.

ОПРЕДЕЛЕНИЕ. Означиванием фрагмента е называется замена жх-миипчсском

записи аргументов примитивов языка ГИД на численные значения и вычисление фрагмента согласно правилам языка ГИД.

ОПРЕДЕЛЕНИЕ. Графическим образом фрагмента е; называется множество точек пространства, получаемых при означивании фрагмента е-,,.

Введем следующие обозначения. Пусть изображение ] задано формулой (1), тогда, если для всех версий объекта Ц .....Ик графические образы , формиру-

емые фрагмаггоме равны gl-g2=.„-^^,^oфpQI^^eш•e£oбoзнaчaeICяeJ^ противном случае -как е°

Таким образом, формулу (1) можно переписать:

Сч Со .ч.

3=пате(е £в]в е ) ,

где (е^) или сокращенно у функция равенства фрагментов принимает значение: У(ек)-1,если равны участки изображений для всех версий ( или, другими словами, одинаков вклад фрагмента екв формирование изображения для всех версий ) и ^(е^»0 еслиЗ (Ц, и-)-версии такие, чтogl(''1¿¡&g^(el^.

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

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

ОПРЕДЕЛЕНИЕ. Пусть имеется Р версий объекта и соответственно множество графических образов фрагмента е:

0(е1>-{к1 (е1),8а<е1).....(е^ )}.

Множество полученное из множества С(е^) путем исключения равных графических образов, называется множеством версий графических образов фрагмента изображения. Будем называть мощность множества числом версий фрагмента: ?! "(^ч!

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

В данной работе для удовлетворения условию Т( Э предлагается часть

фрагментов 0 представить в матричном виде. При этом предполагается, что для матричного представления фрагмента е; время визуализации близко к нулю: Т(е^)> 0.

Таким образом, необходимо решить задачу:

где П - множество фрагментов, заданных в натричном виде.

1 И1п X

о (с П

о

2 ni.il £

е с >

3° 'Т(3)аТ

е с П >

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

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

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

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

Метод Формирования оптимальных представлений графических образов в БД САПР.

Алгоритм построения дерева решения.

Определим для дуг весовую функцию г-( £ ' 5) '

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

Левое поддерево каждой вершины включает данный фрагмент в структурном виде, правое в виде матрицы ячеек. Соответственно левая дуга каждой вершины прибавляет к весовой функции время 1[, сопоставленное данной вершине, и одну версию. Правая дуга, в свою очередь, увеличивает весовую функцию на и

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

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

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

Условия отсечения ветви дерева решений:

1. Нарушено ограничение но времени - критерий 3* (£ ^^Тд)

2. Имеется решение, оптимальепе текущего по критерию 1 , т.е. существует такое решение, у которого сумма версий фрагментов в функции £ меньше текущей.

реш тек

3. Имеется решение, равное по критерию 1 и не хуже тс кущего по критерию 2°

Методы представления изображения на языке "ГИП" пля большой размерности задрч.

Редукция дерева постпоения изображения.

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

Данный метод основан нл понятии функции равенства фрагментов (е^). Если £(е , то для фрагмента е [графические образы всех версий равны. Или, другими словами, число и версий фрагмента равно единице ^ »1 . Если^(е^-О, то число версий фрагмента может находиться в диапазоне: Г; -2...к, где к-число версий объекта, для которого определено изображение.

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

иелн £(0^,)

1 и £<е2) - 1.

е(еа и е2) =1

С(е1ие2)=0

€<«!> - 1 С(е2) = 1 а).

€(е1) = 0 е(е2) = о б).

Рис 1. Свертывание дерева построения изображения

то е;) ™ I. Размерность дерева построения изображения может быть

ук.гньшена на одну вершину (рис. 1 ,а)

Аналогично можно свернут ь в одну вершину листья-операнды, на которых функция равенства фрагментов равна нулю (рис.1,6).

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

Вершина, получившаяся з результате агрегации фрагментов I и взисшивается

следующий образом: t ; V ;

раз 1 3 рез 1 з

роз

1, если и

+ 11 ' есл" 5<е1)=0 и €(в^)=0

Приближенный алгоритм оптимального представления изображения ни языке "ГИЛ".

В основе данного алгоритма лежит понятие частичного порядка, определенного на множестве фрагментов изображения.

ОПРЕДЕЛЕНИЕ. Фрагмент е^изображенияЗболее предпочтителен для структурного представления, чем фрагмент ^ изображения?: е^е^.если:

1). время визуализации и число версий фрагмента е^ больше чиста версий фрагмента е^ : Г*> ^ , или

2). время визуализации ^ и

Г* - ^но объем памяти ''

для хранения всех версий графических образов фрагмента е; в матричном виде, не меньше объема памяти , необходимого для хранения в матричном виде всех версий графических образов фрагмента ej : V-> .

В том случае, когла е; и ej не совпадают, для такой пары принимается отсутствие предпочтения: е.. Во всех других случаях предпочтение отсутствует: е^ .

Приближенный алгоритм оптимального представления изображения на языке ГИД состоит из следующих шагов:

ША Г 1. Определение отношения предпочтения на множестве

фрагментов {е^ } изображенияО.

Ш А Г 2. Построение диаграммы Хассе для частичио-упорядоченнога множества фрагментов.

Ш А Г 3. Инициализация таймера: С-О;

Ш А г 4. Если в множестве минорант диаграммы Хассе есть фрагмент е^, такой что 'г>+ I;.<;То, то е^ включается в множество фрагментов, представленных структурно, и исключается из дальнейшего рассмотрения в алгоритме.

Иш. еШАГб.

Псе.

Ш А Г 5.; переход на шаг 4.

Ш А Г 6. СТОП.

Приведем пример работы данного алгоритма для изображения .состоящего из восьми элементов, веса которых приведены в таблице 1. ТАБЛИЦА ¿. Веса листовых фрагментов

100 50 200 300 50 100 150 400

т 2 3 3 2 5 10 1 2

20 30 50 30 10 20 20 50

Пусть То-500.

Ш А Г 1.

вХад2 е2 < > в3 ез е4 е4Ь в5

е1 $ ез е2 л е4 ез £ в5 е4 * е6

01 5 е4 е2 £ е5 ез £ в6 е4 5 е7

в1 * в5 02 < > в6 ез < > V е4 > е8

в1 * вб е2 Л е7 ез Л в8

в1 а е7 в2 Л е8

е1 * е8

°5 5 е6

е5 5 е7 е5 « е8

Шаг^, (см. рис 2.)

ШАГ 3.

Ш А Г 4.

Ш А Г 5.

ш А Г 4.

'Л А Г 5.

ш А г 4.

ш А г 5.

ш Л г 4.

111 А г 3.

ш А г 4.

ш А г 6.

Ь :-О; рез

в6 * е8

+ Ь__- 0+100-100

рез 6 рез

Выбхраен фрагнект ед ^рез !"^рез+^5 ' "0+В0-180.

^ ^ + - 150 +200 - 350

роз рез 3

роз

- + - 350+50 - ГШП рез 2 '-'

В результате получено время визуализации = 400<То. Фрагменты е6, е5, е^, е2 представляются структурно, а фрагменты е4, еь, е ,, е8 в матричном виде.

2. Частично-упорядоченноэ множество фрагментов и соответствующая ому диаграмма Хасса.

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

Ш А Г I. Редуцировать дерево построения изображения.

Ш А Г 2. Для редуцированного дерева построения изображения использовать

алгоритм оптимального представления изображения с дополнительным условием останова:

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

III А Г 3. Для оставшихся на шаге 2 фрагментов получаем точное решение методом "ветвей с отсечением".

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

Разработано программное обеспечение: средства поддержки предложенного языка ГИД и средства, реализующие методы оптимизации графических выражений. Программы написаны на языке программирования Turbo-C 2.0 и рассчитаны in применение на IBM-совместимых ПЭВМ в операционной среде MS-DOS.

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

Trans_Oid : транслятор языка ГИД: Обрабатывает входные цепочки языка и создает промежуточный метафайл (в формате GKS М или dxf-Autocad), а также специальные файлы, в которых содержится информация для наиболее оптимальной последо- ( вательности запросов к БД в процессе визуализации параметризованных изображений. | Транслятор состоит из лексического анализатора (Lex), грамматического анализатора ! (Gram) и синтезатора метафайла (Synt). '

- Vis_Gid : модуль, осуществляющий визуализацию изображения, хранящегося в метафайле. Основными компонентами модуля является функции: Query - отработка запросов к БД; Tr_coord - видовые преобразования; Visu - собственно визуализатор.

Opt_Gid : модуль, реализующий оптимизационные алгоритмы, предложенные с диссертационной работе: Tree - точный алгоритм, в основе которого метод "ветвей и границ"; Reduct - функция, редуцирующая дерево построения.изображения; Range -Функция, реализующая приближенный алгоритм, основанный на понятии частичного порядка, заданного на множестве фрагментов изображения; Combine - алгоритм, комбинирующий приближенные и точный методы.

Рис 3. Инструментальные средства поддержки графических баз данных САПР.

ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

Разработанный пакет инструментальных средств "ЖБТ-СШ" был внедрен в практику автоматизации проектных работ в ПО "Точмаш" ("Комплексы инструментальных средств поддержки баз данных для персональных рабочих станций "ИНФО-САПР", "ИНФО-ОПТ") как подсистема визуализации графических объектов базы данных. Внедрение комплексов "ИНФО-САПР", "ИНФО-ОПТ" позволило сократить сроки проектирования изделий в четыре раза, повысить качество выполняемых проектов, и улучшить условия труда проектировщиков. Годовой экономический эффект от внедрения подсистемы визуализации графических объектов в размере 7% годового экономического эффекта от внедрения комплексов "ИНФО-САПР", "ИНФО-ОПТ" составил 20,3 тыс.руб.

Внедрение пакета инструментальных средств "ЖЭТ-ОГО" в НИР/ОКР НПО "Компас" по темам, связанным с разработкой специализированных интегрированных САПР/АСТПП приборостроительного профиля (Инструментальные средства информационной технологии: комплексы "ИНФО-САПР","ИНФО-ОПТ", СУБД "ИС-МИКРО") дало эффект 7,5 тыс.руб., что составляет 5% от достигнутого годового экономического эффекта.

Все внедрения подтверждены соответствующими актами.

Разработанныдства также использовались в подсистеме визуализации "САПР специальных способов проходки на основе тампонажа", выполненной на кафедре "Вычислительные машины" МГИ по заказу треста "Шахтспецстрой", что свидетельствует о широте сферы применения и универсальности инструментальных средств поддержки графических БД САПР -"Ш5Т-СГО".

ЗАКЛЮЧЕНИЕ

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

2. Предложен язык графической интерпретации данных (ГИД) , ориентированный на использование в составе инструментальных средств, поддерживающих объектно-ориентированную модель данных, позволяющий описывать сложные изображении в САПР. Язык обеспечивает простые в использовании средства интеграции |рафической и геометрической информации; переносимость и соответствие между народным стандартам (СК8), благодаря чему достигается полное соответствие между моделируемым объектом и его изображением, становится возможным создавать параметризованные изображения.

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

изображения ( одновременно матричное и структурное описания), с учетом которого сформулирована задача оптимизации комбинированного представления изображения.

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

5. Разработаны инструментальные программные средства поддержки предложенного языка ГИД и реализующие методы оптимизации графических выражений. Эти средства по форматам представления данных совместимы с широко используемыми системами поддержки баз данных (dbf-файлы) и графики (dxf-файлы) и со стандартом GKS.

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

Основные положения диссертационной работы изложены в следующих публикациях:

1. Комиссаров М.Ю. Реализация графических свойств в базах данных для ПЭВМ. -В кн.: Логическое управление с использованием ЭВМ. Тезисы докладов XI Всесоюзного симпозиума. - М. - Орджоникидзе: ИСК АН СССР, 1988, с.241-243.

2. Комиссаров М.Ю. Представление графической информации в базе данных САШ'.

- В кн.: Интегрированные системы автоматизированного проектирования. Тезисы докладов Всесоюзной научно-технической конференции. - М., 1989, с.50-52.

3. Комиссаров М.Ю. Языковые средства графических баз данных в САПР. - В кн.: Логическое управление с использованием ЭВМ. Тезисы докладов XII Всесоюзного симпозиума. - М. - Симферополь: НСК АН СССР, 1989, с.221-224.

4. Торхов В.Л., Комиссаров М.Ю. Инструментарий графических баз данных САПР.

- В кн.: V Всесоюзная конференция по машинной графике "Машинная графика 89".-Новосибирск: ВЦ СО АН СССР, 1989.

5. Торхов В.Л., Комиссаров М.Ю. Информационная технология CAIIP/ACHII, интегрирующая разнородные данные. - В кн.: XXVI Всесоюзная школа ноавючагизании научных исследовании. - Апатиты: Кольский научный центр ЛИ СССР, 1990. C.104-I0.S.

(>. Комиссаров М.Ю. Язык |рафических выражений в им reí риронаинпп 1>Л СМИ'

- В кн.: Логическое \ правление с использованием ЭВМ. Тезисы докладов \[|| Ikeuiio i-ного симпозиума. - М. - Симеиз: НСК АН СССР, 1990, с.274-27«.

7. Торхов В.Л., Комиссаров М.Ю., Корочкова И.Г. Инструментарий поддержки БД в САПР передач и редукторов. - В кн.: Разработка и внедрение САПР и АСТПП в машиностроении. Материалы научно-технической конференции. - Ижевск: Удм. правление Союза НИО СССР, 1990, с.47-50.

8. Komissarov M.Y. Graphical language G1D as tool for CAD. В кн.: 8-th International Conference on Control Systems and Computer Science, vol. 3, PJB, Bucharest, 1991, p.p. 43-47.

9. Комиссаров M. Ю. Методы формирования оптимальных представлений графических образов в БД САПР. - В кн.: Логическое управление с использованием ЭВМ. Тезисы докладов XIV Всесоюзного симпозиума. - М. - Феодосия: ИСК АН СССР, 1991, с.146-161.

Ю.Комиссаров М.Ю. Оптимальное представление графической информации в БД САПР. - В кн.: Логическое управление с использованием ЭВМ. Тезисы докладов XIV Всесоюзного симпозиума. - М. - Феодосия: ИСК АН СССР, 1991, с.146-161.