Геометрическое моделирование

Подписаться на эту рубрику по RSS

Заметки на геометрическую тематику.

Инкрементальное подавление скруглений

"All problems in computer science can be solved by another level of indirection" (David Wheeler).

Введение

Если твердотельная булева операция не сработала, разработчики ACIS рекомендуют использовать т.н. «инкрементальный режим». Инкрементальная вычислительная схема есть способ многократного вызова некоторого алгоритма ядра с целью повышения общей отказоустойчивости. Обычно, такие вычислительные процедуры пишутся не от хорошей жизни, а как средство, помогающее выжать из рухнувшего алгоритма все, что он способен дать. Так, если для определенного положения операндов булев алгоритм ломается, можно попробовать незначительно «пошевелить» входные данные, чтобы вывести их в более съедобную для алгоритма конфигурацию (Рис. 1).

Рис. 1. Индикатор успешности булевой операции, в зависимости от положения X одного из операндов. Достаточно «тронуть» X влево или вправо, чтобы алгоритм сработал.

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

Рис. 2. Инкрементальное подавление скруглений на одном из этапов разрушает целостность модели (испорченные грани показаны красным цветом).

Блок-схема нашей инкрементальной процедуры показана на Рис. 3. Здесь приняты следующие обозначения:

  • F — индексы граней, распознанных как скругления;
  • T — транзиентные указатели (TShape) на неподавляемые грани;
  • G — атрибутированный граф смежности граней (AAG);
  • H — накопленная история модификаций;
  • s — результирующая модель;
  • r — радиус распознаваемых скруглений;
  • h — история модификаций на текущем шаге подавления;
  • chain(f) — цепочка скруглений, начинающаяся из грани f.
  • Рис. 3. Блок-схема инкрементальной процедуры подавления скруглений.
    Подробнее алгоритм подавления скруглений и соответствующая инкрементальная процедура будут рассмотрены нами в одной из академических статей.

    Отладка

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

    Коротко поговорим о том, как происходит отладка в среде «Анализ Положения». Рассмотрим тестовую модель (Рис. 4) и выполним на ней инкрементальное подавление.

    Рис. 4. Тестовая CAD-модель.

    В данном случае неожиданно происходит разрушение топологической целостности модели (Рис. 5).

    Рис. 5. Тестовая модель после неудачного инкрементального подавления.

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

    Рис. 6. Уточнение тестового сценария. Красным отмечена «виновная» функция.

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