Алгоритм обрезки поверхностей при поверхностном моделировании в CAD/CAM системах

А.И.Макаров
доц., к.т.н.
ИПУ РАН, г. Москва

Математический аппарат, используемый для моделирования криволинейных поверхностей в системах CAD/CAM, не позволяет описывать поверхности со сложной геометрией границ. Трудности возникают уже при построении поверхностей с пятью граничными линиями, не говоря уже о вырезании отверстий внутри поверхности.

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

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

Плодотворность такого подхода подтверждена тем, что он реализован в известных CAD/CAM системах, связанные с таким подходом структуры предусмотрены в стандарте межсистемного обмена информации VDA FS и IGES.

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

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

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

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

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

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

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

На рис. 1а показаны кривые А, В, С, D, из которых связан контур, кривые Е и F, не включенные в контур (пассивные ограничения), и вновь созданная кривая G, появление которой приводит к перестройке ограничений. Стрелками показана ориентация кривых. При движении вдоль кривой выделяемая ее поверхность будет находиться слева.

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

а) б) в)

Рис.1. Контур, ограничивающие кривые и перестройка ограничений

Таким образом, задача построения контуров содержит следующие этапы:

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

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

в) определить куски кривых, входящие в контуры и последовательность кусков кривых для каждого контура.

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

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

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

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

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

Исключив ориентацию дуг в графе G, получим неориентированный граф G. Остовное дерево графа G будет включать все его вершины и содержать между каждой парой вершин в точности один путь. Процесс построения остовного дерева можно начать в любой вершине графа G и в процессе прохождения текущей вершины из нее можно выйти по любой из инцидентных ей дуг, кроме той, по которой вошли в вершину [1,2]. В процессе построения остового дерева определяется список обратных дуг. Включение в остовное дерево каждой обратной дуги ведет к образованию цикла, которые в совокупности образуют фундаментальное множество циклов графа относительно его остовного дерева.

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

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

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

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

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

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

a) фрагмент б) окно

Рис.2 Типы контуров

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

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

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

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

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

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

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

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

Такая схема определяет несколько особенностей построения ограничений:

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

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

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

Для ориентации используется вершина дуг контура, имеющая максимальную или минимальную U или V -координату, предшествующая ей вершина и последующая вершина. По приращениям координат этих вершин можно определить тип контура текущей ориентации.

Пусть имеется контур, показанный на рис.3а, в котором определена вершина q с максимальной U-координатой. Вычислим приращение по V координате вершины q относительно предшествующей вершины (ΔV-) и приращение последующей вершины относительно q (ΔV₊). Если оба приращения имеют одинаковые знаки, то сразу же можно определить тип контура: если приращения положительны, то контур имеет тип "фрагмент" (рис.3б); в противном случае -тип "окно" (рис.3в).

Если приращения имеют разные знаки, то для определения типа контура выбирается одно из них. Для этого из двух отрезков, имеющих общую вершину q, определяется тот, у которого больше абсолютная величина косинуса угла с прямой, параллельной оси V. Знак приращения координаты V выбранного отрезка используется для установления типа контура. Например, в ситуации, показанной на рис.3г, тип контура будет установлен по ΔV-.

a) б) в) г)

рис.3 Установление типа контура

Если вершина q совпадает с разрывным полюсом, то нет третьей вершины для анализа типа контура. Тогда тип контура определяется по двум вершинам, а в качестве 3-ей берется вершина, совпадающая с q. Если разрывный полюс лежит на линиях U=0 и V=1, то ориентация по вершине в нем может быть выполнена только по приращению ΔU, т.е. для ориентации нужно выбрать вершину с минимальной или максимальной V-координатой.

Алгоритм предусматривает до 4-х попыток установления типа контура по разным вершинам: с U_min, U_max, , V_min , V_max . Очередная делается, если предшествующая оказалась неудачной. Кроме описанной ситуации с разрывными полюсами, попытка «установления типа» контура может быть неудачной только в случае совпадения отрезков с общей вершиной q.

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

рис. 4 Пример обрезки поверхностей при проектировании головной части электропоезда в системе СПОП-3

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

рис. 5 Геометрическая модель диска колеса

рис.6. Фрагмент протектора шины

Литература

1. Э.Рейнгольд, Ю.Нивергельт, Н.Део. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.

2. Paton K. An Algorithm for finding a Fundamental Set of Cycles of a Graph, Comm. ACM, 12 (1969), 514-518.

3. Jonson D.B. Finding All the Elementary Circuits of a Directed Graph, SIAM J. Comput., 4(1975), 77-84.