Редактор геометрической системы

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

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

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

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

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

В свою очередь развитие аппаратных средств — мини и микроЭВМ, графических дисплеев, устройств для человекоориентированного ввода — вывода графической информации, — дает возможность построения на их основе интеллектуальных графических терминалов. Актуальной становится разработка фундаментального программного обеспечения для графических станций типа АРМ (автоматизированное рабочее место). По оценкам зарубежных специалистов, внедрение систем автоматизации проектирования и конструирования в производство увеличивает эффективность деятельности проектировщиков в 5−10 раз /I/.

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

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

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

— разработку пакета прикладных программ инженерного анализа;

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

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

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

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

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

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

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

— иметь диалоговый характер;

— предоставлять проектировщику развитые средства описания объектов из выделенного класса, содержательные возможности языка должны отвечать выбранному способу моделирования;

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

В работах /2,3,4/ проанализированы различные методы описания трехмерных объектов и дан обзор наиболее известных зарубежных систем геометрического моделирования. и1сЬа Л6/2/ выделяет следующие формальные свойства схем представления объектов:

1) соответствие модели реальному объекту (разумно выбрать подход, в котором строится модель, отвечающая реальному объекту, чем осуществлять последующую проверку реальности);

2) полнота схемы представления: любой объект из выбранного класса должен иметь модель;

3) однозначность: такая модель должна определяться единственным образом;

4) непротиворечивость: любая модель должна определять точно один объект.

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

Важно рассмотреть также и неформальные свойства схем представления, такие как:

1) легкость построения модели;

2) возможность сжатого представления модели и легкость построения по нему развернутого;

3) порождающие возможности данной схемы представления;

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

На основании сравнения различных схем представления по перечисленным параметрам в /2/ сделан вывод, что существуют две наиболее изученные и в настоящее время наиболее распространенные схемы представления, которые так или иначе включают в себя большинство остальных: схема конструктивной геометрии и схема граничного моделирования. В первом случае объект синтезируется из элементарных геометрических компонент — базисных объектов — в результате выполнения некоторых операций над ними, таких как объединение, пересечение, отсечение, сдвиг и т. д. Во втором случае объект описывается в виде иерархической структуры: набором базисных поверхностей, ограничивающих объект в трехмерном пространстве, границы которых в свою очередь представляются набором ребер и вершин периметра. Базисные ограничивающие поверхности не пересекаются, исключая общие ребра или вершины периметра. Обычно базисные поверхности выбираются так, что их геометрическая форма может быть представлена единым уравнением с помощью параметрической функции. В общем случае базисная поверхность может иметь «дырки». Тогда ее граница — совокупность ребер периметра — распадается на несколько компонент связности. Граничное моделирование — достаточно общее понятие, включающее широкий спектр описаний моделей.

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

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

Наиболее распространенные системы геометрического моделирования основаны на одной из этих двух схем представления либо имеют несколько форм представления одного и того же объекта, например системы P-RDL-2 /7−9/, GMSoCzot /10,11/, что позволяет их эффективно использовать в различных прикладных областях.

Система Tl Р£ -I /12/ основана на схеме конструктивной геометрии. В качестве примитивов выбраны восемь стандартных объектов: плоскость, цилиндрическая поверхность, прямоугольная призма, сфера и т. д., а также имеется нестандартный примитив. В качестве внутреннего представления используется матричная форма описания поверхностей. В системе, описанной в /13/, сложные объекты образуются из примитивов с помощью теоретико-множественных операций объединения, пересечения и т. д. и представляются в форме дерева.

Среди систем, использующих граничное представление, следует отметить системы EUK Lib /2/, GEOMEX) /23/, в WE /25/, предназначенные для описания многогранных поверхностей, &UILD,.

НОñ-ULUS' для описания плоских и цилиндрических поверхностей, систему 2>ь316л/ для описания квадратичных поверхностей /2,11/.

Известен алгоритм, использованный в системе PA1>LI /8/ преобразования модели, получаемой в рамках конструктивной геометрии, в граничную модель. Работы /17−20/ посвящены проблемам согласованности и эквивалентности различных схем представления и преобразованию представлений из одной схемы в другую.

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

Среди работ по созданию универсальных геометрических языков необходимо отметить язык ГЕОМАЛ /49/, являющийся расширением МГ0Ла-60. Такой подход к описанию трехмерных объектов предполагает введение новых типов данных (точка, прямая, плоскость, общегеометрический: тип) и операций, применяемых к ним (пересечение, объединение, параметрическое объединение и т. д.) в основном путем добавления к существующему «базовому» языку программирования новых синтаксических конструкций. В качестве внутреннего представления геометрических объектов в языке ГЕОМАЛ, например, выступает программа проверки принадлежности произвольной точки объекту.

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

Большинство существующих систем моделирования имеют процедурный входной язык, реализованный на базе языков программирования типа ФОРТРАН, ПЛ/1, ПАСКАЛЬ, и предназначены для описания определенного класса поверхностей: многогранных, цилиндрических, квадратичных.

Выбор способа представления математической модели объекта определяется эффективностью его использования, которая зависит от характера решаемых при этом вычислительных задач. Для решения задач типа: установить принадлежность точки объекту, оценить расстояние от точки до объекта, — эффективен алгебраический способ описания поверхности объекта с помощью Яфункций, неявных функций /51/- применяются матричные методы описания поверхностей /52,53/.

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

Система геометрического моделирования ГЕ0М0Д /54/ предназначена для описания плоско-ограниченных объектов средствами комбинаторной геометрии. Ориентированная двусторонняя многогранная поверхность описывается как результат применения теоретико-множественных операций пересечения и объединения к положительным полупространствам граней. Входной язык системы является макрорасширением ФОРТРАНа. Внутреннее описание объекта состоит из логического уравнения (характеристической функции) и алгебраических коэффициентов уравнений несущих плоскостей. Однако алгоритм визуализации, включенный в систему, функционирует над списочной структурой данных, где каждый объект описывается набором граней, специфицированных упорядоченными списками вершин и ребер контуров. Поэтому внутреннее представление объекта каждый раз с целью визуализации подвергается преобразованию, обеспечивающему интерфейс с алгоритмом визуализации.

Интересным является подход интерактивного проектирования трехмерных объектов на перспективных и аксонометрических изображениях, предложенный в /55/. Для такого проектирования разработана математическая модель, позволяющая формировать цифровую модель трехмерного объекта по наглядным изображениям, создаваемым пользователем в процессе графического диалога. Эта задача вплотную примыкает к проблеме восстановления описания трехмерного объекта по его проекциям /18,19/. Б системе рйшкоыцъ/ такое восстановление проводится в два этапа, на втором — двумерные данные интерпретируются с помощью некоторых семантических описаний.

Среди языков, предназначенных для операций с многогранниками и их элементами, следует отметить ГЕОМ /56/, являющийся макрорасширением автокода ЕЕМШ и языка АСТРА. В этом языке используется метод граничного моделирования: многогранник определяется набором граней, каждая из которых задается массивом вершин периметра. Внутренним представлением многогранника является графоподобная структура, описываемая средствами языка АСТРА. В ГЕОМ принято соглашение о разделении топологических и метрических свойств объекта, общее преобразование производится, как правило, в два этапа: этап топологической перестройки и этап вычисления метрики, что в ряде случаев очень удобно.

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

Целью диссертационной работы является разработка и реализация экспериментального редактора геометрической системы, предназначенного для описания Эйлеровых многогранников и двусторонних незамкнутых многогранных поверхностей, удовлетворяющих обобщенному уравнению Эйлера. Для решения этой задачи разработан способ формирования граничной модели объекта в плане дальнейшего развития принципов моделирования с помощью операторов Эйлера, изложенных в работах / 23 — 36. /. Разработана структура внутреннего представления модели в памяти ЭВМ и реализован набор операций, дающих достаточно широкие возможности для описания и манипулирования объектами.

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

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

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

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

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

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

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

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

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

Впервые ввел в рассмотрение операторы Эйлера Ватмда^ /23/. Хотя он не дал теоретического обоснования возможности использования этих операторов моделирования, созданная им система &bomsj) продемонстрировала эффективность такого подхода.

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

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

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

В целом такой подход является весьма перспективным и новым направлением в моделировании.

Для представления объекта в памяти ЭВМ используется метод «крыльев» /23,24/, или метод косвенного доступа к вершинам и ребрам периметра грани. Преимущество этого метода заключается в том, что каждый элемент для описания вершин, ребер или граней имеет фиксированный объем. На основании этого метода в диссертационной работе разработана списковая структура данных для представления граничной модели, обеспечивающая эффективную выборку добавление и уничтожение элементов структуры.

Для описания трехмерных объектов из выделенного класса с помощью редактора геометрической системы в диссертационной работе разработан и реализован на языке ПАСКАЛЬ набор операций, автоматически формирующих корректную структуру данных для описания объекта и позволяющих:

— определять новый объект различными средствами;

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

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

— вносить изменения в структуру объекта;

— использовать прикладные алгоритмы обработки и вычисления характеристик объектов.

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

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

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

7 т £()/е /28/ предлагает рекурсивный метод построения граничной модели объекта, полученного в результате регуляризованных операций пересечения, объединения и отсечения, который используется в системе РЯВЬ. В /29/ описан алгоритм, использующий вычисления на сетке, что позволяет обрабатывать поверхности Эйлера с тысячами граней.

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

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

Проблема удаления скрытых линий и поверхностей достаточно содержательна, несколько подходов к ее решению и обзор по этой теме даны в работах /32−35,58−62/. Первое известное решение для выпуклых многогранников, основанное на методах линейного программирования, предложено Робертсом /58/. Однако задача декомпозиции произвольного многогранного объекта на выпуклые многогранники сама по себе сложна. В существующих графических системах довольно часто используются различные модификации алгоритмов /35,34/. В их основе лежит метод определения «количественной невидимости» /34/ или «порядка невидимости» /35/ для точки и определения реберного пути из этой точки, тлеющего тот же порядок невидимости.

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

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

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

В предлагаемом редакторе геометрической системы реализован алгоритм удаления скрытых линий, основанный на методе построчного сканирования Уоткинса /36,37/.

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

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

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

Разработанная и реализованная в данной диссертационной работе экспериментальная система геометрического моделирования, названная ОРТ (описание и редактирование трехмерное) предназначена для:

— конструирования трехмерных многогранных объектов на экране графического дисплея;

— выполнения геометрических и топологических операций над ними;

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

— для визуальной оценки изображения с целью проверки правильности конструкторских решений;

— для анализа объектов, вычисления некоторых их характеристик.

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

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

ЗАКЛЮЧЕНИЕ

.

В диссертационной работе получены следующие основные результаты.

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

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

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

4. Предложен набор операций для описания, редактирования и визуализации трехмерных объектов.

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

Автор пользуется случаем, чтобы выразить благодарность своим руководителям, Михаилу Романовичу Шура-Бура и Игорю Евгеньевичу Педанову за ряд ценных замечаний и постоянную поддержу и внимание в работе.