Введение
Разбиение пространства на ячейки
Генерация сетки — это процесс создания сетки, разбиения непрерывного геометрического пространства на дискретные геометрические и топологические ячейки. Часто эти ячейки образуют симплициальный комплекс. Обычно ячейки разделяют исходную геометрическую область. Ячейки сетки используются в качестве дискретных локальных аппроксимаций большей области. Сетки создаются компьютерными алгоритмами, часто с привлечением человека через графический интерфейс, в зависимости от сложности области и требуемого типа сетки. Типичная цель — создать сетку, которая точно воспроизводит геометрию исходной области, с ячейками высокого качества (правильной формы) и без избыточного количества ячеек, делающего последующие вычисления невыполнимыми. Сетка должна быть достаточно мелкой (иметь малые элементы) в областях, важных для последующих расчетов. Сетки используются для рендеринга на компьютерный экран и для физического моделирования, такого как анализ методом конечных элементов или вычислительная гидродинамика. Сетки состоят из простых ячеек, таких как треугольники, поскольку, например, мы знаем, как выполнять операции, такие как вычисления методом конечных элементов (в инженерии) или трассировка лучей (в компьютерной графике) на треугольниках, но не знаем, как выполнять эти операции непосредственно на сложных пространствах и формах, например, на дорожном мосту. Мы можем смоделировать прочность моста или отобразить его на экране компьютера, выполняя вычисления для каждого треугольника и рассчитывая взаимодействия между треугольниками. Основное различие заключается между структурированной и неструктурированной сеткой. В структурированной сетке сетка представляет собой регулярную решетку, например, массив, с подразумеваемой связностью между элементами. В неструктурированной сетке элементы могут быть соединены друг с другом по нерегулярным схемам, что позволяет моделировать более сложные области. Эта страница посвящена в основном неструктурированным сеткам. Хотя сетка может быть триангуляцией, процесс создания сетки отличается от триангуляции множества точек тем, что при создании сетки допускается добавление вершин, отсутствующих в исходных данных. "Фасетация" (триангуляция) CAD-моделей для черчения также допускает добавление вершин, но цель состоит в том, чтобы точно представить форму, используя как можно меньше треугольников, при этом форма отдельных треугольников не имеет значения. Вместо этого сетки используются для рендеринга текстур и реалистичных условий освещения в компьютерной графике. Многие программы для генерации сеток связаны с CAD-системой, определяющей входные данные, и с программным обеспечением для моделирования, получающим выходные данные. Входные данные могут сильно различаться, но распространенными форматами являются твердотельное моделирование, геометрическое моделирование, NURBS, B-Rep, STL или облако точек.
Терминология
Термины "генерация сетки", "генерация сетки", "сеткование" и "дискретизация" часто используются как взаимозаменяемые, хотя, строго говоря, последние два более широки и включают в себя улучшение сетки: изменение сетки с целью повышения скорости или точности численных расчетов, которые будут выполняться на ней. В компьютерной графике и математике сетка иногда называется тесселяцией. Грани сетки (ячейки, элементы) имеют разные названия в зависимости от их размерности и контекста использования сетки. В методе конечных элементов, элементы с наибольшей размерностью называются "элементами", "рёбра" – одномерными (1D), а "узлы" – нульмерными (0D). Если элементы трехмерные (3D), то двумерные (2D) элементы называются "гранями". В вычислительной геометрии нульмерные точки называются вершинами. Тетраэдры часто сокращают до "тетов", треугольники – до "трисов", четырехугольники – до "квадов", а гексаэдры (топологические кубы) – до "гексов".
Техника
Многие методы построения сеток основаны на принципах триангуляции Делоне, а также на правилах добавления вершин, таких как алгоритм Рупперта. Отличительной особенностью является то, что сначала формируется начальная грубая сетка для всего пространства, а затем добавляются вершины и треугольники. В отличие от этого, алгоритмы продвигающегося фронта начинают с границы области и добавляют элементы, постепенно заполняя внутреннюю область. Гибридные методы сочетают оба подхода. Специальный класс алгоритмов продвигающегося фронта создает тонкие пограничные слои элементов для расчетов течений жидкости. В структурированном построении сетки вся сетка представляет собой решетчатый граф, например, регулярная сетка квадратов. При блочно-структурированном построении сетки область разделяется на крупные подобласти, каждая из которых является структурированной сеткой. Некоторые прямые методы начинают с блочно-структурированной сетки, а затем изменяют ее, чтобы она соответствовала входным данным; см. Автоматическое создание гексаэдрических сеток на основе поликубов. Другой прямой метод заключается в разрезании структурированных ячеек границей области; см. скульптурирование на основе марширующих кубов. Некоторые типы сеток намного сложнее создать, чем другие. Симплексные сетки, как правило, проще в создании, чем кубические. Важной категорией является создание гексаэдрической сетки, соответствующей фиксированной тетраэдрической поверхностной сетке; отдельное направление исследований посвящено изучению существования и создания сеток специфических небольших конфигураций, таких как тетрагональный трапецоэдр. Из-за сложности этой задачи существование комбинаторных гексаэдрических сеток изучалось отдельно от задачи создания хороших геометрических реализаций. В то время как известные алгоритмы генерируют симплексные сетки с гарантированным минимальным качеством, такие гарантии редки для кубических сеток, и многие популярные реализации генерируют инвертированные (вывернутые наизнанку) гексаэдры для некоторых входных данных. Сетки часто создаются последовательно на рабочих станциях, даже если последующие вычисления по сетке будут выполняться параллельно на суперкомпьютерах. Это связано как с тем, что большинство генераторов сеток являются интерактивными, так и с тем, что время создания сетки обычно незначительно по сравнению со временем решения. Однако, если сетка слишком велика, чтобы поместиться в память одной последовательной машины, или сетку необходимо изменить (адаптировать) в процессе моделирования, построение сетки выполняется параллельно.
Методы дифференциальных уравнений
Как и алгебраические методы, методы дифференциальных уравнений также используются для генерации сеток. Преимущество использования уравнений в частных производных (PDEs) заключается в том, что решение уравнений генерации сетки можно использовать для создания сетки. Построение сетки может быть выполнено с использованием всех трех классов уравнений в частных производных.
Параболические схемы
Метод решения аналогичен методу решения гиперболических уравнений в частных производных (PDE), поскольку решение продвигается от начальной поверхности данных, удовлетворяющей граничным условиям на концах. Накамура (1982) и Эдвардс (1985) разработали основные идеи для генерации параболических сеток. В основе метода лежит использование либо уравнения Лапласа, либо уравнения Пуассона, с особым вниманием к частям, определяющим эллиптическое поведение. Начальные значения задаются как координаты точек на поверхности, а решение продвигается к внешней поверхности объекта, удовлетворяя граничным условиям на гранях. До сих пор не предлагалось способов управления шагом сетки. У Накамуры и Эдвардса управление сеткой осуществлялось с помощью неравномерного шага. Параболическая генерация сеток имеет преимущество перед гиперболической в том, что не возникают скачки или разрывы, и сетка получается относительно гладкой. Однако задание начальных значений и выбор шага для управления точками сетки – трудоемкий процесс, но эти методы могут быть эффективными при приобретении достаточного опыта и навыков.
Вариационные методы
Этот метод включает в себя технику, минимизирующую гладкость сетки, ортогональность и изменение объёма. Этот метод представляет собой математическую основу для решения задач генерации сеток. В рамках этого метода на каждой итерации генерируется альтернативная сетка с использованием новой сетки и вычисляется скорость сетки методом обратных разностей. Эта техника является эффективной, однако требует значительных усилий для решения уравнений, связанных с сеткой. Для снижения времени вычислений необходимо провести дальнейшие исследования по минимизации интегралов.
Неструктурированная генерация сети
Основное преимущество данной схемы заключается в том, что она предоставляет метод автоматической генерации сетки. При использовании этого метода сетки сегментируются на блоки в соответствии с поверхностью элемента, обеспечивая структуру для поддержания необходимой связности. Для интерпретации потока данных используется решатель. При использовании неструктурированной схемы основное внимание уделяется удовлетворению требований пользователя, для чего используется генератор сетки. В структурированных схемах информация хранится от ячейки к ячейке, а не от сетки к сетке, что требует большего объема памяти. Из-за случайного расположения ячеек эффективность решателя в неструктурированных схемах ниже, чем в структурированных. При построении сетки необходимо учитывать ряд моментов. Точки сетки с высоким разрешением создают трудности как для структурированных, так и для неструктурированных сеток. Например, в случае пограничного слоя структурированная схема создает вытянутую сетку по направлению потока. С другой стороны, неструктурированным сеткам требуется более высокая плотность ячеек в пограничном слое, поскольку ячейки должны быть максимально равносторонними, чтобы избежать ошибок. Необходимо определить, какая информация требуется для идентификации ячейки и всех ее соседей в вычислительной сетке. Для неструктурированной сетки мы можем произвольно выбирать местоположение точек. Для вставки точек используется схема независимой вставки точек, после чего определяется связность ячеек. Это означает, что точки должны быть идентифицированы в момент их вставки. Логика установления новой связности определяется после вставки точек. Необходимы данные, определяющие точку сетки и идентифицирующие ячейку сетки. По мере формирования каждой ячейке присваивается номер, а точки сортируются. Кроме того, требуется информация о соседних ячейках.
Адаптируемая сетка
Проблема при решении уравнений в частных производных с использованием прежних методов заключается в том, что сетка строится, а точки распределяются в физической области до того, как становятся известны детали решения. Таким образом, сетка может оказаться как оптимальной, так и не оптимальной для данной задачи. Адаптивные методы используются для повышения точности решений. Адаптивный метод называют ‘h’-методом, если применяется уточнение сетки, ‘r’-методом, если число точек сетки фиксировано и не перераспределяется, и ‘p’-методом, если в методе конечных элементов увеличивается порядок аппроксимации. Многомерные задачи с использованием схемы эквидистрибуции могут быть решены несколькими способами. Наиболее простыми для понимания являются генераторы сетки Пуассона с управляющей функцией, основанной на эквидистрибуции весовой функции, при этом диффузионный набор задается как кратное желаемому объему ячейки. Схему эквидистрибуции также можно применять к неструктурированным задачам. Проблема заключается в том, что связность затрудняется при значительном перемещении точек сетки. Установившееся течение и расчет течения с заданной точностью по времени могут быть решены с помощью этого адаптивного метода. Сетка уточняется после заранее определенного числа итераций для адаптации к задаче установившегося течения. Уточнение сетки прекращается, когда решение сходится. В случае расчета течения с заданной точностью по времени требуется связь между уравнениями в частных производных, описывающими физическую задачу, и уравнениями, описывающими движение сетки.
Топология ячейки
Обычно ячейки имеют форму многоугольников или многогранников и образуют сетку, которая разбивает область. Важные классы двухмерных элементов включают треугольники (симплексы) и четырехугольники (топологические квадраты). В трех измерениях наиболее распространенными ячейками являются тетраэдры (симплексы) и гексаэдры (топологические кубы). Симплексные сетки могут быть любой размерности и включают треугольники (2D) и тетраэдры (3D) как важные примеры. Кубические сетки – это пан-мерная категория, включающая четырехугольники (2D) и гексаэдры (3D). В 3D, в конформных сетках со смешанным типом ячеек встречаются 4-сторонние пирамиды и 3-сторонние призмы.
Размер ячейки
Сетка встроена в геометрическое пространство, которое обычно двумерно или трехмерно, хотя иногда размерность увеличивается на единицу путем добавления измерения времени. Высокоразмерные сетки используются в специализированных областях. Одномерные сетки также полезны. Значимой категорией являются поверхностные сетки – это двумерные сетки, встроенные в трехмерное пространство для представления изогнутой поверхности.
Двойственность
Двойные графы играют несколько ролей в построении сеток. Можно создать многогранную сетку диаграммы Вороного, выполнив дуализацию симплициальной сетки триангуляции Делоне. Можно создать кубическую сетку, генерируя расположение поверхностей и дуализируя граф пересечений; см. пространственный континуум скручивания. Иногда в одном и том же моделировании используются как исходная сетка, так и ее двойственная сетка; см. оператор звезды Ходжа. Это возникает в физике, связанной с операторами дивергенции и ротора (математики), такими как поток и вихрение или электричество и магнетизм, где одна переменная естественным образом определяется на гранях исходной сетки, а ее соответствующая переменная – на гранях двойственной сетки.
Тип сетки по назначению
Трехмерные сетки, созданные для анализа конечных элементов, должны состоять из тетраэдров, пирамид, призм или гексаэдров. Сетки, используемые для метода конечных объемов, могут состоять из произвольных многогранников. Сетки, используемые для методов конечных разностей, состоят из кусочно структурированных массивов гексаэдров, известных как многоблочные структурированные сетки. Четырехсторонние пирамиды полезны для конформного соединения гексаэдров с тетраэдрами. Трехсторонние призмы используются для создания граничных слоев, соответствующих тетраэдральной сетке внутренней области объекта. Поверхностные сетки полезны в компьютерной графике, где поверхности объектов отражают свет (включая подповерхностное рассеяние) и не требуется полная трехмерная сетка. Поверхностные сетки также используются для моделирования тонких объектов, таких как листовой металл в автомобильной промышленности и внешние элементы зданий в архитектуре. Высокоразмерные (например, 17-мерные) кубические сетки часто используются в астрофизике и теории струн.
Математическое определение и варианты
Каково точное определение сетки? Не существует универсально принятого математического описания, применимого во всех контекстах. Однако некоторые математические объекты явно являются сетками: симплициальный комплекс – это сетка, состоящая из симплексов. Большинство полиэдрических (например, кубических) сеток являются конформными, то есть имеют клеточную структуру CW-комплекса, являющегося обобщением симплициального комплекса. Сетка не обязательно должна быть симплициальной, поскольку произвольное подмножество узлов ячейки не обязательно является ячейкой: например, три узла квадрата не определяют ячейку. Однако две ячейки пересекаются по ячейкам: например, квадрат не имеет узла внутри себя. Пересечение двух ячеек может состоять из нескольких ячеек: например, два квадрата могут иметь два общих ребра. Пересечение более чем одной ячейки иногда запрещено и редко желательно; цель некоторых методов улучшения сетки (например, сглаживания) – устранить такие конфигурации. В некоторых контекстах различают топологическую сетку и геометрическую сетку, чье вложение удовлетворяет определенным критериям качества. Важные варианты сеток, не являющиеся CW-комплексами, включают неконформные сетки, где ячейки не соприкасаются строго грань к грани, но при этом ячейки разделяют область. Примером является октальное дерево, где грань элемента может быть разделена гранями соседних элементов. Такие сетки полезны для расчетов, основанных на потоках. В наложенных сетках существует несколько конформных сеток, которые геометрически перекрываются и не разделяют область; см., например, Overflow, решатель OVERset grid FLOW. Так называемые методы, не требующие сетки (meshless или meshfree), часто используют некоторое дискретизированное представление области, похожее на сетку, и базисные функции с перекрывающейся областью определения. Иногда локальная сетка создается вблизи каждой точки степеней свободы моделирования, и эти сетки могут перекрываться и быть неконформными друг по отношению к другу. Неявные триангуляции основаны на дельта-комплексе: для каждого треугольника определяются длины его ребер и карта склеивания между ребрами граней. (пожалуйста, расширьте)
Элементы высшего порядка
Многие сетки используют линейные элементы, где соответствие между абстрактным и физическим элементом линейно, а рёбра сетки — прямые отрезки. Широко распространены многочленные соответствия более высокого порядка, особенно квадратичные. Основная цель элементов более высокого порядка — более точно представить границу области, хотя они также обладают преимуществами в точности и внутри сетки. Одной из мотиваций для использования кубических сеток является то, что линейные кубические элементы обладают некоторыми из тех же численных преимуществ, что и квадратичные симплексные элементы. В методе моделирования изогеометрического анализа ячейки сетки, содержащие границу области, используют CAD-представление напрямую, а не линейное или полиномиальное приближение.
Улучшение сетчатки
Улучшение сетки включает в себя изменение ее дискретной связности, непрерывного геометрического положения ее ячеек или и того, и другого. Для дискретных изменений, для симплексных элементов выполняется замена ребер и вставка/удаление узлов. Те же операции выполняются для кубических (квадратных/гексаэдральных) сеток, хотя возможных операций меньше, а локальные изменения имеют глобальные последствия. Например, для гексаэдральной сетки, слияние двух узлов создает ячейки, которые не являются гексаэдрами, но если диагонально противоположные узлы на четырехугольнике сливаются, и это приводит к схлопыванию всей соединенной по грани колонны гексаэдров, то все оставшиеся ячейки все равно будут гексаэдрами. При адаптивной детализации сетки элементы разделяются (h-детализация) в областях, где вычисляемая функция имеет высокий градиент. Сетки также упрощаются, удаляя элементы для повышения эффективности. Метод многосеточных вычислений делает нечто похожее на детализацию и упрощение для ускорения численного решения, но без фактического изменения сетки. Для непрерывных изменений перемещаются узлы или высокоразмерные грани, изменяя полиномиальный порядок элементов. Перемещение узлов для улучшения качества называется "сглаживанием" или "r-уточнением", а увеличение порядка элементов называется "p-уточнением". Узлы также перемещаются в симуляциях, где форма объектов изменяется со временем. Это ухудшает форму элементов. Если объект достаточно деформируется, весь объект перестраивается, а текущее решение переносится со старой сетки на новую сетку.
Практикующие
Эта область отличается высокой междисциплинарностью, в ней есть вклад математики, информатики и инженерии. Исследования в области создания сеток (meshing R&D) характеризуются одинаковым вниманием к дискретной и непрерывной математике и вычислениям, как, например, в вычислительной геометрии, но в отличие от теории графов (дискретной) и численного анализа (непрерывного). Генерация сеток представляется обманчиво сложной задачей: человеку легко представить, как создать сетку для заданного объекта, но сложно запрограммировать компьютер для принятия оптимальных решений для произвольных входных данных заранее. Геометрия в природе и создаваемых человеком объектах представлена в бесконечном разнообразии. Многие исследователей в области генерации сеток изначально были пользователями сеток. Генерация сеток продолжает привлекать широкое внимание, получать поддержку и финансирование, поскольку время, затрачиваемое человеком на создание сетки, значительно превышает время, необходимое для настройки и решения задачи после её завершения. Такая ситуация наблюдается с момента изобретения численного моделирования и компьютерной графики, поскольку с развитием компьютерного оборудования и программного обеспечения для решения простых уравнений люди стали обращаться к более крупным и сложным геометрическим моделям в стремлении к большей точности, научным открытиям и художественному выражению.