Методология

Введение

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

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

Эйлеровы операторы в библиотеке OpenCascade не реализованы. Кроме того, в библиотеке нет полного набора инструментов для локального редактирования топологии модели с возможностью исчерпывающего контроля результата. Скрупулезное отделение геометрии от топологии (оба типа данных «ничего не знают» друг о друге) говорит о том, что первые разработчики OpenCascade внимательно относились к чистоте архитектуры ядра. Но несмотря на это, ядро почти не содержит средств редактирования собственных базовых структур данных. Такие средства должны быть разработаны.

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

Проблема и пути решения

CAD-модель можно абстрагировать от геометрической формы и дать ей чисто топологическое описание в виде ориентированного графа. Узлами графа являются топологические элементы (грани, ребра, вершины, контуры, оболочки, сплошные тела и проч.). Дуги графа задают отношение включения. При этом дуги раскрашены в соответствии с ориентацией каждого топологического элемента в своем родителе (красный для ориентации FORWARD и синий — REVERSED). На следующей картинке изображен топологический граф одной грани кубика.

Теперь тот же граф после удаления ребра. Здесь вершины (желтые кружки) «разлетелись» в разные стороны:

Топологический оператор работает исключительно на графе. Нас будут интересовать ЛОКАЛЬНЫЕ топологические операторы, при помощи которых модель редактируется, а не создается с нуля. Локальность оператора означает, что он изменяет не весь граф, а какую-то его часть. Кроме того, в силу устройства модели данных OpenCascade, топологический оператор всегда оставляет на модели «след», начинающийся от корневого узла и оканчивающийся в узлах, где совершалась модификация. Например, если меняется ребро кубика, то перестроенными окажутся сам кубик (TopoDS_Solid), его оболочка (TopoDS_Shell), две смежные грани (TopoDS_Face) и их контуры (TopoDS_Wire), поскольку все эти элементы оказываются родительскими.

Валидация топологического оператора, вообще говоря, состоит в сравнении двух графов. Проверять следует такие показатели алгоритма редактирования:

1. Какие топологические элементы были затронуты оператором?
2. Какие топологические элементы остались неизменны?
3. Совпадает ли итоговая топология с той, которая ожидалась, то есть равны ли графы (с учетом цветов)?

Есть одно обстоятельство, которое осложняет проверку графа и которое послужило мотивом для написания данной заметки. Дело в том, что граничные элементы в OpenCascade не содержат уникальных идентификаторов, по которым их можно однозначно отыскать в структуре B-Rep и сравнить с эталоном (что и требуется при автоматическом тестировании). Вместо уникальных идентификаторов на практике часто используются серийные номера элементов модели. Эти номера (индексы) не хранятся в модели, а назначаются при обходе топологического графа, например, в глубину. Как следствие, удаление одной единственной грани, вообще говоря, приводит к полной переиндексации всех элементов модели. В принципе, такое поведение индексов можно считать допустимым для нужд тестирования, ведь эти индексы, хотя бы и неустойчивые к редактированию, все же не изменяются при сохранении и открытии моделей. Мы однако считаем такой подход порочным ввиду того, что он затрудняет ручную верификацию результата. Действительно, глядя на два топологических графа модели до и после редактирования, обнаружить аномалии вручную («глазом») будет очень непросто. Для ручной верификации нужно иметь соответствие старых и новых индексов граничных элементов.

Пусть в исходной модели вершина 10 принадлежит ребру 15. Допустим, что такая конфигурация должна сохраниться в результате некоторой операции прямого редактирования. Для проверки этого отношения в результирующей модели индексы 10 и 15 должны быть заменены на какие-то новые значения, которые, в свою очередь, «произвольно» выбираются алгоритмом. С технической точки зрения особых проблем нет, но идеологически этот подход немного коряв. Дело в том, что такой принцип верификации противоречит разумной установке проверять КАЧЕСТВЕННЫЙ признак оператора редактирования, что особенно актуально на топологических (т.е. качественных) изменениях модели. Вместо того, чтобы проверить свойство «вершина A принадлежит ребру B», мы начинаем проверять, что «образ A1 вершины А принадлежит образу B1 ребра B» даже в случае, если вершина A и ее ребро B никак не менялись. Фраза, подлежащая верификации, становится сложнее из-за нашей неспособности зафиксировать некоторый устойчивый идентификатор для каждого топологического элемента. Ручная проверка ожидаемых топологических свойств при таких формулировках становится ночным кошмаром, хотя работать это, конечно, будет (железо все стерпит).

Давайте остановимся подробнее на способах однозначной идентификации топологических элементов CAD-модели.

Индексы итератора

Использование серийных индексов итератора удобно для работы на статических объектах, которые не подвержены топологическим преобразованиям. В корректно работающих системах, индексы не меняются при чтении и записи файла (то есть являются персистентными), что делает эти индексы пригодными для решения многих задач. На их использовании основана работа системы Analysis Situs. Недостаток серийной индексации состоит в их глобальном изменении даже на локальном, незначительном преобразовании модели. Так, топологические элементы, которые не менялись, могут получить новые индексы просто из-за того, что итератор «посетил» их раньше или позже, чем прежде.

"Any simple scheme, such as sequentially enumerating all entities in the model, is also not enough because when the model is edited and automatically reevaluated, the topology of the model may change and the enumeration becomes invalid. Even if the topology of the model doesn’t change and only the geometry is modified, the modeling algorithms such as Boolean operations may create or modify the topological entities of the model in a different order and consequently the enumeration cannot be preserved." (Kripac, J. A mechanism for persistently naming topological entities in history-based parametric solid models. 1997.)

Адреса в памяти

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

"Unfortunately, directly using pointers to topological entities is not good enough because pointers are transient. Whenever the parametric modeler reevaluates the model, it creates a brand new model and the original pointers become invalid." (Kripac, J. A mechanism for persistently naming topological entities in history-based parametric solid models. 1997.)

Топологическое именование

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

"Topological naming is extensively used in [CAD] application to record the geometric arguments of algorithms, for example the edge to be blended. If parameters of operations performed before the blend are modified the application needs to identify the new edge to be blended. We can say that applications use topological naming to update the geometric arguments of high-level editing operations and to update technical attributes." (Lequette, R. Considerations on Topological Naming. 1997.)

"One of fundamental problems in history-based parametric solid modeling systems is to identify topological entities of solid models in such a way that the same entities can still be identified after the models have been reevaluated from the sequential history of modeling operations." (Kripac, J. A mechanism for persistently naming topological entities in history-based parametric solid models. 1997.)

R. Lequette (один из первых разработчиков OpenCascade) отмечает, что топологическое именование имеет смысл только для топологически близких моделей. Действительно, если пользователь меняет параметрическую модель, начиная от двумерного эскиза, то результирующая топология тела может не иметь ничего общего с топологией, ранее атрибутированной. Проблемы с топологическим именованием, как правило, возникают при изменении кардинального числа модели («cardinality change problem»), то есть количества топологических элементов. В библиотеке OpenCascade топологическое именование базируется на двух компонентах:

1. Граф истории модели, позволяющий хранить все промежуточные состояния топологических элементов.
2. Средство ассоциирования метаданных с граничной моделью, т.к. сами геометрические и топологические структуры данных OpenCascade не допускают хранения в них атрибутов. Данным средством является OCAF (OpenCascade Application Framework).

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

Давайте сравним приведенные подходы к индексации, чтобы подвести промежуточный итог.

Сравнение подходов

Первая таблица дает сводку об эволюции индексов на операторе прямого редактирования.

Противоположным образом дело обстоит на сохранении/чтении модели.

Грамотное решение

В работе (J. Kripac 1997) рассматривается подсистема топологической идентификации (Topological ID System), которая назначает идентификаторы (имена) граничным элементам модели (граням, ребрам, вершинам). Подсистема именования работает в связке с историей моделирования, которая хранит соответствия между состояниями граничной модели до и после применения оператора моделирования. При этом используемый подход к проектированию не имеет определяющего значения, так как фундаментальная проблема топологического именования возникает и в классических САПР, использующих историю построения, и в средствах прямого редактирования (например, для поддержания декларативных ограничений на соосность, параллельность и т.п.).

Система именования, предлагаемая нами для реализации проверки топологической корректности моделей, вдохновлена работой (J. Kripac 1997). Система состоит из следующих основных компонент:

• История построения (History). Это граф, вершинами которого являются топологические элементы, а дуги соответствуют трем возможным преобразованиям топологического элемента: Generated, Modified и Deleted.
• Сервис именования (Naming). Этот сервис (класс C++) используется для первичного именования топологических элементов. Кроме того, сервис именования поддерживает экземпляр истории, который должен передаваться из одной операции моделирования в другую для обеспечения непрерывности истории.

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

• Generated: в модели был создан новый топологический элемент, неоднородный исходному (например, ребро породило грань). Это может быть создание «с нуля», либо порождение другим элементом. Стандартным примером такого порождения является вытягивание призмы из плоской грани.
• Modified: топологический элемент был перестроен. Например, это происходит с базовой гранью при добавлении в нее фичера, скажем, цилиндрического отверстия. Другой пример: разделение ребра на несколько частей. Важно, что новые и старые элементы модели однородны (ребро превращается в ребро).
• Deleted: топологический элемент был уничтожен. Ясно, что ситуация одновременного наличия Deleted и Modified исключена, хотя Deleted и Generated могут соседствовать, скажем, на операции скругления ребра.

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

Пример

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

Перед началом прямого редактирования каждый топологический элемент модели получает уникальное имя (идентификатор). Это имя может задаваться пользователем, либо выбираться автоматически. Ниже представлен топологический граф с выделенной вершиной, которая отвечает произвольно взятому ребру. Мы видим транзиентный адрес ребра, его «родовой» индекс (pedigree ID), его глобальный индекс (global ID) и, наконец, топологическое имя (в данном случае «edge_2»). Родовой и глобальный индексы отличаются только тем, что родовой учитывает однородные элементы модели (только ребра, только грани и т.д.), тогда как глобальный индекс есть результат полного обхода топологического графа.

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

Мы видим, что родовой и глобальный идентификаторы ребра «edge_2» изменились. Мы, однако, все еще можем различить это выделенное ребро в модели, поскольку его транзиентный адрес не менялся. Удалим теперь вершину с родовым индексом 2 (эта вершина входит в ребро «edge_2»). В результате имеем следующую картину:

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

Обратим внимание на то, что цвета дуг графа остаются неизменными. Это означает, что ориентации топологических объектов сохраняются. Наконец, удаление самого ребра «edge_2» приводит к его полному уничтожению, в то время как имена оставшихся ребер остаются прежними: «edge_3» и «edge_4».

Конечно, граничное представление модели перестало быть сколько-нибудь корректным. Грань, лишенная двух ребер и двух вершин, более непригодна для моделирования. Этого, однако и не требовалось, поскольку примененный оператор не являлся оператором Эйлера.

Реализация

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

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

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

Выводы

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