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

РГБ ОД

2 2 ДЕК пт

11а нраиах рукописи

ЧИЖОВ АЛЕКСАНДР ВЛАДИМИРОВИЧ

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

Специальность: 05.13.! 1 - Математическое и программное обеспечение нмчнслнтелыплх машин, комплекеон и компьютерных сччеп

А1Л ОРНФШ'АТ диссертации на соискание ученой пепсин кандидата технических паук

Москил - 2000г

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

Научный руководитель: член-корреспондент МАИ

профессор Башмаков И.А. Научный консультант: доц., к.т.н. Гордиенко А.П.

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

доктор технических наук, профессор Чхартишвили Г. С. кандидат технических наук, доцент Клишин В. В.

Ведущая организация:

Институт проблем информатики РАН (Орловский филиал).

Защита состоится 14 декабря 2000 года в аудитории в-Зо? в /6 час. 00 мин. на заседании диссертационного Совета К-053.16.09 при Московском энергетическом институте (Техническом университете) по адресу. Москва, ул. Красноказарменная, д.14.

Отзывы в двух экземплярах, заверенные печатью, просим мапраипяп. по адресу: 111250, Москва,ул. Красноказарменная, д.14, Ученый совет МЭИ(ТУ).

С диссертацией можно ознакомиться в библиотеке МЭИ(ТУ). Автореферат разослан «_£_» ноября 2000 г.

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

к.т.н., доц. Дорошенко А Н.

-оШ.Л -г-аг. О

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

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

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

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

1) Исследование подходов к использованию вычислений на основе ограничений з графических системах.

2) Разработка геометрической модели с ограничениями целостности.

3} Разработка механизма удовлетворения ограничений для

интерактивных графических систем.

4) Разработка языка описания геометрических моделей с ограничениями целостности.

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

6) Практическое использование результатов исследований и разработок при проектировании графического редактора.

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

Научная новизна заключается в следующем:

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

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

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

4. Разработаны методы модификации модели с ограничениями.

5. Разработан язык описания геометрических моделей с ограничениями. Его отличает способность описывать не только

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

Практическая значимость разработки определяется следующими положениями:

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

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на: Научно-практической конференции "Языки мозга и тела человека: проблемы и практическое использование в деятельности органов внутренних дел" (Ope.-, 19S6); Всероссийской научной конференции "Проблемы создания и развития информационной телекоммуникационной системы специального назначения (Орел, 1997); Международной научной конференции "Пользовательский интерфейс в современных компьютерных системах" (Орел 1S99); научных семинарах кафедр прикладной математики МЭИ (ТУ) и информационных систем ОрелГТУ.

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

- (>

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, включающего 103 источника. Основная часть содержит 121 страницу машинописного текста и 43 рисунка.

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

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

Глава 1. Анализ подходов к применению ограничений.

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

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

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

удовлетворении ограничения в зависимости от того, какие данные' изменились (А,В или С), выбирается один из методов.

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

Анализ методов задания ограничений показал сложность и трудоемкость явного описания устанавливаемых ограничений, даже если они задаются интерактивными методами. Поэтому решение этой задачи играет важную роль. Ограничения могут явно задаваться пользователем или выводиться системой. Методы автоматизированного вывода необходимых ограничений основываются на правдоподобных предположениях (Peridot), использовании «гравитационных полей» (Briar), учете предыдущих действий пользователя (RocKit) и других принципах.

Представление ограничений является определяющим фактором для понимания пользователем положения или поведения того или иного объекта. Современные системы используют разнообразные способы графического (Opus), текстового (Gamet) или смешанного (Juno) представления ограничений. Целый ряд систем (SketchPad, ThingLab и др.) используют представление ограничений в виде направленного графа. Узлы графа представляют ограничения, а дуги указывают на связанные объекты. Такой метод при использовании локализации обладает хорошей наглядностью.

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

ограничений и интерактивных chc.iom.ix яимяпг.я нок.'шыик* распространение, имеющее наилучшие временные показатели. Анализ существующих механизмов показал целесообразность использования двухэтапного процесса удовлетворения требований ограничений. На первом этапе производится поиск последовательности удовлетворения ограничений, а на втором производится непосредственное изменение значений.

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

• выбор класса и набора ограничений;

• разработка метафоры взаимодействия;

• разработка методов представления ограничений;

• разработка методов задания и редактирования ограничений;

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

Глава 2. Разработка объектно-ориентированной геометрической модели, использующей ограничения целостности.

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

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

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

Структурная схема рассматриваемого уровня представлена на рисунке 1. Она состоит из трех основных частей: 30 модели - множества трехмерных геометрических объектов и связывающих их ограничений; совокупности видов, образующих 20 модель; сзязующих ограничений, соединяющих двумерные и трехмерные модели.

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

Гсимсцшмсскнк \

Рисунок 1 - Структурная схема геометрического уровня модели

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

Структуру уровня можно представить четверкой:

< V, М, Бс, 1с, >

где V - множество видов: М - 30 модель:

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

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

В свою очередь, каждый вид из V можно рассматривать как пятерку:

< 8ои, БСга. 1о2а, 1с2(|> >

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

Бсгй - концептуальная схема 20 ограничений;

1о2а - структурированное множество экземпляров двумерных геометрических объектов, построенное на основе концептуальной схемы Зо2();

1с2<1 - структурированное множество экземпляров 20 ограничений, построенное на основе концептуальной схемы 8см,

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

Концептуальная схема ограничений представлена на рисунке 2.

Уровень решения ограничений - это уровень однородного представления модели и охватывающих ее ограничений целостности. На данном уровне производится удовлетворение ограничений.

Модель уровня можно представить четверкой:

< V, Н, 1_, т >

где: V - множество переменных, образованное как V = \/2 и УЗ и Уд и Уп где

У2 - множество переменных, представляющих геометрические атрибуты объектов двухмерной части модели, охваченные ограничениями;

\/3 - множество переменных, представляющих геометрические атрибуты объектов трехмерной части модели, так же охваченные ограничениями;

Уд - множество переменных, представляющих величины углов и расстояний геометрических ограничений;

Уп - множество переменных, представляющих коэффициенты пропорций и приращения сумматоров;

Ограничение

Рисунок 2 - Концептуальная схема ограничений целостности

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

Н = < Р, Т, Г, Э, Ф, м >

где Р - множество предикатных символов; Т - множество термов:

4' - функция силы, ставящая в соответствие каждому предикатному символу из Р значение силы из диапазона [0..т]. Таким образом, данная

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

Н = Н0 и ^ и Н, ...и Н„ где Н0 - множество обязательных ограничений, имеющих силу 0. Эти

ограничения не должны остаться неудовлетворенными; Н|, ..... -

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

Б - множество значений силы: М - множество методов изменения переменных; ф - функция, ставящая в соответствие каждому предикатному символу из Р подмножество методов из М. I. - множество связей, определяемое как I. • II * V: Г - механизм удовлетворения ограничений целостности; Решением системы ограничений является функция 0, отображающая свободные переменные из Т в элементы домена О. Эта функция формируется совокупностью методов, использованных для достижения истинности предикатов, т.е. для удовлетворения ограничений. Обозначим множество всех решений через К. Каждая функция из К такова, что после ее применения все обязательные ограничения оказываются удовлетворенными. Кроме того, должно быть удовлетворено максимально возможное количество ограничений каждого более слабого уровня, в порядке убывания силы. Определим множество приемлемых решений для которого все 0 удовлетворяют ограничениям из Н0. Через него можно определить множество желаемых решений Я: К„ = {() | \/р(р е //„л рО)} К = {0 I 0 с К„л Уа(а е Я0=> ^учтс(а,0,И))}

где рО результат применения функции 0 к предикату р. Он истинен, если ограничение удовлетворено;

лучше - предикат, утверждающий, что решение ст лучше решения О для множества //.

Рассмотренную четверку, исключив механизм решения, можно интерпретировать как описание ненаправленного двудольного графа С=(\/,С,1-), в котором множества V и С образуют два непересекающихся множества вершин графа, а множество I. представляет множество дуг графа, соединяющих разнотипные вершины.

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

Условия можно разделить на топологические или структурные и геометрические. Структурные условия производят анализ принадлежности переменных геометрическим объектам - точкам. Геометрические условия определяют соответствия геометрических свойств объектов требованиям правила.

На языке исчисления предикатов первого порядка условия применимости правила трансформации определяются через двухместный предикат Разрешимо{ограничение 1, ограничение2). Структурные условия представляются предикатом С/т?руктура(ограничение1, ограничение2). Классификацию ограничений, т.е. принадлежность ограничения определенному типу, определяет предикат Является_ Ограничением{огрантен№, тип). Принадлежность переменной списку переменных, вычисляемых данным методом, определяет предикат Является_Выходом[ переменная, метод). Принадлежность переменной

списку переменных, использующихся для вычислений, но не изменяющих своих значений, определяет предикат Являешс>/_6хосЗом(переменная, метод).

Пример условия применимости для случая конфликта ограничений типа угол - угол можно записать следующим образом:

Ус1. Ус2, Ут1, Ут2. ( Явпяется_Ограничением(с\, Угол) л

Является_Ограничением(с2, Угол) л Значение^, VI) л Значение^с2, м2) л у1<>у2 лш1 е с1 л т2 е с1 л Структура(т1, т2)) => Разрешимо(с1, с2).

Ух1, Уу1, Ух2, \/у2, УхЗ. УуЗ, Ур1, Ур2, УрЗ, Ут1. Ут2. х1 е р1 л у1 е-р1 л х2 е р2 л у2 е р2 л хЗ с рЗ л уЗ е рЗ л (Является_Выходом(р1, т1) л Является_Выходом( р1 т2) л Является_Входом( р2, т1) л Является_Входом{ рЗ, т2) л р2<>рЗ л р1<>р2 л рЗ<>р1 Структура( т1 ,т2).

В данном примере переменные, связанные кванторами, имеют следующий смысл: С| - ограничения; т, - методы ограничений; V, - величины атрибутов ограничений; р, - точки; х„у, - координаты точек.

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

Базовых типов ограничений всего четыре, два геометрических - УГОЛ, РАССТОЯНИЕ и два негеометрических - ПРОПОРЦИЯ и СУММАТОР. Из двух конфликтующих ограничений, как минимум, одно должно быть геометрическим. Таким образом, возможно возникновение семи типов конфликтов (УГОЛ-УГОЛ, УГОЛ-РАССТОЯНИЕ и т.д.), которые учтены при реализации графического редактора.

Глава 3. Реализация интерактивного графического редактора, использующего ограничения.

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

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

Описаны особенности реализации объектно-ориентированного графического редактора на основе объектной модели Common Lisp Object System (CLOS), позволяющей создавать гибкие, хорошо структурированные программы. От объектных моделей широко распространенных императивных языков ее отличает механизм множественного наследования, работающий на основе списков предпочтений классов, и концепция родовых функций, существенно повышающая структурность программ, решающая проблему л-арных функций и обеспечивающая возможность описания сложного поведения объектов на основе комбинации методов.

Рисунок 3 - Структура системы

- u. -

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

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

• «вид» (View) - компонента, отвечающая за распределение экранного пространства среди окон и регулирующая их взаимное расположение;

• «контроллер» (Controller) - компонента, обрабатывающая сообщения от операционной системы и распределяющая их по окнам, через которые осуществляется взаимодействие с моделью;

• «модель» (Model) - компонента, представляющая собственно объемную модель в виде поверхностей, ограничивающих проектируемое изделие.

Поведение системы моделирует модуль управления активностью. Он получает события от компоненты «контроллер», анализирует их и выполняет редактирование модели.

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

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

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

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

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

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

При описании языка использованы нотации достаточно широко известного генератора компиляторов Yacc и языка Lisp.

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

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

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

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

Анализ производительности разработанного графического редактора, производился на основе серии тестов. При создании модели, включающей в себя тысячу ограничений, время реакции системы (без учета скорости вычерчивания) не превысило 120 мс. В целом, время реакции графического редактора на изменение модели пользователем не превысило 1,5 е., что удовлетворяет требованиям, предъявляемым к интерактивным системам.

Гпава 4. Применение графического редактора, использующего ограничения.

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

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

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

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

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

Основные результаты данной диссертационной работы заключаются в следующем:

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

2) На основе анализа принципов объектно-орИентированного подхода и требований, связанных с применением ограничений, разработано

- :о -

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

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

4) Разработаны методы редактирования предложенной геометрической модели с ограничениями.

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

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

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

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

1. Чижов А. В. Ограничения целостности в графических системах. // Инженерный журнал-справочник - 1999. - N.7. - С.42-48.

2. Чижов А. В. Особенности применения ограничений в интерактивных графических системах II Пользовательский интерфейс в современных компьютерных системах. Сб. материалов Междунар. науч. конф. - Орел 1999. - С. 77-85.

3. Чижов А. В. Использование ограничений целостности в геометрических моделях графических редакторов САПР // Проблемы создания и развития информационной телекоммуникационной системы специального назначения. Сб. материалов Всерос. научн. конф. - Орел, 1997.-С. 86-88.

4. Гордиенко А.П., Чижов A.B. Объектно-ориентированная модель системы объемного проектирования изделий сложной формы // Инженерный журнал-спразочник -1999. - N1. С 26-30.

5. Чижов А. В., Тарасов В.В. Современные функциональные языки в разработке визуальных интерфейсов пользователя // Человеческий фактор в правоохранительных системах. Языки мозга и тела человека: проблемы и практическое использование в деятельности органов внутренних дел. Сб. материалов Междунар. научно-практич. конф. - Орел: Высшая школа МВД РФ, 1996. - С. 320-322.

6. Гордиенко А.П., Чижов A.B. Управление интерфейсом пользователя в интерактивной графической системе "ДЕСФОР" // Пользовательский интерфейс: исследование, проектирование, реализация.- Вып.1,- Орел, 1991. С. 84-89.

7. Гордиенко А.П., Новиков Ю.М., Чижов A.B. Объектно-ориентированный пользовательский интерфейс в системе объемного моделирования ГАЛИС // Пользовательский интерфейс: исследование, проектирование, реализация. Вып. 2. -М., 1992. С.161-165.

8. Гордиенко А.П., Костенко Т.П., Амелина О.В., Чижов A.B. Программно-методический комплекс для проектирования изделий машиностроения сложной формы // Программные и технические средства САПР.-М.- 1988.- С. 17-18.

Печ. л. Тираж /QQ Заказ ¿fߣ

Типография МЭИ, Красноказарменная, 13.

Введение.

1. Анализ подходов к применению ограничений.

1.1 Ограничения в графических системах.

1.2 Области применения графических ограничений.

1.3 Проблемы, связанные с использованием ограничений.

1.3.1 Задание ограничений целостности.

1.3.2 Редактирование ограничений.

1.4 Представление ограничений.

1.5 Механизмы удовлетворения ограничений.

1.5.1 Численный алгебраический подход.

1.5.2 Символьный алгебраический.

1.5.3 Логический вывод.

1.5.4 Метод кластеризации.

1.5.5 Локальное распространение.

1.5.6 Цветовая классификация.

1.6 Структура графических систем, использующих ограничения.

1.7 Выводы по первой главе.

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

2.1 Трехуровневая модель представления системы.

2.1.1 Визуальный уровень.

2.1.2 Геометрический уровень модели.

2.1.3 Уровень решения ограничений.

2.2 Механизм удовлетворения ограничений.

2.3 Язык описания модели.

2.4 Выводы по второй главе.

3. Реализация интерактивной графической системы с ограничениями.

3.1 Особенности реализации в среде Harlequin Lisp Works.

3.2 Структура системы.

3.3 Механизм удовлетворения ограничений целостности.

3.3.1 Предварительное решение.

3.3.2 Разрешение конфликтов.

3.4 Библиотеки примитивов.

3.5 Синтаксис языка описания моделей.

3.6 Выводы по третьей главе.

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

4.1 Особенности применения редактора с ограничениями.

4.2 Реализация работы с недоограниченными моделями.

4.3 Реализация библиотек стандартных объектов.

4.4 Применение редактора для конструирования изделий кожгаланереи.

4.5 Применение редактора для разработок в области машиностроения.

4.6 Анализ эффективности механизма удовлетворения ограничений.

4.7 Выводы по четвертой главе.

В последние годы развитие вычислительной техники характеризуется резким повышением производительности вычислительных систем и скоростей ввода/вывода графической информации, развитием операционных систем, таких как WINDOWS,OS/2 и др., обладающих графическим интерфейсом пользователя. Это привело к появлению большого количества систем, работающих с графической информацией, и росту интереса к методам их создания. Успех подобных систем во многом определяется интерфейсом пользователя - компонентами, обеспечивающими взаимодействие пользователя с системой. Пользователь, как правило, не обладает и не желает обладать специализированными знаниями и навыками, связанными с управлением сложными вычислительными системами. Поэтому в современных пользовательских интерфейсах (ПИ) применяются различные методы, позволяющие скрыть специфику управления. Среди этих методов -метафора модели мира [36], прямое манипулирование объектами, ограничения и др. Современный ПИ должен быть простым в изучении и легким в использовании. Это во многом достигается за счет естественности и интуитивности его управления.

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

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

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

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

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

Ограничения в графических системах впервые были применены более 30 лет назад. Одной из первых систем, использовавших язык с ограничениями и объектно-ориентированный подход в интерактивной графике, является Sketchpad [94], разработанный Сазерлендом. Вслед за ним появился целый ряд систем, как развивающих те же идеи, так и разрабатывающих другие подходы. Среди них ThingLab [28], Juno [61, 86], Bertrand и другие. Опыт создания и применения графических систем с ограничениями показал эффективность и практичность таких систем. Многие из них вышли на коммерческий уровень.

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

Основополагающие концепции применения ограничений в графических системах были сформулированы в работах Б.А. Майерса [81, 82, 83, 84], А. Борнинга [25, 26, 28], Р.Д. Хила [62], Б. Фридмана-Бенсона [44, 45,46], Г. Нельсона [86], И. Фудоса [47,48] и других авторов.

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

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

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

1) Исследование подходов к использованию вычислений на основе ограничений в графических системах.

2) Разработка методов задания и редактирования ограничений.

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

4) Разработка языка описания геометрических моделей с ограничениями целостности.

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

6) Практическое использование результатов исследований и разработок при проектировании графического редактора.

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

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

2. Определены наборы примитивов для каждого уровня. Разработаны их концептуальные схемы.

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

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

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

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

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

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

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

- 8

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

Основные результаты данной диссертационной работы заключаются в следующем:

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

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

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

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

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

- 121

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

По теме диссертации опубликовано 8 печатных работ.

Апробация работы. Основные положения диссертации докладывались и обсуждались на: Научно-практической конференции "Языки мозга и тела человека: проблемы и практическое использование в деятельности органов внутренних дел" (Орел, 1996); Всероссийской научной конференции «Проблемы создания и развития информационной телекоммуникационной системы специального назначения (Орел, 1997); Международной научной конференции «Пользовательский интерфейс в современных компьютерных системах» (Орел 1999); Научных семинарах кафедр прикладной математики МЭИ (ТУ) и информационных систем ОрелГТУ.

Заключение

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

1.Буч Г. Объектно - Ориентированное программирование- М.: Конкорд, 1992.-519 с.

2. Гордиенко А.П. Объектно-ориентированный подход к управлению пользовательским интерфейсом в графических редакторах САПР: Автореф. дис. канд. техн. наук.- М., 1995.

3. Гордиенко А.П. Пользовательский интерфейс в графических приложениях: объектно-ориентированный подход // Пользовательский интерфейс: исследование, проектирование, реализация 1993 - N 1. С. 5257.

4. Гордиенко А.П., Костенко Т.П., Амелина О.В., Чижов A.B. Програмно-методический комплекс для проектирования изделий машиностроения сложной формы // Программные и технические средства САПР.-М.- 1988.-С.17-18.

5. Гордиенко А.П., Новиков Ю.М. Чижов A.B. Объектно-ориентированный пользовательский интерфейс в системе объемного моделирования ГАПИС // Пользовательский интерфейс: исследование, проектирование, реализация М., 1992 - С. 161-165.

6. Гордиенко А.П., Чижов A.B. Объектно-ориентированная модель системы объемного проектирования изделий сложной формы // Инженерный журнал-справочник 1999 - N1. С.26-30.

7. Емеличев В.А. и др. Лекции по теории графов М.: Наука, 1990290 с.

8. Кристофидес Н. Теория графов. Алгоритмический подход М.: Мир, 1978.- 520 с.

9. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов М.: Мир, 1979. - 345 с.

10. Николаева Ж.Б., Темкин С.Н., Шаповалова H.H. Моделирование кожгалантерейных изделий М.: Легкая индустрия, 1975 - 181 с.

11. Нильсон Н. Принципы искусственного интеллекта М.: Радио и связь, 1985- 390 с.

12. Телло Э. Объектно-ориентированное программирование в среде WINDOWS.- М.: Высшая школа, 1993.- 347 с.

13. Фоли Д., Дэм В. А. Основы интерактивной машинной графики.-М.: Мир, 1985.- 368 с.

14. Хендерсон П. Функциональное программирование.- М.: Наука, 1983.- 625 с.

15. Хювенен Э.,Сеппянен Й. Мир Лиспа.- М.: Мир, 1990 2т.

16. Чижов А. В. Ограничения целостности в графических системах // Инженерный журнал-справочник 1999 - N.7.- С.42-48.

17. Чижов А. В. Особенности применения ограничений в интерактивных графических системах // Пользовательский интерфейс в современных компьютерных системах. Сб. материалов Междунар. науч. конф.- Орел 1999.- С. 77-85.

18. Шишкин В. Е. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователя- М. Диалог-МИФИ, 1996-240с.

19. Aho, Sethi, Ullman. Compilers: principles, techniques and tools. -Addison-Wesley, 1986.-P.366.

20. Akker J. Applying an Advanced Data Model to Graphic Constraint Handling. // Proceedings of 5th Eurographics Workshop on Programming Paradigms in Graphics Maastricht,- 1995 - P. 1-16.

21. Alpert S.R. Graceful Interaction with Graphical Constraints // IEEE Computer Graphics & Applications 1993 - P.82-86.

22. Barsky B. Computer Graphics and Geometric Modeling using Betasplines. Springer Verlag 1988. - P.525.

23. Borning A. The Programming Language Aspect of ThingLab, a Constraint Oriented Simulation Laboratry // ACM Transactions on Programming Language and Systems.-1981.-Vol.3- N.4.- P.- 353-387.

24. Borning A., Anderson R., Freeman-Benson B.N. The Indigo Algorithm // Proceedings of the ACM Symposium on User Interface Software Technology.-1996. P.36-45.

25. Borning A., Anderson R. Indigo: A Local Propagation Algorithm for Inequality Constraints II UIST'96.- Seatle.1996.- P.129-136.

26. Borning A., Duisberg. Constraint-Based Tools for Building User Interfaces //ACM Transactions on Graphics.- 1986,- Vol.5.- N.4.- P.345-374.

27. Borning A., Freeman-Benson B.N. The OTI Constraint Solver: A Constraint Library for Constructing Interactive Graphical User Interfaces // Proc. Constraint Programming'95. Springer-Verlag LNCS.1995 - Vol.910.

28. Borning A., Freeman-Benson B.N. Wilson M. Constraint Hierarchies // Lisp and Symbolic Computation.-1992,- N.5.- P.223-270.

29. Borning A., Marriott K., Stuckey P., Xiao Y. Solving Linear Arithmetic Constraints for User Interface Applications // Tech. Report 97-06-01, Dept. Computer Science & Engr. Seattle: Univ. Of Washington.- 1997.

30. Bouma W., Chen X., Fudos I., Hoffmann C. An Electronic Primer on Geometric Constraint Solving II Available on www.cs.purdue.edu/data/homes /cmh/electrobook.

31. Bouma W., Chen X., Fudos I., Hoffmann C, Cai J., Paige R. A Geometric Constraint Solver // Department of CS, Purdue Univ. Report CSD-TD-93-054.- 1993.

32. Bruberlin B. Symbolic Computer Geometry for Computer Aided Design. // In Advances in Design and Manufacturing Systems. Tempe - 1990.

33. Buchberger B., Collins G. Kutzer B. Algebraic methods for geometric reasoning //Annual Reviews in Computer Science1993. -N1. -P.123-176.

34. Carroll J.M. Interface Metaphors and User Interface Design II Handbook of Hunman-Computer Interaction /Ed M.Helander. North-Holland-1988.- P.67-85.

35. Cohen E.S., Swith E.T., Iverson L.A. Constraint Based Tiled Windows // IEEE Computer Graphics and Application - 1986 - N.5.- P.35-45.

36. Common Lisp Interface Maneger // Release 2.0,Specification Springer-Verlag.1995.- P.510.

37. DeMichiel L.G., Gabriel R.P. The Common Lisp Object System//Springer-Verlag,Lecture Notes in Computer Science, European Conference on Object-Oriented Programming.- 1987-Vol.276 P.151-170.

38. Donikian S., Hegron G. Constraint Managment in a Declarative Design Method for 3D Scene Sketch Modeling. II Eurographics'93 Conference Proceedings, Barcelone, Septembre- 1993. -P.111-123.

39. Donikian S., Rutten E. Reactivity, Concurrency, Data-Flow and Hierarchical Preemption for Behavioural Animation. //Proceedings of 5th Eurographics Workshop on Programming Paradigms in Graphics. Maastricht 1995.- P. 125-144.

40. Elliot C„ Schechter G., Yeung R„ Abi-Ezzi S. TBAG: A High Level Framefork for Interactive, Animated 3D Graphics Applications // Proceedings of SIGGRAPH 94, Computer Graphics Proceedings, Annual Conference Series,-P.421-434

41. Epstein D., Lalonde W.R. A Smalltalk Window System Based on Constraints // OOPSLA' 88 Proceedings.- 1988.-P.83-94.

42. Freeman-Benson B.N. A Module Mechanism for Constraints in SmallTalk // OOPSLA' 89 Proceedings.- 1989.- P.389-396.

43. Freeman-Benson B.N. Kaleidoscope: Mixing Objects, Constraints, and Imperative Programming // ECOOP/OOPSLA' 90 Proceeding.- 1990.- P.77-88.

44. Freeman-Benson B.N., Maloney J., and Borning A. An Incremental Constraint Solver // Communication of the ACM.- 1990.- Vol.33.- N.1.- P.54-63.

45. Fudos I. Correctness of a Geometric Constraint Solver // Computer Science, Purdue University TR-CSD-93-076 1993.

46. Fudos I. Editable representation for 2d geometric design.// Master's thesis, Purdue University, Dept.of Computer Science 1993.

47. Fuller N., Prusinkiewicz P. Geometric Modeling With Euclidean Constructions // New Trends in Computer Graphics / Ed N. Magnenat-Thalmann, D.Thaimann. Berlin.- 1988.- P.379-391.

48. Gleicher M. Practical Issues in Graphical Constraints //In V. Saraswat and P. Van Hentenryck, eds. Principles and Practice of Constraint Programming. MIT Press,-1994.

49. Gleicher M.,Witkin A. Drawing with Constraints // The Visual Computer.- 1994.- N.11(1).- P.39-51.

50. Gleicher M.,Witkin A. Through-the-Lens Camera Control // Computer Graphics-1992.- N.26(2).- P.331-340.

51. Goldberg A. Smalltalk-80: The Interactive Programming Environment. Massachusetts: Addison-Wesley,- 1984.

52. Goldberg A., Robson D. Smalltalk-80: The Language and its Implementation. Massachusetts: Addison-Wesley 1983.

53. Graf, W.H. The Constraint Based Layout Framework LayLab and Its Applications//Proceedings of the Workshop on Effective Abstractions in Multimedia Layout, Presentations, and Interaction in conjunction with ACM Multimedia '95, San Francisco 1995.

54. Green M. Report on Dialogue Specification Tools // User Interface Managment Systems Ed. G. E. Pfaff. Berlin: Springer-Verlag - 1985 - P.9-20.

55. Green M. The University of Alberta User Interface Managment System // Computer Graphics.- 1986.- Vol.3- N.3.- P.205-213.

56. Guy L.Steele Jr. Common Lisp:The language. Digital Press - 1984.

57. Helm R., Huynh T., Marriott K., Vlissides J. An object-oriented architecture for constraint-based graphical editing. // In Proceedings of the Third Eurographics Workshop on Object-oriented Graphics, Champery, Switzerland, October 1992.

58. Hewitt C. Viewing control structures as patterns of passing messages // Jornal of Artificial Intelligence.- 1977.-Vol.8.- N.3.- P.323-364.

59. Heydon A. Nelson G. The Juno-2 Constraint-Based Drawing Editor // SRC Research Report 131a. -D.E.C.- 1994.

60. Hill R.D. A 2-D Graphics System for Multi-User Interactive Graphics Based on Objects and Constraints // Advances in object-oriented Graphics I/ Ed. E.H. Blake, P. Wisskirchen.- Berlin: Springer Verlag.- 1991- P.67-92.

61. Hosobe H., Miyashita K., Takahashi S., Matsuoka S., Yonezawa A. Locally Simultaneous Constraint Satisfaction. // Principles and Practice of Constraint Programming vol. 874 of Lecture Notes in Computer Science, Springer-Verlag, Oct.- 1994.- P. 51-62

62. Hower W., Graf W.H. A bibliographical survey of constraint-based approaches to CAD, graphics, layout, visualization, and related topics // Knowledge-Based Systems Oxford, UK: Elsevier - 1996 - N9(7).- P.449-464.

63. Hull R., King R. Semantic Database Modeling: Survey, Application, and Research Issues //ACM Computing Surveys.-1987.- Vol.19.- N.3.

64. Hutchins E. Metaphors for Interface Design // The Structure of Multimodal Dialogue /Ed M.M. Taylor at al.- North-Holland.- 1989. P. 11-28.

65. Jones O. Introdaction to the X Window System.- New Jersey, Prentice Hall, 1989.

66. Johnson S.C. Yacc yet another compiler-compiler //CSTR-32 Bell Telephone Laboratories, 1974.

67. Kalra D., Barr A. H. A Constraint-Based Figure-Maker // Eurographics'90. Elsevier Science Publisher B.V.,1990. - P.413-424

68. Karsenty S.,Landey J.A.,Weikart C. Inferring graphical constraints with RocKit. // In: HCI'92 Conference on Piople and Computer VII.British Computer Society.-1992.-P.137-153.

69. Keene Sonya E. Object-Oriented Programming in COMMON LISP: A Programmer's Guide to CLOS. Addison-Wesley,1989.

70. Kin N., Noma T.,Kunii T.L. PictureEditor: A 2d Picture Editing System Based on Geometric Constructions and Constraints // New Advances in Computer Graphics/ Ed.RAEarnshaw, B.Wyvill. Tokyo,1989. - P.193-207.

71. Kurlander D., Feiner S. Inferring Constraints from Multiple Snapshots. // ACM Transactions on Graphics, -1993. N.12(4). P.277-304.

72. Lesk M.E. Lex lexical analyser generator // CSTR-39 Bell Telephone Laboratories, 1975.

73. LispWorks CAPI Reference Manual. Harlequin, 1998. - P.525

74. Maloney J.H., Borning A., Freeman-Benson B.N. Constraint Technology for User-Interface Construction in ThingLab II // OOPSLA'89 Proceedings. -1989. -P.381-388.

75. Maulsby D.L., Kittlitz K.A., Witten I.H. Constraint-Solving in Interactive Graphics: A User-Friendly Approach // New advances in computer graphics. Proceeding of CG International '89. 1989. - P.305-318.

76. McDaniel R. Myers B. A. Amulet's Dynamic And Flexible Prototype-Instance Object And Constraint System In C++. // Carnegie Mellon University School of Computer Science Technical Report CMU-CS-95-176 -1995.

77. McDaniel R. Myers B. A. Building Applications Using Only Demonstration, // IUr98lnternational Conference On Intelligent User Interfaces. -1998.-P. 109-116.

78. Myers B.A. Creating Interaction Techniques by Demonstration // IEEE Computer Graphics and Applications.- 1987.- P.51-60.

79. Myers B.A. Creating User Interfaces by Demonstration. Boston: Academic Press. - 1988.

80. Myers B.A. A New Model for Handling Input // ACM Transaction on Information Systems.-1990.-Vol.8.-N.3.- P.289-320.

81. Myers B.A., McDaniel R.G., Kosbie D.S. Marquise: Creating Complete User Interfaces by Demonstration // Proceedings INTERCHl'93.ln Human Factors in Computing Systems. Amsterdam, 1993. - P.293-300.

82. Myers B. A., Giuse D., Dannenberg R. B., Zanden B. V., Kosbie D., Pervin E., Mickish A., Marchal P. Garnet: Comprehensive Support for Graphical, Highly-Interactive User Interfaces.// IEEE Computer.- 1990.- Vol.23.- N.11.

83. Nelson G. Juno, a constraint-based graphics system // SIGGRAPH'85 1985.-Vol.19.- N.3.- P.235-243.

84. Noma T. at al. Drawing Input Through Geometrical Constructions: Specifications and Applications // New Trends in Computer Graphics /Ed N. Magnenat-Thalmann, D. Thaimann. Berlin1988.- P.403-415.

85. Sannella M. Constraint Satisfaction and Debugging for Interactive User Interface. // PhD.thesis.Dep. of CS.,Univ. of Washington,- 1994.

86. Sannella M. Sky Blue: A Multyway Local Propagation Constraints Solver for User Interface Construction. // Proceedings UIST'94, Marina del Rey. -C.A.,1994.- P.137-146.

87. Sannella M. The SkyBlue Constraint Solver and Its Application II Proceedings of the 1993 Workshop on Principles and Practice of Constarint Programming. MIT Press, 1994.

88. Scheifler R.W., Gettys J. The X Window System // ACM Transactions on Graphics.- 1986.-Vol.5.- N.2.- P.79-109.

89. Shneiderman B. Direct manipulation. A step beyong programming languages // Computer.-1983.- Vol.16.-N.8.-P.57-69.

90. Sussman G.J., Steele G.J. Constraints A language for Expressing Almost-Hierarchical Description // Artificial Intelligence: North-Holland Publishing Company - 1980.-P.1-39.

91. Sutherland I.E. Sketchpad: A Man-Machine Graphical Communication System // Proceedings of the Spring Join Computer Conference 1963.- P.329-345.

92. Szekely P.A., Myers B.A. A user interface toolkit based on graphical objects and constraints // OOPSLA'88 Proceeding.-1988.- P.36-45.

93. Tanimura T., Noma T., Okada N. Inferring Graphical Constraints from Users' Modification // In: Y. Anzai et al.(eds.), Symbiosis of Human and Artifact. -Elsevier.- 1995. -Vol.2. -P.205-210.

94. Thennarangam S., Singh G. Inferring 3-dimentional constraint with DEVI // Proceedings. Lecture Notes in Computer Science, Vol. 874. Springer 1994.-P.78-83.

95. Zanden B.V. An incremental algorithm for satisfying hierarchies of multy-way dataflow constraints //ACM TOPLAS. -1996. -N.18(1). -P.30-72.

96. Zanden B.V. Constraint grammars in user interface management systems // Graphics lnreface'88.- 1988.- P. 176-184.

97. Zanden B.V., Myers B.A. Demonstrational and Constraint-Based Techniques for Pictorially Specifying Application Objects and Behaviors // ACM Transactions on Computer-Human Interaction. -1995. -Vol.2. -N.4. -P.308-356.

98. White R.M. Applying Direct Manipulation to Geometric Construction System // New Trends in Computer Graphics /Ed N. Magnenat-Thalmann, D. Thaimann. -Berlin, 1988.- P.446-468.

99. Winston P.H. Artificial Intellegence. Addison-Wesley, 1993.-737 p.

100. Zalik B., Guid N., Vesel A. Triggering Machanism for Constraints Solving in Constraint-based Geometric Modeling System //IEEE Computer Systems and Software Engineering 1992 - P.544-549.