Генерация сетки

Конечно-элементная сетка четырехугольников криволинейной области.

Генерация сетки - это практика создания сетки , подразделение непрерывного геометрического пространства на дискретные геометрические и топологические ячейки. Часто эти клетки образуют симплициальный комплекс . Обычно ячейки разделяют геометрическую область ввода. Ячейки сетки используются как дискретные локальные аппроксимации более крупной области. Сетки создаются с помощью компьютерных алгоритмов, часто под руководством человека через графический интерфейс.в зависимости от сложности области и желаемого типа сетки. Цель состоит в том, чтобы создать сетку, которая точно отражает геометрию входной области, с высококачественными ячейками (правильной формы) и без такого количества ячеек, чтобы сделать последующие вычисления трудноразрешимыми. Сетка также должна быть мелкой (иметь мелкие элементы) в областях, важных для последующих расчетов.

Сетки используются для визуализации на экране компьютера и для физического моделирования, такого как анализ методом конечных элементов или вычислительная гидродинамика . Сетки состоят из простых ячеек, таких как треугольники, потому что, например, мы знаем, как выполнять такие операции, как вычисления методом конечных элементов (инженерия) или трассировка лучей (компьютерная графика) на треугольниках, но мы не знаем, как выполнять эти операции непосредственно на сложных пространствах. и формы, такие как проезжий мост. Мы можем смоделировать прочность моста или нарисовать его на экране компьютера, выполнив вычисления для каждого треугольника и вычислив взаимодействия между треугольниками.

Основное различие между структурированными и неструктурированными сетками. В структурированной сетке сетка представляет собой обычную решетку, такую ​​как массив, с подразумеваемой связностью между элементами. В неструктурированной сетке элементы могут быть соединены друг с другом по нерегулярной схеме, и могут быть захвачены более сложные области. Эта страница в основном посвящена неструктурированным сеткам. Хотя сетка может быть триангуляцией , процесс создания сетки отличается от триангуляции набора точек тем, что создание сетки включает свободу добавления вершин, отсутствующих во входных данных. «Фацетирование» (триангуляция) САПРмодели для черчения имеют такую ​​же свободу добавления вершин, но цель состоит в том, чтобы точно представить форму, используя как можно меньше треугольников, а форма отдельных треугольников не важна. При визуализации текстур и реалистичных условий освещения компьютерной графикой вместо этого используются сетки.

Многие программы для создания сетки связаны с CAD-системой, определяющей входные данные, и программным обеспечением для моделирования для получения выходных данных. Входные данные могут сильно различаться, но распространенными формами являются твердотельное моделирование , геометрическое моделирование , NURBS , B-rep , STL или облако точек .

Терминология [ править ]

Термины « создание сетки », « создание сетки », « сетка » и « сетка » часто используются взаимозаменяемо, хотя, строго говоря, последние два являются более широкими и охватывают улучшение сетки: изменение сетки с целью увеличения скорости или точность численных вычислений, которые будут выполнены над ним. В рендеринге компьютерной графики и математике сетку иногда называют тесселяцией .

Грани сетки (ячейки, объекты) имеют разные имена в зависимости от их размера и контекста, в котором будет использоваться сетка. В конечных элементах элементы сетки с наибольшей размерностью называются «элементами», «ребра» - 1D, а «узлы» - 0D. Если элементы являются трехмерными, то двумерные объекты являются «гранями». В вычислительной геометрии 0D-точки называются вершинами. Тетраэдры часто сокращенно называют «тетраэдрами»; треугольники - это «трис», четырехугольники - «четырехугольники», а шестигранники (топологические кубы) - «шестиугольники».

Методы [ править ]

Многие методы построения сетки построены на принципах триангуляции Делоне вместе с правилами добавления вершин, такими как алгоритм Рупперта . Отличительной особенностью является то, что сначала формируется грубая сетка всего пространства, затем добавляются вершины и треугольники. Напротив, прогрессивные передние алгоритмы начинаются с границы домена и добавляют элементы, постепенно заполняя внутреннюю часть. Гибридные методы делают и то, и другое. Особый класс методов продвижения фронта создает тонкие пограничные слои элементов для потока жидкости. При создании структурированной сетки вся сетка представляет собой решетчатый граф , например регулярную сетку квадратов. Создание структурированной сетки длярегулярные сетки - это само по себе целое поле, с математическими методами, применяемыми для обеспечения того, чтобы линии сетки с высоким полиномиальным порядком следовали пространству решения плавно и точно. При блочно-структурированной сетке домен делится на большие подобласти, каждая из которых представляет собой структурированную сетку. Некоторые прямые методы начинаются с сетки с блочной структурой, а затем перемещают сетку в соответствии с входными данными; см. Автоматическое создание шестиугольной сетки на основе поликуба . Другой прямой метод - разрезать структурированные ячейки по границе домена; см. лепить по маршевым кубам .

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

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

Типы сеток [ править ]

См. Также Типы сеток .

Топология ячейки [ править ]

Обычно ячейки имеют многоугольную или многогранную форму и образуют сетку , разделяющую область. Важные классы двумерных элементов включают треугольники (симплексы) и четырехугольники (топологические квадраты). В трехмерном пространстве наиболее распространенными ячейками являются тетраэдры (симплексы) и шестигранники (топологические кубы). Симплициальные сетки могут иметь любую размерность и включать треугольники (2D) и тетраэдры (3D) в качестве важных примеров.Кубические сетки - это категория пан-измерений, которая включает четырехугольники (2D) и шестиугольники (3D). В 3D 4-сторонние пирамиды и 3-сторонние призмы появляются в конформных сетках смешанного типа ячеек.

Размер ячейки [ править ]

Сетка встроена в геометрическое пространство, которое обычно бывает двух- или трехмерным , хотя иногда размерность увеличивается на единицу путем добавления измерения времени. Сетки более высокой размерности используются в нишевых контекстах. Одномерные сетки тоже полезны. Важная категория - это поверхностные сетки, которые представляют собой 2D-сетки, встроенные в 3D для представления криволинейной поверхности.

Двойственность [ править ]

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

Тип сетки по использованию [ править ]

Трехмерные сетки, созданные для анализа методом конечных элементов, должны состоять из тетраэдров , пирамид , призм или шестигранников . Те, которые используются для метода конечных объемов, могут состоять из произвольных многогранников . Те, которые используются для методов конечных разностей, состоят из кусочно-структурированных массивов гексаэдров, известных как многоблочные структурированные сетки. Четырехсторонние пирамиды используются для конформного соединения шестиугольников с тетами. Трехсторонние призмы используются для граничных слоев, соответствующих решетчатой ​​сетке дальней внутренней части объекта.

Поверхностные сетки полезны в компьютерной графике, где поверхности объектов отражают свет (также подповерхностное рассеяние ) и полная трехмерная сетка не требуется. Поверхностные сетки также используются для моделирования тонких объектов, таких как листовой металл, в автомобилестроении и экстерьеров зданий в архитектуре. Кубические сетки большой (например, 17) размерности распространены в астрофизике и теории струн .

Математическое определение и варианты [ править ]

Каково точное определение сетки? Не существует общепринятого математического описания, применимого во всех контекстах. Однако некоторые математические объекты явно являются сетками: симплициальный комплекс - это сетка, составленная из симплексов. Большинство полиэдральных (например, кубических) сеток являются конформными, что означает , что они имеют ячеечную структуру комплекса CW , обобщения симплициального комплекса.. Сетка не обязательно должна быть симплициальной, потому что произвольное подмножество узлов ячейки не обязательно является ячейкой: например, три узла четырехугольника не определяют ячейку. Однако две ячейки пересекаются в ячейках: например, у четырехугольника нет узла внутри. На пересечении двух ячеек может быть несколько ячеек: например, два квадрата могут иметь два общих ребра. Пересечение более чем одной ячейки иногда запрещено и редко желательно; цель некоторых методов улучшения сетки (например, подушки) - удалить эти конфигурации. В некоторых контекстах проводится различие между топологической сеткой и геометрической сеткой, встраивание которой удовлетворяет определенным критериям качества.

Важные варианты сеток, которые не являются комплексами CW, включают неконформные сетки, где ячейки не встречаются строго лицом к лицу, но ячейки, тем не менее, разделяют домен. Примером этого является октодерево , где грань элемента может быть разделена гранями смежных элементов. Такие сетки полезны для моделирования на основе потоков. В сетках с перекрытием есть несколько конформных сеток, которые геометрически перекрываются и не разделяют область; см., например, Overflow, решатель OVERset grid FLOW . Так называемые методы без сетки или без сеткичасто используют некоторую сетчатую дискретизацию области и имеют базовые функции с поддержкой перекрытия. Иногда локальная сетка создается около каждой точки степени свободы моделирования, и эти сетки могут перекрываться и быть неконформными друг другу.

Элементы высокого порядка [ править ]

Многие сетки используют линейные элементы, где отображение абстрактного элемента в реализованный является линейным, а края сетки представляют собой прямые сегменты. Часто встречаются полиномиальные отображения более высокого порядка, особенно квадратичные. Основная цель для элементов более высокого порядка - более точно представить границу домена, хотя они также имеют преимущество в точности внутри сетки. Одним из мотивов создания кубических сеток является то, что линейные кубические элементы имеют те же числовые преимущества, что и квадратичные симплициальные элементы. В методе моделирования изогеометрического анализа ячейки сетки, содержащие границу домена, используют представление САПР напрямую вместо линейного или полиномиального приближения.

Улучшение сетки [ править ]

Улучшение сетки включает изменение ее дискретной связности, непрерывного геометрического положения ее ячеек или того и другого. Для дискретных изменений, для симплициальных элементов меняют местами края и вставляют / удаляют узлы. Те же операции выполняются и для кубических (четырехугольных / шестнадцатеричных) сеток, хотя существует меньше возможных операций, а локальные изменения имеют глобальные последствия. Например, для гексаэдрической сетки слияние двух узлов создает ячейки, которые не являются гексагонами, но если диагонально противоположные узлы на четырехугольнике объединяются, и это распространяется на сжатие всего соединенного гранями столбца гексов, тогда все оставшиеся ячейки все равно будут гексы. В адаптивном уточнении сетки, элементы разделяются (h-уточнение) в областях, где вычисляемая функция имеет высокий градиент. Сетки также огрубляют, удаляя элементы для большей эффективности. Многосеточный метод делает что - то похожее на утонченность и огрубление для ускорения численного решения, но без фактического изменения сетки.

Для непрерывных изменений узлы перемещаются или грани более высоких измерений перемещаются путем изменения полиномиального порядка элементов. Перемещение узлов для улучшения качества называется «сглаживанием» или «r-уточнением», а увеличение порядка элементов называется «p-уточнением». Узлы также перемещаются при моделировании, когда форма объектов меняется со временем. Это ухудшает форму элементов. Если объект достаточно деформируется, весь объект заменяется сеткой, и текущее решение отображается из старой сетки в новую.

Практикующие [ править ]

Эта область является междисциплинарной и включает в себя математику , информатику и инженерию . Исследования и разработки по построению сетки отличаются тем, что в равной степени сосредоточены на дискретной и непрерывной математике и вычислениях, как и в случае с вычислительной геометрией , но в отличие от теории графов (дискретного) и численного анализа(непрерывный). Создание сетки обманчиво сложно: людям легко увидеть, как создать сетку из заданного объекта, но сложно запрограммировать компьютер, чтобы априори принимать правильные решения для произвольного ввода. В природе и объектах, созданных руками человека, существует бесконечное разнообразие геометрии. Многие исследователи создания сеток были первыми пользователями сеток. Генерация сеток продолжает получать широкое внимание, поддержку и финансирование, потому что человеческое время для создания сетки затмевает время на настройку и выполнение расчетов после завершения сетки. Так было всегда с тех пор, как были изобретены численное моделирование и компьютерная графика, потому что по мере совершенствования компьютерного оборудования и простого программного обеспечения для решения уравнений люди были привлечены к более крупным и более сложным геометрическим моделям в стремлении к большей точности, научному пониманию,и художественное выражение.

Действия сообщества [ править ]

Литература на сайте списка Mesh Generation

Журналы [ править ]

Исследования построения сеток публикуются во многих журналах. Это соответствует междисциплинарному характеру исследований, необходимых для достижения прогресса, а также широкому спектру приложений, в которых используются сетки. Ежегодно в 20 журналах появляется около 150 взаимосвязанных публикаций, причем в одном журнале появляется не более 20 публикаций. Нет журнала, основная тема которого связана с сеткой. Журналы, которые публикуют не менее 10 статей в год, выделены жирным шрифтом.

• Достижения в инженерном программном обеспечении
• Американский институт аэронавтики и астронавтики, журнал (AIAAJ)
• Алгоритмика
• Журнал Общества прикладной вычислительной электромагнетизма
• Прикладная вычислительная математика
• Астрономия и вычисления
• Вычислительная геометрия: теория и приложения
• Система автоматизированного проектирования (САПР) часто включает специальный выпуск, посвященный расширенным статьям IMR (см. Конференции ниже)
• Компьютерный геометрический дизайн (CAGD)
• Форум компьютерной графики (Eurographics)
• Компьютерные методы в прикладной механике и технике
• Дискретная и вычислительная геометрия
• Разработка с помощью компьютеров
• Конечные элементы в анализе и дизайне
• Международный журнал численных методов в инженерии (IJNME)
• Международный журнал численных методов в жидкостях
• Международный журнал численных методов в биомедицинской инженерии
• Международный журнал вычислительной геометрии и приложений
• Журнал вычислительной физики (JCP)
• Журнал численного анализа
• Журнал по научным вычислениям (SISC)
• Транзакции с графикой (ACM TOG)
• Транзакции по математическому программному обеспечению (ACM TOMS)
• Транзакции по визуализации и компьютерной графике (IEEE TVCG)
• Конспект лекций по вычислительным наукам и технике (LNCSE)
• Вычислительная математика и математическая физика (CMMP)

Конференции [ править ]

Жирным шрифтом выделены конференции, основная тема которых - объединение .

Веб-сайт со списком конференций, семинаров, летних школ

• Встреча по аэрокосмическим наукам AIAA (15 взаимосвязанных докладов / докладов)
• Канадская конференция по вычислительной геометрии CCCG
• CompIMAGE: Международный симпозиум по вычислительному моделированию объектов, представленных в изображениях
• Конференция по вычислительной гидродинамике AIAA
• Конференция по вычислительной гидродинамике ECCOMAS
• Вычислительная наука и инженерия CS&E
• Конференция ISGG по созданию цифровых сетей
• Ежегодная конференция Eurographics (Eurographics) (материалы Форума компьютерной графики )
• Геометрическое и физическое моделирование SIAM
• Международная конференция по изогеометрическому анализу IGA
• Международный круглый стол IMR
• Международный симпозиум по вычислительной геометрии SoCG
• Числовая геометрия, построение сеток и научные вычисления (NUMGRID) (материалы лекций по вычислительной науке и технике )
• SIGGRAPH (работа в ACM Transactions on Graphics )
• Симпозиум по обработке геометрии SGP ( Eurographics ) (материалы форума по компьютерной графике )
• Всемирный инженерный конгресс

Мастерские [ править ]

Жирным шрифтом выделены семинары, основной темой которых является создание сетки .

• Конференция по геометрии: теория и приложения CGTA
• Европейский семинар по вычислительной геометрии EuroCG
• Осенний семинар по вычислительной геометрии
• Конечные элементы в жидкостях FEF
• Симпозиум MeshTrends (в другие годы WCCM или USNCCM)
• Методы многогранных элементов в математике и инженерии
• Мастерская тетраэдра

Ресурсы [ править ]

Генераторы сеток [ править ]

Во многих описаниях коммерческих продуктов делается упор на моделирование, а не на технологию построения сеток, обеспечивающую моделирование.

• Списки генераторов сеток (внешних):
  • Бесплатные / открытые генераторы сеток
  • Общественное достояние и коммерческие генераторы сетки
• Препроцессор ANSA
• ANSYS
• CD-adapco и Siemens DISW
• Comet Solutions
• Библиотека алгоритмов вычислительной геометрии CGAL
  • Генерация сетки
    • Соответствующие 2D-триангуляции и сетки
    • Создание 3D-сетки
• ЛОКОТЬ
• Gmsh
• Hextreme сетки
• MeshLab
• Программное обеспечение MSC
• Omega_h Tri / Tet Адаптивность
• Создание и преобразование Open FOAM Mesh
• Модуль Salome Mesh
• TetGen
• TetWild
• ТРЕУГОЛЬНИК Генерация сетки и триангуляция Делоне

Генераторы многодоменных секционированных сеток [ править ]

Эти инструменты генерируют разделенные сетки, необходимые для моделирования методом конечных элементов из нескольких материалов.

• MDM (Multiple Domain Meshing) автоматически и эффективно генерирует неструктурированные тетраэдрические и гексаэдрические сетки для композитного домена, состоящего из гетерогенных материалов.

• QMDM (Quality Multi-Domain Meshing) создает высококачественные взаимно согласованные треугольные поверхностные сетки для нескольких доменов.

• QMDMNG (Качественная многодоменная сетка без зазоров) создает качественные сетки, каждая из которых представляет собой двумерный коллектор и без зазора между двумя соседними сетками.

• SOFA_mesh_partitioning_tools генерирует разделенные тетраэдрические сетки для многоматериальных FEM на основе CGAL.

Статьи [ править ]

• Еще одна тонкая сетка, блог MeshTrends, Pointwise
• Генерация сеток и сеток в Интернете
• Группа создания сетки в LinkedIn

Исследовательские группы и люди [ править ]

• Пользователи Mesh Generation в Google Scholar
• Дэвид Боммс, Группа компьютерной графики, Бернский университет
• Геометрия Дэвида Эппштейна в действии, создание сетки
• Джонатан Шеучек «s раскатывания и триангуляции в графике, инженерии и моделирования
• Скотт А. Митчелл
• Роберт Шнайдерс

Модели и сетки [ править ]

Полезные модели (входы) и сетки (выходы) для сравнения алгоритмов построения сеток и сеток.

• В HexaLab есть модели и сетки, которые были опубликованы в исследовательских работах, реконструированы или взяты из исходной статьи.
• Тест формы Принстона
• Конкурс на поиск формы SHREC предлагает разные модели каждый год, например,
  • Конкурс на поиск формы нежестких 3D водонепроницаемых сеток 2011
• Сеточные модели Thingi10k из вселенной Thingiverse

Модели САПР [ править ]

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

• ACIS от Spatial
• Открытый каскад

Форматы файлов сетки [ править ]

Общие (выходные) форматы файлов для описания сеток.

• NetCDF
• Бытие / Исход
• XDMF
• ВТК / ВТУ
• МЕДИТ
• MED / Саломея
• Gmsh
• ANSYS сетка
• ВЫКЛЮЧЕННЫЙ
• OBJ волнового фронта
• PLY
• STL

meshio может конвертировать между всеми перечисленными выше форматами.

Визуализаторы сетки [ править ]

• Блендер
• Средство просмотра сетки
• Paraview

Книги [ править ]

• Методы построения сеток - Лисейкин Владимир Д.

Учебники [ править ]

• Cubit уроки

См. Также [ править ]

• Триангуляция Делоне
• Алгоритм фортуны
• Классификация сетки
• Параметризация сетки
• Meshfree методы
• Создание параллельной сетки
• Периодическая таблица конечных элементов
• Принципы построения сетки
• Многоугольная сетка
• Обычная сетка
• Алгоритм Рупперта
• Метод растянутой сетки
• Мозаика
• Виды сетки
• Неструктурированная сетка

Ссылки [ править ]

• Эдельсбруннер, Герберт (2001), «Геометрия и топология для создания сетки», Обзоры прикладной механики , Cambridge University Press, 55 (1): B1 – B2, Bibcode : 2002ApMRv..55B ... 1E , doi : 10.1115 / 1.1445302 , ISBN 978-0-521-79309-4.
• Фрей, Паскаль Жан; Джордж, Поль-Луи (2000), Создание сетки: применение к конечным элементам , Hermes Science, ISBN 978-1-903398-00-5.
• П. Смит и С. Sritharan (1988), "Теория Harmonic сетки поколения" (PDF) , комплексные переменные , 10 (4): 359-369, DOI : 10,1080 / 17476938808814314
• СС Sritharan (1992), "Теория гармонического поколения Сетка-II", Применимое анализ , 44 (1): 127-149, DOI : 10,1080 / 00036819208840072
• Томпсон, JF ; Warsi, ZUA; Мастин, К.В. (1985), Создание числовой сетки: основы и приложения , Северная Голландия , Elsevier.
• CGAL Библиотека алгоритмов вычислительной геометрии
• Оден, Дж. Тинсли; Чо, Дж. Р. (1996), "Адаптивные hpq-методы конечных элементов иерархических моделей для пластинчатых и оболочечных структур", Компьютерные методы в прикладной механике и технике , 136 (3): 317–345, Bibcode : 1996CMAME.136. .317O , DOI : 10,1016 / 0045-7825 (95) 00986-8
• Стивен Дж. Оуэн (1998), Обзор технологии создания неструктурированной сетки , стр. 239–267
• Шимада, Кендзи; Госсард, Дэвид С. (1995), Bubble Mesh: Автоматизированное Треугольное зацепление Non-Manifold геометрия сферы упаковки ., АКМ, С.  409-419 , DOI : 10,1145 / 218013,218095 , ISBN 0-89791-672-7

• Ян Брандтс, Сергей Коротов, Михал Крижек: «Симплициальные разбиения с приложениями к методу конечных элементов», Монографии Springer по математике, ISBN 978-3030556761 (2020). url = " https://www.springer.com/gp/book/9783030556761 "