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

ОД

На правах р> копией

МИТИН Сергей Вячеславович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ВИЗУАЛИЗАЦИИ ТРЕХМЕРНЫХ ОБЪЕКТОВ

С5.01.01 - Прикладная геометрия н инженерная галфика

Автореферат

£!!ссертпшп1 на соискание ученой степени сакандзта технкчесюос наук

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

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

МИТИН Сергеи Вячеславопич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И СРЕДСТВ ВИЗУАЛИЗАЦИИ ТРЕХМЕРНЫХ ОЬЬЕКТОВ

05.01.01 - Прикладная геометрия и инженерная графика

Автореферат

диссертации на соискаю!е )ченой степени кандидата технических наук

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

Работа выполнена в Научно-исследовательском институте механики пр Нижегородском государственном ордена Трудового Красного Знамен университете им. Н.11. Лобачевского

Наушые руководители - "октор технических наук, профессор В.С. Полозов. кандидат технических наук, доценг С.И. Ротков.

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

доктор технических наук, профессор ЮЛ. Кетхов,

кандидат технических наук, профессор В-А. Аниснмов.

Ведущее прелпрняше - Опытмсгкскструкторское бюро машиностроение г. НижниЦ Новгород.

Защита состоится 26 декабря • 1994 г. в 15 час на заседанп слеинадизироЕанпого совета К064.09.02 при Нижегородской государственно архитектурно-строительной академии по адресу: г. Нижнй Новгород, ул. Ильинская, 65.

С диссертацией можно ознакомится в библиотеке НГАСА.

Автореферат разослан " " ноября 1994 г. .

Ученый секретарь

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

Актуальность проблемы. Результаты исследования н анализа современных систем геометрического моделирования и проекционной машинной графики Показа.-«, что lex це1ггральным звеном является генератор изображений, важный сгязуюашй блок систем моделирования на плоскости (2D системы) и в трехмерном пространстве (3D сис.емы). Его широкое применение обусловливается необходимостью решения, во-первых, задач автоматизации чертежно-графических работ, Ео-зтсрцх, залач организации специальных графических форм диалога в процессе создал кя моделей трехмерных геометрических объектов.

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

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

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

Uc.TW является:

- исследование роли и места генераторов изображений в системах геометрического моделирования, ориентированных на САПР н ACH И различной проблемной ориентации,

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

поьсрхчослй трехмерных объектов,

- ралработка структур данных для описаг-ш изображений трехмерных геометрических объектов сложных технически? форм и структур (ТГО СТФС) с )чегом процессов создания гео.метри :ских моделей и формирования технических чертежей,

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

- создание проблемно-инвариантного программного обеспечения формирования изображении трехмерных объектов аля САПР, АСНИ и АСТПП.

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

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

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

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

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

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

Реализация результатов работы. Методы, структуры и алгоритмы, разработанные в диссертационной работе, были воплощены в ряде систем геометрического моделирования и проекционной машинной графики, а именно: 1) в системе геометрического моделирования трехмерных объектов "Китеж", разработанной в рамках НТГ1 Гособразования СССР "Математическое м ¡ели-рованис в научных и технических системах", приказ № 905 от 26.10.89, 2) в подсистеме создания альбомов изображений трехмерных объектов "Альбом-ЗР", 3) в системе визуализации физико-механических полей (постпроцессор), разрзботаиной по заказу ГНТУ Минтомжергопрома, 4) в подсистеме визуализации результатов научных экспериментов по экологии.

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

Апробация работы. Материалы диссертации докладывались нз Республиканских. Всесоюзных и Международных конференциях и выставках:

- "Роль инженерной графики и машинного проектирования в подготовке специхтистов для народного хозяйства". Ленинград, 1984.

- "Методы и средства обработки сложной графической информации". Горький. 1983. 1985.

- "Проблемы машинной графики". Протвино, 1987.

- "Грзфикон - 94". Нижний Новгород, 1994.

Публикации. Список печатных работ по теме диссертации содержит 7

наименований.

Объем работы. Диссертация состоит из введения, четырех глав, заключения списка литературы из 94 наименований и приложений; содержит 114 странш текста, 35 рисунков и 3 таблицы.

СОДЕРЖАНИЕ РАБОТЫ Во введении дана общая характеристика работы, сформулированы цел« теоретических, экспериментальных и практических исследований i разработок В пепвой главе "Генерация проекционны* изображений в система) автоматизированного проектирования" приведен анализ способов по луче нш изображений в САПР, выявлена роль и место генератора изображений в система) npoeimoinioii машинной графики с целью определения степени значимости t возможности решения задачи диссертационной работы - разработки структу! данных для описания изображений трехмерных геометрических объектов сложны) технических форм и структур с учетом процессов создания геометрических моделе£ и форми1ювания технических чертежей.

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

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

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

В начале 70-х годов появились отечественные работы (Полозов B.C., Широкова Л.В.), в которых исследовались и решались новые для традиционной машинной графики классы задач, одной из которых является оптимизация аппарата проецирования с целью получения изображений, обладающих нужными для конструктора признаками (аксонометрии, на которых видны необходимые для' конструктора особенности предмета, перспективы). Аналогичные ■..••„ичи возникают и при выборе изображений в процессе формирования техническою чертежа (выбор главного и основных видов, принятие решения о необходимости разреза и т.п.). Все эти задачи фундаментально используют процедуры определения Е иди мости элементов объекта, при этом алгоритмы, реализующие эти процедуры (алгоритмы видимости - АВ) имеют существенные особенности, не наблюдаемые в других задачах. Эти особенности накладывают новые ограничен!«! на АВ и ецдг.;:г2!зт новые требования. К ним относятся, в частности, необходимость определения видимости линий, закрытых гранями объекта, лежащими в проецирующих плоскостях.

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

Первой из них является проблема организации обратной связи от изображения с оригиналу, возникающая при организации интерактивного взаимо-

депеткия с объектом через его изображение.

¡3горой проблемой, возникающей при создр-ши генератора изображений, лг.ляется проблема сохранения информации на изображении, необходимой для реи.ения ряда графических и геометрических задач проекционной машин) й графики, таких как размещение изображении на чертеже, разм щение размеров, штриховки 11Л1! нанесения фл^гуря на изображение.

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

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

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

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

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

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

Наличие большого числа алгоритмов удаленна невидимых линий различных классов ставит перед создателями САПР проблему выбора или создания наилучшего, с точки зрения использования, алгоритма. Обычными требованиями, которые предъявляются к алгоритмам и реализующим их программам, являются: 1) минимум требуемой оперативной памяти; 2) минимум реального времени "зботы программы.

Выбор лучшего алгоритма удален»,.! невидимых линии для целей создания ~АПР не исчерпывается анализом эф Активности алгоритмов. Наиболее важным ¡ритерием выбора является возможность и удобство использования ког :ретного Алгоритма видимости в конкретном месте САПР, во-первых, а процессе конструирования объекта, во-вторых, на этапе подготовки и выпуска чертежно-графичесхои документации. Каждый из этих этапов имеет свои особенности и выдвигает свои тре'овакия к алгоритму ввдшош, к его входным и выходным данным.

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

г Так на этапе проектирования изделия в системе геометрического моделирования нежелательно использовать:

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

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

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

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

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

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

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

В каждом алгоритме видимости можно выделить блоки, поддерживающие когерентность элементов объекта, т.е. их создание, изменение, и блоки, сортирующие данные элементы. Модель предлагаемого алгоритма имеет следующую структуру".

1. Блок создания когерентных единиц включает в ссбя:

- удаление "задних" граней.

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

2. Блок сортировки когерентных единиц:

- формирование множества упорядо"енных пар КЕ на основе анализа их глубины и возможности взаимного перекрытия.

- принятие решения о видимости, невидимости, нарушения когерентности данной КЕ.

3. Блок изменения (редактирования) когерентных единиц содержит:

- проецирование граничных ребер на грани, принадлежащие когерентной единице.

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

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

Использование в предлагаемом алгоритме когерентности связной поверхности

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

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

При формировании этой стратегии возникают следующие проблемы:

- как определить возможность ачияния НФ2 на видимость НФ1,

- как'определить степень влияния НФ2 на НФ1.

- как имбрать порядок определения видимости СФ.

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

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

конкретные воплощения разработанных методов, структур и алгоритмов в программны* продуктах: системе геометрического моделирования трехмерных объектов "Китеж", подсистеме создания альбомов изображений трехмерных объектов "Альбом-ЗО". системе визуализации физико-механических полей (постпроцессор), подсистеме визуализации результатов научных экспериментов по экологии. Все реализации осуществлены для ПЭВМ 1ВМ РС 286 и выше на языке С

Применение системы "Китеж." даст возможность выполнять следующие вилы работ: 1) проектирование и редактирование внешней формы изделий; 2) получение и просмотр реалистических полутоновых изображении проектируемых объектов; 3) решение компоновочных задач и задач по размещению объектов в заданном габаритном пространстве; 4) проверка геометрической непротиворечивости сборочных единиц (собираемость конструкций, определение зазоров); 5) определение масс-инсршюнных характеристик проектируемых объектов

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

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

"Альбом Зй" представляет собой библиотеку программ на языке С для 1ВМ РС и может быть использован для создания электронных справочников и каталогов.

Алгоритм определения видимости линчи в подсистеме "Атьбом ЗПГ имеет

Программная реализация алгоритмов" рассматриваются

ряд принципиальных отличий от штатного алгоритма системы "Китеж":

- целочисленное представление координат объекта;

- полная предварительная сортировка граней вдоль оси Z (оси взгляда):

- отсутствие в сложных моделях иерархических древовидных сгруктур;

- вся модель объекта располагается а оперативной памяти.

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

На рисунке изображены графики сравнения Бремени работы рашпных процедур удаления невидимых линий, полученные на IBM PC ЗЯ6 DX 33 Mh.

• Время в сек.

Использование агоритма Я-буфера и билинейной интерполяции позволило создать процедуру еи ¿уализапни физико-механичесхнх полей т поверхностях трехмерных объехгов (постпроцессора) как результата прочпосшых расчетов.

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

В заключении изложены основные результаты диссертационной работы:

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

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

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

4. Разработаны новые эффективные алгоритмы построения изображений трехмерных объектов ç определением видимости поверхностей по их компьютерным моделям. Максимальное г.-пользование в данных алгоритмах

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

использование эвристического подхода в алгоритмах определения видимости

л

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

5. Разработано и соатано проблемно-инвариантное программное обеспечение формирования изображений трехмерных объектов с удалением невидимых линий и поверхностей, которое вошло в состав системы геометрического моделирования "Китеж", подсистему создания альбомев изображена;! трехмерных объектов "Алъбом-ЗО", систему визуализации физико-механических полей (постпроцессор) и подсистему визуализации результату научных экспериментов по экологии. Приведенные в диссертационной работе данные сравнения быстродействия разработанных процедур определения видимости с аналогичной про"едурой в системе AutoCAD показывают их эффективность и конкурентноспособность.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Митин C.B. О некоторой задачах в проблеме удаления невидимых линий. // Алгоритмы и программы поискового конструирования. Йошкар-Ола, 1934.

2. М'.ггин C.B. Удаление невидимых линий для сложноструктурированных многогранников. // Тез. докл. Республиканской научно-методической конференции "Роль инженерной графики и машшшого проектирования в подготовке специалистов для народного хозяйства". Ленинград, 1984.

3. Митин C.B., Полозов B.C., Ротков С.И. Информационная связь изображений в проекционной машинной графике. // Автоматизация обработки сложной |рафической информации": Межвуз.сб.иаучлр./Подред. Ю.Г.Васина; Горьк.гос.ун-т. Горький, 1986.

Митин C.B. Алгоригм удаления невидимых поверхностен для нросгран-

cTBcinsux объектов сложных структур. // Тез. докл.Г/ Всесоюзной конференции по проблемам машинной графики, Серпухов 1987.

5. Митин C.B., Ротков С.И. Организация информационной связи между изображением и объектом. //Тез. докл. V Всесоюзной конференции по машинной графике "Машинная графика 89", Новосибирск 1989.

6. Митин C.B. Опыт решения задач удаления невидимых линий в системах геометрического моделирования. // Материалы 4 Международной конференции по компьютерной графике и визуализации Трафькон-94", Нижний Новгород, 1994.

7. Аристова Е.В., Зудин А.А., Лабутин С.Е., Митин C.B., Ротков С.И., Шубин В.П. Система геометрического моделирования пространственнух объектов КИТЕЖ. // Материалы 4 Международной конференции по компьютерной графике и визуализации Трафикон-94", Нижний Новгород, 1994.