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

РГ6

в ДЕК 1356

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

Кондрашин Юрий Алексеевич

"Разработка алгоритма удаления невидимых

линий при автоматизированном проектировании объектов машиностроения".

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

Автореферат

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

Москва 1996 г.

Работа выполнена в Московском государственном технологическом университете "Станкин"

Научный руководитель: - член-корреспондент РАН,

Соломенцев Ю.М.

Научный консультант: - кандидат физико-математических наук, доцент Судзиловский В.Ю.

Официальные оппоненты: - доктор технических наук, профессор Султан-Заде Н.М.

Защита состоится декабря 1996 года в 10 час на заседании Диссертационного Совета Д 063.42.02 при МГТУ "СТАНКИН" по адресу 101472, ГСП, Москва, К-55, Вадковский пер., д. За.

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

Автореферат разослан "<?/ " ноября 1996 года.

- кандидат технических наук, Кузнецов Л.В.

Ведущее предприятие: - ИКТИ РАН

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

Волкова Г. Д.

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

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

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

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

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

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

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

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

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

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

В соответствии с целью в диссертационной работе формулируются и решаются следующие задачи:

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

• формулировка и обоснование требований к получаемой модели объекта с удалёнными невидимыми частями;

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

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

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

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

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

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

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

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

Достоверность полученных результатов подтверждается экспериментальной проверкой, выполненной при использовании в системе геометрического моделирования T-Flex CAD 3D.

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

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

повысить качество ПО САПР за счёт более эффективного использования ресурсов вычислительных комплексов.

Реализация и внедрение результатов. Полученные результаты были оформлены в качестве исходного кода на языке С++ (в среде BorlandC v.4.5 версия для DOS и MFC Visual С++ v.4.2 версия для Windows 95 и Windows NT) и предназначены для использования в системе отображения информации, реализованной на базе персонального компьютера типа IBM AT.

Реализованный алгоритм представлен в системе параметрического моделирования T-Flex CAD 3D, в составе которой он используется на различных предприятиях как в России, так и за рубежом.

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

Краткое содержание работы

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

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

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

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

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

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

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

и будут требовать некоторые дополнительные характеристики объектов модели.

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

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

В работе приводится сравнение этих двух способов обработки изображения.

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

Вторая глава работы посвящена способам повышения производительности алгоритмов удаления невидимых поверхностей.

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

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

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

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

стоимость построения самой покрывающей оболочки и простота её использования.

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

X

Рис 1. Сравнение двух ограничивающих оболочек

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

Существуют также одномерные и трёхмерные ограничивающие оболочки.

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

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

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

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

Третий раздел работы (Использование свойств связности изображения) и посвящен этому исследованию.

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

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

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

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

Рис 2. Построение очерковой линии

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

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

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

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

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

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

Четвёртая глава работы посвящена вопросам реализации графической системы.

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

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

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

Для объектов типа тело введено понятие ограничивающей оболочки. Тела рассматриваются как картинки, ограниченные этими оболочками. При этом вводятся две плоскости: ближайшая к

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

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

Дальняя

ограничибсшщая плоскость и_

Точка йзгляба

Рис 3. Построение ограничивающих плоскостей

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

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

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

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

Также приводится решение задач определения взаимного положения точки и контура и определение ориентации контуров.

Разработанная модель также позволяет обрабатывать детали с разрезами. Для этого, в плоскости, по которым проходит разрез,

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

Рис 4. Пример модели с разрезом

Приложение содержит акты о внедрении и авторское свидетельство об участии в разработке программного пакета T-Flex CAD 3D.

Общие выводы

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

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

130

150

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

4. Организация обмена с внешними системами посредством графических метафайлов обеспечивает достаточную связь между двумя подсистемами САПР.

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

По теме диссертации сделаны следующие работы:

1. Кондрашин Ю.А., Саблин К.П. Методы визуализации объёмных моделей для САПР машиностроения // Проблемы машиностроения и автоматизации, 1996, N1-2.

2. Саблин К.П., Кондрашин Ю.А. Получение параметрических ступенчатых разрезов в машиностроительных САПР. // Проблемы машиностроения и автоматизации, 1996, N5-6.

3. Кондрашин Ю. А., Саблин К.П., . Судзиловский В.Ю. Использование свойств связности изображения в алгоритмах удаления невидимых поверхностей. // Информационные технологии (в печати).

4. Кураксин С.А., Козлов С.Ю., Бикулов С.А., Ефремов А.Н., Баранов JI.B., Ксенофонтов Д.К., Иванов В.А., Кондрашин Ю.А., Саблин К.П., Ильин A.B., Ахмед Яхья М.М., Алтухов В.В., Софронова Ю.В., Конева C.B. Свидетельство о регистрации программы для ЭВМ "Система автоматизированного и черчения CT-FLRX CAD) // №950128,

заявка №950069 от 10.04.1995.

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

Кондрашин Юрий Алексеевич

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

Подписано в печать 19.11.96 Формат 60x84/16

Бумага ZOOM 80 гр/м Гарнитура

Объем уч.-изд. л. - 1.4 Тираж 100 экз

Заказ 128

Издание отпечатано в издательстве "Станкин". Лицензия на полиграфическую деятельность: ПЛД № 53-227 от 09.02.96г.