¬аше окно в мир —јѕ–
Ќовости —татьи јвторы —обыти€ ¬акансии Ёнциклопеди€ –екламодател€м
—татьи

24 окт€бр€ 2023

ѕолигональное моделирование: от фундамента к продвинутым алгоритмам

јлександр Ћонин

јлександр Ћонин

јвтор Ч руководитель группы по полигональному моделированию, к. ф.-м. н., C3D Labs

ќригинал публикации в блоге компании C3D Labs


јвтор представл€ет обзор топологии полигональной сетки, делитс€ информацией об усовершенствовани€х и новом функционале, а также знакомит с планами развити€ направлени€ полигонального моделировани€.


ƒл€ работы большинства алгоритмов недостаточно иметь представление о сетке только как о наборе треугольников, примером чего служит результат ее конвертации из формата STL. ≈динственное, что можно сделать с такой сеткой, Ч это нарисовать ее и посчитать площадь. ƒл€ всего остального в нашем распор€жении должна быть нека€ топологическа€ структура, котора€ и €вл€етс€ фундаментом в полигональном моделировании.

Ёта структура содержит две основные составл€ющие. ¬о-первых, это топологи€ сетки, котора€ описывает св€зи между вершинами, ребрами и полигонами. ќна должна поддерживать не только треугольники, но и полигоны с произвольным числом сторон, или фасеты.  роме того, в зоне ее ответственности Ч обеспечение р€да базовых элементарных операций над ними, например, таких, как упор€доченный обход фасетов соседних с выбранным, упор€доченный обход веера вершины, коллапс ребра, вставка вершины, переброс ребра и некоторых других.

 ак правило, сетка интересна не столько сама по себе, сколько вместе с неким логическим разбиением фасетов на группы. ќтсюда возникает втора€ составл€юща€ топологии Ч сегментаци€. ѕо структуре она аналогична стандартной B-rep-модели: те же грани, циклы и ребра, только гран€ми €вл€ютс€ св€занные группы фасетов, а ребра составлены из последовательностей ребер сетки. «десь также необходим набор базовых операций по аналогии с топологией сетки, а именно разнообразный обход соседних сегментов, создание новой сегментации или разбиение существующей заданным набором ребер или фасетов, объединение одного или нескольких сегментов, переброска граничных фасетов из одного сегмента в другой и т. п.

»ллюстраци€ демонстрирует разбиение существующей сегментации. –азные сегменты подсвечены разными цветами, заданными набором ребер, который обозначен желтой полилинией. ¬торое изображение Ч результат такого разбиени€.  роме этого, каждому топологическому элементу необходимо поставить в соответствие некий абстрактный атрибут Ч это может быть число, вектор, поверхность, произвольна€ структура.

ѕолигональное моделирование

–ис. 1

Ќа первый взгл€д, все, о чем шла речь, это давно известные факты, которые кажутс€ весьма простыми дл€ имплементации. ќднако если учесть все разнообразие алгоритмов, которое складываетс€ из этих базовых операций как из кубиков, то оказываетс€, что это весьма ответственна€ часть работы, к которой надо относитьс€ максимально серьезно. ќсобенно если брать в расчет необходимость поддержки актуальности и валидности топологической информации на каждом этапе алгоритма. «ато в результате мы получаем мощный универсальный инструмент, отталкива€сь от которого как от фундамента, можно решать любые задачи в области полигонального моделировани€. Ќа данный момент мы €вл€емс€ полностью самодостаточными разработчиками в полигональном моделировании и не опираемс€ ни на какие сторонние или open source-решени€ или продукты.

–ассмотрим результаты, полученные с применением такого системного подхода. √лобально мы наблюдаем улучшение всего имеющегос€ функционала, преимущественно Ч ускорение. Ѕазовое лечение сетки на сегодн€ сводитс€ к созданию топологии. Ќа этом этапе устран€ютс€ наиболее очевидные проблемы: дублированные вершины, вырожденные треугольники, дублированные треугольники, неконсистентные нормали. ѕомимо этого, отслеживаютс€ разного рода неманифолдности. Ѕулевы операции и 3D-выпукла€ оболочка были ускорены до 30-40 раз соответственно. „ем больше сетка Ч тем больше ускорение. “акие операции, как поиск открытых границ или границ св€зных частей заданного набора фасетов, станов€тс€ практически тривиальными. Ќа иллюстрации Ч лечение сетки с неконсистентными нормал€ми. Ќа первом рисунке каждый треугольник перевернут относительно соседей, а на втором Ч результат приведени€ сетки к нормальному виду.

ѕолигональное моделирование

–ис. 2

Ќовый функционал объедин€ет добавление 2D-выпуклой оболочки, упрощение триангул€ции, параметризацию сеток, вписывание NURBS-поверхности и аналитических поверхностей в набор полигонов.

Ќа данной иллюстрации мы видим, что все точки триангул€ции спроецированы на плоскость, и синим цветом обозначена выпукла€ оболочка. ≈сли она есть в наличии, можно построить минимально описанный пр€моугольник.

ѕолигональное моделирование

–ис. 3

¬ случае с упрощением триангул€ции возможны два варианта: упрощение до заданного количества треугольников или до достижени€ заданной точности. ¬месте с тем есть возможность получить набор упрощенных сеток с разным уровнем детализации. ”прощение представл€ет собой последовательность коллапсов ребер, то есть базовой операции, упом€нутой вначале. ѕри этом запрещен р€д коллапсов, например, тот, который может привести к сшивке двух треугольников по двум ребрам, схлопыванию открытого контура и т. д. Ёто гарантирует сохранение топологических свойств полигонального объекта. ≈сли он был подобен диску Ч он таким и останетс€, если на нем было n контуров или n ручек, это число также останетс€ неизменным.

Ќа иллюстраци€х нагл€дно показан набор сеток разной степени детализации.   примеру, на последнем из серии рисунков бегемотик симплифицирован до состо€ни€ тетраэдра. ≈го дальнейша€ симплификаци€ невозможна без нарушени€ топологических свойств.

ѕолигональное моделирование

–ис. 4

ƒанное изображение Ч пример симплификации сетки более сложной топологический структуры.

ѕолигональное моделирование

–ис. 5

Ќесмотр€ на то что параметризаци€ сеток пока не присутствует в API, она €вл€етс€ одним из основных инструментов меш-процессинга. ѕроанализируем этот сегмент на примере модели, в качестве которой выбрано лицо Ќаполеона, вз€тое из открытых источников.

ѕолигональное моделирование

–ис. 6

¬ самом упрощенном виде возможны два случа€ Ч параметризаци€ со свободной границей и параметризаци€ с фиксированной границей. ѕод параметризацией мы понимаем отображение сетки на плоскость. ѕараметризаци€ со свободной границей Ч самый общий случай и самый вычислительно сложный. «адача алгоритма Ч придумать 2D-координаты дл€ каждой вершины сетки. “опологически она должна быть подобна диску. »зображение Ч результат работы алгоритма.

ѕолигональное моделирование

–ис. 7

Ќа плоскости лицо выгл€дит так, как на рисунке слева. Ќаиболее известное применение параметризации сеток Ч нат€гивание структуры на поверхность сложной формы. ≈сли в 2D мы нарисуем регул€рную пр€моугольную сетку, то в 3D она будет выгл€деть так, как на рисунке справа.

ѕараметризаци€ с фиксированной границей Ч более простой вариант. ƒл€ граничных вершин задаем 2D-координаты из неких соображений, а дл€ внутренних Ч вычисл€ем. ¬ общем случае, когда ничего неизвестно, можно остановитьс€ на отображении на круге. Ћицо на круге выгл€дит как на рисунке слева, справа Ч иллюстраци€ в 3D.

ѕолигональное моделирование

–ис. 8

≈сли имеютс€ некие априорные знани€ о сетке, как в данном случае, мы понимаем, что на открытом контуре есть четыре угла, и можем отобразить лицо на пр€моугольник. ‘ормально это самый предпочтительный вариант, и результат представлен на картинке.

ѕолигональное моделирование

–ис. 9

ќднако у такого подхода есть границы применени€. ¬озьмем сетку более сложной формы, такую, как, например, —тэнфордский кролик. –исунок слева Ч то, как он выгл€дит при отображении на круг. ѕараметризаци€ крайне неравномерна€: внизу квадратики маленькие, вверху Ч большие. —ледовательно, нужно придумывать какие-то другие методы.

ѕолигональное моделирование

–ис. 10

¬ таком разделе, как вписывание NURBS-поверхности, возможен автоматический подбор узлового вектора. ¬ходными данными €вл€ютс€ набор треугольников, пор€док сплайна, максимально разрешенное количество контрольных точек, коэффициент сглаживани€ и желаема€ точность, в которую мы стараемс€ уложитьс€. ¬писывание NURBS-поверхности основано именно на параметризации сеток. ќна подсказывает, какие 2D-параметры должны быть у вершин, а име€ 2D-параметры, мы можем осуществить аппроксимацию поверхности.

Ёта иллюстраци€ демонстрирует результаты дл€ разных стратегий параметризации.

ѕолигональное моделирование

–ис. 11

—лева Ч самый общий вариант параметризации с открытой границей. ¬идно, что поверхность хорошо совпадает с сеткой в тех местах, где она есть, и определенным образом ведет себ€ там, где ее нет. ќтображение на круг Ч естественно, наименее желательный случай. ѕри этом использование некоторой априорной информации о сетке обеспечивает наиболее приемлемый результат.

ƒалее проиллюстрирована сеть контрольных точек получившейс€ поверхности.

ѕолигональное моделирование

–ис. 12

Ќа следующем изображении Ч вли€ние степени сглаживани€. —лева направо степень сглаживани€ уменьшаетс€.

ѕолигональное моделирование

–ис. 13

ќп€ть же этот подход имеет ограниченные области применени€.   примеру, если попытатьс€ представить одной поверхностью кролика, то получитс€ совершенно неудовлетворительный результат, а значит, нужно искать другие пути.

ѕолигональное моделирование

–ис. 14

„то касаетс€ вписывани€ аналитических поверхностей методом наименьших квадратов, здесь тоже имеютс€ варианты, а именно вписывание поверхности заданного типа, либо ее автоопределение. ¬озможность отбраковки выбросов по разным критери€м, а также некий контроль формы, направленный на то, чтобы не создавать поверхности, близкие к вырожденным, например, почти плоские или почти цилиндрические конусы. ¬ходными данными здесь также €вл€ютс€ набор треугольников и желаема€ точность. “олько в этом случае точность используетс€ исключительно дл€ контрол€ результата в формате Ђуложились-не уложилисьї.

Ќа следующих слайдах Ч примеры вписывани€ разных примитивов. ѕлоскость:

ѕолигональное моделирование

–ис. 15

÷илиндр, вписанный в сетку довольно плохого качества:

ѕолигональное моделирование

–ис. 16

ƒалее представлен сектор цилиндра:

ѕолигональное моделирование

–ис. 17

Ёта иллюстраци€ подтверждает необходимость отбраковки выбросов. ќбратите внимание на артефакты, расположенные слева внизу на сетке. ≈сли учитывать их при вписывании, они об€зательно дадут какой-то систематический сдвиг. —истема отбраковки позвол€ет избавитьс€ от них и получить более качественный результат.

Ќа этом рисунке Ч пример вписывани€ сферы.

ѕолигональное моделирование

–ис. 18

Ёто Ч конус.

ѕолигональное моделирование

–ис. 19

Ёто Ч тор.

ѕолигональное моделирование

–ис. 20

“аким образом мы покрываем все виды аналитических примитивов.


ѕару слов о B-Shaper.  онцептуально он не изменилс€, но был несколько обновлен, в частности, его функционал был переведен на новую топологию.  роме того, были использованы новые алгоритмы вписывани€. Ёто позволило улучшить работу со швами замкнутых поверхностей и оптимизировать р€д других процессов.

ѕланы в области B-Shaper касаютс€, в первую очередь, формировани€ специального подхода к скан-сеткам. »звестно, что любой автоматический алгоритм не дает на них удовлетворительных результатов. ≈ще одна ключева€ задача Ч развитие полуавтоматического реверса с интерактивной сегментацией и с подсказками пользовател€м. —ледующа€ цель Ч распознавание кинематических поверхностей. Ќа данном этапе инструмент включает распознавание поверхностей вращени€, но его необходимо оптимизировать и дополнить распознаванием поверхностей выдавливани€, или экструзии. Ќе менее важна€ задача Ч автоматическа€ генераци€ сети из NURBS-патчей. Ёто необходимо, чтобы в параметрическом виде представл€ть сложные поверхности наподобие того же —тэнфордского кролика.

¬ планах в области полигонального моделировани€ Ч вписывание поверхностей с учетом ограничений. Ќапример, когда требуетс€ вписать не просто цилиндр, а цилиндр, ось которого должна быть перпендикул€рна заданной плоскости. ¬ отношении диагностики и лечени€ сеток также есть планы.  ак правило, базового лечени€ недостаточно. Ќа сетке могут быть совершенно разнообразные проблемы Ч зазоры, дырки, самопересечени€, топологические дефекты. ¬ажно иметь функционал дл€ эффективных диагностики и лечени€. ¬ перспективе Ч регистраци€ или совмещение сеток и облаков, которые наход€тс€ в разных системах координат. Ёто важно дл€ того же самого контрол€, чтобы определ€ть, насколько хорошо была сделана та или ина€ деталь. ѕредположим, у нас есть сама деталь в параметрическом виде и есть набор точек, полученных сканированием. Ќадо их совместить и спроецировать одно на другое. —писок задач также включает дальнейшее развитие булевых операций и представление в API уже существующих алгоритмов, которые сейчас там не представлены, но используютс€ на отдельных внутренних стади€х. Ќапример, сегментаци€ по острым сломам, сглаживание сетки или оценка разных параметров поверхностей по сетке, в том числе кривизн.

—лева на иллюстрации мы можем увидеть направление главных кривизн, оцененных по триангул€ции, справа Ч направление нормалей.

ѕолигональное моделирование

–ис. 21



¬акансии:

јктуальное обсуждение

RSS-лента комментариев

-->

ƒавид Ћевин
ƒавид Ћевин
ќт редактора: „тобы не пострадать от роботов, человеку нужно надЄжно отличатьс€ от продуктового контейнера
ѕроект ЂЌародное —јѕ–-интервьюї

—лучайна€ стать€:

 алендарный график производства работ: ключевой инструмент эффективного [...] — Ќатали€ “орлопова, директор по продуктам Formind (13 окт€бр€ 2023)
isicad Top 10

—амые попул€рные материалы

   ‘орумы isicad:

isicad-2010 isicad-2008
isicad-2006 isicad-2004

ќ проекте

ѕриглашаем публиковать на сайте isicad.ru новости и пресс-релизы о новых решени€х и продуктах, о проводимых меропри€ти€х и другую информацию. јдрес дл€ корреспонденции - info@isicad.ru

ѕроект isicad нацелен на

  • укрепление контактов между разработчиками, поставщиками и потребител€ми промышленных решений в област€х PLM и ERP...
ѕодробнее

»нформаци€ дл€ рекламодателей


¬се права защищены. © 2004-2023 √руппа компаний «Ћ≈ƒј—»

ѕерепечатка материалов сайта допускаетс€ с согласи€ редакции, ссылка на isicad.ru об€зательна.
¬ы можете обратитьс€ к нам по адресу info@isicad.ru.