Разработка структур данных и алгоритмов расчета параметрических моделей геометрических объектов тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Копорушкин, Павел Анатольевич

• Копорушкин, Павел Анатольевич
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Копорушкин, Павел Анатольевич

Введение.

1. Состояние вопросов диссертационного исследования. Постановка основных задач.

1.1. Основные методы параметризации.

1.1.1. Проектирование с использованием параметрических ограничений

1.1.2. Проектирование с помощью истории построения.

1.1.3. Проектирование с использованием конструктивных элементов, фичерсов.

1.1.4. Проектирование сборок.

1.1.5. Ассоциативное проектирование.

1.2. Обзор существующих средств параметризации.

1.3. Постановка основных задач диссертационного исследования

1.3.1. Разработка структур данных параметрических моделей.

1.3.2. Разработка средств создания параметрических моделей

1.3.3. Разработка алгоритмов анализа определенности моделей

1.3.4. Разработка алгоритмов расчета геометрии объекта.

Выводы.

2. Структуры данных.

2.1. Структура для хранения геометрии плоских объектов.

2.2. Структура для хранения геометрии трехмерных объектов

2.3. Идентификация элементов геометрической модели.

2.4. Структура для хранения плоских параметризованных объектов

2.5. Структуры для хранения параметрических ограничений.

Выводы.

3. Методы расчета параметрических моделей геометрических объектов.

3.1. Основные методы расчета параметрических моделей.

3.1.1. Численные и символические методы.

3.1.2. Методы деления на подзадачи.

3.1.3. Метод Хоффмана.

3.2. Декомпозиция систем алгебраических уравнений.

3.2.1. Система алгебраических уравнений и граф.

3.2.2. Структурные свойства двудольных графов

3.2.3. Декомпозиция Дульмаджа-Мендельсона.

3.2.4. Двудольные графы с совершенным паросочетанием

3.2.5. Общий случай.

3.3. Алгоритмы декомпозиции систем уравнений.

3.3.1. Алгоритм декомпозиции на несократимые части для полностью определенных систем.

3.3.2. Алгоритм декомпозиции на несократимые части для полностью определенных и переопределенных системы.

3.3.3. Практические примеры.

3.4. Проблемы практической реализации метода декомпозиции

3.4.1. Практический пример.

3.4.2. Анализ конфликтных ситуаций.

3.4.3. Пересчет модифицированного контура и поддержка актуальности контура.

3.4.4. Применение метода декомпозиции систем уравнений . 13 1 Выводы.

4. Метод Хоффмана.

4.1. Основные определения.

4.2. Декомпозиция на подзадачи с использованием графа ограничений.

4.3. Конденсационный алгоритм.

4.4. Модифицированный граничный алгоритм.

4.5. Расчет параметрической модели в соответствии с полученной декомпозицией.

4.6. Выбор подходящего из дискретного множества решений.

4.7. Сравнительный анализ методов декомпозиции.

Введение диссертации (часть автореферата) на тему «Разработка структур данных и алгоритмов расчета параметрических моделей геометрических объектов»

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

Одним из методов проектирования, позволивших совершить качественный прорыв в развитии CAD-систем стала так называемая параметризация[2,3].

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

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

6] (например, размерам). Из этих деталей в дальнейшем можно составлять стандартные узлы (с помощь того же языка). При конструировании сложного механизма можно использовать созданные ранее стандартные детали и узлы, вводя их параметры и вставляя полученный объект в нужное место чертежа или модели.

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

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

Термин "параметризация" получил довольно большое распространение. Он может означать и процесс создания модели, и результат проектирования, который характеризует параметрические свойства модели[10]. В широком смысле под параметризацией понимается процесс проектирования, результатом которого является модель с небольшим набором простых и понятных параметров[9]. Меняя их, конструктор получает нужную ему модель объекта. В процессе проектирования конструктор постепенно абстрагируется от исходных примитивов и получает результат, максимально соответствующий его представлениям^].

До недавнего времени большинство промышленных САПР могли предложить только средства геометрического моделирования и частичной параметризации. Главное достоинство таких систем - это легкость внесения изменений в проект без необходимости серьезной переработки отдельных деталей и узлов. Немаловажным является и удобство совместной работы коллектива конструкторов над целым проектом и отдельными деталями [11].

За последние пять лет ситуация принципиально изменилась[ 12]. Расширилась сфера применения современных САПР-решений. На сегодняшний день оказались востребованными системы PLM (Product Lifecycle Management — управление жизненным циклом изделия)[13,14,17]. PLM - это название группы программных продуктов, используемых для создания изделия (проектирование изделия и процессов его производства), организации продаж, обслуживания покупателей, а также для создания четкой обратной связи между этапами проектирования, дальнейшими маркетинговыми исследованиями и работой с покупателями [15,16].

Ключевым моментом является повышение эффективности на этапе проектирования изделия, а именно: возможность решения смешанных задач, включающих геометрические и инженерные ограничения на различных этапах проектирования изделия — от этапа создания моделей отдельных деталей до получения сборочных чертежей; возможность организации эффективной коллективной работы над проектом - так называемого распределенного, коллективного проектирования. Участники обмениваются не геометрией тех или иных деталей, а их параметрическими моделями. Это позволяет на порядок ускорить этап проектирования. Конструктор может начать работу еще до того, как необходимые ему детали будут закончены. Например, конструктор может начать компоновку узлов и агрегатов автомобиля еще до того, как будут получены, основанные на прочностных и силовых расчетах, модели двигателя и трансмиссии. Компоновка может зависеть от расположения органов управления и габаритов узлов, а параметры подвески и мощности двигателя от массы всего автомобиля; возможность использования базы параметрических моделей и сборок в системах автоматического документооборота.

Таким образом, термин "параметризация" приобретает более широкий смысл, расширяется сфера ее применения, а конструктор получает более мощный набор инструментов.

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

К сожалению, на рынке CAD-продуктов практически отсутствуют готовые компоненты, позволяющие встраивать параметризацию в пользовательские приложения. Исключением являются ядро параметрического твердотельного моделирования Parasolid и пара-метризатор британской фирмы D-Cubed, которые позиционируются фирмой Urographies как PLM-компоненты.

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

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

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

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

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

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

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

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

Апробирование работы. По теме диссертации выполнены доклады на научно-практических конференциях молодых ученых УГТУ-УПИ с 2002 по 2005 г.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Копорушкин, Павел Анатольевич

Заключение

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

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

2. Декомпозиция общей задачи на подзадачи, близкая к оптимальной. Формирование некоторой последовательности решения подзадач. В зависимости от метода, такая последовательность может представлять собой очередь, сеть или дерево[51].

3. Решение подзадач в порядке, определенном декомпозицией.

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

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

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

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

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

Рис. 78. Структура взаимодействия методов расчета параметрических объектов и методов проектирования

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

Выдавливание^ к на Нг )

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

DOF=210-117=3

Hi Н2 НЗ Rl R2 R3 R4 R5 R6

Rs-es))—*[R6(e2)

1) Hi + H3-H2 = 0

2) (Rs+R3)/2-R6=0

3) R2-Ri + 5=0

4) R2-2-HI = 0 [ Ri(e3} | 5) R5-R4=0 - инцидентность t - касательность d - размер

I'hc. 79. Для создания параметрической модели можно использовать комбинацию различных методов

При обработке параметрической модели используются два основных метода: модифицированный метод Хоффмана для обработки геометрических ограничений и модифицированный метод DM-декомпозиции для расчета ограничений произвольного характера.

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

G - корпус

A, D, С - шестерни

F, В - валы - шестерня с валом

DOF=6 7-3-5-3-6-1-2=7

Рис. 80. Сборка и соответствующий этой сборке граф объектов

Вершинами в графе объектов выступают отдельные детали, входящие в сборку. Каждый элемент сборки обладает 6 степенями свободы. Мощность связи зависит от ее типа. Жесткое соединение фиксирует 6 степеней, сферический шарнир - 3, крепление вала на подшипниках - 5, а зубчатое зацепление - 1 степень.

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

Технология работы со сборками, по своей эффективности не уступает технологии адаптивного моделирования, реализованной фирмой Autodesk в CAD-системе Inventor. Суть традиционной технологии работы со сборками состоит в том, что расчет параметров деталей, входящих в сборки, как правило, является односторонним, последовательность их расчета фиксирована. Для изменения этой последовательности конструктору приходится работать историей построения, отслеживать все цепочку расчетов самостоятельно.

Ядро параметрического моделирования позволяет использовать два режима расчета: традиционный и расширенный.

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

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

В расширенном режиме проявляется конкурентные преимущества предложенного ядра параметризации.

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

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

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

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

2. Исследованы методы параметризации геометрических объектов. В ходе работы были изучены различные широко известные методы расчета параметрических моделей, рассмотрены и проанализированы их достоинства и недостатки.

3. Выполнена модификация методов с учетом эффективной работы с переопределенными и недоопределенными объектами.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Копорушкин, Павел Анатольевич, 2005 год

1. Рутковский И.В. CAD/CAM/CAE 20 лет развития http://www.nocikt.krgtu.rU/bulletin/b 1 s2.html

2. Параметрическое моделирование. Словарь терминов. http://www.niac.ru/graphinfo.nsf/

3. Параметризация анализ по прессе в Интернете. http://vm.msun.ru/Vectorwi/Vbsdoc/Parametr.htm

4. Кононов В., Миронова М., Левкин Д. Autodesk Inventor уникальный инструмент для инженеров в новом тысячелетии. http://www.cad.ru/publ/pl 1 .shtml5. Аскон. КОМПАС-ЗЭhttp://www.cps.ru/vendorsru/ascon/kompas3d.shtml

5. Кузьмин Б., Хараджиев В. SprutCAD: особенности национальной параметризации // САПР и Графика № 09 2001 год

6. Жигулин В. О том, как твердое тело может быть слишком твердым, или Взгляд на параметризацию сбоку // САПР и графика №1 2000 год

7. Motta Е., Zdrahal Z. Parametric Design Problem Solving // Presented at the 10th Knowledge Acquisition for Knowledge-Based Systems Workshop, Banff Canada, November 1996. http://ksi.cpsc.ucalgary.ca/KAW/KAW96/motta/pardes-banff.html

8. Monedero J. Parametric design. A review and some experiences http://info.tuwien.ac.at/ecaade/proc/moneder/moneder.htm

9. Rosen D. Parametric modeling http://www.srl.gatech.edu/education/ME6104/notes/ParamModel/Pa-ramModeling.html

10. Головин М.П. CAD-системы глазами пользователя http.V/www.nocikt.krgtu.ru/bulletin/b 1 s4.html

11. Баранов Jl.В., Сёмин Д.В. Современные тенденции развития инструментальных средств разработки программного обеспечения для САПР" http://magazine.stankin.ru/arch/nl7/29/index.htm

12. Коваленко В. Системы автоматизации проектирования вчера, сегодня, завтра // Открытые системы №02/97

13. Черняк Л. PLM не роскошь, а необходимость // Открытые системы, №06/2003

14. Дубова Н. Автоматизация: от идеи до утилизации // Открытые системы, №6/2003

15. Очередько С. Концепция управления жизненным циклом // Открытые системы, №02/2002

16. Д'Агустино Д. Тернистый путь к PLM // PC Week Russian Edition САПР №15/2004

17. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: Графы, матроиды, алгоритмы Ижевск: НИЦ "РХД", 2001. -288 с.:ил.

18. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов М.: Мир, 1979. - 536 стр.:ил.

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

20. Харари Ф. Теория графов М.: Мир, 1973. - 300 стр.

21. Копорушкин П.А., Партии А.С. Алгоритм расчета параметризованных геометрических объектов. Электронный журнал "Исследовано в России", 18, 1 184-197, 2004. zhurnal.gpi.ru/articles/2004/018.pdf• • 2

22. Hoffmann С.М., Vermeer P.J. Geometric constraint solving in R and R3. Computing in Euclidian Geometry. World Scientific Publishing, 1994. Second Edition.

23. Ait-Aoudia S., Jegou R., Michelucci D. Reduction of constraint systerns. Compugraphics, p. 83-92, 1993.

24. Hoffmann C., Lomonosov A., Sitharam M. Finding solvable subsets of constraint graphs. Principles and Practice of Constraint Programming, p 463-477. Springer LNCS 1330, 1997.

25. Leea K.-Y., Kwonb O-H., Leec J.-Y., Kimd T.-W. A hybrid approach to geometric constraint solving with graph analysis and reduction. Advances in Engineering Software 34 (2003) 103-1 13

26. Autodesk Inventor 6: искусство, не требующее жертв // CadMaster №2/2002 http://www.cadmaster.rU/articles/l6inventor.cfm

27. Autodesk Speeds Up Inventor // CadDigesthttp://www.caddigest.com/subjects/adskinventor/select/cadcamnetinve ntor8.htm

28. CAD Acquisition Shocker: UGS Buys D-Cubed // CadDigest http://www.caddigest.com/subjects/unigraphics/select/061004grabowsk idcubed.htm

29. Dean A. Autodesk Inventor 4 // CADserverhttp://www.cadserver.co.uk/common/viewer/archive/2001/Mar/2 8/featur e3.phtm

30. Knowledgebase Solid Modeling Glossary - ACIS http://www.mathdata.com/faqs/solidmodelingglossary.html

31. Евченко К. Выбор геометрического моделировщика // «САПР играфика» №2/2002

32. История SolidWorks и перспективы дальнейшего развития // SolidWorks Россия http://www.solidworks.ru/SWHistory.html

33. Гореткина Е. Обзор САПР: вчера и сегодня // PCWeek Russian Edition САПР №02/2003

34. Борисов С.А., Смолянинов В.В., Терентьев М.Н. Способы создания параметризованной геометрической модели http://cosmos.rcnet.ru/articles/param.html

35. Малов М. SolidWorks 2005: может всё, нужен всем! // САПР и графика №09/2004

36. Кто может конкурировать с Dassault Systems? CAD/CAM/CAE Observer №3 (4) 2001

37. Денискин Ю.И. О методах формирования твердотельных моделей в CAD/CAM/CAE системах // Электронный журнал "Прикладная геометрия", Выпуск 3, №4 (2001)

38. Денискин Ю.И. Методы решения позиционных задач в твердотельном моделировании (часть 1) // Электронный журнал "Прикладная геометрия", Выпуск 4, №5 (2002)

39. Игнатенко А. Геометрическое моделирование сплошных тел //Graphics & Media journal №1, 2003 http://cgm.graphicon.ru/issueO/solidmodelling/

40. Fudos I. Geometric Constraint Solving. PhD thesis, Purdue University, Dept of Computer Science, 1995.

41. Fudos I. and Hoffmann C.M. A graph-constructive approach to solving systems of geometric constraints // ACM Transactions on Graphics, 16:179-216, 1997

42. Hoffmann C.M., Sitharam M., Yuan B. Making constraint solvers more usable: overconstraint problem // Computer-Aided Design 36(4): 377-399 (2004)

43. Hoffmann C.M., Yuan В. // On Spatial Constraint Solving Approaches. Automated Deduction in Geometry 2000: 1-15

44. Hoffmann C.M., Lomonosov A., Sitharam M. Planning Geometric Constraint Decomposition via Optimal Graph Transformations // AG-TIVE 1999, Applications of Graph Transformations with Industrial Relevance, International Workshop, The Netherlands: 309-324

45. Jermann C., Trombettoni G., Neveu В., Rueher M. A Constraint Programming Approach for Solving Rigid Geometric Systems // Principles and Practice of Constraint Programming CP 2000, 6th International Conference, Singapore: 233-248

46. Sitharam M., Arbree A., Zhou Y., Kohareswaran N. Solution space navigation for wellconstrained geometric constraint systems // University of Florida, Submitted in ACM Transactions on Graphics, http://www.cise.ufl.edu/~sitharam/pub.html

47. Hoffman C.M., Lomonosov A., Sitharam M. Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD. Journal of Symbolic Computation, Volume 31, №4, 2001, pages 367-408

48. Hoffman C.M., Lomonosov A., Sitharam M. Decomposition Plans for Geometric Constraint Systems, Part II: New Algorithms. Journal of Symbolic Computation, Volume 31, №4, 2001, pages 409-427

49. Sitharam M. Combinatorial approaches to geometric constraint solving: problems, progress and directions // DIMACS Workshop on computer aided design and manufacturing. 2004 http://www.cise.ufl.edu/~sitharam/pub.html

50. Sitharam M., Oung J.-J., Zhou Y., Arbee A. Geometric constraints within feature hierarchies. 2004

51. Режим доступа: http://www.cise.ufl.edu/~sitharam/pub.html

52. Durand С. Symbolic and Numerical Techniques for Constraint Solving. PhD thesis, Purdue University, Dept of Computer Science, 1998.

53. Wielinga В.J., Akkermans J.M., Schreiber A.Th. A formal analysis of parametric design problem solving // Proceedings of the 9th Banff Knowledge Acquisition Workshop, pages 37-1 37-15

54. Durand C., Hoffman C.M. A systematic framework for solving geometric constraints analytically // Journal of Symbolic Computation, Volume 30, №5, 2000, pages 493-519

55. Hoffman C.M., Joan-Arinyo R. Symbolic constraints in constructive geometric constraint solving // Journal of Symbolic Computation, Volume 23, №2-3, 1997, pages 287 299

56. Chen J., Kanj I.A. Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms // Journal of Computer and System Sciences № 67, 2003, pages 833-847

57. Hoffman C.M., Peters J. Geometric constraints for CAGD // Mathematical Methods for Curves and Surfaces, M.Daehken, T.Lyche & L.L.Schumaker ed., Vanderbilt University Press, pages 237-253, 1995.

58. Joan-Arinyo R., Soto-Riera A. Combining constructive and equa-tional geometric constraint solving techniques // ACM Transactions on Graphics, Volume 18, №1, 1999, pages 35-55

59. Joan-Arinyo R., Soto-Riera A., Vila-Marta S. Tools to Deal with Under-constrained Geometric Constraint Graphs // The Asian Symposium on Computer Mathematics ASCM 2003, Beijing, October 23-25, 2003

60. Yong-Sang Рае, Geometric constraint satisfaction by generalized degrees of freedom analysis // PhD thesis, University of Texas, Austin, Faculty of the Graduate School, 1997.

61. Michelucci D., Foufouy S. Using Cayley-Menger Determinants for Geometric Constraint Solving // ACM Symposium on Solid Modeling and Applications (2004)

62. Копорушкин П.А. Программный продукт для документированияисходных текстов программ, реализованных на языке С++ / П.А.Копорушкин // Вестник УГТУ-УПИ. 2000. № 3(11). С 114-116.

63. Копорушкин П.А. Модуль автоматизированного ввода и обработки параметрической информации / П.А.Копорушкин // Научные труды VI отчетной конференции молодых ученых УГТУ-УПИ. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2004. С 418-419.

64. Копорушкин П.А. Система документирования исходных текстов программ на языке С++ / П.А.Копорушкин // Научные труды II отчетной конференции молодых ученых УГТУ-УПИ. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2002. С 40.

65. Копорушкин П.А. Эффективный ввод и обработка параметризованной геометрической информации / П.А.Копорушкин // Научные труды V отчетной конференции молодых ученых УГТУ-УПИ. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2003. С 112-113.

66. Копорушкин П.А. Модули ввода и обработки параметризованной геометрической информации / П.А.Копорушкин // Научные труды IV отчетной конференции молодых ученых УГТУ-УПИ. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2003. С 93-94.

67. Копорушкин П.А. Создание и обработка параметрических моделей геометрических объектов / П.А.Копорушкин, А.А.Петунин // Научные труды VIII отчетной конференции молодых ученых УГТУ-УПИ. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. С 368-370.

68. Cleve Ashcraft, Joseph W.H. Liu, Applications of the Dulmage-Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement // SIAM J. Matrix Anal., 19 (1998), pages 325-354.

69. Lovasz, L., M.D. Plummer, M.D. Matching Theory, North-Holland, 1986