group homepage                                                                                                          English version

Проект sotm - построитель сеток Делоне и полиэдральных сеток для аналитически заданных тел.

Идея алгоритма предложена в работе Перссона и Стренга в 2004 г. и состоит в том, чтобы рассматривать расчетную сетку как упругую сеть, в которой каждое ребро Делоне является упругой распоркой. В результате расталкивания и изменения связности в соответствии с критерием Делоне, сетка заполняет неявно заданную область, словно строительная пена. В оригинальной работе текст генератора занимает одну страницу на языке Matlab. В 2008г. в работе Белоусовой (Кудрявцевой) и Гаранжи было предложено добавить для управления сеткой обостряющую силу, которая ранее была предложена для решения задачи визуализации неявно заданных поверхностей в работе Беляева, 2002г. На основе этой идеи А.И. Белокрыс-Федотов реализовал алгоритм на C++, который не только автоматически воспроизводит острые ребра на границе неявно заданных тел, но и строит при этом сетки Делоне без  плоских тетраэдров. Текущая версия алгоритма самоорганизация - исследовательская. Она пока существенно уступает по эффективности известным кодам для построения сеток Делоне в сложных областях, однако, по-видимому, это единственный код, который позволяет строить сетки Делоне прямо по аналитически заданным неявным функциям и автоматически воспроизводит ребра и конические точки на поверхности без их явного задания пользователем. Этот код одновременно решает задачу точной реконструкции модели, и строит достаточно качественную поверхностную и объемную сетку.


Работа алгоритма иллюстрируется на основе теста из работы А. Беляева с соавторами, 2002. Показано начальное приближение - сетка, которая даже не заполняет область. Довольно быстро граница восстанавливается. После этого добавляются упругие силы, которые исправляют формы ячеек. При этом не происходит разрушения формы тела и ребра сетки не уходят с острых граничных ребер.


Видно, как добавление оптимизации формы позволяет удалить плоские тетраэдры. При этом сетка остается сеткой Делоне в строгом смысле.


В анимации  показан процесс восстановления аналитически заданной области, при котором "проявляются"  острые граничные ребра.




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


Объединяя призматический генератор с тераэдральным, получаем генератор гибридных сеток.


На основе такой сетки строится гибридная сетка из полиэдров со слоем полигональных призм около тела.