Содержание к диссертации
Введение
Глава 1 Постановка задачи и проблемы исследования 13
1.1. Постановка задачи 13
1.2. Возможности синтеза 3D моделей нсплоских объектов в современных графических системах 24
1.2 Л Система автоматизации черчения AutoCAD 25
L2.2 Система моделирования Autodesk Mechanical Desktop
(AMD) и её расширение CADMECH DESKTOP 26
1.2.3 Система Prelude 28
1.2.4 Система Intergraph 29
1.2.5 Система Personal Designer 29
1.2.6 Система твердотельного трёхмерного моделирования КИТЕЖ (НИИ механики ННГУ им. Н.И.Лобачевского, ННГАСУ) 30
1.2.7. Система геометрического моделирования КОМПАС-КЗ.. 31
1.3. Существующие подходы к решению задачи восстановления образа объекта по многовидовому техническому чертежу 36
1.4. Существуюшие подходы и методы преобразования каркасных моделей в граничные модели 52
1.5. Выводы по главе 1 58
Глава 2, Преобразование восстановленной по чертежу каркасной модели 3D объекта в граничную модель 61
2.1. Классы графической информации, регламентированной ЕСКД,. позволяющие восстанавливать 3D образы объектов в случае ортогонального проецирования 61
2.J.1 Изображения 64
2.1.2 Условные обозначения 66
2.2. Этап автоматического создания каркасной модели..», 70
2.2.1 Общая схема формирования каркасной модели 70
2.2.2 Причины возникновения ЛГЭ 78
2.2.3 Область существования множества ЛГЭ . 80
2.2.4 Анализ проекций 86
23. Математическая модель каркаса 90
2.4. Подготовка входной информации 92
2.5. Алгоритм преобразования каркаса 94
2.5.1 Алгоритм построения фундаментальной системы циклов графа 94
2.5.2 Первичная редукция 100
2.5.3 Алгоритм выявления разрешимых аномалий 106
2.5.4 Получение списков граничных моделей, удовлетворяющих исходным проекциям 114
2.6. Выводы по Главе 2 , 116
Глава 3. Практическая реализация алгоритма преобразования каркасной модели в граничную модель 119
3.1.Краткое описание блок-схемы решения общей задачи синтеза моделей по чертежу 119
3.2, Описание блок-схемы алгоритма преобразования предварительной каркасной модели в набор граничных модеей ... 122
3.3. Программная реализация алгоритма 123
преобразования КМ в ГМ . 123
3.4. Выводы по Главе 3 , 135
Заключение 136
Список литературы
- Возможности синтеза 3D моделей нсплоских объектов в современных графических системах
- Система твердотельного трёхмерного моделирования КИТЕЖ (НИИ механики ННГУ им. Н.И.Лобачевского, ННГАСУ)
- Этап автоматического создания каркасной модели..»,
- Описание блок-схемы алгоритма преобразования предварительной каркасной модели в набор граничных модеей
Введение к работе
Академик Б.С- Воинов в монографии «Информационные системы» пишет: «.. .задачи синтеза в соответствии с классификацией теории познания относятся к высшему уровню по своей значимости и сложности в сравнении с задачами анализа. Поэтому подходы к постановке и решению задач синтеза должны составлять одно из приоритетных мест в системных науках, научных и образовательных дисциплинах» [10],
К таким задачам, в частности, относится проблема синтеза геометрических моделей пространственных объектов по его проекциям.
Данная задача известна в начертательной геометрии как обратная задача начертательной геометрии, а в машинной графике - как задача "автоматического чтения" чертежа. До сих пор не доказано утверждение, что рассматриваемая задача может быть решена (или не решена) в общем виде для всего многообразия геометрических элементов, составляющих изображения на поле чертежа.
Как отмечал один из основоположников отечественной машинной графики профессор В.С.Полозов: "Процессы чтения и построения чертежа являются основными в системе графического конструирования. Они обеспечивают возможность построения различных изображений одного и того же объекта...", [40].
Сущность операции проецирования такова, что между двумя изображениями одного и того же объекта стоит его пространственный образ, анализ которого необходим для образования структуры нового изображения. В некоторых моделирующих системах предусмотрен ввод непосредственно пространственного образа. Однако такой ввод неудобен, по крайней мере, по двум причинам [40]:
1). сложность описания пространственного образа по сравнению с описанием его проекций, которые являются естественным и универсальным языком в инженерной графике;
2). трудности мысленного представления и анализа объекта на уровне 3D образа в связи с ограниченностью процесса мышления человека.
Поэтому естественной исходной информацией для алгоритмов построения и чтения чертежа, является некоторый набор проекционных изображений объекта (в частном случае, набор ортогональных видов). Он может быть введён в память ЭВМ, например, средствами 2D пакетов компьютерной графики.
Возможность автоматически восстанавливать образы объектов в процессе автоматического проектирования полностью соответствует современной идеологии С ALS-технологий. Под С ALS-технологиями (Computer Aided Acquisition and Life Cicle Support) понимается совокупность информационных технологий, позволяющих интегрировать в единый комплекс материальные и информационные потоки, существующие на всех этапах существования изделия [83, 101]. Практически на каждом таком этапе, в том или ином виде, генерируется или обрабатывается геометрическая и графическая информация об объекте проектирования и производства. При различных структурах данных и алгоритмах решения задач каждая из составляющих CALS-технологий решает одну и ту же функциональную задачу преобразования размерности пространства [70, 79]. Следовательно, современные системы геометрии и графики, используемые на различных этапах CALS, должны работать одновременно в двух пространствах измерений таким образом, чтобы между моделью объекта (3-х мерное пространство, далее 3D) и его изображением (2-х мерное пространство, далее 2D) была двухсторонняя взаимно однозначная информационная связь (далее 3D <-» 2D).
Подавляющее большинство систем предоставляют только связь 3D-*2D, что существенно ограничивает возможности проектирования.
Актуальность
Для систем геометрии и графики, работающих одновременно в двух пространствах измерений, необходим совершенный алгоритмический аппарат. Наименее разработана алгоритмизация процесса преобразования 2D —> 3D, т.е. задачи автоматического "чтения чертежа". В большинстве разработок под "чертежом" понимается многовидовый технический чертеж.
Так как данная проблема относится к разряду сложных для формализации задач, то её удобно разделять на подзадачи, решение которых может базироваться на определённых методах и подходах. Можно выделить три основных задачи:
Автоматический синтез каркасной модели 3D объекта.
Преобразование каркасной модели в граничную модель.
Визуализация пространственного образа 3D объекта. Каркасная модель (КМ) представляет тело множеством
принадлежащих ему вершин и информацией об их соединении. Граничная модель (ГМ) - множеством отсеков поверхностей, ограничивающих тело.
Как показывает анализ литературы, алгоритмы, реализующие учет всей информации, содержащейся на многовидовом техническом чертеже, до сих пор не разработаны [79]. Поэтому КМ, полученные известными способами автоматического синтеза [40], часто несут в себе ложную геометрическую информацию, что существенно затрудняет дальнейшее преобразование модели и её последующую визуализацию.
Нельзя не учитывать также тот факт, что достаточно часто в реальной работе встречаются неполные чертежи, а также чертежи, изображения объекта на которых выбраны неудачно. Поэтому чертежи, с которыми придётся иметь дело алгоритмам автоматического синтеза объекта, могут быть неоднозначными, допускающими различное толкование.
В связи с этим становится актуальной разработка алгоритмов, позволяющих на этапе создания каркасной модели отфильтровывать ложную геометрическую информацию, а также получать весь набор возможных каркасных моделей, удовлетворяющих исходным проекциям.
Дальнейшее преобразование каркасной модели заключается в необходимости выделить информацию о поверхностях, ограничивающих тело, т.е. получить граничную модель (или набор моделей) объекта.
Этап преобразования каркасной модели в граничную модель является одним из наиболее значимых в задаче восстановления образа объекта и наименее изученным в литературе по рассматриваемой теме. Данный этап является достаточно сложным с точки зрения алгоритмической реализации. Кроме того, на него затрачивается значительное количество времени действия всего алгоритма синтеза.
Алгоритмы построения моделей твердых тел по проекциям, даже с ограничениями на входную информацию, могут находить большое применение в CAD/САМ системах [122], например, в таких областях, как:
синтез моделей проектируемых или изготавливаемых объектов по архивным чертежам;
связь 2D и 3D CAD систем;
создание новых интерактивных инструментальных средств для описания твердых тел в CAD системах.
Таким образом, необходимой является разработка новых подходов к этапу преобразования каркасной модели внутри задачи синтеза объекта по чертежу, с целью повышения эффективности и увеличения быстродействия алгоритма решения этой задачи.
Внедрение подобной технологии будет способствовать скорейшему переходу отечественной промышленности на безбумажную технологию проектирования, производства и сбыта продукции.
Системная характеристика предлагаемого научного направления приведена на рис Л -
Целью работы является:
исследование и разработка методов исключения из каркасной модели, восстановленной по проекциям объекта, ложных геометрических элементов;
исследование и разработка эффективных методов преобразования каркасной модели в граничную модель;
разработка и создание алгоритмов, осуществляющих данные преобразования.
Научная новизна состоит:
в разработанных методах автоматического поиска и удаления ложных геометрических элементов, возникающих в структуре каркасной модели, восстановленной по проекциям, путём моделирования логики рассуждений конструктора при "чтении чертежа";
в разработанном алгоритме преобразования каркасной модели ЗО-объекта в граничную модель, использующем преимущественно топологическую информацию о каркасе;
в разработанных методах автоматического поиска и удаления ложных геометрических элементов, возникающих в процессе преобразования каркасной модели в граничную модель.
Практическая ценность.
Практическая ценность работы, выполненной в рамках фундаментальной НИР «Разработка теоретических основ, алгоритмов и программ геометрии и графики для параллельных технологий проектирования (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет)», состоит в разработке
фрагмента алгоритмических основ новой информационной технологии обработки и преобразования архивной чертежно-конструкторской документации в электронные модели изделий, а также технологии организации банков 3-х мерных объектов на основании ввода их проекций* Практическая ценность работы также состоит в возможности реализации данных алгоритмов средствами целочисленной арифметики ЭВМ.
Апробация.
Материалы диссертации докладывались:
на Международных конференциях по компьютерной геометрии и графике: "Графикон-96", г. Санкт-Петербург, 1996 г,; "Графикон-97", г. Санкт-Петербург, 1997 г.; "Графикон-2002", г. Нижний Новгород, 2002 г.
на Всероссийских семинарах-совещаниях заведующих кафедрами начертательной геометрии и машинной графики вузов РФ, Нижний Новгород, 1996, 1997, 1999;
на Всероссийской конференции по компьютерной геометрии и графике "КОГРАФ-99'\ Нижний Новгород, 1999.
на научно-практических конференциях аспирантов и студентов ННГАСУ, 1996-2000 гг.;
Публикации.
Материалы диссертации изложены в 9 печатных работах,
Тюрина, В.А. Автоматическое определение ложных граней в задаче преобразования каркасной модели пространственного объекта в граничную модель / СИ. Ротков, В.А. Тюрина // Сб. тр. VII межд. науч. конф, по комп. графике и визуализации "Графикон-97". - С.-Петербург, 1997.-т.2,-С 97-101.
Тюрина, В.А. Алгоритм построения фундаментальной системы циклов графа / В.А. Тюрина // Начертат. геометрия» инженерн. и компьютера
графика: Материалы семинара-совещания зав. каф. начертат. геометрии и графики вузов Поволжской зоны РФ. - НЛовгород, 1996. - С.60-63.
Тюрина, В.А. Алгоритм проверки истинности каркаса в задаче преобразования каркасной модели пространственного объекта в граничную модель / В.А. Тюрина // Начертат. геометрия, инженерн. и компьютеры, графика: Материалы семинара-совещания зав. каф. начертат. геометрии, инженерн. и компьютерн. графики вузов Центральной, Поволжской, Южной, Уральской и Северо-западной зон РФ. - Н.Новгород, 1997--С.102-105.
Тюрина, В.А. Алгоритм редукции фундаментальной системы циклов графа, описывающего 3D объект / В.А, Тюрина // КОГРАФ-99: Тез. докл. Всероссийской научно-практ. конф. - Н.Новгород, 1999. -С.67-68,
Тюрина, В.А. Анализ ложных геометрических элементов каркаса в задаче синтеза образа ЗО-объекта по его проекциям. / ВЛ. Тюрина // Архитектура и строительство-2000: Тез. докл. научно-техн. конф. проф.-преподават. состава, докторантов, аспирантов и студентов. — Н.Новгород: ННГАСУ, 2000. - 43. - С. 7-8.
Тюрина, В.А. Информационная модель каркаса трёхмерного геометрического объекта для задачи синтеза 3D объекта по ортогональным проекциям / В.А. Тюрина, СИ. Ротков // Начертат, геометрия, инженерная и компьютерная графика. — Н.Новгород, 1999, — ВыпА-СЛ49-156.
7. Тюрина, В.А, Использование матрицы интерактивности в процессе
преобразования каркасной модели в граничную / В.А. Тюрина //
Строительный комплекс - 96: Тез. докл. науч.-техн, конф. проф.-
преподават. сост. аспирантов и студентов: - Н. Новгород, 1996, - С. 91.
8> Тюрина, В А, Нахождение множества ложных геометрических элементов каркасной модели 3D объекта, восстановленной по трём
неоднозначно читаемым ортогональным проекциям / В.А. Тюрина // Сб. тр. междунар. научи, конф. по комп. графике и визуализации "Графикон-2002'\ - Н. Новгород, 2002. - т.2. - С. 112-116, 9. Тюрина, В.А, Преобразование каркасной модели трёхмерного геометрического объекта в конструктивную модель / В.А. Тюрина, СИ. Ротков // Труды 6-й Меящунар. конф. по комп. графике и визуализации Графикон-96. - С- Петербург, 1996. - С. 56-58.
Струетура диссертации* Диссертация состоит из введения, трёх глав, заключения, списка литературы и двух приложений- В диссертации 170 стр. текста, 40 рис, 4 таблицы- Список использованных литературных источников включает в себя 136 позиций.
Необходимость повышения конкурентоспособности отечественной промышленности на мировых рынках
Интеграция в единый комплекс материальных и информационных потоков, существующих на всех этапах жизненного цикла изделия (CALS-технологии)
Преодоление противоречия между ручной технологией проектирования и современными требованиями CALS-технологий
Переход на безбумажную
технологию проектирования (CAD),
производства (САМ), инженерных
расчетов (САЕ) н сбыта продукции»
Использование накопленных
архивов чертежно-
конструкторской
документации
і
Синтез 3D модели объекта по его проекциям
Раскрыть актуальное научное направление "Разработка методов преобразований каркасной модели в задаче синтеза образа ЗО-объекта по его
проекциям"
1. Исследовать и усовершенствовать
методы преобразований каркасной
моделис целью исключения из её
структуры ложных геометрических
элементов
2. Исследовать и разработать
методы преобразования
каркасной модели в граничную,
использующие преимущественно
топологическую информацию
3. Разработать и создать алгоритмы, позволяющие осуществить данные преобразования средствами целочисленной арифметики ЭВМ
н о в и
В разработанных алгоритмах
автоматического поиска и удаления
ложных геометрических элементов,
возникающих в процессе синтеза
В разработанном алгоритме,
позволяющем осуществить
преобразования каркасной модели 3D-
объекта в граничную преимущественно
на основе топологической информации
РисЛ- Системная характеристика научного направления
Возможности синтеза 3D моделей нсплоских объектов в современных графических системах
Машинную (компьютерную) графику по своим возможностям работать с математическими моделями геометрических фигур разной сложности разделяют на линейную, плоскую и проекционную (или «графику трёхмерных объектов») [53, 60, 71, 73]. Если пакеты двух первых классов (несвязанные системы) получили очень большое развитие, как в теоретическом, так и практическом плане, то, несмотря на большое количество работ в области машинной графики, большая часть проблем проекционной графики не решена полностью [11, 18, 66].
Одной из таких задач, решать которую пытаются многие пакеты проекционной машинной графики, является формирование математической модели трёхмерной геометрической фигуры и ее визуализация. Данная задача включает в себя важную подзадачу, а именно, выбор исходной информации для синтеза проекционных моделей [7].
Рассмотрим некоторые пакеты машинной графики и геометрического моделирования, применяемые для получения 3D образов неплоских объектов, чтобы выяснить, как решается в них эта задача. Также обратим внимание на возможности этих систем генерировать 3D модели по проекционным изображениям.
Мы ограничимся рассмотрением систем, предназначенных для ПЭВМ, так как основные задачи, ими решаемые, в основном совпадают с задачами в системах для рабочих станций [50, 51, 79].
В таблице 1 _ 1 приведены наиболее известные в нашей стране зарубежные системы CAD/CAM/CAE для ПЭВМ, краткая характеристика которых, а также некоторых отечественных систем, дана ниже.
Для получения изображений неплоских объектов применяют переменную, называемую уровнем. Уровень — это задание высоты для плоского примитива- Таким образом, задавая высоту примитивов (операция носит название «выдавливание»), пользователь может отрисовывать трёхмерные объекты, при этом AutoCAD будет правильно удалять невидимые линии [43].
Методы генерации модели также основаны на sweeping-технологии -практическом применении теории определителя геометрической фигуры, т.е. движения образующей линии вдоль направляющей. Поскольку изначально система создавалась для целей визуализации, а не моделирования, то гладкая поверхность заменяется её кусочно-линейной аппроксимацией, что приводит к различным неудобствам при работе с моделью и формировании чертежа.
Система AutoCAD предназначена в основном для формирования чертёжно-конструкторской документации и, в современных версиях, дополнена некоторыми функциями моделирования пространственных объектов. Следует отметить» что такое дополнение различными модулями не может обеспечить полное сохранение принятой идеологии проектирования от трёхмерной модели к проецированию и оформлению чертежа.
Существующие в настоящее время системы 3D проектирования на ПК предоставляют пользователю базовые инструментальные средства и технологию моделирования на основе двухмерных контуров (feature based modeling). Одним из таких программных пакетов является Autodesk Mechanical Desktop (AMD), включающий в себя широко известный AutoCAD Rl ЗС4, Autocad Designer - систему твердотельного параметрического проектирования» AutoSURF - систему моделирования сложных поверхностей, Assembly - модуль сборки и IGES транслятор-Система CADMECH DESKTOP (разработка НЛП "ИНТЕРМЕХ" г.Минск), расширяющая возможности AMD в области конструкторского проектирования позволяет создать трехмерную модель на базе двумерного чертежа, выполненного в AutoCAD. Процесс состоит из трех этапов.
Этап первый. Подготовка двумерного чертежа. Суть данного этапа состоит в выделении на двумерном чертеже детали отдельных видов (проекций) и разрезов 27
В зависимости от отмеченных видов затем рамкой выбора поочередно указываются примитивы, принадлежащие соответствующему виду, и базовая точка вставки вида. После этого чертеж сохраняется средствами AutoCAD.
Этап второй. Создание базовой трехмерной модели. В зависимости от типа создаваемой модели CADMECH использует разные алгоритмы построения. Тип модели определяется пользователем. - вал втулка плоская деталь (детали отличные от валов и втулок)
Все дальнейшие действия по созданию базовой трехмерной модели выполняются системой автоматически. Система сама разделяет двумерный чертеж детали на отдельные проекции, строит максимальный контур каждой проекции, определяет максимальные габариты модели и строит по данным габаритам базовую заготовку, размещает указанные проекции модели на соответствующих гранях базовой заготовки и последовательно выдавливает (либо вращает) проекции на базовой заготовке. В результате всех действий получается трехмерная базовая модель детали. В некоторых случаях полученная базовая модель достаточно точно соответствует окончательной модели, в других случаях базовая модель требует определенной доработки. После завершения выполнения данного этапа кроме базовой модели остаются и двухмерные проекции, расположенные вокруг базовой модели в проекционной связи.
Система твердотельного трёхмерного моделирования КИТЕЖ (НИИ механики ННГУ им. Н.И.Лобачевского, ННГАСУ)
Эвристическое моделирование — это моделирование поведения человека в ходе решения некоторой задачи с целью выявления алгоритма её решения [69J. Достоинство эвристического подхода заключается в том, что в процессе решения задачи происходит подключение жизненного опыта человека.
Структурно-лингвистический подход заключается в эффективном применении для построения моделей процессов языковых моделей и является универсальным для решения трудно формализуемых задач вообще [87].
Выяснив, какие подходы используются для решения задач по систематизации графической информации и её анализу на чертеже, необходимо рассмотреть, по каким принципам могут быть связаны между собой 2D системы машинной графики и 3D системы геометрического моделирования в пространстве [57]. 2D системы, имеющие очень большое распространение, это интерактивные системы, позволяющие вводить двумерную геометрическую и графическую пояснительную алфавитно-цифровую информацию, редактировать её, используя при этом аналитический аппарат геометрических построений на плоскости, а также создавать и хранить в архивной форме типовые изображения для дальнейшего использования в других чертежах. Системы данного класса дают пользователю достаточно удобные средства извлечения информации о геометрии двумерных объектов, используемых как при расчётах, так и при технологической подготовке производства. Заметим, что некоторые возможности 2D систем делают реальным переход к объёмным геометрическим моделям, К таким возможностям относятся: - возможность подготовить данные о координатах точек и топологии их соединения в любом изображении, входящем в состав чертежа; - возможность передачи полученной информации с помощью пре- и постпроцессоров в различные САПР, . 3D системы геометрического моделирования используют подходы, в результате которых синтезируется каркасное, граничное либо конструктивное представление пространственного объекта. Напомним, что в наиболее развитых 3D системах используется обобщённая модель пространственного объекта, включающая в себя информационные массивы, соответствующие всем видам представления объектов, но изначально синтезируется именно каркасная модель, а уже от неё происходит переход к обобщённой модели. Поэтому для решения задачи получения трёхмерных моделей по информации, импортируемой из 2D систем, наиболее предпочтительна каркасная модель [7]- Кроме того, она наиболее удобна именно для импортирования и экспортирования из других систем графики.
Итак, для решения проблемы связи 2D— 3D (проблему связи 3D 2D мы не рассматриваем, т.к. она достаточно изучена), а именно, проблемы синтеза трёхмерных моделей по информации, содержащейся на чертеже проекций объекта (в данном случае ортогональным), и полученной из 2D системы, необходимо извлекать из 2D пакетов машинной графики координаты точек объекта по всем трём осям декартовой системы координат (вершины) и информацию об их соединении (рёбра), а также интерпретировать различную текстовую информацию. Важной задачей здесь является необходимость выбора наиболее подходящих двумерных систем координат для правильного восстановления координат вершин.
Прежде чем перейти к рассмотрению подходов к преобразованию каркасной модели в задаче синтеза необходимо проследить историю решения задачи синтеза 3D моделей объектов по их проекциям у нас в стране и за рубежом.
Заметим вначале, что иностранными авторами предпринимались попытки решить задачу получения каркасной модели иным путём, не используя в качестве посредника 2D системы. Известны работы I.E. Sutherland, посвященные разработке аппаратного и математического обеспечения для «скалывания», В них предложены методы генерирования трёхмерных вершин с помощью скалывания с двух проекций [132]. Работы R.W. Thornton, описывают интерактивную технику трёхмерного ввода с двумерных проекций [134], Но ни тот, ни другой авторы не исследовали алгоритмы восстановления моделей геометрических тел по их проекциям.
Впервые задача восстановления объекта по его проекциям была рассмотрена в работе "Использование математических методов и электр.-вычислит. техники в машиностроении", опубликованной в 1965 году в сборнике трудов ПТИНИИ ВВСНХ в г. Горьком [65]. В ней были описаны схемы алгоритма задачи анализа пространственной ситуации по линиям чертежа- При этом использовалась геометрическая схема производственного чертежа, предложенная B.C. Полозовым в 1962 г. [67], Схема является моделью действий конструктора при формировании многовидового чертежа из ортогональных проекций. На основе информации о линиях проекций производилась оценка взаимного расположения элементов оригинала в пространстве
Этап автоматического создания каркасной модели..»,
Воспользуемся некоторыми понятиями и обозначениями, введенными в книге B.C. Полозова "Алгоритмы машинной графики" [40], а также добавим к ним новые.
Определение 2.2.L1. Назовем М-средой и обозначим как некоторое множество, обладающее свойствами непрерывности, однородности и ограниченной проницаемости для проецирующих лучей и состоящее из точек А таких, что: VAM є С? , 3є 0, что UE (АМ) Є С", где Us (Ам) - окрестность точки AMf гомеоморфная шару. Согласно введенному определению будем рассматривать оригинал, являющийся расширенной моделью физического объекта Фм, Определение 2 2.1.2, 0м — это часть пространства, заполненная Cf4, имеющая определенную форму, размеры и объем, ограниченный от остального пространства. Определение 2.2,1.3. Назовем М-поверхностью и обозначим Пм среду С , состоящую из предельных точек Ам, таких что; VAM є 17м, 3 5 0, что Us (Ам) є IIм, где Us (Ам) окрестность точки, гомеоморфная кругу. Объект Фм допускает над собой следующие операции:
1. Операция сечения Фм, которая выделяет в См с: Фм множество элементов как принадлежащих П , так и не принадлежащих ей, но обладающих свойствами принадлежности некоторой геометрической поверхности сечения.
2. Операция разъединения по поверхности сечения. При этом геометрическая поверхность сечения становится в разъединенных частях поверхностью П .
3. Операция объединения нескольких Фм в один, при котором Пм составляющих оригиналов объединяются в единую Пм, При этом М-точки в области объединения перестают быть предельными и принадлежать Пм.
Основные свойства 1. Всюду замкнут Пм. 2. Любая часть, которая может быть получена операциями сечения и разъединения, обладает свойством: V D1м є Фм, 3 Ам є Фім , для которой ЭШ (Ам) є См . Т.е. любая часть, полученная сечением или разъединением, не может быть Пм, ребром или вершиной. 3. V (Ам є Фм) л (Ам е= Пм), ЗШ (Ам) є См. Можно выделить на множестве Пм точки, обладающие определенными геометрическими свойствами. Определение 2.2.1.4 Геометрическое место точек G є їм, принадлежащих одной и той же геометрической поверхности-носителю S, будем называть гранью. IIм объекта Фм состоит из объединения конечного множества N граней: nM=JGi. I
В таком случае геометрическая поверхность S, представляющая П , является составной поверхностью 3 = 51 uS2 U-..U SN, где S1, S2, ... , SN -геометрические поверхности-носители граней G1, G2, „MG .
Составная поверхность S является геометрической моделью П . Согласно сведениям из геометрии поверхностей [92, 106]: Определение 2.2.1.5. Параметрически заданной поверхностью называется множество S точек A(xt у, z) пространства, декартовы координаты х, yr z которых определяются посредством соотношений; x=x(u,v)ry=y(ur v)tz = z(u,v)r а и Ъ, с v dt где х (ut v)t у (и, v), z (ut v) - функции, непрерывные є прямоугольнике Р = {(u, v) / а и b3 с v Й d } ИЛИ в векторно-матричной форме: y(u,v) i z(u,v)J fx(u,v) , (u,v)eP. S = S(u,v) = Эти соотношения называют параметризацией поверхности S, Определение 2,2,1,6. Поверхность S называется С - гладкой относительно заданной параметризации, если векторная функция S (и, v) является С -гладкой в прям-ке Рг т.е. каждая из функций х (и, v)t у (ut v), z (ur v) имеет в нем непрерывные производные до порядка г включительно. Определение 2.2,1,7, Гладкая параметризация называется регулярной, если вектор Su (u, v) х Sv (и, v) Ф 0, (и, v) є Р
Требование регулярности обеспечивает отсутствие у поверхности ребер [102]. Определение 2.2,1.8, Составная поверхность S = S1 LSS2, гдеS иУ регулярные поверхности, описанные в параметрическом виде S = S (u,v), af u Ъ!, cf v d!, S = S (u,v)t a и b t с v d t такие, что их граничные кривые имеют общий участок, называется Сг-непрерывной.
Определение 2 2,1.9, (f-непрерывная составная поверхность S — SUo называется G -непрерывной, если ее касательная плоскость при переходе через общую кривую изменяется непрерывно.
Описание блок-схемы алгоритма преобразования предварительной каркасной модели в набор граничных модеей
Теоретическое обоснование алгоритма, представленного данной блок-схемой, полностью изложено в Главе 2. Описание алгоритма основано на полу формальном методе Кнута [39] 1 - Проверка на существование ложных геометрических элементов (ЛГЭ) в каркасе KMj (для фиксированного і) (см.пп.2.2,2, 2,2-3 Главы 2). Если ЛГЭ нет, то выполнение п.23 если ЛГЭ есть - п. 3. 2. Основной блок преобразования КМ — ГМ: 2Л. Преобразование данных KMj в одномерные списки (см.п-2.4 Главы 2); 2Л. Формирование ФСЦ (фундаментальной системы циклов) (смл.2.5,1 Главы 2); 2.3. Первичная редукция циклов ФСЦ (см.П-2,5.2 Главы 2); 2.4, Переход к п.4. 3. Формирование массива вариантов каркаса КМц, где j = 1, J; 3.1, Формирование на основе анализа проекций возможных множеств ЛГЭ( (см,п.2.2,4 Главы 2); 3.2. Поочередное удаление множеств ЛГЭ, из предварительного каркаса KMj и формирование элементов массива KMjj (см.пп.2.2.3, 3.3- Выполнение пункта 2 для каждого элемента КМ . 4. Проверка условия существования неразрешимых аномалий (смлі.2.5.3 Главы 2). Если их нет, то в массив граничных моделей ГМік добавляется новый элемент и алгоритм переходит к п.б. Если аномалии есть - выполняется п,5.
Проверка на количество рассмотренных вариантов каркаса КМу для фиксированного і. Если вариант только один или просмотрены все варианты, необходимо редактировать рассматриваемый вариант фрагмента чертежа. Если вариантов несколько и остались нерассмотренные, то берется следующий вариант КМу и для него выполняется п,2,
Проверка на количество рассмотренных вариантов каркаса KMjj для фиксированного і. Если просмотрены все варианты, то выполняется п.7. Если остались нерассмотренные, то берется следующий вариант КМ и для него выполняется п.2,
Проверка на количество рассмотренных фрагментов чертежа. Если рассмотрены не все, то берется очередная предварительная КМу для нового значения индекса і и происходит переход к п Л Если рассмотрены все фрагменты, т.е. массив Tj исчерпан полностью, то массив граничных моделей ГМ для исходного чертежа сформирован полностью (в простейшем случае может быть только одна граничная модель).
Программная реализация алгоритма преобразования КМ в ГМ
Разработанные в Главе 2 алгоритмы реализованы на языке С-ЬК Блок-схема реализованного участка общего алгоритма задачи синтеза описана в п.3.2 и показана на рис.33. Программа под названием KMinGM объединяет функциональные блоки Data и MODEL. 1. Блок Data состоит из двух модулей и предназначен для преобразования предварительной каркасной модели в набор возможных каркасных моделей, удовлетворяющих исходным проекционным видам. 1.1. Модуль LGE осуществляет поиск множеств ложных геометрических элементов каркаса Слгэ 124 1.2, Модуль КМ содержит функции удаления множеств Одгэ из структуры предварительного каркаса и построения массива возможных каркасных моделей искомого объекта 2. Блок MODEL состоит из девяти модулей и предназначен для преобразования каркасной модели в граничную. Каждый модуль выполняет тот или иной шаг алгоритма, либо является вспомогательным. 2.1. Модуль GRAN содержит главную функцию программы main, которая представляет собой наглядное выполнение алгоритма, за счет вызова из нее функций, осуществляющих основные его этапы. 2.2. Модуль GRAF позволяет осуществить ввод данных из файла, с клавиатуры в виде списка структур, либо получить их из блока Data, Затем позволяет перевести эти данные в формат одномерного массива- Кроме того, модуль содержит функцию, строящую структуру графа, состоящего из ребер, инцидентных менее чем двум граням, а также функции, облегчающие работу со списками. 2.3. Модуль KARKAS производит построение остовного дерева с одновременным генерированием системы фундаментальных циклов. 2.4. Модуль CICL содержит функции, предназначенные для работы с ФСЦ графа, задающего объект. 2.5. Модуль REDUC позволяет проводить первичную редукцию ФСЦ графа. 2.6. Модуль ANOMAL содержит функции, осуществляющие преобразования циклов в истинные грани в случае обнаружения аномалий в процессе редукции.
