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

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

ЩЕРБАКОВ Дмитрий Эдуардович

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

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

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

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

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

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

доктор технических наук, профессор Вайсбурд Р.А.

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

доктор технических наук, профессор Зобнин Б. Б.

кандидат технических наук,

Грицаев И.М.

Ведущее предприятие:

ЗАО НПО «Уралсистем»

Защита состоится 25 июня 2004 г. в 15.00 часов в ауд. Р-217 на заседании диссертационного совета К 212.285.02 в Уральском государственном техническом университете - УПИ, г. Екатеринбург, ул. Мира, 19.

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

Ваш отзыв в одном экземпляре, заверенный гербовой печатью, просим направлять по адресу: 620002, Екатеринбург, К-2, ул. Мира, 19, УГТУ-УПИ. Ученому секретарю университета.

Телефон (343)375-45-74, факс (343) 374-53-35.

Автореферат разослан 24 мая 2004 г.

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

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

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

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

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

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

(►ОС. НАЦИОНАЛЬНА«| БИБЛИОТЕКА | СПтрб^ 03 мол

I >

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Работа выполнялась в рамках проекта А-0058 «Современная технология исследования материалов и проектирования машин» Федеральной целевой программы «Интеграция» в разделе «Создание систем геометрического моделирования для проектирования машин и исследования качества изделий при их изготовлении» в 1998 - 2001 гг.

Алгоритмы и структуры данных, разработанные в представленной диссертационной работе, используются в лаборатории механики деформаций ИМАШ УрО РАН в рамках темы «Разработать математические и компьютерные модели формообразования изделий из металлических материалов при высокотемпературных больших пластических деформациях, обеспечивающих проектирование материалосберегающих технологий. № гос.рег. 01.200.1. 10671». Имеется соответствующий акт о внедрении.

Разработанное на основе результатов работы геометрическое ядро используется в составе системы автоматизации проектирования пресс-форм турбинных лопаток спроектированной ЗАО «ВЕЕ РГГЯО№> (г. Екатеринбург) для ОАО «Тюменские моторостроители». Имеется соответствующий акт о внедрении.

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

работ.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, основных выводов по работе, перечня библиографических источников и приложений. Основной текст занимает 170 страниц, библиография (161 наименование) - 13 страниц, приложения - 9 страниц. В работе содержится 49 рисунков, схем и таблиц.

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

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

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

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

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

результанта означает необходимое и достаточное условие наличия общего корня у данной системы. Поскольку результант не содержит переменных исходной системы, говорится, что он исключает эти переменные. Существует много способов построения и вычисления результантов, самыми известными из которых являются результанты Сильвестра, Безу и Кэли. Общее выражение для исключения к (<]) переменных из у однородных уравнений было предложено Маколеем. В случае, когда ],к = 2, можно вычислить результант Сильвестра для двух полиномов степеней т и п как определитель матрицы размера (т+п). Пусть п£т, тогда для неоднородных полиномов вида

Там, где пустые места соответствуют нулевым коэффициентам, коэффициентыf составляют т строк, а коэффициенты g - п строк. Даже если /и £ не являются полиномами по одной переменной, результант Сильвестра может удалить выбранную переменную, считая остальные символическими константами.

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

где: гет(а,Ь) - означает остаток от деления а на Ь, а последний элемент Р отличен от 0. В получившемся наборе имеют значение только знаки результатов р,(а) для исследуемого значения а. Совпадением знака называется ситуация, когда знак р,(а) совпадает со знаком £>,+/(а).Необходимо подсчитать число таких совпадений для всех р,(а) - так называемое значение Штурма. Если исследуемое а не является точным корнемр, значение Штурма для а определяет число корней р, меньших по значению а, плюс половину комплексных корней. При вычитании значения Штурма в а из значения Штурма в Ь получается точный номер действительных корней, внутри интервала [а,Ь]. Аналогично просто проводится и изоляция корней: если интервал содержит более одного корня, достаточно рекурсивно делить интервал пополам, до тех пор, пока полученные части не будут содержать не более одного корня. Известно, что для полинома степени и, с коэффициентами а¡, ¡=1...п, в худшем случае время изоляции корней составит

что в среднем составляет время работы Подобный метод нахождения

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

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

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

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

пределы изменения параметрических координат м и V числовыми границами в диапазоне от 0.0 до 1.0 включительно.

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

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

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

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

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

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

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

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

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

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

Алгоритм нахождения пересечения двух кривых принимает на вход две алгебраические плоские кривые вида:

/(и,у) = 0,£(и,у) = 0 и прямоугольную область определения: [и,,и2]х 1у1»у2]> Результатом работы является множество точек, являющихся решением лежащих внутри заданной прямоугольной области. В процессе алгоритма производится получение полиномов вида

Если = 0, то и(и) = 0,У(у)-0, следовательно, координаты

и-решений определяются корнями и и координаты у-решений определяются корнями V. Далее производится изоляция корней полинома и внутри интервала [и^щ] и корней полинома Квнутри и н т е р в ал та п р и помощи одномерных последовательностей Штурма. Каждый изолированный корень представляется в виде определенного граничного интервала, так называемого интервального корня, тогда число корней и составит т, а число корней V соответственно п. Необходимо рассмотреть тп комбинаций интервальных корней, образующих прямоугольные области, для дальнейшего определения, какие из них будут соответствовать решению Алгоритм определяет

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

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

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

/ = 0 имеет вертикальную или горизонтальную касательные. На втором этапе выполняется рекурсивная процедура, соединяющая друг с другом ранее найденные точки.

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

В пятой главе Модификация поверхностей геометрических объектов при выполнении логических операций приводится алгоритм для проведения модификации поверхности геометрического объекта (рис.3-4) при выполнении' логических операций: объединения, вычитания, пересечения.

Рис. 4. Этапы 6-9 алгоритма модификации поверхности

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

Этап 1 - Построение линии пересечения. Если объект 5| состоит из т порций, а объект состоит из п порций, тогда необходимо тп раз произвести построение линии пересечения для каждой пары порций из разных объектов.

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

Поверхность порции в рациональном параметрическом виде

задается через и, соответственно, в неявном виде:

Р\(х,у,г) = 0. Аналогично, поверхность порции Р2 в рациональном параметрическом виде задается через: Х(з,0, У(х,0, Н(х,0 и в неявном

виде: Г2(х,у,г) = 0. Путем замены и так далее в и удаления

Я(и,У)

делителя /м приводится к однородному виду У&Н) = 0. Аналогично приводится к однородному виду

Вычисление линии пересечения производится для каждой области определения. В области определения Р\ линия пересечения имеет вид (И. V). (". («. (и, V)) = /, (и, V) = 0.

В области определения Р2 линия пересечения имеет вид

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

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

А, , А,

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

степени и в исходном виде набора коэффициентов практически непригодны в работе. Поэтому, согласно структуре данных и алгоритму из четвертой главы, они разбиваются на связанные сегменты монотонных участков, образующие ориентированные цепочки, согласно структуре данных третьей главы. Кривая разбивается на области определения [Ы|,Ы2]*[У|,у2] порции а кривая соответственно, на области определения

\\ г?""'^

*\ * • 5 »

В, _

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

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

одному прогону алгоритма нахождения пересечения кривых на каждую граничную кривую. Например, пусть 7/ в формате структуры данных является граничной кривой, с исходным полиномом вида */и,у,)=0. Тогда необходимо вычислить точки пересечения между внутри области

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

Г(и,у)=0 - уравнение линии пересечения, (пересечение ^и,у)=0 с уравнением кривой Т|, «1(и,у)=0 дает две точки: <}] и <?2. Только (Ь расположена на Т1 и является точкой

пересечения для Т|)

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

Если линия пересечения /\(иу)=0 разделилась на т кривых пересечения в области определения а линия пересечения разделилась на п кривых пересечения В, в области определения Р2, то результат будет иметь форму таблицы из т строк на п столбцов с элементами у', описывающими, как кривая А, относится к кривой Б1 - например, для рис. 5 таблица отношений примет вид:__

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

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

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

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

они являются конечными точками некоторых сегментов С. Таким образом, если некоторые две точки А и В на кривой С принадлежат Q или R, а точки между А и В на кривой С не принадлежат Q или R, то все сегменты С начинающиеся в точке Л и заканчивающиеся в точке В, будут иметь одинаковый признак «оставить» или «удалить» (рис. 7).

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

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

а)

А / Г" чВ 1Г [г 8 ]

б) А / г- чв Ч V (с в 1

В) А / с- чВ о 3

Рис. 7. Отсечение кривых пересечения границами порций: а- исходные кривые; б-результат работы алгоритма отсечения для левой порции; в-результат работы алгоритма отсечения для правой порции (точки, обозначенные * — эквивалентные

точкам пересечения)

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

Рис. 8. Объединение кривых пересечения: а- найденные кривые пересечения С|-С«; б-С1,Сг,Сз,С; объединены в замкнутую компоненту Ji, С4,С« объединены в

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

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

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

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

Рис. 9. Разрезание порции: три компоненты пересечения (а) делят исходную

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

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

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

Рис. 10. Граф смежности между частями порций объекта:- - смежность по

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

по ребрам, получившимся из компонент пересечения

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

• выбрать любую порцию первого объекта.^/;

• получить точку внутри данной порции;

• определить ее положение относительно внутренней области5.г;

• если точка лежит внутри другого объекта, следовательно, вся порция лежит внутри того объекта, и наоборот, если точка лежит снаружи, значит, и вся порция лежит снаружи другого объекта;

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

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

логической операции:

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

5,.

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

3. Логическое вычитание. Результат составляется из всех порций расположенных снаружи ¿2, и всех порций £3, расположенных внутри

5,.

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

Конец алгоритма модификации, поверхностей. Изменение топологической информации в ходе работы алгоритма представлено на примере объединения двух параллелепипедов (рис. 11).

В шестой главе Тестирование и результаты рассматривается программная реализация разработанных структур данных и алгоритмов в рамках модуля граничного представления объектов геометрического ядра системы моделирования трехмерных объектов «GM-SoШ».

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

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

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

модификации

3. В тестах оценивалось число пересекающихся порций, максимальная степень возникающих кривых пересечения, число обращений к алгоритмам пересечения кривых, поиска и уточнения корней полинома, исключения переменной, а также общее время. Результаты показали устойчивый прирост точности и скорости при работе с простыми примитивами по сравнению с подходом, основанным на приближенном итерационном поиске точек линии пересечения. (Предыдущая разработка кафедры ПГиИ УГТУ - система «GM+»). Однако при работе со сложными объектами степень кривых и поверхностей значительно возрастает, что приводит к замедлению работы. В этом случае необходимы оптимизированные структуры данных и алгоритмы, что составляет направление дальнейших исследований.

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

Рис. 12. Результаты моделирования деталей

Разработанное геометрическое ядро соответствуют своей области применения как «легкого», встраивоемого компонента в готовые, узкоспециализированные системы, с целью дополнить их основными, базовыми возможностями геометрического моделирования, что подтверждается его использованием в составе системы автоматизации проектирования пресс-форм турбинных лопаток для ОЛО «Тюменские моторостроители» и в лаборатории механики деформаций ИМАШ УрО РАН в рамках темы «Разработать математические и компьютерные модели формообразования изделий из металлических материалов при высокотемпературных больших пластических деформациях, обеспечивающих проектирование материалосберегающих технологий № госрег. 01.200.1. 10671» Имеются соответствующие акты о внедрении

ОСНОВНЫЕ ВЫВОДЫ ПО РАБОТЕ

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

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

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

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

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

Выполнена программная реализация разработанных алгоритмов в рамках модуля граничного представления объектов геометрического ядра системы моделирования трехмерных объектов «ОМ-8оНЛ>. Результаты работы алгоритмов модификации граничного представления протестированы на различных геометрических объектах.

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

1. Разработка системы геометрического моделирования объектов сложной формы. Структура данных и некоторые алгоритмы / Р.А.Вайсбурд, Д.Э.Щербаков, Д.В.Куреннов, Е.И.Каменщиков, Л.Г.Лимонов//Трансфертные технологии в информатике. 1999. Вып. 1. С. 72-81.

2. Щербаков Д.Э. Разработка систем геометрического моделирования / Д.Э.Щербаков, А.Р.Саматов// Технология и оборудование современного машиностроения. Уфа. 1998. С. 118.

3. Разработка составляющих системы геометрического моделирования / Е.И.Каменщиков, Д.В.Куреннов, А.ГЛимонов, Д.Э.Щербаков // Технология и оборудование современного машиностроения. Уфа. 1998. С. 120.

4. Щербаков Д.Э. Разработка алгоритмов выполнения логических операций над твердотельными геометрическими объектами САПР//Вестник УГТУ-УПИ. 2000. №3(11). С.121-122.

5. Щербаков Д.Э. Алгоритмы выполнения логических операций над геометрическими объектами САПР//Фундаментальные и прикладные исследования - транспорту 2000: Российская научно-техническая конференция, 15.05.2000.Екатеринбург, 2001.С.72-73

ИД№ 06263 от 12.11.2001 г.

Подписано в печать 20.05.2004. Формат 60x84 Бумага типографская. Плоская печать. Усл. печ. л. 1,39 Уч.-изд. л. 1,4. Тираж 100. Заказ 131. Бесплатно.

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

р 12 9 3 4