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

НИЖЕГОРОДСКАЯ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННАЯ АРХИТЕКТУРНО-чГГРОИТЕЛЬНАЯ АКАДЕМИЯ

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

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

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

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

Автореферат

диссертации на соискмше ученой степени кандидата технических наук

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

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

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

Официальные опяонеэты: ^ >

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

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

Защита состоится 26 декабря 1994 г. в 15 час на заседанш слеииализпрОБашюго совета К064.09.02 при Нижегородской государственно) архитектурно-строительной академии по адресу; г. Нижн'й Новгород, ул. Ильинская, 65.

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

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

»

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

кандидат технических наук, доцент ^—— МЛ. Лапши».

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

Актуальность проблемы. Результаты исследования и анализа современных систем геометрического моделирования н проекционной машинной графики показа-.и, что их центральным з&еном является генератор изображений. важный связующий блок систем моделирования на плоскости (20 системы) к в трехмерном пространстве (ЗР системы). Его широкое применение обусловливается необходимость!-.) решения, во-первых, задач ааюмтшшш чертежно-графнчоских работ, зо-вторых, задач организации специальных графических форм дна-юга в процессе создания мояелей.трехмерных геометричссю« объектов.

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

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

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

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

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

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

гюбсрхчсси-й трехмерных обьсхтоЕ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выбор лучшего алгоритма удалена невидимых линии для целей создания САПР не исчерпывается анализом зф |>е1спшности алгоритмов. Наиболее гласным критерием выбора является возможность и удобство использования ког ;ретаого игоритма видимости в конкретном месте САПР, во-первых, а процессе

е

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение системы "Китеж" даст возможность выполнять следующие вилы работ: 1) проектирование н редактирование внешней формы изделий; 2) латучение

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

3) решение компоновочных задач и задач по размещению объектов в заданном габаритном пространстве; 4) проверка геометрической непротиворечивости сборочных единиц (собираемость конструкций, определение зазоров); 5) определение Macc-KHcpuiiomiux характеристик проектируемых объектов

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

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

"Альбом 3D" представляет собой библиотеку программ на языке С для IBM PC и может быть использован для создания электронных справочников и каталогов.

Алгоритм определения видимости лшгш в подсистеме "Альбом 3D" имеет

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

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

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

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

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

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

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

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

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

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

1. Исследована роль и «¿сто генераторов изображений в системах геометрического моделирования, ориентированных на САПР и АСНИ различной

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рисунке представлены примеры использования генератора изображений системы "Кмтсж"