Geometric modeling

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

Три дня докладов

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

В секции геометрического моделирования особенно выделился доклад о циклографической начертательной геометрии. Признаюсь, мы с коллегами были настолько сражены суровостью предлагаемого изложения начерталки, что толком ничего не поняли. Докладывал Панчук Константин Леонидович из Омска. Вывод мы сделали ровно один: работы этого ученого обязательны к изучению, и, особенно, молодыми умами, «испорченными» легкомысленной наглядностью и чрезмерной технологичностью компьютерной графики. Картинка ниже отрезвляет. Найдите там параллельные плоскости.

Конференция была организована на базе Нижегородского Государственного Архитектурно-Строительного Университета (ННГАСУ). Этот вуз занимает особое место в научно-техническом облике Нижнего Новгорода. Инженерно-геометрические традиции, заложенные деятелями советских школ, все еще живы в этих стенах.

Распознавание фичеров (feature recognition)

Ниже мы приводим в сжатом виде общую канву сделанного доклада о распознавании конструктивных элементов.

Общая постановка задачи состоит в том, чтобы воссоздать геометрическую твердотельную модель машиностроительного изделия из оцифрованных данных (скажем, лазерного сканирования). Если ограничиться лишь геометрией, то на выходе, очевидно, получается «немая» модель, т.е. «всего лишь» композиция граней, представленных лоскутами того или иного типа поверхности. Это немало, но и не предел мечтаний, так как уже несколько десятилетий инженер-конструктор мыслит в более прагматичных образах, чем грань, ребро или вершина. Основным элементом модели принято считать фичер (feature) — конструктивный элемент. Фичер — штука стереотипная, но при всей неоднозначности трактовок данного понятия, именно набором фичеров оперируют все классические кады, начиная с дедушки Pro/ENGINEER и кончая красавицей Onshape. Ян Страуд, написавший книгу о создании CAD-системы с нуля [1], отмечает, что вообще-то есть два подхода при работе с геометрией модели. Это проектирование в терминах фичеров (design-by-features) и распознавание фичеров (feature recognition). Проектирование в терминах конструктивных элементов дает ВНЕШНЮЮ семантику геометрических объектов и их наборов. Так, наряду с граничным представлением цифрового изделия, мы имеем его «раскладку» на компоненты в виде дерева построения. Редактирование модели осуществляется путем редактирования внешнего по отношению к модели дерева построения (рис. 1).

Альтернативный подход состоит в выявлении конструктивных элементов модели из нее самой. Этот подход нейтрален по отношению к технологии конструирования, так как изначальная САПР никоим образом не участвует в процедуре распознавания фичеров (рис. 2). Алгоритмы распознавания фичеров пытаются извлечь ВНУТРЕННЮЮ семантику модели, избавляясь тем самым от присутствия порождающей САПР. Этот подход критикуют, например, Ушаков в своем прекрасном обзоре [2]. Критика справедлива, так как распознавание фичеров — задача трудоемкая и принципиально разрешимая отнюдь не для всех типов конструктивных элементов.

Отдавая должное всем доводам против распознавания фичеров, нельзя все-таки говорить о несостоятельности концепции как таковой. Дерево построения не всегда содержит информацию обо всех фичерах, имеющихся в модели. Так, на рис. 3 поверхность скругления, которую модифицирует пользователь, отсутствует в дереве просто из-за того, что эта поверхность образовалась путем вытягивания арки окружности исходного профиля. Система достаточно умна, чтобы позволить пользователю модифицировать этот неявный фичер, не возвращаясь к параметризованному скетчу. Правда, для этого разработчики вынуждены были ввести специальную операцию «Modify fillet». Не очень-то бьется с чистой концепцией design-by-features, не так ли?

Пристальное рассмотрение системы Onshape обнаруживает в ней и другие способы непосредственного редактирования модели, такие как удаление и перемещение грани тела. Все эти операции бесхитростно дописываются в историю построения модели, никак не отражаясь на исходном скетче, чего и следовало ожидать. Нетрудно сообразить, что в предельном случае итоговая форма модели может не иметь ничего общего с изначальным скетчем, и замысел проектировщика оказывается размазанным по дереву фичеров. Здесь возникает нужда в соблюдении некоторой культуры моделирования, нарушение которой ведет к полному рассогласованию между ВНЕШНЕЙ семантикой модели и ее актуальной геометрией. В общем, ничего хорошего. Особенно, если вспомнить, что на предприятиях часто используется не одна САПР, а несколько. Кроме того, модель может быть сохранена в нейтральном формате (STEP / IGES), где никаких фичеров и деревьев построения нет и быть не может. Наконец, сценарий реинжиниринга также не способствует появлению у хрупкого тела B-Rep какого-то параметрического «экзоскелета» в виде дерева построения.

Но вернемся на минутку к критике обоих подходов [2] и посмотрим, что предлагается взамен. Еще один подход состоит в том, чтобы избавиться от истории построения модели, не свалившись при этом в высокоуровневый семантический анализ геометрии в терминах ее фичеров. Используя т.н. геометрический решатель, можно реализовать редактирование модели, сохраняя концептуальный замысел проектировщика. Этот замысел выражается в таких свойствах, как параллельность и ортогональность граней, гладкость сопряжений, соосность элементов составных отверстий и др. Речь идет о «вариационном прямом моделировании», суть которого сводится к решению нелинейной задачи удовлетворения низкоуровневых ограничений, накладываемых на структуры B-Rep. Нельзя отказать этому подходу в изящности и своеобразной «экологичности», так как ВНЕШНЯЯ семантика модели, имеющая свойство «магически испаряться» при трансляции данных из одной САПР в другую, здесь не используется. Точно как и в случае с feature recognition, модификация модели сообразуется с ее ВНУТРЕННЕЙ семантикой. Разница в том, что выведение этой внутренней семантики больше не предполагает получение фичера в явном виде, а потому существенно упрощается. Отметим это разделение на ВНЕШНЮЮ и ВНУТРЕННЮЮ семантику и двинемся дальше.

...Мы не собираемся повторять ошибки большинства вендоров, реализуя в очередной раз идею тридцатилетней давности о том, что параметризация трёхмерной модели должна быть основана на истории её построения. По моему глубокому убеждению эта идея тупиковая, т.к. она не позволяет ответить на современные вызовы, такие как совместная работа пользователей разных MCAD-систем, использование большого объёма данных в устаревших форматах, необходимость внесения быстрых изменений в модель, плавный переход от двумерного черчения к трёхмерному моделированию, а также технологическая подготовка производства изделия прямо в CAD-системе. Точнее, ответ на все эти вызовы у большинства вендоров один: создайте модель заново. Что означает лишь потерю времени и ресурсов, неприемлемую в нынешних конкурентных условиях. [Дмитрий Ушаков, Есть ли будущее у DWG?..]

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

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

Положим, что «немая» модель воссоздана (как? — предмет отдельного разговора), и ее нужно дополнить некоторой семантикой. Образно выражаясь, надо «допросить» модель для выявления составляющих ее геометрию фичеров. Речь идет о выведении ВНУТРЕННЕЙ семантики модели, что даст возможность ее редактировать, управляя параметрами найденных фичеров (например, радиусами скруглений, глубинами отверстий и т.д.). Заметим, что прямое редактирование, а также его вариационный извод, требующий сложного (и дорогого) геометрического решателя, мы оставляем в стороне, хотя упомянутая тема вполне заслуживает особого, предметного разговора. Чтобы поставить здесь некоторое многоточие, отошлем читателя к системе SpaceClaim и его реализации схемы реинжиниринга в единстве с впечатляющими средствами прямого редактирования. В простейшей постановке для распознавания конструктивных элементов известны два основных подхода: это методы, основанные на графах (будем говорить «графовые методы»), и методы объемной декомпозиции модели. Оба подхода вполне реализуемы на любом геометрическом ядре, так как требования, предъявляемые к операторам моделирования, здесь не слишком строгие. К нашему удовольствию, ядро OpenCascade вполне годится для нужд, возникающих в парадигме feature recognition. Это обстоятельство открывает путь исследователю, не обремененному мега-грантами на лицензирование коммерческих ядер.

Графовый метод

Идея заключается в анализе графа смежности граней (AAG = Attributed Adjacency Graph) и выделении в нем компонент, «похожих» на фичер. Здесь имеет смысл говорить о двух направлениях решения задачи: поиск динамически задаваемого подграфа и поиск по фиксированным правилам. Поиск подграфа в графе — это проблема изоморфизма графов, которая, как известно, NP-полна. К счастью, как отмечают Хан, Пратт и Регли в обзоре [3], на практике все не так уж печально. Графовый метод хорош тем, что позволяет сравнительно шустро (по сравнению с другими методами) находить многие типовые машиностроительные фичеры, такие как отверстия, канавки и некоторые карманы. Минусы тоже есть. Во-первых, на выходе мы получаем только грани конструктивного элемента, а не его твердотельное описание, что было бы полезно в задачах инженерного анализа (например, исследование тока горючего в двигателе). Во-вторых, и это, пожалуй, пострашнее, метод весьма серьезно ограничен. Мы можем описать шаблоны или правила для поиска изолированного отверстия с зенковкой, но что если оно выпадает на канавку, врезающуюся в карман? Проблема взаимно пересекающихся фичеров графовыми методами толком не решается. Чтобы почувствовать сложность расширений графого метода для нетривиальных взаимовложений фичеров, читателю достаточно бегло ознакомиться с работой Гао и Шаха [4]. Сложно. Очень.

Объемная декомпозиция

В обзоре Хана, Пратта и Регли [3] методы объемной декомпозиции соседствуют с третьим классом методов, называемым «hint-based recognition», то есть «распознавание на основании подсказок». Ниже мы не будем делать такого разделения и вот почему. Дело в том, что к задаче распознавания фичеров не следует подходить только с геометрической стороны, чем грешат «чистые» методы объемной декомпозиции. Последние опираются на последовательное построение объемных ячеек, выпуклых оболочек и прочую занимательную вычислительную геометрию, тогда как технология производства нередко остается где-то за кадром. Но именно технология определяет фичер. Скажем, карман всегда имеет скругления на внутренних углах в силу природы техпроцесса фрезерования. А если не имеет — карман ли это вообще? Другой вопрос: может ли данный фичер быть произведен без смены инструмента на станке? И таких вопросов много. Оставляя их без внимания, исследователь рискует оказаться в стране волшебных пони, не имеющей никакого отношения к машиностроению и его реальным проблемам. По окончании нашего доклада, в перерыве, мне довелось пообщаться с представителем Тульского оружейного завода. Человек интересовался, учитываются ли в предлагаемой работе технологические допуски. Чистая геометрия никому не нужна. У геометрии в САПР инженерный генотип и плох тот исследователь, который не желает этого видеть.

Декомпозиция дельта-объема

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

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

Указав ограничения, двинемся дальше. Общий вид вычислительной схемы представлен на рис. 7. Этапы 1 и 2 преследуют цель получения дельта-объема, то есть геометрической модели той части материала, которая будет удалена станком для производства детали. Этап 3 представляет собственно декомпозицию. Наличный дельта-объем подвергается последовательному исчерпанию призматическими фичерами. Заключительный аккорд схемы связан с выявлением типов всех изолированных фичеров. Построенное дерево конструктивных элементов является в то же время деревом булевых операций вычитания. По сути это производящий алгоритм, операндами которого являются фичеры. Их параметры можно менять, а сами фичеры удалять из производящего процесса, осуществляя тем самым редактирование модели изделия.

На рис. 8, 9 изображен результат декомпозиции тестовой модели.

Ключевым ингредиентом подхода является, конечно, твердотельная булева операция. Путем вычитания исходного тела из заготовки, образуется дельта-объем, подлежащий распознаванию на составляющие его фичеры. Чтобы булев алгоритм отработал как надо, следует должным образом подготовить его операнды. Так, модель заготовки лучше всего набирать из ограничивающих поверхностей исходного тела. Если этого не сделать, то любое незначительное расхождение между почти соприкасающимися геометриями рискует загубить все дело. Для практиков вычислительной геометрии не новость, что при вычислении всякого рода пересечений, будь операндами ребра или грани, определяющее значение для успеха алгоритма имеет взаимное расположение объектов. В англоязычной литературе встречается термин «general position» (т.е. общность положения), характеризующий ситуацию, когда операнды не выходят на взаимное касание и пересекаются наиболее приятным для вычислителя образом. Но вернемся к булеву вычитанию. Если модель заготовки незначительно (в пределах малой погрешности) отличается от модели изделия, локально выходя на касание, то булева операция лишается свойства общности положения. В парадигме B-Rep это нередко приводит к неожиданным последствиям, вплоть до утраты топологической целостности результата. Впрочем, создание надежного, точного и эффективного булева алгоритма — это задача настолько амбициозная, что ей вполне мог бы заняться какой-нибудь неизвестный герой, в рамках, скажем, диссертационного исследования.

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

Заключение

Графикон — это такое место, где собираются инженеры, геометры, архитекторы, профессионалы компьютерной графики и другие прагматически настроенные технари. Вопрос «а зачем нужно все то, что вы сделали?» прозвучит всякий раз, когда докладчик покажется излишне абстрактным в своем выступлении. Это радует, когда в стенах академического заведения собираются люди, твердо нацеленные на Дело и готовые ради Дела терпеть недостаток финансирования и связанные с призванием ученого бытовые трудности. Вычислительная геометрия и компьютерная графика привлекают молодежь присущей этим областям эффектной красотой, обусловленной современными технологиями. Этот юный порыв, будучи подкрепленным фундаментальным математическим образованием и инженерным складом ума, конечно, можно только приветствовать и всячески способствовать его зарождению и развитию. Но одних приветов мало. Кто-то из докладчиков, презентуя работу по компьютерному зрению, упомянул вскользь, что аспиранты в их учреждении не задерживаются, ведь «в банке платят больше». Несомненно так. Но настоящая работа — это всегда пот, кровь и слезы. И это вообще не про деньги.

1. [1] Stroud I., Nagy H. Solid Modelling and CAD Systems: How to Survive a CAD System. 2011. 689 p.
2. [2] Ушаков Д., Кому и зачем нужно прямое моделирование? Обзор конкурентных технологий, http://isicad.ru/ru/articles.php?article_num=14775
3. [3] Han J.H.J., Pratt M., Regli W.C. Manufacturing feature recognition from solid models: a status report // IEEE Trans. Robot. Autom. 2000. Vol. 16, N 6. P. 1-31.
4. [4] Gao S., Shah J.J. Automatic recognition of interacting machining features based on minimal condition subgraph // Comput. Aided Des. 1998. Vol. 30, N 9. P. 727-739.