автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Разработка методов преобразований каркасной модели в задаче синтеза образа 3D-объекта по его проекциям

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

Тюрина Валерия Александровна

РАЗРАБОТКА МЕТОДОВ ПРЕОБРАЗОВАНИЙ КАРКАСНОЙ МОДЕЛИ В ЗАДАЧЕ СИНТЕЗА ОБРАЗА ЗБ-ОБЪЕКТА ПО ЕГО ПРОЕКЦИЯМ

05.01.01 - Инженерная геометрия и компьютерная графика

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

Нижний Новгород - 2003

РАБОТА ВЫПОЛНЕНА В НИЖЕГОРОДСКОМ ГОСУДАРСТВЕННОМ АРХИТЕКТУРНО-СТРОИТЕЛЬНОМ УНИВЕРСИТЕТЕ

\

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

доктор технических наук, профессор Ротков Сергей Игоревич

1

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

доктор технических наук, профессор Кетков Юлий Лазаревич, доктор технических наук, профессор Кучуганов Валерий Никонорович

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

НИИ Механики ННГУ им. Н.И. Лобачевского

Защита состоится 23 декабря 2003 года в 13 часов на заседании диссертационного совета Д 212.162.04 при Нижегородском государственном архитектурно-строительном университете по адресу: 603950, Нижний Новгород, ул. Ильинская, д.65, корпус 5, аудитория 202.

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

Автореферат разослан 2003 г.

Ученый секретарь диссертационного совета, кандидат технических наук, профессор / ' В.И. Дергунов

2«=>о?-А

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

Актуальность темы. «...Задачи синтеза, в соответствии с классификацией теории познания, относятся к высшему уровню по своей значимости и сложности в сравнении с задачами анализа».*

Такой задачей, в частности, является задача синтеза образа пространственного объекта по проекциям.

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

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

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

1) сложность описания пространственного образа по сравнению с

* Воинов, Б С. Информационные системы / Б С. Воинов. — кн I. — Н.Новгород: Изд-во ННГУ им. Н И Лобачевского, 2001. - С. 16

** Котов, ИИ. Алгоритмы машинной графики / ИИ. Котов, ВС. Полозов, Л В Широкова - М: Машиностроение, 1977. - С. 118 ! РОС. НАЦИОНАЛЬНАЯ {

БИБЛИОТЕКА

описанием его проекций, которые являются естественным и универсальным языком в инженерной графике;

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

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

Возможность автоматически восстанавливать образы объектов в процессе автоматизированного проектирования полностью соответствует современной идеологии CALS-технологий. Современные системы геометрии и графики, используемые на различных этапах CALS, должны работать одновременно в двух пространствах измерений, чтобы между моделью объекта и его изображением была двухсторонняя взаимно однозначная информационная связь (далее 3D <-» 2D).

Подавляющее большинство систем предоставляют только связь 3D—>2D, что существенно ограничивает возможности проектирования. Алгоритмизация процесса преобразования 2D—>3D разработана недостаточно. Так как задача относится к разряду трудно формализуемых, то её удобно разделять на подзадачи, решение которых может осуществляться автономно. Можно выделить три основных этапа:

1. Автоматический синтез каркасной модели ЗБ-объекта.

2. Преобразование каркасной модели в граничную модель.

3. Визуализация пространственного образа ЗО-объекта.

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

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

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

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

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

Алгоритмы построения моделей твердых тел по проекциям, даже с ограничениями на входную информацию, могут находить большое применение в САЕ)/САМ-системах, например, в таких областях, как:

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

- связь ТО и ЗБ САО-систем;

- создание новых интерактивных инструментальных средств для описания моделей твёрдых тел в САЛ)-системах.

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

Целью диссертационной работы является:

- исследование и разработка методов исключения ложных геометрических элементов из каркасной модели, восстановленной по проекциям объекта;

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

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

Предметом исследования является процесс преобразований каркасной модели в задаче автоматического синтеза ЗБ-объекта по проекциям.

Научная новизна состоит:

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

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

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

Практическая значимость диссертационного исследования, выполненного в рамках фундаментальной НИР «Разработка теоретических основ, алгоритмов и программ геометрии и графики для параллельных технологий проектирования (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет)», состоит в

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

На защиту выносятся:

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

- топологический метод преобразования каркасной модели в граничную модель в задаче синтеза образа ЗО-объекта по проекциям;

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

Апробация работы. Основные результаты диссертационного исследования были опубликованы в 9 научных работах и докладывались:

- на Международных конференциях по компьютерной геометрии и графике: "Графикон-96", г. Санкт-Петербург, 1996 г.; "Графикон-97", г. Санкт-Петербург, 1997 г.; "Графикон-2002", г. Нижний Новгород, 2002 г.

- на Всероссийских семинарах-совещаниях заведующих кафедрами начертательной геометрии и машинной графики вузов РФ, Нижний Новгород, 1996,1997,1999;

- на Всероссийской конференции по компьютерной геометрии и графике "КОГРАФ-99", Нижний Новгород, 1999.

- на научно-практических конференциях аспирантов и студентов ННГАСУ, 1996-2000 гг.;

Публикации. Материалы диссертации опубликованы в 9 статьях.

Структура и объём диссертации. Диссертация состоит из введения, трёх глав, заключения, списка используемой литературы и двух приложений, общим объёмом 170 страниц, в том числе 152 страницы основного текста, 40 рис., 4 таблицы. Список использованных литературных источников включает в себя 136 позиций.

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

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

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

Рассмотрены возможности синтеза ЗЭ-моделей неплоских объектов в современных графических системах. Проведён обзор ряда существующих систем машинной графики и геометрического моделирования для выяснения наиболее перспективного типа исходной информации для синтеза. Выяснено, что наиболее близкий к инженерному подходу сценарий ввода исходной информации позволяет моделировать объект по трём «прозрачным» ортогональным проекциям. Такой исходной информации не всегда достаточно для синтеза единственно верного трёхмерного образа объекта, поэтому алгоритм синтеза по проекциям должен учитывать возможность мультипликативных решений. Сделан вывод, что целесообразно получать исходную информацию из пакетов автоматизации черчения (AutoCAD, КОМПАС-ГРАФИК и другие).

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

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

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

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

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

Определение 1. Каркасной моделью (КМ) геометрического объекта называется совокупность КМ = { V, Ы, А }, где V - вектор координат (Х„У„г,) вершин объекта, где 1 = 1,...,п; Л - информационный массив, содержащий данные о ребрах соединяющих вершины V, и V, объекта; А - информационный массив атрибутов вершин V, и ребер II,г

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

Определение 2. Граничной моделью (ГМ) пространственного объекта называется совокупность ГМ = { в, V, Н, А }, где V, Я -информационные массивы, используемые в КМ, С - информационный массив граней, где ¡-тый элемент массива в, = {(Ун, У2„ Уз„ ...УП1) е Р„ где Б; 6 Б, а Уц,..., Уш е V} задаётся своими вершинами, перечисленными в порядке обхода грани против часовой стрелки, начиная с произвольно • выбранной вершины; А - информационный массив атрибутов вершин V,, ребер Яу и граней в,, в который входят массивы: ¥ - содержащий коэффициенты уравнений поверхностей-носителей граней в,; Ь - массив, содержащий коэффициенты уравнений линий-носителей рёбер Остальными атрибутами могут быть те же признаки, что и в КМ, а также текстура (материал покрытия и раскраски) граней поверхности и т.п.

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

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

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

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

Описываются классы графической информации,

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

1. Расширение классов графической информации, доступной для обработки;

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

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

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

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

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

- поверхность оригинала Пм, состоящая из предельных точек Фм;

- множества точек, обладающих на Пм определенными геометрическими свойствами, а именно:

1. множество граней С оригинала Фм (в, е поверхности 8^;

2. множество рёбер К оригинала Фм (11к€ ( в, г> в,));

3. множество вершин V оригинала Фм (V) е в, п в, п.. .п вт).

Поверхность Пм оригинала Фм состоит из объединения

N

конечного множества граней: Пм = У в!. Геометрической моделью Пм,

является непрерывная составная поверхность 8 = 81 и в2 и...и в", где в1, 82,... ,8м-геометрические поверхности-носители граней в1, в2,..., См .

Ребра делятся на конструктивные И" и неконструктивные Ян.

Определение 3. Конструктивным ребром 11* называется линия поверхности тела, при переходе через которую уравнение касательной плоскости терпит разрыв, т.е. поверхность является С?-поверхностью (нарушается гладкость).

Определение 4. Неконструктивным ребром Я" называется линия поверхности тела, при переходе через которую уравнение касательной плоскости изменяется непрерывно, т.е. составная поверхность является как минимум О1 -поверхностью.

Среди неконструктивных ребер И" выделены типы касательных и очерковых ребер.

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

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

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

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

| вырожденные). На проекциях к этим элементам добавляются линии

| очерка. Их образы могут совпадать с рёбрами Фм или, в случае

| криволинейных граней, появляться как новые очерковые рёбра.

I Существуют разработанные процедуры автоматического получения

информации о координатах вершин, их возможных соединениях (рёбрах) , и уравнениях несущих линий по проекциям. Таким образом, множества V,

I

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

Касательные Кн рёбра не вызывают видимого клеточного разбиения оригинала и не попадают на проекции. Но для того, чтобы выделить из структуры оригинала множество в (которое в дальнейшем войдёт в структуру граничной модели ГМ), они должны быть восстановлены по геометрическим признакам и добавлены в структуру КМ. Касательные Лн рёбра выявляются наличием на проекциях точек сопряжения дуг, имеющих отличные друг от друга уравнения геометрических носителей. Анализируя эти точки на всех видах, строятся и добавляются в КМ дополнительные вершины и ребра, которые позволяют максимально приблизить КМ к реальному клеточному разбиению Фм.

Итак, в общем случае на начальном этапе синтеза от реального клеточного разбиения оригинала Фм каркасную модель отличает присутствие очерковых ребер, разбивающих некоторые грани на р несколько, а также присутствие ложных геометрических элементов (ЛГЭ).

Определение 7. Под ложными геометрическими элементами (ЛГЭ) \ каркаса будем понимать такие его элементы (рёбра и вершины), которые

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

Далее сформулированы причины возникновения ЛГЭ:

■ существование конкурирующих геометрических элементов;

■ недостаточное количество проекций;

■ при ортогональном проецировании:

- неудачный выбор видов,

- недостаточное количество видов;

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

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

Далее рассмотрена область существования множества ЛГЭ СдГЭ и предложен алгоритм нахождения подмножеств Одрз этого множества.

Так как в алгоритме используется только топологическая информация, то для формального описания каркасной модели использовался такой математический объект как граф: в = (V, К), где V -множество вершин, а Я - множество рёбер каркаса.

Ск = (Ук, Як)-подграф С, задающий множество всех конкурирующих элементов каркаса. Доказаны следующие утверждения:

Утверждение 1. ОдрЭ является подмножеством множества всех конкурирующих элементов восстановленных с проекций, т.е. <

^лгэ

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

элементов О дрэ будет своим, но Одгэ'-^'к.- Целью является выделение

подмножеств ОдГЭ из ОдГЭ, для получения всех возможных образов

I, оригинала. Множество Ок во многих случаях может содержать большое

число элементов, поэтому простой перебор всех сочетаний С^, » принадлежащих ему элементов, который выражается суммой:

п п д!

Л С' = X-, где п - число элементов в к, нецелесообразен,

1=1 ¡=1 (пЧ)Ш

хотя возможен, как один из вариантов решения данной задачи.

Найден ряд эвристик, позволяющих сократить во множестве Ск область поиска ОдрЭ •

Утверждение 2. ЛГЭ могут находиться только среди элементов, имеющих конкурирующие элементы на каждом проекционном виде.

Определение 8. Множество Си, состоящее из таких ребер и вершин, которые не имеют конкурирующих элементов хотя бы в одном проецирующем направлении, будем называть множеством истинных геометрических элементов (ИГЭ).

Утверждение 3. Если ребро й е Си, мо м вершины, инцидентные ему е Ои.

Утверждение 4. Если у ребра Я конечные точки у е Си и * валентность этих вершин Р ( УЦ) = 3, то и Я еОи.

Утверждения 2, 3, 4 позволяют существенно сокращать область » существования ЛГЭ. Исключив множество Ои из множества

получаем его подмножество Ок, т.е.: Ок=(Ок\Ои).

Дальнейший поиск СЗдрЭ проводится в этом подмножестве.

I

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

элементов проекций, что моделирует мыслительную деятельность I

конструктора во время "чтения чертежа". |

Далее описан этап преобразования освобожденной от ЛГЭ каркасной |

модели в граничную модель. Описана математическая модель каркаса, I

дополняющая опр.1, с целью уточнения входных данных алгоритма 7

преобразования КМ—»ГМ. В частности, уточнён массив атрибутов ,

А = {Ау, Ал, Аь Акм} - множество атрибутов, содержащее массивы: Ау = {Ау| = Р, где Р - валентность вершины; I = 1...Ыу }- массив атрибутов вершин;

Ал= {Аис = {0, 1,-1}, где 0 - конструктивное ребро, 1 - очерковое ребро, -1 - касательное ребро; к = 1 } - массив атрибутов рёбер. Аь = {Ц = (Х/1), 2ДО) е Я3, Т0, < I < 1-, Ац - атрибут, j = -

множество несущих линий;

Акм = {У*км, Я*км}, V* км = <Л .Ь • ■ к), где j, к - номера вершин из V,

I

И.* км = (I, т, ..., р), где г, ш, р - номера рёбер из Л, а КМ= 1...М, где М -количество возможных вариантов каркасов, удовлетворяющих исходным |

проекциям} - атрибут каркаса.

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

Предлагается хранить топологическую информацию в списке I

следующего вида: {У| - вершина из У, Ю - валентность вершины, Уи> — » Ум - набор смежных ей вершин из V, где к = 1...К!? { = 1...Р}у}- I

Доказаны преимущества такого способа хранения информации по сравнению с традиционным способом хранения информации в виде ,

матрицы смежности. Основной алгоритм преобразования КМ—>ГМ использует только топологическую информацию.

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

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

Алгоритм преобразования КМ—>ГМ делится на несколько этапов: 1 шаг. Выделение из структуры каркаса топологической информации о неориентированном графе, представляющем каркас (рис.1);

3 шаг. Процесс преобразования (редукции) ФСЦ в истинные грани с одновременным поиском и удалением ложных геометрических элементов;

4 шаг. Построение замыкающей грани объекта;

5 шаг. Формирование структуры граничной модели.

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

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

Ю 11 12 13

2 шаг. Генерирование фундаментальной системы циклов графа;

4

3

ппрпгтяттсппшАт 1ГЛД

Рис. 1. Пример графа,

Рис. 2. Пример построенного остовного дерева. «Крестиками» помечены ребра, на основе которых генерируется ФСЦ графа

В основе алгоритма построения ФСЦ лежат следующие факты, доказанные в теории графов:

■ Число ребер, которое нужно удалить из конечного связного графа, чтобы получить остовное дерево, равно его цикломатическому числу:

к = кЕ - ку + 1;

■ добавление к остовному дереву хотя бы одного ребра приводит к появлению цикла. Следовательно, число циклов в ФСЦ = к.

Разработанный алгоритм соединяет процесс генерирования остовного дерева с процессом формирования набора циклов. На рис.3 приведён пример ФСЦ, построенной для КМ, показанной на рис.1.

11

9 8 1

Рис. 3. Пример ФСЦ графа

Следующий этап: преобразование (редукция) ФСЦ в набор истинных граней. Входные данные - список циклов, имеющий следующую структуру: {С| - цикл из ФСЦ, М) - число ребер в цикле, У115..., Уы - набор вершин, составляющих цикл, где к = 1 ... М(, 1 = 1 ... N0, N0 - число циклов в ФСЦ}.

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

* Процесс редукции использует операцию строгой дизъюнкции. Для двух графов 01 и а, строгая дизъюнкция - это граф, состоящий из рёбер,

- которые есть или в или в 02, но ни в том и другом вместе.

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

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

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

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

Процесс редукции эффективен при использовании матрицы взаимодействия рёбер У7Ы между циклами ФСЦ.

Это симметричная матрица пхп, где п - число циклов в фундаментальной системе. Каждый элемент матрицы содержит число рёбер, общих для циклов в, и в, . Диагональный элемент [1, ¡] содержит число рёбер в цикле в,. Пример работы с матрицей ~Ч7М для ФСЦ,

* построенной для каркаса с рис. 1, показан на рис.4.

Описан ряд тестов, позволяющих контролировать процесс редукции.

^ Чтобы проверить полезность редуцирования (сжатия) цикла в, проводится

тест, который показывает, будет ли цикл О, иметь меньше рёбер после дизъюнкции, чем до неё.

Тест 1: полезность редуцирования: < 2*\ЪШ [Щ.

Следующий, более общий тест, определяет необходимость редукции.

© 2 3 4 (5) 6 7 8 9

1 4 0 1 0 3' 0 1 3° 2

2 0 4 1 1 0° 0 1 0° 1

3 1 1 3 0 1° 0 0 1° 1

4 0 1 0 4 0° 1 1 0° 2

II диз. 3' 0° Г 0" 6' 0" 2' 5' Г

6 0 0 0 1 0° 4 1 0° 2

7 1 1 0 1 2' 1 7 3' 2

I диз. (§) 31 0° 1° 0° 5' 0° 3' 4'

9 2 1 1 2 1' 2 2 4' 9

Рис. 4. Пример работы с матрицей взаимодействия между циклами

Тест 2: необходимость редукции: новая сумма чисел взаимодействия

п н п

циклов должна быть не больше старой:

к=1 к=1

Процесс редукции выполняется стиранием общих ребер у С, и GJ в

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

Тест 3 позволяет досрочно закончить процесс редукции, если каждое ребро встречается только в двух циклах. Если же редукция пройдена полностью, а данный тест даёт отрицательный результат (как в примере на рис.5, а), то это сигнализирует о том, что имеются аномалии, т.е. требуется дальнейшая обработка ФСЦ графа. В рассматриваемом примере получены 8 циклов, описывающие границы истинных граней объекта и цикл 9, пока не представляющий истинную грань.

Далее приведена классификация разрешимых аномалий, описаны алгоритмы выявления ложных граней и замены их истинными, а также алгоритм нахождения замыкающей грани (рис.5, б).

I (

.ф:

9 8

©

Рис. 5. Работа с циклами:

а) пример ФСЦ, прошедшей первичную редукцию;

б) изменённый цикл 9 и цикл 10, представляющий замыкающую грань.

В конце алгоритма проводится тест 4, проверяющий, действительно ли для

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

п

его с другими циклами. Тест 4: VZM[i, к] = УгМ[М].

к=1

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

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

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

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

преобразования. Описывается программа КМтвМ, реализующая преобразование каркасной модели.

Программа объединяет два функциональных блока:

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

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

Приведены тестовые примеры работы программы (один из них показан на рис.6, 7, 8).

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

Приложение 1 содержит Акт о внедрении результатов работы.

Приложение 2 содержит фрагменты программы, написанной на языке программирования высокого уровня С++.

J_I

71

I I I I I I I I I

"7

а) вид спереди

б) вид сверху

с) вид слева

Рис.6. Проекционные виды объекта, взятого в качестве тестового примера

Рис.7. Каркасная модель, включающая 4 компоненты связности: кол-во рёбер I комп. = 132, кол-во рёбер П комп. = 20, кол-во рёбер III комп. = 18, кол-во рёбер IV комп. = 18

Рис.8. Визуализация полученной конструктивной модели (в основе лежат 4 граничных модели) средствами системы Компас ЗЭ 5.11. Кол-во граней IГМ = 38, кол-во граней II ГМ = 10, кол-во граней III ГМ = 8, кол-во граней IV ГМ = 8, общее кол-во граней = 58

Основные выводы I

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

пока не разработаны. Поэтому необходимо разрабатывать метода, *

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

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

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

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

а

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

Содержание диссертации отражено в следующих работах:

1. Тюрина, В.А. Автоматическое определение ложных граней в задаче преобразования каркасной модели пространственного объекта в граничную модель / С.И. Ротков, В.А. Тюрина // Сб. тр. VII межд. науч. конф. по комп. графике и визуализации "Графикон-97". - С.-Петербург,

* 1997.-Т.2.-С. 97-101.

2. Тюрина, В.А. Алгоритм построения фундаментальной системы циклов графа / В.А. Тюрина // Начертат. геометрия, инженерн. и компьютерн.

i

, графика: Материалы семинара-совещания зав. каф. начертат. геометрии

i

и графики вузов Поволжской зоны РФ. - Н. Новгород, 1996. - С. 60-63.

3. Тюрина, В.А. Алгоритм проверки истинности каркаса в задаче преобразования каркасной модели пространственного объекта в граничную модель / В.А. Тюрина // Начертат. геометрия, инженерн. и компьютерн. графика: Материалы семинара-совещания зав. каф. начертат. геометрии, инженерн. и компьютерн. графики вузов Центральной, Поволжской, Южной, Уральской и Северо-западной зон РФ. - Н. Новгород, 1997. - С.102-105.

4. Тюрина, В.А. Алгоритм редукции фундаментальной системы циклов графа, описывающего ЗО-объект / В.А. Тюрина // КОГРАФ-99: Всероссийская научно-практ. конф.: Тез. докл., - Н. Новгород, 1999. -С.67-68.

*

5. Тюрина, В.А. Анализ ложных геометрических элементов каркаса в задаче синтеза образа ЗО-объекта по его проекциям. / В.А. Тюрина //

к

Архитектура и строительство-2000: Науч.-техн. конф. проф,-преподават. состава, докторантов, аспирантов и студентов: Тез. докл., -Н. Новгород: ННГАСУ, 2000. - Ч.З. - С. 7-8.

6. Тюрина, В.А. Информационная модель каркаса трёхмерного геометрического объекта для задачи синтеза ЗО-объекта по

ортогональным проекциям / В.А. Тюрина, С.И. Ротков // Начертат. геом., инженерн. и компьютерн. графика. - Н. Новгород, 1999. - Вып.4. -С. 99-107.

7. Тюрина, В.А. Использование матрицы интерактивности в процессе * преобразования каркасной модели в граничную / В.А. Тюрина // Строительный комплекс - 96: Науч.-техн. конф. проф.-преподават.

состава аспирантов и студентов: Тез. докл. - Н.Новгород, 1996. - С. 91.

8. Тюрина, В.А. Нахождение множества ложных геометрических элементов каркасной модели ЗО-объекта, восстановленной по трём неоднозначно читаемым ортогональным проекциям / В.А. Тюрина П Сб. тр. междунар. научн. конф. по комп. графике и визуализации "Графикон-2002". - Н. Новгород, 2002. - т.2. - С. 112-116.

9. Тюрина, В.А. Преобразование каркасной модели трёхмерного геометрического объекта в конструктивную модель / В.А. Тюрина, С.И. Ротков // Труды 6-й Междунар. конф. по комп. графике и визуализации Графикон-96. - С.- Петербург, 1996. - С. 56-58.

<

ЛР№ 020823 от 21.09.98 Подписано к печати 8.11.2003г. Формат 60 х 90 1/16. Бумага писчая. Печать офсетная.

Объем 1 печ. л. Тираж 100 экз. Заказ № 0.17 Нижегородский государственный архитектурно-строительный университет, 603950, Н.Новгород, Ильинская, 65.

Полиграфцентр ННГАСУ, 603950, Н. Новгород, Ильинская, 65.

l fééo

» 196 60

Введение.

Глава 1. Постановка задачи и проблемы исследования.

1.1. Постановка задачи.

1.2. Возможности синтеза 3D моделей неплоских объектов в современных графических системах.

1.2.1 Система автоматизации черчения AutoCAD.

1.2.2 Система моделирования Autodesk Mechanical Desktop (AMD) и её расширение CADMECH DESKTOP.

1.2.3 Система Prelude.

1.2.4 Система Intergraph.

1.2.5 Система Personal Designer.

1.2.6 Система твердотельного трёхмерного моделирования КИТЕЖ (НИИ механики ННГУ им. Н.И.Лобачевского,

ННГАСУ).

1.2.7. Система геометрического моделирования КОМПАС-КЗ

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

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

1.5. Выводы по главе 1.

Глава 2. Преобразование восстановленной по чертежу каркасной модели

3D объекта в граничную модель.

2.1. Классы графической информации, регламентированной ЕСКД,. позволяющие восстанавливать 3D образы объектов в случае ортогонального проецирования.

2.1.1 Изображения.

2.1.2 Условные обозначения.

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

2.2.1 Общая схема формирования каркасной модели.

2.2.2 Причины возникновения ЛГЭ.

2.2.3 Область существования множества ЛГЭ.

2.2.4 Анализ проекций.

2.3. Математическая модель каркаса.

2.4. Подготовка входной информации.

2.5. Алгоритм преобразования каркаса.

2.5.1 Алгоритм построения фундаментальной системы циклов графа.

2.5.2 Первичная редукция.

2.5.3 Алгоритм выявления разрешимых аномалий.

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

2.6. Выводы по Главе 2.

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

3.1. Краткое описание блок-схемы решения общей задачи синтеза моделей по чертежу.

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

3.3. Программная реализация алгоритма. преобразования КМ в ГМ.

3.4. Выводы по Главе 3.

Академик Б.С. Воинов в монографии «Информационные системы» пишет: «.задачи синтеза в соответствии с классификацией теории познания относятся к высшему уровню по своей значимости и сложности в сравнении с задачами анализа. Поэтому подходы к постановке и решению задач синтеза должны составлять одно из приоритетных мест в системных науках, научных и образовательных дисциплинах» [10].

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

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

Как отмечал один из основоположников отечественной машинной графики профессор В.С.Полозов: "Процессы чтения и построения чертежа являются основными в системе графического конструирования. Они обеспечивают возможность построения различных изображений одного и того же объекта.", [40].

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

1). сложность описания пространственного образа по сравнению с описанием его проекций, которые являются естественным и универсальным языком в инженерной графике;

2). трудности мысленного представления и анализа объекта на уровне 3D образа в связи с ограниченностью процесса мышления человека.

Поэтому естественной исходной информацией для алгоритмов построения и чтения чертежа, является некоторый набор проекционных изображений объекта (в частном случае, набор ортогональных видов). Он может быть введён в память ЭВМ, например, средствами 2D пакетов компьютерной графики.

Возможность автоматически восстанавливать образы объектов в процессе автоматического проектирования полностью соответствует современной идеологии CALS-технологий. Под CALS-технологиями (Computer Aided Acquisition and Life Cicle Support) понимается совокупность информационных технологий, позволяющих интегрировать в единый комплекс материальные и информационные потоки, существующие на всех этапах существования изделия [83, 101]. Практически на каждом таком этапе, в том или ином виде, генерируется или обрабатывается геометрическая и графическая информация об объекте проектирования и производства. При различных структурах данных и алгоритмах решения задач каждая из составляющих CALS-технологий решает одну и ту же функциональную задачу преобразования размерности пространства [70, 79]. Следовательно, современные системы геометрии и графики, используемые на различных этапах CALS, должны работать одновременно в двух пространствах измерений таким образом, чтобы между моделью объекта (3-х мерное пространство, далее 3D) и его изображением (2-х мерное пространство, далее 2D) была двухсторонняя взаимно однозначная информационная связь (далее 3D <-> 2D).

Подавляющее большинство систем предоставляют только связь 3D->2D, что существенно ограничивает возможности проектирования.

Актуальность

Для систем геометрии и графики, работающих одновременно в двух пространствах измерений, необходим совершенный алгоритмический аппарат. Наименее разработана алгоритмизация процесса преобразования 2D —> 3D, т.е. задачи автоматического "чтения чертежа". В большинстве разработок под "чертежом" понимается многовидовый технический чертеж.

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

1. Автоматический синтез каркасной модели 3D объекта.

2. Преобразование каркасной модели в граничную модель.

3. Визуализация пространственного образа 3D объекта.

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

Как показывает анализ литературы, алгоритмы, реализующие учет всей информации, содержащейся на многовидовом техническом чертеже, до сих пор не разработаны [79]. Поэтому КМ, полученные известными способами автоматического синтеза [40], часто несут в себе ложную геометрическую информацию, что существенно затрудняет дальнейшее преобразование модели и её последующую визуализацию.

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

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

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

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

Алгоритмы построения моделей твердых тел по проекциям, даже с ограничениями на входную информацию, могут находить большое применение в CAD/CAM системах [122], например, в таких областях, как:

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

- связь 2D и 3D CAD систем;

- создание новых интерактивных инструментальных средств для описания твердых тел в CAD системах.

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

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

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

Целью работы является:

- исследование и разработка методов исключения из каркасной модели, восстановленной по проекциям объекта, ложных геометрических элементов;

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

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

Научная новизна состоит:

- в разработанных методах автоматического поиска и удаления ложных геометрических элементов, возникающих в структуре каркасной модели, восстановленной по проекциям, путём моделирования логики рассуждений конструктора при "чтении чертежа";

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

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

Практическая ценность.

Практическая ценность работы, выполненной в рамках фундаментальной НИР «Разработка теоретических основ, алгоритмов и программ геометрии и графики для параллельных технологий проектирования (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет)», состоит в разработке фрагмента алгоритмических основ новой информационной технологии обработки и преобразования архивной чертежно-конструкторской документации в электронные модели изделий, а также технологии организации банков 3-х мерных объектов на основании ввода их проекций. Практическая ценность работы также состоит в возможности реализации данных алгоритмов средствами целочисленной арифметики ЭВМ.

Апробация.

Материалы диссертации докладывались:

- на Международных конференциях по компьютерной геометрии и графике: "Графикон-96", г. Санкт-Петербург, 1996 г.; "Графикон-97", г. Санкт-Петербург, 1997 г.; "Графикон-2002", г. Нижний Новгород, 2002 г.

- на Всероссийских семинарах-совещаниях заведующих кафедрами начертательной геометрии и машинной графики вузов РФ, Нижний Новгород, 1996, 1997, 1999;

- на Всероссийской конференции по компьютерной геометрии и графике "КОГРАФ-99", Нижний Новгород, 1999.

- на научно-практических конференциях аспирантов и студентов ННГАСУ, 1996-2000 гг.;

Публикации.

Материалы диссертации изложены в 9 печатных работах.

1. Тюрина, В.А. Автоматическое определение ложных граней в задаче преобразования каркасной модели пространственного объекта в граничную модель / С.И. Ротков, В.А. Тюрина // Сб. тр. VII межд. науч. конф. по комп. графике и визуализации "Графикон-97". - С.-Петербург, 1997.-Т.2.-С. 97-101.

2. Тюрина, В.А. Алгоритм построения фундаментальной системы циклов графа / В.А. Тюрина // Начертат. геометрия, инженерн. и компьютерн. графика: Материалы семинара-совещания зав. каф. начертат. геометрии и графики вузов Поволжской зоны РФ. - Н.Новгород, 1996. - С.60-63.

3. Тюрина, В.А. Алгоритм проверки истинности каркаса в задаче преобразования каркасной модели пространственного объекта в граничную модель / В.А. Тюрина // Начертат. геометрия, инженерн. и компьютерн. графика: Материалы семинара-совещания зав. каф. начертат. геометрии, инженерн. и компьютерн. графики вузов Центральной, Поволжской, Южной, Уральской и Северо-западной зон РФ. - Н.Новгород, 1997. - С.102-105.

4. Тюрина, В.А. Алгоритм редукции фундаментальной системы циклов графа, описывающего 3D объект / В.А. Тюрина // КОГРАФ-99: Тез. докл. Всероссийской научно-практ. конф. - Н.Новгород, 1999. -С.67-68.

5. Тюрина, В.А. Анализ ложных геометрических элементов каркаса в задаче синтеза образа ЗО-объекта по его проекциям. / В.А. Тюрина // Архитектура и строительство-2000: Тез. докл. научно-техн. конф. проф.-преподават. состава, докторантов, аспирантов и студентов. — Н.Новгород: ННГАСУ, 2000. - Ч.З. - С. 7-8.

6. Тюрина, В.А. Информационная модель каркаса трёхмерного геометрического объекта для задачи синтеза 3D объекта по ортогональным проекциям / В.А. Тюрина, С.И. Ротков // Начертат. геометрия, инженерная и компьютерная графика. — Н.Новгород, 1999. — Вып.4. - С. 149-156.

7. Тюрина, В.А. Использование матрицы интерактивности в процессе преобразования каркасной модели в граничную / В.А. Тюрина // Строительный комплекс - 96: Тез. докл. науч.-техн. конф. проф.-преподават. сост. аспирантов и студентов: - Н. Новгород, 1996. - С. 91.

8. Тюрина, В.А. Нахождение множества ложных геометрических элементов каркасной модели 3D объекта, восстановленной по трём неоднозначно читаемым ортогональным проекциям / В.А. Тюрина // Сб. тр. междунар. научн. конф. по комп. графике и визуализации "Графикон-2002". - Н. Новгород, 2002. - т.2. - С. 112-116. 9. Тюрина, В.А. Преобразование каркасной модели трёхмерного геометрического объекта в конструктивную модель / В.А. Тюрина, С.И. Ротков // Труды 6-й Междунар. конф. по комп. графике и визуализации Графикон-96. - С.- Петербург, 1996. - С. 56-58.

Структура диссертации. Диссертация состоит из введения, трёх глав, заключения, списка литературы и двух приложений. В диссертации 170 стр. текста, 40 рис., 4 таблицы. Список использованных литературных источников включает в себя 136 позиций.

3.4. Выводы по Главе 3

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

2. Показано место решаемой в работе задачи преобразований КМ в общей задаче синтеза. Предложена подробная блок-схема данного процесса.

3. Сделан вывод, что дальнейшее развитие представленных в работе алгоритмов и объединение программного блока, реализующего этап преобразования КМ—>ГМ, с блоком автоматического синтеза КМ позволит одновременно решать две, поставленные в Главе 2, задачи, направленные на разрешение проблемы «автоматического чтения чертежа», а именно:

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

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

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

Заключение

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

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

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

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

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

1. Анапрейчик, К.К. Интерактивное графическое пространственное проектирование объемных тел методом свободного формообразования: Автореф. дис. . канд. техн. наук. / К.К. Анапрейчик — Киев, 1990. — 22 с.

2. Апресян, Ю.Д. Лексическая семантика. Семиотические средства языка / Ю.Д. Апресян. М.: Наука, 1974. 366 с.

3. Аристова, Е.В. КИТЕЖ — система геометрии и графики пространственных объектов / Е.В. Аристова, А.А. Зудин, С.В. Митин, С.И. Ротков, В.П. Шубин // Сб. тезисов 5-ой Всесоюзной конференции по проблемам машинной графики. Новосибирск, 1989.

4. Аристова, Е.В. Модуль стереолитографии для системы геометрического моделирования КИТЕЖ / Е.В. Аристова, С.Е. Лабутин, С.В. Митин, В.П. Шубин // Сб. трудов 4-ой Междунар. конф. по комп. графике и визуализации ГРАФИКОН-94. Н. Новгород, 1994. - С. 71 - 72.

5. Аристова, Е.С. КЗ: профессионалам — профессиональные персональные инструменты. Конструкторские и дизайнерские системы на базе КЗ фирмы Теос" / Е.С. Аристова, С.В. Митин, Е.В. Попов, В.В. Розанов, А.И. Тарасов // САПР и Графика. 2000. - № 4, С. 53 - 57.

6. Балабан, О.М. Интерфейс 2D-3D в графических системах: Автореф. дис. . канд. техн. наук: 05.01.01. / О.М. Балабан. Н. Новгород, 1995. - 21 с.

7. Баяковский, Ю.М. Стандарты на передачу геометрической информации между системами автоматизированного проектирования / Ю.М. Баяковский, В.А. Галактионов, В.А. Галатенко, Т.Н. Михайлова, И.Г.

8. Рыжова, А.Б Ходулев // Зарубежная радиоэлектроника. — 1987. т.8. -С. 42 - 52. - ISSN 0373-2428.

9. Бронштейн, И.Н. Справочник по математике / И.Н. Бронштейн, К. А. Семендяев.— М.: Гос. Изд. Физ.-мат. лит-ры, 1962. 491 с.

10. Ю.Воинов, Б.С. Информационные системы / Б.С. Воинов.— книга I — Нижний Новгород: Издательство ННГУ имени Н.И.Лобачевского, 2001. — 404 с.

11. Гардан, И. Машинная графика и автоматизация проектирования / И. Гардан, М. Люка. М.: Мир, 1987. - 222 с.

12. Гельмерих, Р. Введение в автоматизированное проектирование / Р. Гельмерих, П. Швиндт. Пер. с нем. - М.: Машиностроение, 1990. - 176 с.

13. Гладкий, А.В. Формальные грамматики и языки / А.В. Гладкий. — М.: Наука, 1973.-368 с.

14. Глушков, В.М. Основы безбумажной информатики / В.М. Глушков. М.: Наука., 1982. — 552 с.

15. Годун, Н.В. Интерактивное графическое пространственное моделирование сложных архитектурных объектов: Автореф. Дис. . канд. техн. наук: 05.01.01./Н.В. Годун.-Киев, 1989.-21 с.

16. Горелик, А.Г. Автоматизация инженерно-графических работ с помощью ЭВМ / А.Г. Горелик. Минск: Высшая школа, 1982. - 250 с.

17. ГОСТ 2.305-68 Изображения: виды, разрезы, сечения.

18. Грувер, М. САПР и Автоматизация производства / М. Грувер, Э.Зиммерс. М.: Мир, 1987. - 450 с.

19. Джамп, Д. AutoCAD: Программирование / Д. Джамп. — М.: Радио и связь, 1992. 332 с.

20. Евстигнеев, В.А. Применение теории графов в программировании / В.А. Евстигнеев. М.: Наука, 1985.

21. Ершов, А.П. Человек и машина / А.П. Ершов. М.: Знание, 1985.21 с.

22. Иванов, А.А. Сравнение форматов графического обмена в чертежных системах / А.А. Иванов, С.И Ротков // Сб. трудов 4-ой Международной конференции по компьютерной графике и визуализации ГРАФИКОН-94 Н. Новгород, 1994. - С. 74 - 86.

23. Интегрированная система автоматизированного проектирования и производства UNTGRAPHICS // Компьютерная графика, 1992. № 3. - с. 44

24. Кияш, Ю.Б. Синтез трехмерных объектов на основе теоретико-множественного подхода: Автореф. дис. . канд. техн. наук./ Ю.Б. Кияш. — М, 1986.-21 с.

25. Клишин, В.В. Моделирование трёхмерных объектов на основе объёмных базовых элементов формы: Автореф. дис. . канд. техн. наук. /В.В.Клишин. М., МЭИ, 1983. - 22 с.

26. Кнут, Д. Искусство программирования для ЭВМ. / Д. Кнут. т.1. Основные алгоритмы. - М.: Мир, 1980. — 700 с.

27. Котов, И.И. Алгоритмы машинной графики / И.И. Котов, В.С.Полозов, JI.B. Широкова. — М.: Машиностроение, 1977. — 232 с.

28. Краузе, Ф.Л. Автоматизированное проектирование в машиностроении: / Ф.Л. Краузе, Г. Шпур. М.: Машиностроение, 1988. -650 с.

29. Курс практической работы с системой АВТОКАД 10 / С. Гладков, Ю.Кречко, К. Молодцов и др. -М.: Диалог-МИФИ, 1991. С. 188-194.

30. Кучуганов, В.Н. Автоматический анализ деталей в САПР / В.Н. Кучуганов, А.А. Чистяков, В.Н. Захаров // Математическое обеспечение систем с машинной графикой: Материалы Всесоюзн. научн.-техн. семинара. — Ижевск, 1979. С. 22 - 25.

31. Кучуганов, В.Н. Автоматический анализ машиностроительных чертежей / В.Н. Кучуганов. — Иркутск: Изд-во Иркутск. Ун-та, 1985.-112 с.

32. Кучуганов, В.Н. Анализ форм деталей в задачах САПР / В.Н. Кучуганов.-М.: ВИНИТИ.-ДР 1539, 1981.- 175 с.

33. Кучуганов, В.Н. Методология и инструментальные средства синтеза сценариев графического инженерного диалога и объектно-ориентированных САПР: Автореферат дис. .докт. техн. наук: 05.01.01 / В.Н. Кучуганов. Ижевск: ИМИ, 1993, 43 с.

34. Локшин, С.М. Системы PDM на WEB-серверах Internet. / С.М. Локшин, С.И.Ротков // САПР и ГРАФИКА. 1998. - № 1. - С. 68 - 76.

35. Львов, В.А. Машинная графика / В.А. Львов. М.: МИНиГ, 1987. - 100 с.

36. Митин, С.В. Исследование и разработка методов и средств визуализации трехмерных объектов: Дис. . канд. техн. наук: 05.01.01 / С.В. Митин. Н. Новгород, 1994. - 150 с.

37. Митин, С.В. Алгоритм удаления невидимых на изображении линий / С.В. Митин, B.C. Полозов, С.И. Ротков // Тез. докл. Всесоюзной конференции «Современные вопросы математики и механики и приложения». М.: ВДНХ, 1983.

38. Митин, С.В. Информационная связь изображений в проекционной машинной графике / С.В. Митин, B.C. Полозов, С.И. Ротков // Методы и средства обработки графической информации: Сб. ст. Горький, 1986.

39. Митин, С.В. Операция отсечения для пространственных объектов / С.В. Митин, А.В. Нагорный, С.И. Ротков // Сб. тезисов 2-ой Всесоюзной конференции «Методы и средства обработки сложной графической информации». Горький, 1985.

40. Надь, Г. Распознавание образов (обзор): Труды ИИЭР / Г. Надь. — М.: ИИЭР, 1968. т. 56. - № 5. - С. 334 - 361.

41. Ньюмен, У. Основы интерактивной машинной графики: пер. с англ. / У. Ньюмен, Р. Спрулл. М.: Мир, 1976. -573 с.

42. Оре, О. Графы и их применение / О. Ope. — М.: Мир, 1965.62,Оре, О. Теория графов / О. Оре. М.: Наука, 1977.

43. Первикова, В.Н. Основы обратимых отображений линейных пространств в применении к чертежам многомерных фигур. / В.Н. Первикова. // Вопросы прикладной геометрии: Сб. статей аспирантов и соискателей-М.: МАИ, 1965.

44. Первикова, В.Н. Теория обратимых отображений п-мерных пространств и геометрических диаграмм многокомпонентных систем / Первикова В.Н. // Тез. докл. II Всесоюзной геометрической конференции — Харьков: изд. ХГУ, 1964.

45. Полозов, B.C. Геометрические и графические задачи: Автоматизированное проектирование / B.C. Полозов, О.А. Будеков, С.И. Ротков, JI.B. Широкова. М.: Машиностроение, 1983. - 280 с.

46. Полозов, B.C. К вопросу о способе построения технического чертежа / B.C. Полозов // Вопросы психологии (АПН РСФСР). 1962. -№26.

47. Полозов, B.C. Эвристическое моделирование. Управляющие системы и машины / B.C. Полозов. К.: 1981. - № 3. - С. 7 - 11.

48. Попов, Е.В. Метод натянутых сеток в задачах геометрического моделирования: Автореф. дис. . докт. техн. наук: 05.01.01 / Е.В. Попов — Н. Новгород, 2001. 45 е.

49. Райан, Д. Инженерная графика в САПР / Д. Райан. М.: Мир, 1989. -390 с.

50. Распознавание деталей и фрагментов общемашиностроительного применения: Тез докл. Всесоюзн. конф. "Методы и средства обработки сложноструктурированной семантически насыщенной графической информации". Горький, 1983. - С. 74.

51. Роджерс, Д. Алгоритмические основы машинной графики / Д. Роджерс. М.: Мир, 1989. 400 с.

52. Ротков, С.И. Анализ некоторых систем геометрии и графики пространственных объектов / С.И. Ротков // Проблемы информационных систем: сб.ст. М.: МЦНТИ, 1988. - № 5.

53. Ротков, С.И. Интеграция 2D и 3D систем геометрии и графики / С.И. Ротков // Сб. трудов международ, конф. 'Трафикон-93", С. Петербург, 1993.

54. Ротков, С.И. Преобразование каркасной модели трёхмерного геометрического объекта в конструктивную модель / С.И. Ротков, В.А. Тюрина // Труды 6-й Междунар. конф. по комп. графике и визуализации Графикон-96. С.- Петербург, 1996. - С. 56 - 58.

55. Ротков, С.И. Синтез моделей пространственных объектов по многовидовому чертежу / С.И. Ротков // Сб. трудов 4-ой международной конференции по компьютерной графике и визуализации Графикон-94, Н. Новгород, 1994. С. 37 - 39.

56. Ротков, С.И. Средства геометрического моделирования и компьютерной графики пространственных объектов для CALS-технологий: Дис. докт. техн. наук: 05.01.01 / С.И. Ротков. — Н. Новгород, 1999.-287 с.

57. Справочное руководство по черчению / В.И. Богданов, И.Ф. Малежик, А.П. Верхона и др. М.: Машиностроение, 1989. — 864 с. - ил.

58. Судов, Е.В. CALS-технологии или информационная поддержка жизненного цикла изделия / Е.В. Судов // PC Week Rewiew. 1998. - №45.

59. Тани, Х.И. Автоматическое чтение геометрического рисунка машиностроительных чертежей / Х.И. Тани // Тез. докл. научн.-техн. конф. по механизации и автоматизации инженерного и управленческого труда в промышленности. Киев, 1967.

60. Тани, Х.И. Алгоритм построения пространственного описания тела, заданного проекциями / Х.И. Тани // Известия АН СССР. Техническая кибернетика. 1966. - № 6.

61. Тани, Х.И. Ввод чертежей и синтез пространственного образа тел в ЦВМ: Автореф. дис. . канд. техн. наук / Х.И. Тани. Минск, 1968. -23 с.

62. Толковый словарь по вычислительным системам / под ред. В. Иллингоурта и др.: Пер. с англ. М.: Машиностроение, 1991. - 560 с.

63. Тюрина, В.А. Алгоритм редукции фундаментальной системы циклов графа, описывающего 3D объект / В.А. Тюрина // Тез. докл. Всероссийской научно-практ. конф. КОГРАФ-99. — Н. Новгород, 1999. — С. 67 68.

64. Уинстон, П. Искусственный интеллект: Пер. с англ. / П. Уинстон. М.: Машиностроение, 1991. - 560 с.

65. Фокс, А. Вычислительная геометрия. Применение в проектировании и производстве: Пер. с англ. / А. Фокс, М. Пратт. — М.: Мир, 1982.-304 с.-ил.

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

67. Харари, Теория графов / Харари. М.: Наука, 1977.

68. Хейман А.Ф. CADMECH DESKTOP мощный инструмент трехмерного проектирования. Режим доступа: Интернет: htpp: // www /cals.ru/what.htm#history.

69. Четверухин, Н.Ф. Теоретические основания начертательной геометрии. Ч.И. Геометрические преобразования и основные теоремы начертательной геометрии / Н.Ф. Четверухин. М.: МАИ, 1978.

70. Что такое CALS. Режим доступа: Интернет: htpp: // www /cals.ru/what.htm#history.

71. Шикин, Е.В. Кривые и поверхности на экране компьютера / Е.В. Шикин, Л.И. Плис. М.: Диалог-МИФИ, 1996. - 238 с.

72. Щеколдин, В.А. Итерационный метод построения пространственного описания тела, заданного своими проекциями / В.А. Щеколдин // Вычислительная техника в машиностроении: Сб. ст. Минск. - ИТК АН БССР, 1969.

73. Щеколдин, В.А. Построение на ЭВМ пространственного описания многогранного тела по описаниям его проекций / В.А. Щеколдин // Вычислительная техника в машиностроении: Сб. ст. — Минск. ИТК АН БССР, 1968.

74. Энкарначчо, Ж. Автоматизированное проектирование: Основные понятия и архитектура систем. / Ж. Энкарначчо, Э. Шлехтендаль. М.: Мир, 1986. - 290 с.

75. Aizawa, Т. Interactive Geometric Modelling System based on Practical Engineering Drawings / T. Aizawa, K. Yamato, M. Nakazawa // Bulleting of JSME. 1984. - Vol. 27, № 230. P. 1788 - 1795.

76. Aldefeld, B. On automatic recognition of 3D structures from 2D representations / B. Aldefeld // Computer-Aided Desing. 1983. - Vol. 15, № 2. -P. 59-64.

77. Aldefeld, B. Semiautomatic three-dimensional interpretation of line drawings / B. Aldefeld, H. Richter // Comp.& Graphics. 1984. - Vol. 8, № 4. -P. 371-380.

78. CATIA. Drafting User Manual. Licensed Program N5668-837.

79. CATIA. Basic 3D design User Manual. V.l, Licensed Program N5668-830

80. Cobb, E.C. On the Extraction of Solid Gtometry from a Wire Frame Geometric Data Base / E.C. Cobb // M.S. Thesis: University of Wiscosin-Madison. -1978.

81. Courter, M. Automated Conversuon of Curvilinean Wire-Frame Models to Surface Boundary Models; A Topological Approach / M. Courter, J. Brewer // SIGGRAF-86. Dallas, 18-22 aug.1986. - Vol. 20, № 4.

82. Dutton, R. Efficiently Identifying the Faces of a Solid / R. Dutton, R.C. Brigham // Computers and Graphics in mecanical engineering. 1983. -Vol.7, №2.-P. 143-147.

83. EUCLID. Technical Report. MATRA Datavision, France, 1988200p.

84. Ganter, M.A. From Wire-Frame to Solid Geometric: Automated Conversion of Data Representations / M.A. Ganter, J.J. Uicker // Computers in mecanical engineering. sept. 1983. - Vol. 2, № 2. - P. 40 — 45.

85. Haralick, R.M. Understanding engineering drawings / R.M. Haralick, D. Queeney // Сотр. Graphics and Image Processing. 1982. — Vol.20, №3.-P. 244-258.

86. Idesawa, M. A Automatic Input of Line Drawing and Generation of Solid Figure from Three-View Data / M.A. Idesawa, T. Soma, E. Goto, S. Shibata // Proceedings of the International Joint Computer Symposium, 1975. — P. 304-311.

87. Idesawa, M. A System to Generate a Solid Figure from a Three View / M.A. Idesawa, Bull. JSME 16. February, 1973. - P. 216 - 225.

88. Information Technology. Solutions for business. Case studies from ESPRIT. / Luxemburg, 1996. ISBN 92-827-8389-8. - 435 p.

89. Kargas, A. Interpretation of engineering drawings as solid models / A. Kargas, P. Cooley, T.H.E. Richards // Computer-Aided Engineering Journal. -april 1988.-P. 67-78.

90. Lafue, G. Recognition of Three Dimensional Objects from Views / G. Lafue // Computer Graphics. 1976. - Vol. 10, № 2.

91. Lequette, R. Automatic construction of curvilinear solids from wire frame views / R. Lequette // France. 1988. - Vol.20, №4. - P. 171-178

92. Markowsky G. Fleshing out projections / G.Markowsky, M.A. Wesley // IBM J. Res.& Develop. November, 1981. Vol. 25, № 6. -P. 934-954.

93. Markowsky, G. Fleshing out wire frames / G. Markowsky, M.A. Wesley // IBM J. Res.& Develop. sept. 1980. - Vol. 24, № 5. - P. 582 - 587.

94. Markowsky, G. Generation of solid models from two-dimensional and three- dimensional data / G. Markowsky, M.A. Wesley // in Pickett, MS and Boyse, J M (eds). Solid modelling by computer: from theory to application: Plenum, 1986.-P. 23-51.

95. Middleditch, A.E. Application of vector sum operator / A.E. Middleditch // Computer Aided Design. 1988. - Vol.20, № 4. - P. 183-188.

96. Nagendra, I.V. 3D Objects from 2D orthographic views A Survey / I.V. Nagendra, U.G. Gujar // Computer&Graphics. - 1988. - Vol.12, №1. -P. 111-114.

97. Preiss, K. Constructing the 3-D Representation of a Plane-Faced Object from a Digitized Engineering Drawings / K. Preiss // Fifth Internasional Conference and Exhibition on Computer in Engineering and Building Desing, 1980.

98. Preiss, K. Constructing the Solid representation from engineering projections / K. Preiss // Computer & Graphics. 1984. - Vol. 8, № 4. -P. 381 -389.

99. Sakurai, H. Solid Model Input Through Orthographic Views / H. Sakurai, D.C.Gossard // Computer Graphics. 1983. - Vol.17, №3. -P. 243 - 252.

100. SOLIDESIGN II. Technical Summury: Фирменный материал COMPUTEPVISION, 1990. 37 с.

101. Sutherland, I.E. SCETCHPAD: A Man-Machine Graphical Communication System / I.E. Sutherland. Proc. SJCC 23,1963. - P. 329.

102. Taijan, R. An Efficient Planarity Algorithm / R. Taijan // Computer Science Department. Report № CS - 244 - 71: Stanford University, November, 1971.

103. Thornton, R.W. Interactive Modelling in Three Dimensions through Two-Dimensional Windows / R.W. Thornton // Third Internasional Conference and Exhibition on Computer in Engineering and Building Desing, 1978.

104. Woo, T.C. Recognition of Three Dimensional designs from orthographic projections / T.C. Woo, J.M. Hammer // Proc. 9th CIRP Conference: Cranfield Institute of Technology, Cranfield, England, 1977. -P.247 255.

105. Yoshiura, H. Top-down construction of 3-D mecanical object shapes from engineering drawings / H. Yoshiura, K. Fujimura, T.L.Kunii // IEEE Сотр. Magazine, dec. 1984. P. 32 - 40.