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



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

}

КОПОРУШКИН Павел Анатольевич

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

Специальность 05.13.12 - Системы автоматизации проектирования

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

Екатеринбург - 2005

Работа выполнена на кафедре прикладной геометрии и информатики Уральского государственного технического университета - УПИ.

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

кандидат технических наук, доцент ПЕТУНИИ А.А.

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

доктор технических наук, профессор Зобнин Б.Б. кандидат физико-математических наук, доцент Замятин А.П.

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

ЗАО НПО «Уралсистем», г.Екатеринбург

Защита состоится «10» июня 2005 г. в 15 часов на заседании

Диссертационного Совета К 212.285.02 при Уральском государственном

техническом университете по адресу: 620002, г. Екатеринбург, К-2, УГТУ-УПИ в ауд. Р-217.

С диссертацией можно ознакомиться в библиотеке Уральского государственного технического университета-УПИ.

Автореферат разослан «10» мая 2005 г.

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

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

Морозова В.А.

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

ij90DHS

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

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

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

■ удобство совместной работы коллектива конструкторов над целым проектом и отдельными деталями.

В последние годы указанные преимущества применения современных САПР-решений оказались особенно востребованными в связи с развитием так называемых PLM-систем (Product Lifecycle Management - управление жизненным циклом изделия). PLM - это название группы программных продуктов, используемых для создания изделия (проектирование изделия и процессов его производства), организации продаж, обслуживания покупателей, а также для создания четкой обратной связи между э гапами проектирования, дальнейших маркетинговых исследований и работы с покупателями. Параметризация оказалась тем средством, которое позволяет связать все этапы жизненного цикла изделия.

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

К сожалению, на рынке CAD-продуктов практически отсутствуют готовые компоненты, позволяющие встраивав параметризацию в пользовательские приложения. Исключением являются ядро параметрического твердотельного модели-

рования РагаэоМ и параметризатор британской фирмы 0-СиЬе<1 которые позиционируются фирмой иг^гарЫсБ как РЬМ-компоненты

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

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

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

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

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

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

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

■ исследованы современные и актуальные методы проектирования и расчета параметрических моделей;

■ предложены модификации существующих методов, улучшающие их функциональные возможности;

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

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

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

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

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

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

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

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

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

Параметризация - это универсальная концепция, которая получила широкое распространение в современных САБ-системах, в результате чего серьезно изменились современные методы проектирования.

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

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

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

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

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

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

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

■ структура для представления свойств объекта, набора его параметров;

■ структура для представления объектов, параметризованных с использованием истории построения;

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

В зависимости от наложенных ограничений парамегрическая модель (на-

пример, плоский контур) может быть полностью определена (англ well constrained parametric model) и плохо определена (англ. badly constrained parametric model).

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

Если модель недоопределена (англ. underconstrained parametric model), го ее геометрическое представление не может быть однозначно рассчитана, т.е. параметрической модели cooTeeiciByci бесконечное множество геометрических конфигураций В этом случае необходимо дополнить модель параметрическими связями либо зафиксировать некоторые параметры. С начала процесса проектирования и до его окончания конструктор преимущественно работает с недоопределен-ной моделью. Недоопределенность означает, что в соответствии с наложенными пользователем ограничениями расположить отдельные элементы модели и однозначно определить ее форму невозможно.

В случае если модель переопределена (англ. over constrained parametric model), то в общем случае не существует ни одного решения, соответствующего этой модели. Переопределенность модели означает избыточность наложенных на нее ограничений. Такая модель может иметь решение только в том случае, если она переопределена непротиворечиво.

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

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

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

скую модель, если это возможно.

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

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

Данный метод является достаточно эффективным для создания твердотельных моделей объектов, однако, он имеет серьезные ограничения, что сужает сферу ее применения. Булевы операции работают с "материалом", что накладывает ограничение на их последовательность. В связи с этим, САО-системы 90-х годов и некоторые современные САО-системы обладали еще одним серьезным граничением: формой модели можно управлять только вручную, модифицируя параметры исходных объектов В результате модель перестраивается в соответствии с историей построения. Г.к. все параметры фиксированы и задаются пользователем, ю считается, что модель, полученная с помощью истории построения всегда поч-иостью определена. Форма объектов в истории построении может зависеть только от объектов, соответствующим дочерним вершинам истории. Поэтому расчет параметров модели носит последовательный характер, т.к., казалось бы, исходный объект не может зависеть от объекта, который пока еще не существует.

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

В данной работе эту проблему предлагается решить следующим образом-

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

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

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

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

За работу с параметризованными плоскими контурами отвечает модуль эскизного ввода параметризованных геометрических обьектов, в разных системах он обычно называется одинаково - эскизировщиком (англ. якйсЬег). Как уже говорилось, в соответствии с современной методологией проектирования именно плоские контуры обычно служат основой для создания трехмерных объектов, являются своеобразными "кирпичиками". Одним из результаюв работы является разработка модуля эскизного ввода и расчета параметризованных плоских контуров.

Рис. 1. Декомпозиция искомого объекта на части и обратные действия в СА1)-системе

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

ш

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

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

Этот подход имеет ряд существенных недостатков, имеющих наследственный характер:

■ односторонняя зависимость, неравноправность параметров деталей сборки;

■ неочевидность "поведения" сборки при изменении значений параметров;

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

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

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

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

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

яю

О

"л

Х1=С0П51,У1=С0П31 Хб= Х1+20,уе=у1 Хь= Хь,у5=у«+30 Х>= Х1,У:=У! Хз= (Хг +Х5)/2-5,уз=у5 Хл- (Хг +Х5)/2+5,у«=у5

Рис. 2. Последовательное наложение ограничений на примере плоского контура

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

В рамках предложенной в данной работе модели параметрического объекта выделяются следующие типы параметрических ограничений:

■ геометрические. Связывают геометрические объекты между собой;

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

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

Суть методов, использующих символические вычисления, заключается в трансляции параметрических связей в систему полиномиальных уравнений и решении этой системы уравнений, например, методом ХУи-Шн'а или методом базисов ОгбЬпег'а. Однако эти ал) оритмы, не использующие предобработку, имеют, по крайней мере, экспоненциальную сложное 1ь, не умеют работать с недоопреде-

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

Часто для декомпозиции исходной системы уравнений применяется декомпозиция исходной системы на отдельные подсистемы. Разновидностью такого метода является DM-декомпозиция (англ Dulmage - Mendelsohn decomposition). Альтернативным методом декомпозиции является метод Хоффмана Его особенности:

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

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

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

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

Трудности развития большинства известных CAD-систем во многом объективны. Прежде всего, любая CAD-система - это "тяжелое" приложение, успех которого зависит от наличия самой мощной и разнообразной компьютерной техники, программного обеспечения, правильной организации деятельности крупных коллективов. Многие методы моделирования и анализа, ставшие сейчас классическими, в свое время потребовали выполнения большого объема научных исследований, которые активно проводились во всем мире. Основоположником коммерческого применения технологии параметризации можно назвать компанию РТС, вышедшую в 1989 году на рынок с Pro/Engineer, изначально ориентированной на полную параметризацию моделей.

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

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

Вся информация об объекте хранится в пользовательском приложении. Модуль параметризации от D-Cubed представляет собой решатель геометрических задач. На вход поступает информация о геометрии, параметрах и наложенных на них связях, а на выходе - решение поставленной проблемы либо анализ конфликтной ситуации. Список коммерческих организаций, когда-либо лицензировавших продукты D-Cubed, включает более 80 разработчиков программного обеспечения. Среди них такие гиганты, как Ansys, Autodesk, Boeing, Cimatron, Dassault, Ford, Mercedes, SolidWorks, Toshiba, Toyota Motor. D-Cubed была приобретена компанией Unigraphics, которая позиционирует его как один из своих PLM-компонентов наряду с ядром Parasolid. Большинство распространенных CAD-систем в качестве ядра геометрического моделирования использует либо ACIS, либо Parasolid, которые приобрели широкие параметрические возможности.

Параметрическими возможностями могут похвастаться не только зарубежные, но и отечественные средства проектирования. Например, продукт T-Flex CAD фирмы "Топ Системы" использует лицензированное ядро Parasolid.

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

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

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

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

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

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

2. СIРУКТУРЫ ДАННЫХ МОДУЛЯ ПАРАМЕТРИЧЕСКОГО КОНСТРУИРОВАНИЯ В главе 2 диссертационной работы представлен анализ видов и спосоГы реализации структур данных необходимых для представления и обработки параметрических моделей.

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

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

Для представления и обработки параметрических моделей геометрических объектов необходимы

■ структуры для плоских объектов (отдельные примитивы, контуры, регионы);

■ структуры для трехмерных объектов (граничное представление, поверхностная либо твердотельная модель);

■ структуры для параметризованных плоских объектов (примитивы, контур л, регионы, наложенные на них связи);

■ структуры для параметризованных трехмерных объектов (история построения объекта);

■ структуры для сборок, состоящих из параметризованных и непараметризован-ных трехмерных объектов.

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

Широко распространенный в современных САР-систсмах способ представ-

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

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

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

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

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

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

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

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

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

• топологические, задают структурные и топологические свойства проектируемого объекта (инцидентность, коаксиальность окружностей и т.п.);

• геометрические (параллельность, перпендикулярность, касание окружностей, эллипсов, сплайнов и т.п.);

• математические (соотношения между параметрами различных элементов контура или параметрами различных объектов);

• размеры (линейные, радиальные, угловые и т.д.).

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

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

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

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

3. МЕТОДЫ РАСЧЕТА ПАРАМЕТРИЧЕСКИХ МОДЕЛЕЙ

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

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

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

1) деление на подзадачи исходя из чисто математических соображений, попытка выделить в системе уравнений отдельные подсистемы, которые можно было бы решать независимо в некоторой последовательности. Разновидность такого метода является DM-декомпозиция (англ. Dulmage - Mendelsohn decomposition);

2) Выделение подзадач исходя из геометрических свойств модели. Такие методы основаны на анализе числа свобод твердою тела. Примером является метод Хоффмана.

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

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

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

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

4. ДЕКОМПОЗИЦИЯ СИСТЕМ УРАВНЕНИЙ Часто при расчете параметрических моделей возникает задача решения системы уравнений, а также проверки ее на полноту. Рассматриваемый метод может использоваться для решения систем уравнений, полученных произвольным способом. Например, такая система уравнений может соответствовать системе геометрических и инженерных ограничений. Инженерные ограничения могут носить произвольный характер. Модифицированный метод ОМ-декомпозиции, в отличие от оригинального метода, позволяет эффективно работать с плохо определенными моделями, независимо от вида используемых параметрических ограничений.

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

Такого двудольного графа достаточно для того, чтобы поделить исходную

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

На рисунке множество вершин {у!,у2,х1,х2} образую! хорошо определенную подсистему уравнений. Множество {уЗ,у4,хЗ} соответствует переопределенной подсистеме, а {у5,х4,х5} - недоопределенной подсистеме.

Рис. 4. Полностью определенный контур

(Ур (Х1-Хг)(К;-

(хЛ (х,-хЛ'-25 I

I (*1> Хд-Х<

(Уз). (хГхз) "*ЧУгУз? МО

Рис. 6. Граф С

Переопределенная система имеет больше уравнений, чем параметров, поэтому обычно не имеет решения. Недоопределенная система имеет больше параметров, чем уравнений, поэтому обычно имеет бесконечный набор решений. Хорошо определенная система обладает одинаковым числом уравнений и параметров, а также имеет конечный набор решений.

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

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

1 (XI) ХгХ;

(VI) (х1-х2)(х2-х3)+(у1-у2)(у2-уз) (Уз) (Х1-Хз)2+(у1-уз)2-100

(У*) У1 У"

(>Ь.) (Х1-Х4) -25

[ (Х3) Х3-Х4 1

Рис. 7. Пример графа пересчета Я

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

На Рис. 7 показан граф К. вершинам которого соответствуют системы уравнений, ребра графа показывают последовательность расчета этих систем.

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

нятного" пользователю поведения пользователя.

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

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

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

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

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

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

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

В отличие от широко распространенных методов расчета параметрических

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

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

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

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

5. МЕТОД ХОФФМАНА

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

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

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

Декомпозиция заключается в рекурсивном делении исходной задачи на же-

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

DOF = 2+2-1 = 3

/' - инцидентность, d - размер orto - ортогональность Pi, Р2 - точки, L - прямая

Рис. 8. Примеры графа объектов

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

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

Параметрическая модель представляется в виде графа G=(V,E,w), где V -это множество вершин (геометрических объектов) w(v) характеризует число степеней свободы, т е. число обобщенных координат, которые необходимо задать, чтобы зафиксировать объект;

Е - множество ребер (ограничений), где \V\ =п, \E\-m. w(e) - мощность ограничения, число параметров, которое фиксирует это 01раниченис. Обычно обозначает число соответствующих уравнений Например, размерное ограничение фиксирует один параметр, следовательно, имеет вес, равный единице

Меюд анализа степеней свободы твердого тела исследует структурные свойства графа геометрических ограничений, называемые структурной жесткостью. Степенью свободы графа А будем называть значение функции DOF(A)'

veA veЛ

Рис. 9. Хорошо определенная модель и ее граф объектов

Структурно жесткий подграф графа ограничений называется кластером. Объект считается переопределенным, число степеней свобод этого объекта меньше Э Б=3 на плоскости. В пространстве В=6

Рис. 10. Недоопределенная модель и ее граф объекюв

Рис. 11. Переопределенная модель и ее граф объектов Модификация метода Хоффмана заключается в использовании шаблонов. Шаблон - это кластер определенной структуры, для которого известно точное аналитическое решение. В процессе декомпозиции происходит поиск и выделение известных системе шаблонов. Для расчета плохо определенных моделей применяются шаблоны переопределенных и недоопределенных объектов. В указанные шаблоны закладываются методы их расчета Усовершенствованный метод Хофф-

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

6. ПАРАМЕТРИЧЕСКАЯ МОДЕЛЬ ГЕОМЕТРИЧЕСКОГО ОБЪЕКТА Далее рассматривается универсальная параметрическая модель геометрического объекта Данная модель сочетает в себе отвечающие всем современным требованиям алгоритмы формирования и расчета параметрической модели, являющиеся эффективными модификациями широко известных методов расчета параметрических моделей, и специально спроектированные структуры данных.

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

■ твердотельное и поверхностное моделирование для формирования трехмерных параметризованных объектов;

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

■ моделирование и анимация сборок.

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

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

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

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

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

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

ВЫВОДЫ

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

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

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

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

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

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

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

2006-4 17869

ПУБЛИКАЦИИ, ОТРАЖАЮЩИЕ ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. Копорушкин П.А., Алгоритм расчета параметризованных геометрических объектов / П.А.Копорушкин, А.С.Партин // Электронный журнал Исследовано в России: 018/040123, С. 184-197. Режим доступа: http://zhurnal.ape.relarn.ru/articles/2004/018.pdf

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

_ИД №06263 от 12.11.2001г._

Подписано в печать 25.04.2005 Формат 60x84 1/16

Бумага типографская Офсетная печать Усл. печ. л. 1,69

_Уч.-изд. л. 1,6_Тираж 100_Заказ_Бесплатно

Редакционно-издательский отдел ГОУ ВПО УГТУ-УПИ 620002, г. Екатеринбург, ул. Мира, 19

1/95*0

Введение.

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. Разработан модуль эскизного ввода параметрических ограничений для плоских контуров. Данный модуль позволяет интерактивно, без программирования накладывать на плоский контур разные типы параметрических ограничений.

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