Андрей Туманин, к.т.н., математик-программист C3D Labs
Основным представлением моделируемого объекта в геометрическом ядре C3D Modeler, как и в большинстве других геометрических ядер, является граничное представление, или B-rep (Boundary representation). По сути, это означает, что для работы основных алгоритмов по редактированию модели (например, применение операций скругления, разрезания и т.д.) и получению плоских проекций необходимо именно ее B-rep представление. С помощью алгоритма триангуляции (тесселяции) по граничному представлению модели относительно просто строится ее полигональное представление, которое используется для визуализации и геометрических расчетов. Обратное же преобразование из полигонального представления в B-rep гораздо сложнее, при этом возникает ряд проблем, связанных как со сложностью распознавания поверхностей различного типа (в том числе и поверхностей свободной формы), так и с наличием шумов в полигональных моделях, которые свойственны, например, результатам 3D-сканирования. Однако быстрорастущее разнообразие 3D-данных в полигональном формате делает задачу преобразования модели из полигонального представления в граничное всё более актуальной, что предопределило необходимость разработки специального инструмента в составе C3D Toolkit, который получил имя C3D B-Shaper.
Обобщенный процесс преобразования модели из полигонального представления в граничное, реализованный в C3D B-Shaper, представлен на рис. 1 и состоит из трех основных этапов: сегментация, реконструкция поверхностей и построение модели B-rep. В общем случае процесс преобразования предполагается итерационным: если пользователя по каким-либо причинам не устраивает полученный результат, он может внести необходимые корректирующие изменения на этапах сегментации и реконструкции поверхностей.
Рис. 1. Схема преобразования полигонального представления в граничное
В некоторых случаях до инициирования процесса преобразования в B-rep необходимо улучшить качество исходной полигональной сетки: согласовать направления нормалей на соседних полигонах, устранить «дыры», применить алгоритмы сглаживания при наличии шумов в исходной сетке.
Сегментация полигональной модели
На первом этапе осуществляется классификация исходного множества полигонов сетки на подмножества (сегменты). Информация о нормалях в вершинах сетки позволяет произвести сегментацию первого порядка и тем самым обеспечить начальное разбиение сетки, а также классифицировать плоские или сильно изогнутые области. Начальное разбиение сетки основано на определении так называемых острых ребер — таких ребер между двумя треугольными полигонами, угол между средними нормалями которых превышает некоторое заранее заданное значение.
Сегментация второго порядка анализирует сетку в соответствии с ее главными кривизнами, что обеспечивает достаточный фундамент для классификации элементарных поверхностей. При расчете кривизн в вершинах сетки использовались результаты работы Майера по определению дискретного дифференциального оператора для триангулированных областей: для каждой вершины исходной сетки рассматривается набор соседних вершин, связанных с данной через ребро (рис. 2). Затем для данной вершины рассчитывается дискретный оператор , на основе которого определяются средняя нормаль, средняя и Гауссова кривизны в вершине сетки.
Рис. 2. К определению дискретного дифференциального оператора для триангулированных областей
Таким образом вычисляется тензор кривизн для каждой вершины сетки, собственными числами которого являются искомые главные кривизны k1 и k2, а собственными векторами — главные направления изменения кривизн. Далее производится классификация вершин сетки согласно рассчитанным в них значениям главных кривизн k1 и k2. Алгоритм классификации вершин основан на методе k-средних, то есть на минимизации суммарного квадратичного отклонения точек кластеров от центров этих кластеров. В результате (рис. 3) на выходе алгоритма каждая вершина сетки ассоциирована с некоторым кластером C1 и парой кривизн (центр кластера) .
Рис. 3. Классификация вершин полигональной сетки
в пространстве кривизн
После классификации вершин полигональной сетки необходимо классифицировать полигоны. В начале этой процедуры выбирается треугольный полигон, для которого кривизна может считаться полностью определенной (все три вершины принадлежат одному кластеру либо две вершины лежат на остром ребре). Этот полигон объявляется новым сегментом, и с него стартует рекурсивная процедура расширения сегмента: для каждого треугольного полигона рассматриваются соседние к нему полигоны при условии, что ребро между ними не «острое». В случае если вершина соседнего полигона, противолежащая общему ребру, лежит на остром ребре либо принадлежит тому же кластеру, то этот полигон добавляется в сегмент. Процесс повторяется до тех пор, пока все полигоны данной сетки не будут просмотрены. Рис. 4 иллюстрирует реализованный в C3D B-Shaper механизм сегментации полигональной сетки.
По окончании процедуры формирования сегментов выполняется специальный алгоритм сшивки соседних сегментов для устранения излишней сегментации рассматриваемой сетки.
Распознавание поверхностей
На следующем этапе каждому из сегментов необходимо поставить в соответствие некоторую поверхность, аппроксимирующую его форму с заданной точностью. Прежде всего, по значениям главных кривизн для данного сегмента определяется возможность описания формы сегмента элементарной поверхностью:
- плоскость, k1 = k2 = 0;
- сфера, k1 = k2 = K > 0;
- цилиндр, k1 = K > 0, k2 = 0;
- конус, k1 [a ,b], k2 = 0;
- тор, k1 = K, k2 [a, b].
В случае если ни одна из элементарных поверхностей не подходит для описания сегмента, будут предприняты попытки распознать поверхность выдавливания или вращения. В конечном счете, если не удалось подобрать аналитическую поверхность для описания формы сегмента, для него будет строиться NURBS-поверхность.
Рис. 4. Механизм сегментации полигональной сетки
Элементарные поверхности строятся с помощью методов вписывания простых геометрических объектов в множество точек. Так, для вписывания окружности и сферы используется метод наименьших квадратов, для вписывания плоскости — метод главных компонентов. Каждая реконструированная поверхность проверяется на соответствие сегменту по заданной точности распознавания. На рис. 5 распознанным поверхностям присвоен свой цвет: плоскости — синий, цилиндры — красный, сферы — зеленый, конусы — желтый, торы — фиолетовый.
Рис. 5. Исходная полигональная сетка (слева) и сегментированная сетка (справа) с распознанными на сегментах поверхностями
Построение модели B-rep
Финальным этапом преобразования является построение на основе сегментации распознанных поверхностей модели B-rep. При этом подходе на основе сегментированных областей строится граф смежных областей, который отражает топологию модели и служит основой для построения окончательной модели B-rep. В отличие от предыдущих этапов преобразования, сборка B-rep выполняется в полностью автоматическом режиме: находятся линии пересечения соседних реконструированных поверхностей, на их основе строятся ребра граней, сами грани, а в завершение — собирается оболочка B-rep (рис. 6).
Рис. 6. Результаты работы C3D B-Shaper: исходная полигональная сетка (слева) и модель B-rep (справа)
Однако топологически корректную оболочку удается построить не всегда. В качестве примера такой ситуации предположим, что в ходе реконструкции поверхностей у нас получились две поверхности — цилиндр и плоскость, причем положение их в пространстве близко к касательному. Из-за погрешностей реконструкции поверхностей их пересечения может не получиться вообще. В таких случаях оболочка может построиться с некоторыми дефектами, которые пользователь может исправить, скорректировав должным образом параметры поверхностей.
Типы полигональных моделей и выбор режима преобразования
На сегодняшний день можно выделить несколько основных источников моделей в полигональном представлении:
- онлайн-каталоги, базы данных 3D-моделей в полигональном формате (STL, VRML, OBJ), например 3D Warehouse, Cults 3D и т.д.;
- результаты 3D-сканирования;
- результаты топологической оптимизации моделей CAE-алгоритмами.
Полигональные модели из этих источников можно условно разделить на две группы: в первую входят модели, которые по сути являются триангуляцией некоторых объектов B-rep, а во вторую — остальные модели. Характерным отличием первой группы от второй является отсутствие шумов в полигональной сетке, а также преобладание аналитически заданных поверхностей. Таким образом, осуществить преобразование в модели B-rep из первой группы представляется возможным либо в полностью автоматическом режиме, либо с минимальным вмешательством пользователя.
С другой стороны, полигональные сетки моделей второй группы подразумевают более плотное интерактивное взаимодействие с пользователем. Поэтому изначально предполагается два основных режима работы C3D B-Shaper: полностью автоматический и интерактивный.
Возможность применения того или иного режима преобразования определяется также целью преобразования: в некоторых случаях топологической связностью элементов получаемой оболочки, а также ее корректностью допустимо пренебречь. Такой подход возможен, например, для оптимизации отрисовки в BIM-приложении, когда пользователь может добавлять произвольные предметы интерьера в текущую модель помещения. В то же время, для задач реверс-инжиниринга необходимо получить как можно более точную копию исходной модели, например с заданной точностью соблюсти соосность цилиндров, обеспечить касательное расположение пары поверхностей и в результате получить корректную топологию модели. В таком случае без вмешательства пользователя в процесс преобразования не обойтись.
Интерфейс автоматического преобразования C3D B-Shaper представлен следующими функциями, которые принимают на вход исходную сетку и настройки преобразования:
MbResultType ConvertMeshToShell( MbMesh & mesh,
MbFaceShell *& shell,
const MbMeshProcessorValues & params );
MbResultType ConvertCollectionToShell( MbCollection & collection,
MbFaceShell *& shell,
const MbMeshProcessorValues & params );
К настройкам преобразования относится значение точности распознавания, то есть максимально допустимого отстояния вершин полигональной сетки в границах данного сегмента до распознаваемой поверхности. Эта точность может быть абсолютной или относительной: при использовании относительной точности отклонение граней тела от сетки проверяется относительно размера модели. Также пользователю доступна опция переключения режимов распознавания, которая позволяет управлять типами поверхностей при реконструкции.
Расширенные возможности по управлению процессами сегментации и распознавания поверхностей предоставляет интерфейс класса MbMeshProcessor:
class MbMeshProcessor {
..
public:
// “Лечение” сетки.
void SetUseMeshSmoothing( bool useSmoothing );
// Управление сегментацией сетки.
const MbCollection & GetSegmentedMesh();
MbResultType SegmentMesh( bool createSurfaces = true );
void ResetSegmentation();
void UniteSegments( size_t firstSegmentIdx, size_t secondSegmentIdx );
MbResultType SegmentMeshBySeparators( const std::vectorvector> & sep );
// Управление распознаванием поверхностей.
void FitSurfaceToSegment( size_t idxSegment );
void FitSurfaceToSegment( size_t idxSegment, MbeSpaceType surfaceType );
const MbSurface * GetSegmentSurface( size_t idxSegment ) const;
// Построение B-Rep модели.
MbResultType CreateBRepShell( MbFaceShell *& pShell );
..
}
Например, для коррекции результатов автоматической сегментации пользователю C3D B-Shaper предоставляются инструменты по объединению сегментов, их разделению и т.д. Пользователь может вписать в данный сегмент поверхность заданного типа, а также изменить параметры для уже распознанной поверхности.
Заключение
На текущий момент C3D B-Shaper активно развивается: улучшаются алгоритмы автоматической сегментации, разрабатываются инструменты для редактирования сегментации, совершенствуется построение поверхности свободной формы (NURBS) на базе сегмента, проводятся работы по улучшению качества сборки оболочек B-Rep. Разумеется, вектор развития для C3D B-Shaper задают и наши заказчики — пользователи геометрического ядра С3D. Надеемся, что в скором будущем мы сможем создать по-настоящему функциональный инструмент по преобразованию из полигонального представления в граничное.
Заинтересованные разработчики могут взять C3D B-Shaper на тестирование в составе C3D Toolkit или в качестве самостоятельного компонента. Заявки направляйте на
info@c3dlabs.com.
