Конференции

На конференции Графикон-2019 в г. Брянске нами был сделан очередной доклад по теме упрощения CAD-моделей путем распознавания и подавления цепочек скруглений. Приводим этот доклад ниже. Полный текст статьи также доступен по ссылке.

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

1. Снижение количества полигонов в модели для подготовки сцен виртуальной и дополненной реальности.
2. Подавление конструктивных элементов для перехода от конструкторской геометрии к расчетной (конечно-элементный анализ, CFD).
3. Подготовка уровней детализации (LODs; levels of details) для рендеринга больших сцен.

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

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

На входе алгоритма — граничная модель в формате STEP (ISO 10303), либо в другом формате, сохраняющем топологическую связность геометрии. Заметим, что помимо собственно геометрического описания объекта, формат STEP содержит дополнительные данные о продукте, такие как цвета, имена, информация об изготовлении (product manufactuting information), структура сборки. Алгоритм подавления скргулений должен, поэтому, предоставлять историю модификации граничных элементов, т.к., в противном случае, будет утеряна ассоциированная с ними информация. В то же время, структура сборки данным алгоритмом не воспринимается: он работает на одиночной детали. Поддержание же целостности структуры сборки решается на вышележащем архитектурном уровне программного комплекса.

Предлагаемый алгоритм строится на базе открытого ядра геометрического моделирования OpenCascade. Мы задействуем следующие элементы ядра:

1. Транслятор формата STEP.
2. Структуры данных для граничного представления CAD-моделей (B-Rep).
3. Базовые средства анализа геометрии, такие как вычисление точек на кривой/поверхности, производных, кривизн и т.п.

В рамках настоящей работы были реализованы:

1. Атрибутированный граф смежности граней (AAG) — структура данных, сохраняющая в явном виде информацию о смежности. Кроме того, данный граф является «носителем» атрибутов как результатов распознавания конструктивных элементов. Атрибуты ассоциируются с вершинами и дугами графа. Использование графа смежности — классический подход в области распознавания конструктивных элементов.
2. Программный модуль распознавания конструктивных элементов на базе AAG.
3. Эйлеровы операторы KEV, KEF, KFMV и сопутствующий инструментарий для обеспечения прямого редактирования модели.
4. Собственно алгоритм подавления скруглений как приложение модуля распознавания КЭ и операторов прямого редактирования.

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

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

1. Скругление ребра (Edge-Blend Face; EBF).
2. Скругление вершины (Vertex-Blend Face; VBF).

Алгоритм распознавания, сам по себе, не формирует цепочку скруглений, ограничиваясь лишь маркировкой граней. Формирование цепочек откладывается до этапа попытки их подавления. На слайде приведена общая структура алгоритма распознавания. Это последовательная процедура, началом которой является построение атрибутированного графа смежности G. На следующем этапе выполняется распознавание граней типа EBF. Далее, грани типа VBF дораспознаются, исходя из информации об их предполагаемой смежности с EBF. Результатом работы алгоритма становится «обогащенный» граф G^*, содержащий классифицирующие атрибуты скруглений.

Распознавание типа грани (EBF, VBF) опирается на дополнительные эвристики, применяемые к ребрам модели.

Мы различаем три типа ребра:

1. Опорное ребро (spring edge). Опорные ребра — это гладкие ребра, являющиеся направляющими скруглений типа EBF.
2. Поперечное ребро (cross edge). Поперечные ребра могут быть гладкими и негладкими. Они характеризуются тем, что в них реализуется смежность двух граней скруглений (EBF или VBF).
3. Терминальное ребро (terminating edge). Эти ребра завершают цепочки скруглений. В случае замкнутой цепочки терминальные ребра отсутствуют.

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

Из набора гладких ребер выделяются опорные ребра граней типа EBF. С этой целью осуществляется анализ главных кривизн на ребре-кандидате. Соотношения между абсолютными величинами кривизн позволяют сделать предположение о том, является ли грань A с кривизнами a₁, a₂ гранью скругления. Так, должны выполняться следующие соотношения:

1. Абсолютная величина a₂ превосходит абсолютную величину a₁, то есть кривизна в поперечном направлении предполагаемого скругления доминирует (скругление является более кривым в своем поперечном направлении, нежели в продольном).
2. Абсолютная величина a₂ превосходит абсолютную величину b₂ не менее, чем в c раз, где c больше единицы. Эта эвристика выражает то наблюдение, что искомая грань EBF опирается на менее кривую поверхность, например, на плоскость.

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

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

Теперь, когда цепочки распознаны, переходим к их подавлению.

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

1. Преобразование топологии путем применения эйлеровых операторов.
2. Нормализация геометрии путем стягивания затронутых ребер.

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

Эйлеровы операторы подготавливают топологию результирующей модели. Конкретный набор операторов и последовательность их применения полностью определяются типом грани-скругления. Так, для грани EBF требуется выполнить дважды оператор KEV и один раз KEF. Как только топология модели оказывается приведенной к желаемому состоянию, контуры затронутых граней перестраиваются для получения «водонепроницаемой» граничной модели.

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

Для выяснения эффективности и надежности нового алгоритма мы произвели сравнение с оператором удаления грани общего назначения (Remove Face, RF), доступного в ядре OpenCascade. Алгоритм распознавания и подавления скруглений (Blend Recognition and Suppression, BRS) был обернут в инкрементальную процедуру, позволяющую обработать все цепочки скруглений последовательно. Оба алгоритма запускались на одной и той же выборке граней, полученной при помощи предварительной процедуры распознавания.

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

Подводя итоги, укажем, что алгоритм BRS выигрывает у алгоритма RF качественно, но проигрывает количественно. Расширение алгоритма BRS с целью повышения его общей результативности — наша цель на ближайшее время. Представленный подход был коммерциализован в программном пакете CAD Processor компании OPEN CASCADE.

Бонус:

Кофе в Калуге. В Qoffee Blanco на ул. Ленина отличный капучино! Без него остаток пути пришелся бы туго.

Первый корпус БГТУ. Конференция была не в нем, но это здание более живописно.

Вид с кургана Бессмертия.

Want to discuss this? Jump in to our forum.