Журнал вычислительной математики и математической физики, 2022, T. 62, № 8, стр. 1402-1427
Построение сетки в пограничном слое с быстрым обнаружением пересечений фронтов
Дж. Као 1, 2, Дж. Гуан 1, 2, *, Ю Фей 1, 2, С. Х. Ло 3, Дж. Шан 4, Х. Янг 1, 2
1 Государственная ключевая лаборатория структурного анализа промышленного оборудования, Даляньский технологический университет
116024 Далянь, Китай
2 Даляньский технологический университет, факультет инженерной механики
116024 Далянь, Китай
3 Университет Гонконга, факультет гражданского строительства
Гонконг, Китай
4 Отдел исследований и разработок, Shanghai Geyu Software Co. Ltd.
201620 Шанхай, Китай
* E-mail: guanzhq@dlut.edu.cn
Поступила в редакцию 10.10.2021
После доработки 03.03.2022
Принята к публикации 11.04.2022
- EDN: VRMMLN
- DOI: 10.31857/S0044466922080105
Аннотация
Вычисление нормалей и определение пересечения фронтов при генерации сетки в пограничном слое являются наиболее трудоемкими частями при реализации надежного алгоритма построения гибридных сеток для моделирования вязких течений. В данной работе представлен общий метод построения сетки в пограничном слое с использованием алгоритма быстрого обнаружения столкновений. Основные результаты работы заключаются в следующем. Во-первых, предлагается новый приближенный линейный по сложности метод представления непрерывной медиальной поверхности, основанный на разбиении триангуляции Делоне с ограничениями (CDT) граничных точек. Во-вторых, мы улучшаем метод Jump-and-Walk для обнаружения пересечений сетки, повышая его устойчивость с помощью разделителя на медиальных поверхностях, введенного между маршевыми фронтами. Разделитель основан только на CDT и прост в реализации, поскольку не требует дополнительных структур данных. И, наконец, для значительного сокращения времени обычных вычислений для построения сетки и операций обнаружения пересечений используется прецизионный метод декомпозиции и роста подобластей, который позволяет значительно сократить время вычислений за счет совместного использования CDT на разных этапах алгоритма. Возможности предложенного алгоритма продемонстрированы на примере построения гибридных сеток высокого качества для очень сложных геометрических моделей. Продемонстрировано значительное ускорение работы алгоритма построения гибридных сеток при сохранении его надежности. В частности, показано, что предложенный алгоритм примерно в 4 раза быстрее алгоритма из известного коммерческого пакета Pointwise. Библ. 41. Фиг. 27. Табл. 3.
1. ВВЕДЕНИЕ
Вычислительная гидродинамика (CFD) – это отрасль механики жидкости, которая занимается проблемами течения жидкости с помощью численного моделирования. Расчет вязкой жидкости вокруг объектов обычно основан на уравнениях Навье–Стокса, осредненных по Рейнольдсу (Reynolds-averaged Navier–Stokes, сокращенно RANS). В типичном анализе первым шагом является генерация численной сетки. Типы сеток, обычно используемые в расчетах RANS, в основном включают структурированную сетку, неструктурированную сетку, сетку с перекрытием, декартову сетку, гибридную сетку и т.д. Различные типы сеток имеют свои собственные характеристики и недостатки. Однако, учитывая простоту использования и численную точность, гибридная сетка, которая использует все преимущества структурированных и неструктурированных сеток с должным учетом эффекта пограничного слоя, считается наилучшей формой сетки для расчетов RANS (см. [1]–[3]). Этот тип сетки использует уплощенные полуструктурированные элементы типа призм вблизи поверхности объекта, что не только более адаптивно к сложной геометрической форме в направлении, параллельном поверхности объекта, но и точно передает чрезвычайно тонкие характеристики поля жидкости в направлении, перпендикулярном поверхности объекта, путем управления количеством слоев сетки. Оставшийся объем заполняется неструктурированными элементами автоматически без ручного разбиения, что значительно снижает сложность генерации сетки и обеспечивает надежность всего алгоритма. Более того, общее количество элементов может быть уменьшено по сравнению с ситуацией, когда неструктурированные сетки используются на всем поле с тем же количеством точек сетки.
Пользуясь зрелостью методов триангуляции Делоне с ограничениями (Constrained Delaunay Triangulation, сокращено CDT) (см. [4]–[8]) основное внимание уделяется построению призматической сетки на границе. Как правило, размер характеристик жидкости намного меньше, чем размер расчетных моделей. Расстояние между ячейками призматических сеток в нормальном направлении может достигать порядка $O({{10}^{{ - 3}}}{\kern 1pt} - {\kern 1pt} {{10}^{{ - 5}}})$ по сравнению с тангенциальным направлением. Благодаря быстрому росту мощности компьютеров, моделирование вязкой жидкости c ${{10}^{7}}{\kern 1pt} - {\kern 1pt} {{10}^{8}}$ узлами часто используeтся для более точного решения. Кроме того, для сложных геометрических моделей с большим разбросом размеров элементов трудно создать правильную сетку, соответствующую геометрическим особенностям с правильным расстоянием между узлами и соотношением сторон. Надежность и эффективность – вот задачи для создания качественной сетки пограничного слоя.
Одним из популярных алгоритмов построения сеток пограничного слоя является метод продвигающегося слоя. Треугольная сетка на нескользящей стенке продвигается в направлении, нормальном к стенке, для создания призматической сетки с высоким искажением формы. Ранние попытки применения этого метода были предложены Лонером (Lohner) (см. [6]) и Пирзаде (Pirzadeh) (см. [9]). Основное различие заключается в том, что Лонер расширял всю граничную поверхность за один раз (одноразовое продвижение, OTA), в то время как Пирзаде продвигал треугольные грани слой за слоем (послойное продвижение, LLA). Предполагая, что количество треугольников на стене равно ${{n}_{{{\text{cell}}}}}$, а количество слоев равно $n$, время вычислений для продвижения одной грани в процессе OTA и LLA составляет ${{n}_{{{\text{cell}}}}}$ и $({{n}_{{{\text{cell}}}}} \times n)$ соответственно. Очевидно, что по сравнению с LLA, OTA намного эффективнее, но должен следовать в фиксированном направлении. Оба процесса сталкиваются с проблемой само- или глобального пересечения сетки, особенно в узких углах ложбин или на смежных поверхностях. Как надежно и эффективно обнаружить столкновение сеток – один из основных вопросов для построения пограничного слоя. В целом алгоритмы обнаружения столкновений можно разделить на две категории в соответствии с используемыми вычислительными стратегиями: 1) тест пересечения элементов, 2) обнаружение пространства.
Если тест на пересечение используется для нахождения пересекающихся или перекрывающихся призм в OTA (см. [6], [10], [11]) или LLA (см. [12]), то область исследования обычно ограничена вокруг проверяемых призм. Для OTA, из-за фиксированных направлений марша, многие призмы в углах ложбин могут быть чрезмерно усечены. Этой проблемы не существует в LLA, которая является более надежным и широко распространенным методом. Однако обнаружение столкновений в трехмерном пространстве – нетривиальный процесс, поскольку необходимо тщательно реализовать геометрические вычисления, чтобы избежать проблем с устойчивостью, вызванных вычислениями с конечной точностью. Кроме того, необходима дополнительная структура данных, например, октодерево или alternating digital tree (ADT) (см. [13]), чтобы уменьшить время поиска, требуемое алгоритмом.
Пересечения сеток также могут быть определены путем оценки пространства продвижения передних точек (см. [1], [9], [14]–[18]), из которых CDT обычно используется в качестве фоновой сетки для алгоритмов поиска, не полагающихся на дополнительную структуру данных. Один из способов определения размера пространства заключается в том, что сетка CDT сначала заполняется в проблемной области, а передние точки маршируют, сохраняя объем тетраэдров положительным (см. [14], [15], [17]). Этот метод прост и надежен, но для настройки CDT требуется большое количество итераций, включающих сглаживание сетки, настройку локальной топологии и другие операции, что существенно снижает эффективность генерации сетки. Ванг и соавт. (см. [18]) вычислили максимальные расстояния до передних точек, проходящих по тетраэдрам с помощью метода прыжков и ходьбы (Jump and Walk, JW). Эффективность процесса построения сетки значительно повышается. Однако, как косвенный способ, метод Ванга все еще не обладает достаточной надежностью при сложных углах и прилегающих поверхностях, что является общей проблемой для алгоритмов обнаружения пространства по сравнению с прямым вычислением пересечений.
В данной работе мы улучшаем метод JW, повышая его робастность для обнаружения столкновений с медиальной поверхностью, используемой для контроля маршевого расстояния передних точек в LLA. Требуемая структура данных проста и может сделать процедуру зацепления пограничного слоя простой в построении и быстрой в исполнении с приемлемым качеством сетки.
Более того, если OTA и LLA используются соответственно в различных областях вязкой стенки (т.е. расширение пограничной поверхности в открытой области с помощью OTA и продвижение границ в узкой области с помощью LLA), можно добиться хорошего эффекта ускорения и качества сетки одновременно. Сложность этого метода заключается в создании эффективного алгоритма разделения области. Поэтому был разработан метод продвигающегося разделенного слоя (Advancing Divided-Layer, AdvDL), который также основан на медиальной поверхности для разделения и продвижения доменов.
Остальная часть статьи организована следующим образом. В разд. 2 сначала перечислены некоторые термины, определения и параметры сетки, которые будут встречаться в последующем тексте. Затем мы представляем процедуру создания гибридной сетки и подробно описываем некоторые ключевые шаги. В разд. 3 мы кратко рассматриваем метод JW и его применение к обнаружению столкновений сеток пограничного слоя, доказывая, что существуют два условия, при которых метод JW не является безопасным. В разд. 4 мы представляем метод разбиения медиальной поверхности для построения независимого маршевого пространства для каждой части фронтальной поверхности. Метод JW улучшается благодаря введению метода медиального разбиения поверхности. В разд. 5 кратко описываются метод AdvDL и его сочетание с усовершенствованным методом JW для повышения эффективности. В разд. 6 на некоторых примерах, включающих модели внутреннего и внешнего потоков, были проведены тесты с использованием усовершенствованного метода JW, чтобы показать его эффективность. В разд. 7 приведены выводы по данной работе.
2. ОБЩИЕ ШАГИ ДЛЯ ПОСТРОЕНИЯ ГИБРИДНОЙ СЕТКИ
Параметры сетки:
$T$: граничные треугольные сетки,
$n$: количество пограничных слоев,
${{d}_{0}}$: толщина первого слоя,
$r$: скорость роста толщины слоя,
$d_{i}^{l}$: толщина ${{i}^{{th}}}$-слоя, $d_{i}^{l} = {{d}_{0}}{{r}^{{i - 1}}}, i = 1, \ldots ,n$,
${{d}_{{all}}}$: общая толщина слоев, ${{d}_{{all}}} = \sum\nolimits_{i = 1}^n {d_{i}^{l}} $.
Основная процедура построения гибридной сетки, предложенная в данной работе, показана на фиг. 1. Сетка пограничного слоя сначала строится методом продвигающегося слоя, при этом вычисление направления и расстояния марша и проверка пересечения сетки являются основными в процессе построения сетки. Затем удаляются нестеновые пограничные поверхности, такие как свободный поток, периодическая поверхность, поверхность симметрии и т.д. Наконец, оставшееся поле потока заполняется изотропной тетраэдральной сеткой.
2.1. Направление и дистанция марша
Вычисление направления марша. Ортогональность призм является важным свойством при построении сетки для точности расчетов жидкости. Начальное направление движения передней точки определяется нормалями треугольных граней, соединенных с точкой. Предположим, что существует $n$ граней, как показано на фиг. 2a. Пусть ${{p}_{1}}, \ldots ,{{p}_{n}}$ – вершины, соединяющиеся с $p$ так, что ${{k}^{{th}}}$ треугольная грань обозначается через $p{{p}_{k}}{{p}_{{k + 1}}}$. Приведем следующие определения:
Фиг. 2.
Методы вычисления нормали в точке: (a) – средневзвешенное значение нормалей поверхности, (б) – построение конуса видимости.
${{{\mathbf{n}}}_{k}}$: единичный нормальный вектор грани ${{f}_{k}}$,
${{{\mathbf{u}}}_{k}}$: единичный вектор в направлении $p{{p}_{k}}$,
${{\alpha }_{k}}$: угол ${{p}_{k}}p{{p}_{{k + 1}}}$,
${{\theta }_{k}}$: угол между нормальными векторами соседних граней,
$\Omega $: телесный угол в точке $p$, $\Omega = 2\pi - \sum\nolimits_{k = 1,n}^{} {{{\theta }_{k}}} $; для плоских поверхностей $\Omega = 2\pi $, для впадин $\Omega > 2\pi $, для пиков $\Omega < 2\pi $. Угол ${{\theta }_{k}}$ может принимать положительное или отрицательное значение в зависимости от тройного произведения $\left( {{{{\mathbf{n}}}_{k}} \times {{{\mathbf{n}}}_{{k + 1}}}} \right) \cdot {{{\mathbf{u}}}_{{k + 1}}}$.
Обычно берется среднее угловое взвешенное этих нормалей, чтобы получить приемлемую нормаль поверхности в данной точке. Мы обозначаем эту нормаль через
(1)
${{{\mathbf{n}}}_{i}} = \frac{{\sum \,{{\alpha }_{k}}{{{\mathbf{n}}}_{k}}}}{{\sum \,{{\alpha }_{k}}}},\quad {{{\mathbf{\bar {n}}}}_{i}} = \frac{{{{{\mathbf{n}}}_{i}}}}{{\left\| {{{{\mathbf{n}}}_{i}}} \right\|}},$Однако это может привести к недействительному условию видимости для дискретных поверхностей с прерывистым наклоном, таких как стыки крыла и фюзеляжа, острые кромки, впадины и пики. Этой ситуации можно избежать, используя вписанный конус с максимальной видимостью, построенный путем расширения граней вокруг передней точки. Как показано на фиг. 2б, конус имеет полуконический угол ${{\beta }_{{{\text{visi}}}}}$ и его центральная ось может создать правильный нормальный вектор, наиболее ортогональный к острому участку (см. [2]). Учитывая, что большая часть граничной поверхности гладкая, неэффективно вычислять конусы видимости для всех точек фронта. Чтобы сбалансировать надежность и эффективность алгоритма, предлагается альтернативная стратегия относительно ${{\theta }_{{{\text{max}}}}}$:
– если ${{\theta }_{{{\text{max}}}}} < 30^\circ $, принимается средневзвешенное значение нормалей поверхности;
– если ${{\theta }_{{{\text{max}}}}} \geqslant 30^\circ $ или нормаль невидима для любой соседней грани, вычисляется конус видимости.
Вычисление маршевого расстояния. Чтобы увеличить ортогональность сетки по мере роста слоев, маршевое расстояние может быть линейной функцией ${{\beta }_{{{\text{visi}}}}}$, которая дает относительно большое значение в вогнутых углах и малое значение в выпуклых углах (см. [18]). Для $i$-го слоя начальное маршевое расстояние ${{d}_{i}}$ настраивается следующим образом:
где $\left| \alpha \right| = \left| {\cos {{\beta }_{{{\text{visi}}}}}} \right|$. Когда поверхность выпуклая, т.е. $\Omega < 2\pi $, знак $\alpha $ отрицательный; когда поверхность вогнутая, т.е. $\Omega > 2\pi $, знак $\alpha $ положительный. Значение функции $\cos $ находится в пределах от $ - 1$ до 1 и нечувствительно к небольшому изменению ${{\beta }_{{{\text{visi}}}}}$, что обеспечивает относительно плавный переход маршевого расстояния между соседними точками.Сглаживание. После вычисления начальных маршевых векторов необходимо сгладить направления маршей или расстояния между фронтальными точками, чтобы упорядочить генерируемую сетку. Для этого можно использовать метод взвешенного сглаживания Лапласа:
(3)
${{V}_{i}} = \omega V_{i}^{'} + \left( {1 - \omega } \right)\frac{{\sum\limits_j \,{{w}_{{ij}}}{{V}_{j}}}}{{\sum\limits_j \,{{w}_{{ij}}}}},$(4)
${{w}_{{ij}}} = \left\{ \begin{gathered} k_{{ij}}^{2},\quad {{\theta }_{{{\text{max}}}}} \geqslant 5^\circ ,\quad \Omega \leqslant 2\pi , \hfill \\ 1{\text{/}}k_{{ij}}^{2},\quad {{\theta }_{{{\text{max}}}}} \geqslant 5^\circ ,\quad \Omega > 2\pi , \hfill \\ 1\quad {\text{иначе,}} \hfill \\ \end{gathered} \right.\quad {{k}_{{ij}}} = \frac{{n{{d}_{{ij}}}}}{{\sum\limits_{j = 1,n} \,{{d}_{{ij}}}}},$2.2. Проверка правильности сетки пограничного слоя
Перед созданием призмы будет проведено несколько тестов на валидность, включая качество элементов, обнаружение столкновений и топологическую связь. Если какой-либо тест не пройдет, призма будет отброшена.
Качество элемента. Ортогональность боковых граней и соотношение сторон треугольных граней – два важных фактора качества призмы. В нашем алгоритме используется масштабная мера качества по соотношению сторон (см. [16]). Призма является свернутым элементом, если ее коэффициент качества $\rho \leqslant 0$, что не допускается. Кроме того, если максимальная длина $h$ боковых граней и средняя длина $l$ нижних граней удовлетворяют условию, что $h{\text{/}}l > \alpha $ (по умолчанию $\alpha $ принимает значение 0.8), фронтальная грань прекращает марширование для поддержания плавного перехода размера к изотропной сетке.
Обнаружение столкновений. Глобальные и локальные пересечения сетки запрещены при продвижении фронтальных граней. Выдающийся алгоритм обнаружения столкновений должен обладать как хорошей надежностью, так и эффективностью. Улучшенный метод JW, предложенный в следующем тексте, может стать хорошим выбором для крупномасштабного построения сеток пограничного слоя.
Переход элемента. Если статус марширования точки выключен, все грани вокруг нее перестают маршировать, а между призмами и изотропной сеткой строятся переходные элементы пирамида/тетраэдр. Разность номеров слоев смежных граней будет оставаться меньше 2, чтобы сохранить качество переходного элемента, как показано на фиг. 3.
2.3. Обработка на граничных сетках без стен
Некоторые модели течения содержат нестеновые граничные поверхности, примыкающие к нескользящей стенке, такие как свободный поток, периодическая поверхность, поверхность симметрии и т.д. Ее сетка будет изменяться вдоль направления продвижения пограничных слоев. В данной работе сетка нестеночной поверхности заменяется триангуляцией Делоне ее граничных точек, как показано на фиг. 4, что требуется для предлагаемого обнаружения столкновений. После того, как сетка пограничного слоя будет сгенерирована, мы переделаем сетку нестеновой поверхности, ограниченной расширенной границей.
2.4. Построение изотропных сеток
С закрытой расширенной границей в качестве входных данных изотропные тетраэдральные сетки могут быть созданы в оставшемся поле потока. Существует множество эффективных, стабильных и открытых генераторов тетраэдральных сеток, таких как Gmsh, NetGen, TetGen и др. В данной работе построение фоновой сетки и изотропной сетки осуществляется с помощью программы TetGen.
3. ОБНАРУЖЕНИЕ СТОЛКНОВЕНИЙ МЕТОДОМ Jump-and-Walk
Нахождение точек широко используется при построении сетки и в других численных алгоритмах, таких как триангуляция Делоне (см. [5]), техника движущегося фронта (AFT) (см. [20]), алгоритм отпечатка сетки (см. [21]) и т.д. Для ускорения поиска объектов, включая точки, края, ячейки и т.д., обычно требуется фоновая сетка. В общем случае может быть использовано $k$-е дерево с вычислительным временем от $O(N\log N)$ до $O({{N}^{2}})$ для предварительной обработки дерева и $O(\log N)$ для каждого запроса (см. [22], [23]). Кроме того, алгоритм поиска ближайшей точки на основе равномерных кубов может достичь временной эффективности $O(1)$, но это при идеальном условии для равномерно распределенного множества точек. Наиболее распространенным алгоритмом для определения положения целевой точки в триангуляции является метод Walk-through (см. [18], [24]–[28]), который можно быстро и легко построить, опираясь только на триангуляцию. Его вычислительная сложность в целом составляет $O({{N}^{{1/4}}})$ на точку, что обусловлено связностью треугольной сетки (см. [29]).
Метод JW как вариант метода Walk-through был применен к обнаружению столкновений при построении сеток пограничного слоя Вангом и Маре (см. [18]). В сочетании с обычным сглаживанием и запретом на многоуровневую разницу в количестве слоев между соседними фронтальными гранями он может исправить большинство пересечений сетки, но все еще не обладает достаточной надежностью.
3.1. Алгоритм
Барицентрические координаты точки $p$ относительно тетраэдра $V({{p}_{1}}{{p}_{2}}{{p}_{3}}{{p}_{4}})$ можно обозначить через ${{L}_{i}},i = 1,2,3,4$, путем вычисления объема тетраэдра, где
(5)
${{L}_{1}} = {\text{Volume}}(p{{p}_{2}}{{p}_{3}}{{p}_{4}}),\quad {{L}_{2}} = {\text{Volume}}({{p}_{1}}p{{p}_{3}}{{p}_{4}}),$(6)
${{L}_{3}} = {\text{Volume}}({{p}_{1}}{{p}_{2}}p{{p}_{4}}),\quad {{L}_{4}} = {\text{Volume}}({{p}_{1}}{{p}_{2}}{{p}_{3}}p).$Если $p$ находится на стороне грани, направленной в сторону $V({{p}_{1}}{{p}_{2}}{{p}_{3}}{{p}_{4}})$, то знак координаты положительный, в противном случае – отрицательный. Для всех возможных положений существует не более трех отрицательных значений.
Algorithm 1. JW
Require: A CDT сетки граничных поверхностей $T$ и ее топологической структуры данных со сложностью запроса $O(1)$; начальная точка $p \in T$; целевая точка $q$ достаточно далеко от $p$ вдоль направления движения; объективная функция: Барицентрический координатный поиск.
Ensure: Максимальное маршевое расстояние ${{d}_{{{\text{max}}}}}$ для $p$.
Инициализируем случайный d-симплекс ${{\sigma }_{0}} \in $ CDT с $p$ в качестве одной из вершин. State $\sigma \leftarrow {{\sigma }_{0}}$.
while do $n < {{n}_{{{\text{max}}}}}$
Определите грань $\tau $ от $\sigma $ с помощью целевой функции:
• Если не выбрано $\tau $, $q$ находится внутри $\sigma $, то ${{d}_{{{\text{max}}}}} = \left\| {{\mathbf{q}} - {\mathbf{p}}} \right\|$. Возврат.
• Если $\tau $ выбрано и лежит на границе, то $q$ находится вне CDT:
– Если $\sigma = {{\sigma }_{0}}$, то ${{d}_{{{\text{max}}}}} = \left\| {{{{\mathbf{p}}}_{{{\text{inter}}}}} - {\mathbf{p}}} \right\|$, где ${{{\mathbf{p}}}_{{{\text{inter}}}}}$ – пересечение лучей ${{n}_{p}}$ и $\tau $ (фиг. 5a). Возврат.
– Если $\sigma \ne {{\sigma }_{0}}$, то ${{d}_{{{\text{max}}}}} = \left\| {{{{\mathbf{p}}}_{\tau }} - {\mathbf{p}}} \right\|$, где ${{{\mathbf{p}}}_{\tau }}$ – координата вершины $\tau $, ближайшей к $p$ (фиг. 5б). Возврат.
• Если $\tau $ выбрана и ${{\sigma }_{{{\text{neigh}}}}}$ может быть получена, движение продолжается.
Перейдите через $\tau $ к ${{\sigma }_{{{\text{neigh}}}}}$.
$\sigma \leftarrow {{\sigma }_{{{\text{neigh}}}}}$.
$n = n + 1$.
end while
Простым способом избежать пересечения сеток является определение максимального расстояния марша передней точки на границе, как показано на фиг. 5. Проходя по тетраэдрам CDT вдоль направления движения передней точки, будет найден тетраэдр, содержащий целевую точку, или движение, наконец, достигнет границы. Тогда общее расстояние движения можно принять за максимальное расстояние марша. Подробно это показано в алгоритме 3.1. Ключом к повышению эффективности поиска является выбор приемлемой объективной функции для определения того, через какую грань нужно перепрыгнуть, чтобы достичь соседнего тетраэдра. Обычно используются следующие методы:
Фиг. 5.
Максимальные маршевые расстояния вычисляются с помощью JW в двух случаях: (a) – $\sigma = {{\sigma }_{0}}$, (б) – $\sigma \ne {{\sigma }_{0}}$.
Тест на пересечение сегмента с гранью (см. [26]). Этот метод является точным, но самым трудоемким.
Поиск против часовой стрелки (см. [25]). Эта простая стратегия заключается в том, что выбирается случайная грань с $L < 0$ относительно целевой точки. Но если более одной барицентрической координаты отрицательны, то образуется извилистый путь.
Поиск по барицентрическим координатам (см. [27], [28]). В этом поиске используется шагание, подобное градиентному спуску. Если существует несколько граней с $L < 0$, предполагая, что ${{L}_{i}} > {{L}_{j}} > {{L}_{k}}$, то грань ${{\tau }_{k}}$ является оптимальным выбором.
Очевидно, что барицентрический поиск координат позволяет достичь хорошего баланса между точностью и эффективностью. После получения ${{d}_{{{\text{max}}}}}$ общее расстояние марша изменяется как
(7)
${{d}_{{{\text{all}}}}} = \min \{ d_{{{\text{all}}}}^{'},{{d}_{{{\text{max}}}}}{{r}_{{{\text{gap}}}}}\} ,$3.2. Недостаток: рискованные точки обрыва
Обнаружение столкновений сеток, основанное на методе JW, не всегда надежно. На фиг. 6 показаны два типичных примера, когда обнаружение может не сработать. В углу, когда максимальные расстояния между фронтальными точками достаточно велики, идущие лучи перекрывают друг друга и призмы, созданные на этих лучах, вырождаются, из чего формируется ступенчатая сетка пограничного слоя. При увеличении числа слоев сетка локально пересекается. На выходе из узкого канала пространство поля резко увеличивается, и пересечения сетки появляются в аналогичной форме. Каждый слой ступенчатой сетки создает несколько точек обрыва, которые представляют собой точки с неполным участком поверхности вокруг. Если последовательно соединить точки обрыва на одной стороне угла или разрыва, можно построить инкрементальную кривую, как показано на фиг. 7. Когда кривая касается биссектрисы угла или разрыва, сетка может пересечься, а побуждающими факторами являются малый угол, большое минимальное количество слоев, большой градиент толщины слоя и т.д. Первые два фактора связаны с геометрической сложностью. Кроме того, сглаживание сетки может увеличить минимальное количество слоев, а градиент приращения связан с размером сетки и скоростью роста толщины слоя.
4. УСОВЕРШЕНСТВОВАННЫЙ МЕТОД Jump-and-Walk (EJW)
Для исправления сетки вблизи точек обрыва предлагается усовершенствованный метод JW, при котором граница медиальной поверхности вводится в фоновую сетку для предотвращения локального пересечения сетки.
4.1. Медиальная поверхность (MS)
МS как скелетная абстракция твердого объекта обеспечивает представление, которое просто фиксирует геометрическую близость граничных элементов, которая описывается локусом центра максимальной сферы при ее качении вдоль границы. Благодаря хорошим свойствам в распознавании смежных признаков и сегментации областей, МS используется во многих приложениях, таких как планирование траектории, контроль размеров (см. [30], [31]), построение структурированных сеток (см. [32]–[35]) и т.д. Однако эффективная стратегия построения непрерывного представления по геометрической поверхности или треугольной сетке оказалась сложной, особенно в 3D. Часто используется DT набора точек на границе благодаря своей простоте и надежности. Описанные сферы тетраэдров в DT в общем случае намного больше и могут выходить за пределы области, в то время как максимальные сферы МS всегда находятся в пределах области. Ю и соавт. (см. [36]) доказали, что при увеличении плотности граничных точек описанные сферы стремятся к максимальным сферам. Шии и соавт. (см. [37]) и Редди и Туркия (см. [38]) проделали работу по оптимизации оптимальной плотности и распределения точек на границе объекта и достигли неплохих результатов.
В данной работе MS будет построена как естественная стена, чтобы разделить противоположные границы в узких областях и избежать столкновений глобальной и локальной сетки. Предлагается новый метод для приблизительного представления МS с помощью треугольной сетки. Более того, простое приближенное представление используется для определения размера областей для разделения фронтальной поверхности.
Приближенное представление 1: точки медиальной поверхности (MSP). Самый простой способ представить МS – это построить набор точек, состоящий из центров описанных сфер всех тетраэдров в CDT граничного набора точек, а именно MSP, которая обычно используется для определения размера геометрических особенностей в твердом объекте (см. [30], [31]). Возьмем в качестве примера двумерный случай, показанный на фиг. 8, область заполнена CDT, а точки внутри области являются окружностями треугольников. Видно, что эти точки в основном распределены по средней оси плоской геометрии с плотным интервалом, связанным с дискретными размерами границы. На увеличенном фиг. 8 видно, что угол наклона краев границы с двух сторон треугольника ближе к 0°, расстояние между окружностями плотнее и отклонение MSP от фактической MS меньше.
Приблизительное представление 2: медиальные поверхностные сетки (MSM). Хотя MSP может соответствовать положению МS с высокой точностью, пока граничные точки достаточно плотные, непрерывное выражение геометрическими поверхностями или треугольной сеткой обычно необходимо во многих приложениях, таких как абстракция скелета твердого тела и сегментация области для генерации четырехугольной/шестигранной сетки (см. [32]–[35]). Поскольку CDT разбивается по биссектрисе тетраэдров, как показано на фиг. 9, MS может быть получена как треугольная сетка с гранями из части тетраэдров в разложенной CDT (DCDT), а именно MSM. Подробности описаны в алгоритме 4.1.
Фиг. 9.
(a) – Тетраэдр разлагается на 17 маленьких тетраэдров, (б) – грань, содержащая 0, 1 или 2 граничных ребра, декомпозируется путем вставки дополнительных точек.
Algorithm 2. Построение MSM
Require: CDT.
Ensure: MSM встроена в DCDT.
for каждый тетраэдр $T \in $ CDT do
Разделите его на 17 маленьких тетраэдров, вставляя точки на ребрах или внутри граней.
• 6 точек ставятся на серединах граней.
• 4 точки размещаются внутри граней. Для грани, содержащей 1 граничное ребро, точка ставится на середине линии, соединяющей середины двух не граничных ребер; в противном случае, точка ставится в барицентр грани.
Отметьте грани внутри $T$.
• Отметьте все грани, состоящие из трех новых вставленных точек.
• Если тетраэдр содержит граничные ребра, отметьте грани, соединяющиеся со средней точкой граничного ребра; если число граничных ребер $ \ne 2$, отметьте грани, противоположные конечной точке граничного ребра.
end for
Соберите все отмеченные грани как MSM.
Как показано на фиг. 10, существует семь видов тетраэдров в зависимости от количества содержащихся граничных ребер. Этот алгоритм может построить сетку с плотной стенкой в линейной сложности путем двухэтапной маркировки, как показано на фиг. 11. Топология MSM тесно связана с тетраэдрализацией, которая аналогична двойственному графу CDT, т.е. диаграмме Вороного. Дополнительная фильтрация для MSM не допускается, чтобы избежать образования небольших отверстий. Грани MSM параллельны граничным треугольникам попеременно с половиной размера. Если угол между нормальными векторами граничных поверхностей близок к 180°, то MSM стремится быть плоской поверхностью с минимальной ошибкой аппроксимации.
4.2. Обнаружение столкновений сеток пограничного слоя
Согласно свойству MS, траектория движения фронтальной точки ясна без пересечения с другими траекториями, если она не пересекает MS. Поэтому MSM может быть использована как новая граница метода JW для обнаружения столкновений при генерации сетки пограничного слоя. Как показано на фиг. 12, улучшенный метод JW использует быструю корректировку общего маршевого расстояния фронтальных точек с помощью CDT и тщательный расчет расстояния для точек обрыва с помощью DCDT для более надежного обнаружения столкновений сетки.
Фиг. 12.
Создание сетки пограничного слоя с помощью EJW для обнаружения столкновений: (a) – построение CDT граничных точек, (б) – обнаружение столкновения сеток с помощью EJW-A, (в) – обнаружение столкновения сетки с помощью EJW-B, (г) – построение сеток пограничного слоя, (д) – заполнение изотропных сеток в оставшейся области.
Пусть $p$ – фронтальная точка, которая может создать точку обрыва в следующем слое, ${{p}_{0}}$ – начальная точка $p$ на границе, а $q$ – целевая точка $({{d}_{i}} + {{d}_{{{\text{meshsize}}}}})$, удаленная от $p$ по вектору марша, что достаточно безопасно, так как ошибка построения MSM близка к $0.5{{d}_{{{\text{meshsize}}}}}$. Максимальные маршевые расстояния всех фронтальных точек были оценены в начале с помощью алгоритма 3.1 (часть A метода EJW). Если расстояние от ${{p}_{0}}$ до $p$ меньше максимального маршевого расстояния, то выполняется двухшаговая схема для проверки безопасности следующего продвижения $p$. Как показано на фиг. 13, первый шаг от ${{p}_{0}}$ до $p$ – это определение тетраэдра, в котором находится $p$, а второй шаг от $p$ до $q$ – это оценка того, пересекается ли путь ходьбы с MSM. Особенности изображены в алгоритме 4.2 (часть B метода EJW).
Фиг. 13.
Jump-and-Walk на основе различных объективных функций: (a) – поиск барицентрических координат, (б) – тест на пересечение сегмента с гранью.
Algorithm 3. Часть В EJW
Require: DCDT и его топологическая структура данных со сложностью запроса $O(1)$; начальная точка ${{p}_{0}} \in T$, фронтальная точка $p$; целевая точка $q$; функция цели: тест на пересечение сегмента и грани.
Ensure: Результат, является ли продвижение $p$ безопасным.
Первое продвижение: ${{p}_{0}} \to p$.
Инициализируем случайный тетраэдр ${{\sigma }_{0}} \in $ DCDT с ${{p}_{0}}$ в качестве одной из вершин.
$\sigma \leftarrow {{\sigma }_{0}}$.
while do $n < {{n}_{{{\text{max}}}}}$
Определите грань $\tau $ из $\sigma $ с объективной функцией:
• Если не выбрано ни одной грани $\tau $, то $p$ находится внутри $\sigma $. Выход.
• Если $\tau \in $ MSM и включен безопасный режим (по умолчанию выключен), то продвижение опасно. Возврат.
• Если $\tau $ выбрано и ${{\sigma }_{{{\text{neigh}}}}}$ может быть получена, продвижение продолжается.
Перейти через $\tau $ к ${{\sigma }_{{{\text{neigh}}}}}$.
$\sigma \leftarrow {{\sigma }_{{{\text{neigh}}}}}$.
$n = n + 1$.
end while
Второе продвижение: $p \to q$.
Выберите $\sigma $ в качестве начального тетраэдра.
while do $n < {{n}_{{{\text{max}}}}}$
Определите грань $\tau $ из $\sigma $ с помощью объективной функции:
• Если не выбрано ни одной грани $\tau $, то продвижение безопасно. Возврат.
• Если $\tau \in $ MSM или $T$, то продвижение опасно. Возврат.
• Если $\tau $ выбрано и ${{\sigma }_{{{\text{neigh}}}}}$ может быть получена, то продвижение продолжается.
Перейти через $\tau $ к ${{\sigma }_{{{\text{neigh}}}}}$.
$\sigma \leftarrow {{\sigma }_{{{\text{neigh}}}}}$.
$n = n + 1$.
end while
В части B EJW поиск барицентрических координат не применим в качестве объективной функции, поскольку MSM как стенка имеет зубчатую форму. Как показано на фиг. 13a, ${{d}_{1}}$ приблизительно равен ${{d}_{2}}$, так что объем $({{d}_{1}} \times {{s}_{1}})$ намного меньше объема $({{d}_{2}} \times {{s}_{2}})$ и ${{s}_{2}}$ будет выбран в соответствии с правилом. Поэтому вместо этого используется точный тест на пересечение сегментов, как показано на фиг. 13б.
Если $p$ прекратит маршировать, то точки на его соседях в следующем слое станут точками обрыва. Поэтому его соседи также будут проверяться, пока все точки не пройдут этот тест. Если ${{p}_{0}}$ является точкой особенности, то $p$ не будет проверяться, так как MSM простирается до точки особенности. Как показано на фиг. 14, приемлемое количество граничных слоев генерируется даже вблизи изогнутой поверхности.
4.3. Затраты по времени
Пусть $n$ – количество фронтальных точек на границе, EJW-A будет обрабатывать $n$ точек, а EJW-B только $\varepsilon n$ точек; $\varepsilon $ меньше 1, так как EJW-B может проверить только фронтальные точки верхнего слоя в узкой области. Как показано в пунктирной рамке на фиг. 14, мы отметили все проверенные точки. Всего операция обнаружения столкновений будет выполняться $(1 + \varepsilon )n$ раз. Поскольку метод JW требует ожидаемого времени $O({{n}^{{1/4}}})$ для каждого запроса, сложность предлагаемого метода составляет $O({{n}^{{5/4}}})$.
5. МЕТОД Advancing Divided-Layer (AdvDL)
Вычисление направления и расстояния марша, а также проверка правильности новых призм занимают много времени при продвижении пограничных слоев. Пусть число границ равно ${{n}_{s}}$ и число слоев равно $n$, общее время вычислений составляет ${{n}_{s}} \times n$. Однако большая часть вязкой стенки является открытой и плоской, границы имеют достаточно пространства для перехода к ${{n}^{{{\text{th}}}}}$-слою напрямую, не беспокоясь о пересекающихся сетках или других вычислениях.
Ванг и соавт. (см. [12]) предложили стратегию разделения границы внешнего слоя (OLB) для разделения граничной поверхности на открытую поверхность и узкую поверхность в соответствии с тестом пересечения сеток, который ускоряется альтернативным цифровым деревом (см. [13]), которое по сути является $k$-м деревом со средней сложностью построения $O(n{\text{log}}n)$ и сложностью запроса $O({\text{log}}n)$ для каждого объекта. Поэтому общее количество вычислений марша и проверки элементов может быть сокращено до $({{n}_{s}} + \varepsilon ({{n}_{s}} \times n))$, где $\varepsilon $ зависит от доли узкозонных границ и геометрической сложности.
В данной работе для замены цифрового дерева используется алгоритм прогнозирования пространства на основе MSP с временной сложностью $O(1)$. Хаббард и соавт. (см. [30]) представили аналогичную работу по аппроксимации многогранника максимальными сферами для обнаружения столкновений, критичных по времени. Одним из преимуществ является то, что генерация MSP и вычисление расстояния имеют линейную сложность, и наиболее трудоемкая часть, т.е. построение CDT, может быть опущена, поскольку CDT уже сгенерирован для EJW. Метод, описанный в этом разделе, называется Advancing Divided-Layer (AdvDL), который также был представлен Као и др. (см. [39]).
5.1. Мера пространства по MSP
Для дискретной точки $p$ на границе существует несколько тетраэдров, соединенных с ней в CDT. Как показано на фиг. 15, мы вычисляем проективные расстояния между $p$ и окружностями тетраэдров на нормаль к ее поверхности, и берем наименьшее значение ${{d}_{{{\text{min}}}}}$ в качестве размера пространства в текущей позиции. Точность аппроксимации обратно пропорциональна размеру поверхностной сетки.
Если общая толщина слоя
$p$ классифицируется как точка узкой области, где ${{r}_{{{\text{gap}}}}}$ – коэффициент сжатия расстояния, который меньше 1. Больший ${{r}_{{{\text{gap}}}}}$ может обеспечить более эффективный процесс продвижения. В данной работе ${{r}_{{{\text{gap}}}}}$ составляет 0.4 для расширения узкой области и достижения лучшего сглаживания направлений и расстояний марша.5.2. Продвижение фронтальных граней
Все фронтальные грани изначально классифицируются как грани с открытой областью. Если $p$ является узкозональной точкой, то фронтальные грани, соединенные с $p$, будут рассматриваться как узкозональные грани. Как показано на фиг. 16, грани с открытой областью будут двигаться вдоль фиксированного направления и быстро создавать $n$ слоев за один раз, в то время как грани с узкой областью будут следовать обычной процедуре послойного продвижения. Проверка пересечения сетки выполняется, когда текущее общее расстояние марша превышает ${{d}_{{{\text{min}}}}}{{r}_{{{\text{gap}}}}}$.
Фиг. 16.
Создание сетки пограничного слоя с использованием AdvDL для разделения границ: (a) – построение CDT граничных точек, (б) – определение геометрического пространства и разбиение граничных фронтальных граней, (в) – построение сеток пограничного слоя на узких границах с помощью процедуры послойного продвижения, (г) – генерация сеток пограничного слоя на границах открытых областей с помощью процедуры быстрого продвижения, (д) – заполнение изотропных сеток в оставшейся области.
6. ПРИМЕРЫ РАБОТЫ И ПРОМЫШЛЕННОЕ ПРИМЕНЕНИЕ
Для оценки эффективности предложенного метода из нашей библиотеки моделей выбраны три образца моделей, а именно: 3D-полость (Cav), канал охлаждения при натекании (ICC) и самолет F16. 3D-Cavity построена путем модификации и выдавливания двумерной полости под камерой сгорания газотурбинного двигателя, которая имеет сложную форму, но без каких-либо криволинейных особенностей в качестве базового объекта для тестирования производительности; ICC – это обычная модель внутреннего потока, содержащая периодические поверхности и гладкие углы, а F16 – это сложная модель самолета с внешним потоком и множеством сложных геометрических особенностей. Все тесты для этих моделей проводились на одном ядре процессора Intel Core i7-8850H с 16 ГБ оперативной памяти.
6.1. MSM
MSM извлекается из DCDT, чтобы проиллюстрировать, может ли предложенный метод приближенного представления эффективно захватывать геометрические особенности и разделять область потока. Для удобства изучения поверхностные сетки в открытых областях отмечены зеленым цветом, а остальные – красным, в соответствии с результатом, полученным методом AdvDL. Для модели Cav, показанной на фиг. 17, местоположение MSM соответствует реальной медиальной поверхности в целом, а геометрические особенности, включая маленькие углы и узкие зазоры, были идентифицированы. На фиг. 18 показан MSM в модели ICC и его вид в разрезе. Хотя MSM агломерирована вблизи периодических поверхностей и сглаженных углов, сетки пограничного слоя все еще могут быть построены с достаточным количеством слоев, потому что точки обрыва, как правило, находятся далеко от криволинейных поверхностей благодаря сглаживанию направлений маршей. На фиг. 19 показан разрез DCDT вне модели самолета. Локус MSM в DCDT виден на увеличенных изображениях.
Поскольку максимальное маршевое расстояние передней точки, вычисленное методом обнаружения столкновений на основе MSM, является грубой величиной, герметичность MSM между соседними подобластями более важна, чем точность аппроксимации. Поэтому не существует прямых фильтров для граней, составляющих MSM. К счастью, две косвенные меры могут улучшить результаты обнаружения столкновений. Во-первых, проверяемые фронтальные точки в основном распределяются в узкой области с помощью метода AdvDL, что означает, что только часть MSM, расположенная в узкой области, играет роль в алгоритме. Во-вторых, метод обнаружения столкновений проверяет только родительскую точку точки обрыва, которая обычно находится далеко от поверхности кривой.
6.2. Гибридная сетка
Гибридные сетки были созданы с помощью предложенного метода для этих моделей, а статистика данных приведена в табл. 1. На фиг. 20a показан весь вид гибридной сетки в модели Cav. На фиг. 20б показана сетка пограничного слоя в непрерывных узких каналах на локально увеличенных снимках, где размер элемента на несколько порядков меньше, чем у всей модели. Сетки вокруг углов $10^\circ $, $20^\circ $, $40^\circ $ и $90^\circ $ также показаны на фиг. 20в. Видно, что алгоритм эффективно избегает как глобальных, так и локальных пересечений сетки.
Таблица 1.
Статистика для гибридной сетки
| Модели | Методы | NT | Prism | Pyramid | Tet. | Всего |
|---|---|---|---|---|---|---|
| Cav | Наш | 762k | 13.3M | 59k | 8.8M | 22.2M |
| PW | 762k | 13.8M | 76k | 9.4M | 23.2M | |
| ICC | Наш | 304k | 6.1M | 34k | 2.9M | 9.1M |
| PW | 304k | 6.3M | 42k | 2.8M | 9.1M | |
| Самолет | Наш | 299k | 8.8M | 59k | 2.1M | 10.9M |
| PW | 299k | 9.3M | 49k | 1.9M | 11.3M |
Фиг. 20.
Гибридная сетка Cav в различных областях: (a) – вид в разрезе, (б) – непрерывные узкие каналы, (в) – углы 10°, 20°, 40° и 90°.
В модели ICC имеется много тонких охлаждающих трубок, соединенных с основными каналами, и глобальная, и частичная гибридные сетки показаны на фиг. 21. На фиг. 21б, в показано, что вокруг периодической поверхности и изогнутого угла может быть создано достаточно слоев призматических сеток.
Фиг. 21.
Гибридная сетка ICC в различных областях: (a) – вид в разрезе, (б) – периодическая поверхность, (в) – изогнутый угол, (г) – место соединения тонких охлаждающих трубок и основных каналов.
На фиг. 22a показан вид спереди гибридной сетки вне модели самолета. Видно, что форма самолета гладкая, непрерывная и нерегулярная, что значительно увеличивает сложность обнаружения столкновений сеток. На фиг. 22б, в показаны сетки в двух узких областях, где переход толщины пограничного слоя плавный, и всегда сохраняется четкое расстояние между призматическими сетками.
6.3. Эффективность построения сеток пограничного слоя
Чтобы продемонстрировать эффективность предложенного метода для обнаружения пересечений сетки и продвижения пограничного слоя, было проведено сравнение с популярной коммерческой программой Pointwise (PW) для вязкого построения гибридных сеток с одинаковой поверхностной сеткой и параметрами пользователя. В Pointwise используется метод T-Rex для послойного создания анизотропных тетраэдральных элементов и их послойного объединения в призматические сетки (см. [40], [41]), а остальная часть области заполняется изотропными элементами с помощью генератора сеток на основе сетки Делоне. В этой программе определение самопересечения в сетке передней поверхности во время непрерывной локальной модификации сетки ускоряется с помощью выровненного по оси дерева разбиения двоичного пространства.
В табл. 2 приведены статистика элементов сетки и время построения сеток для модели с различным количеством элементов поверхностной сетки (NT) или скоростью роста толщины слоя $(r)$ и одинаковыми другими параметрами пользователя. Около $30\% $ открытых граней внутренних моделей быстро продвигаются методом AdvDL, а коэффициент $(\delta )$ аналога для модели F16 составляет около $70\% $. Более того, затраты метода AdvDL чрезвычайно малы за счет совместного использования CDT и метода EJW. Более желательная эффективность построения сетки наблюдается в результате, полученном нашим алгоритмом. Скорость построения сетки из призматических элементов с помощью предложенного алгоритма может поддерживать около $100{\text{k/c}}$ в различных случаях, что в $3 \sim 4$ раза быстрее, чем у Pointwise. Когда количество поверхностных сеток меньше $100{\text{k}}$, повышение эффективности может быть необязательным, так как временные затраты на построение гибридной сетки Pointwise могут быть меньше $100{\text{c}}$. Более того, точность аппроксимации MSM обратно пропорциональна размеру граничного элемента, что означает, что предложенный алгоритм может получить лучшие результаты для крупномасштабных задач.
Таблица 2.
Сравнение эффективности построения сеток
| Модели | Методы | NT | r | Partitioning | Prism | Всего | |||
|---|---|---|---|---|---|---|---|---|---|
| $\delta $ | Время, с | Количе-ство | Время, с | Количе-ство | Время, с | ||||
| Cav | Наш | 183k | 1.2 | 35% | 0.2 | 3.2M | 27.2 | 5.0M | 35.5 |
| 351k | 1.2 | 37% | 0.3 | 6.0M | 55.8 | 9.8M | 72.2 | ||
| 762k | 1.2 | 40% | 0.7 | 13.3M | 137.1 | 22.2M | 178.9 | ||
| 1125k | 1.2 | 41% | 1.1 | 19.7M | 217.6 | 37.4M | 330.3 | ||
| PW | 183k | 1.2 | – | – | 3.4M | 140.5 | 5.1M | 156 | |
| 351k | 1.2 | – | – | 6.3M | 227.3 | 9.9M | 260 | ||
| 762k | 1.2 | – | – | 13.8M | 564.3 | 23.2M | 649 | ||
| 1125k | 1.2 | – | – | 19.9M | 681.7 | 39.1M | 872 | ||
| ICC | Наш | 304k | 1.3 | 31% | 0.5 | 4.4M | 62.0 | 7.7M | 77.3 |
| 304k | 1.2 | 24% | 0.5 | 6.1M | 77.0 | 9.1M | 91.8 | ||
| 304k | 1.08 | 22% | 0.5 | 11.3M | 116.7 | 14.4M | 130.7 | ||
| 304k | 1.03 | 21% | 0.5 | 19.0M | 180.8 | 22.5M | 203.0 | ||
| PW | 304k | 1.3 | – | – | 4.5M | 147.4 | 7.4M | 203 | |
| 304k | 1.2 | – | – | 6.3M | 199.2 | 9.1M | 253 | ||
| 304k | 1.08 | – | – | 11.7M | 344.6 | 14.5M | 399 | ||
| 304k | 1.03 | – | – | 22.0M | 670.7 | 25.1M | 726 | ||
| Самолет | Наш | 299k | 1.2 | 65% | 0.4 | 8.8M | 65.5 | 10.9M | 81.0 |
| 1016k | 1.2 | 72% | 1.4 | 29.7M | 304.7 | 36.2M | 325.7 | ||
| PW | 299k | 1.2 | – | – | 9.3M | 239.9 | 11.3M | 288 | |
| 1016k | 1.2 | – | – | 29.3M | 1185.0 | 35.7M | 1341 | ||
6.4. Сравнение методов JW и EJW
Как показано в разделе о методе EJW, как EJW-A, так и EJW-B состоят из двух частей: построение фоновой сетки (т.е. CDT/DCDT) и расчет максимального маршевого расстояния (MMD). В табл. 3 приведено распределение времени, затрачиваемого на использование метода EJW для коррекции пересечений сетки в различных случаях. Затраты времени на CDT соотносятся с геометрической сложностью, размером поверхностной сетки и производительностью генератора тетраэдральной сетки. Скорость триангуляции граничных точек составляет около $60{\text{k/c}}$ и $40{\text{k/c}}$ для моделей внутреннего и внешнего потока соответственно. Это немного быстрее, чем шаг декомпозиции CDT, где определение типов элементов и обновление топологии занимают больше всего времени, но много времени можно сэкономить, используя информацию о топологии CDT. Фильтр передних точек для вычисления MMD может быть построен методом AdvDL за несколько секунд. Пусть количество фронтальных точек на границе равно ${{n}_{0}}$, а доля граней с открытой областью равна $\delta $, количество точек, проверяемых EJW-A, составляет около $(1 - \delta ){{n}_{0}}$ и $\varepsilon {{n}_{0}} (\varepsilon < 1 - \delta )$ точки проверяются EJW-B. Таким образом, время вычисления MMD для EJW-A больше, чем для EJW-B, но их временные сложности составляют $O({{n}^{{1/4}}})$ для каждого запроса, где $n$ – количество точек в фоновой сетке, и нечувствительны к количеству слоев, относящихся к данным для модели ICC.
Таблица 3.
Время выполнения метода EJW
| Moдели | NT | r | Часть A, c | Часть B, c | Без B (T/F) | С B (T/F) | ||
|---|---|---|---|---|---|---|---|---|
| CDT | MMD | DCDT | MMD | |||||
| Cav | 183k | 1.2 | 3.2 | 2.3 | 4.2 | 0.5 | T | T |
| 351k | 1.2 | 6.5 | 9.2 | 8.3 | 1.5 | T | T | |
| 762k | 1.2 | 13.7 | 16.3 | 23.8 | 4.0 | F | T | |
| 1125k | 1.2 | 23.3 | 34.7 | 41.7 | 5.4 | F | T | |
| ICC | 304k | 1.03 | 9.6 | 7.8 | 13.4 | 4.4 | T | T |
| 304k | 1.08 | 9.2 | 7.6 | 12.8 | 2.0 | T | T | |
| 304k | 1.2 | 9.1 | 7.9 | 13.0 | 1.9 | F | T | |
| 304k | 1.3 | 8.9 | 7.5 | 12.7 | 1.2 | F | T | |
| Самолет | 299k | 1.2 | 11.7 | 6.3 | 12.9 | 2.6 | F | T |
| 1016k | 1.2 | 91.8 | 34.8 | 43.9 | 4.7 | F | T | |
Если в алгоритме не выполняется часть B метода EJW, то он эквивалентен методу JW. Полный список результатов тестирования пересечения сетки без части B и с частью B можно посмотреть в последних двух колонках табл. 3. Видно, что JW не прошел тест на пересечение, когда количество элементов поверхности или скорость роста увеличивается. На фиг. 23 показаны некоторые виды сетки пограничного слоя с удалением пересечений с помощью JW и EJW в тех же позициях. В результатах JW, пересекающиеся или почти пересекающиеся сетки все еще существуют и в основном появляются в местах, показанных на фиг. 7, что указывает на то, что улучшенный метод является более надежным и может дать достоверный результат при различных условиях.
6.5. Качество
Для оценки качества сеток пограничного слоя, построенных предложенным методом, в данном исследовании использовалась мера качества масштабированного отношения сторон, упомянутая в разделе проверки правильности сеток, и было проведено сравнение с коммерческим программным обеспечением Pointwise. Статистика призматических элементов, полученных предложенным методом и Pointwise, приведена в табл. 1, а распределения качества построены на фиг. 24, где коэффициенты в диапазоне $0.9{\kern 1pt} - {\kern 1pt} 1.0$ были сокращены на $0.7$ для удобства исследования. Призматические элементы с $\rho < 0$ являются инвертированными элементами, которые не допускаются в данном исследовании, и мы называем элементы с $\rho < 0.3$ низкокачественными элементами. Отношение низкокачественных элементов, сгенерированных Pointwise, составляет $0.292$, $1.351$ и $0.324\% $ соответственно, в то время как отношение аналогов, сгенерированных предложенным методом, составляет всего $0.083$, $0.002$ и $0.023\% $. Более того, коэффициенты призматических элементов с $\rho > 0.9$, полученных методом Pointwise, были ниже, чем предложенный метод. Это показывает, что в целом элементы, созданные нашим алгоритмом, имеют более желательное распределение, чем элементы, созданные методом Pointwise.
Для проверки достоверности и точности вычислений сгенерированной гибридной сетки было проведено моделирование вязкого течения в модели самолета с помощью коммерческого программного обеспечения Fluent. Вычислительная модель была задана как SST k-omega, $Mach = 0.6$, и угол атаки $\alpha = 0$. Для сравнения, мы также провели эксперимент по моделированию с теми же параметрами пользователя, используя сетки, сгенерированные Pointwise. На фиг. 25 представлены контурные графики вычисленного распределения давления на основе сеток Pointwise и предложенного алгоритма. Видно, что контур давления в нашем результате очень хорошо согласуется с контуром Pointwise. Отклонения минимального и максимального давления на поверхности самолета составляют $0.745$ и $0.204\% $ соответственно.
6.6. Надежность
Истребитель в состоянии посадки с полной загрузкой ракет был использован в качестве экстремального теста для демонстрации надежности предложенного метода. Как показано на фиг. 26, эта модель содержит десятки частей и почти охватывает все общие геометрические структуры самолетов, такие как комбинация крыло–корпус, трехэлементное аэродинамическое крыло, комбинация пилон–стойка, шасси и т.д., что является огромной проблемой для предложенного алгоритма. На фиг. 27a показан вид гибридной сетки в разрезе спереди. С $1147{\text{k}}$ поверхностных элементов в качестве входных данных, $22.2{\text{M}}$ призмы, $324{\text{k}}$ пирамиды и $8.7{\text{M}}$ тетраэдры были сгенерированы с процессорным временем $523.5{\text{c}}$. На фиг. 27б показаны сетки в узком зазоре бокового пилона-ракеты, который имеет довольно жесткие требования к алгоритму определения расстояния, так как находится вблизи сложных передних и задних шасси, показанных на фиг. 27в, г. Гибридные сетки в областях с большим переходом размеров показаны на фиг. 27д, е, где количество пограничных слоев постепенно увеличивается, а пересечения сетки эффективно удаляются.
7. ВЫВОДЫ И ОБСУЖДЕНИЕ
В данной работе был разработан метод JW, опирающийся только на CDT без дополнительных сложных структур данных. Он применяется для обнаружения столкновений призматических сеток с акцентом на приложениях для внутренних потоков. Благодаря введению медиальной поверхностной стенки в фоновую сетку, сетки хорошего качества последовательно создаются для сложных моделей внешнего потока. Кроме того, для ускорения работы алгоритма при небольших затратах предлагается метод AdvDL. Для демонстрации эффективности предложенного метода было обработано несколько сложных геометрий с большим количеством особенностей.
В случаях, когда одна единственная нормаль не может обеспечить достоверность конуса видимости, в алгоритм без особых трудностей может быть введена многонормальная стратегия. Предложенный алгоритм принимает треугольную сетку в качестве входных данных и строит призматическую/тетраэдральную гибридную сетку. Четырехугольные сетки также могут быть обработаны путем разбиения каждого элемента на два треугольных элемента. После генерации сетки исходная четырехугольная сетка может быть получена путем слияния каждой пары треугольных элементов и соответствующих призм.
Кроме того, был разработан метод выделения поверхности среды с помощью CDT. Однако, несмотря на его эффективность, дальнейшие исследования все еще заслуживают улучшения точности аппроксимации поверхности среды для сложных геометрий.
Список литературы
Kallinderis Y., Khawaja A., McMorris H. Hybrid prismatic/tetrahedral grid generation for viscous flows around complex geometries // AIAA J. 1996. V. 34. № 2. P. 291–298.
Kallinderis Y., Ward S. Prismatic grid generation for three-dimensional complex geometries // AIAA J. 1993. V. 31. № 10. P. 1850–1856.
Zheng Y., Xiao Z., Chen J., Zhang J. Novel methodology for viscous-layer meshing by the boundary element method // AIAA J. 2018. V. 56. № 1. P. 209–221.
Liu Y., Lo S.H., Guan Z.Q., Zhang H.W. Boundary recovery for 3d delaunay triangulation // Finite Element. Analys. Design. 2014. V. 84. P. 32–43.
Lo S.H. 3d delaunay triangulation of non-uniform point distributions // Finite Element. Analys. Design. 2014. V. 90. P. 113–130.
Loehner R. Matching semi-structured and unstructured grids for navier-stokes calculations // 11th Comput. Fluid Dynam. Conf. AIAA. 1993. P. 555–564.
Si H. Tetgen, a delaunay-based quality tetrahedral mesh generator // ACM Trans. Math. Softw. 2015. V. 41. № 2. Article 11.
Yu F., Zeng Y., Guan Z.Q., Lo S.H. A robust delaunay-aft based parallel method for the generation of large-scale fully constrained meshes // Comput. Structur. 2020. V. 228. P. 106170.
Pirzadeh S. Unstructured viscous grid generation by the advancing-layers method // AIAA J. 1994. V. 32. № 8. P. 1735–1737.
Garimella R.V., Shephard M.S. Boundary layer mesh generation for viscous flow simulations // Inter. J. Numer. Meth. Engineer. 2000. V. 49. № 1. P. 193–218.
Tomac M., Eller D. Towards automated hybrid-prismatic mesh generation // Procedia Engineer. 2014. V. 82. P. 377–389.
Wang Z., Quintanal J., Corral R. Accelerating advancing layer viscous mesh generation for 3d complex configurations // Computer-Aided Design. 2019. V. 112. P. 35–46.
Bonet J., Peraire J. An alternating digital tree (adt) algorithm for 3d geometric searching and intersection problems // Inter. J. Numerical Meth. Engineer. 1991. V. 31. № 1. P. 1–17.
Alauzet F., Marcum D. A closed advancing-layer method with changing topology mesh movement for viscous mesh generation // Proceed. of the 22th Inter. Mesh. Roundtable. Springer. 2014. P. 241–261.
Bottasso C.L., Detomi D. A procedure for tetrahedral boundary layer mesh generation // Engineer. Comput. 2002. V. 18. № 1. P. 66–79.
Dyedov V., Einstein D.R., Jiao X., Kuprat A.P., Carson J.P. Variational generation of prismatic boundary-layer meshes for biomedical computing // Inter. J. Numer. Meth. Engineer. 2009. V. 79. № 8. P. 907–945.
Ito Y., Nakahashi K. Improvements in the reliability and quality of unstructured hybrid mesh generation // Inter. J. Numer. Meth. Fluid. 2004. V. 45. № 1. P. 79–108.
Wang F., Mare L.D. Hybrid meshing using constrained delaunay triangulation for viscous flow simulations // Inter. J. Numer. Meth. Engineer. 2016. V. 108. № 13. P. 1667–1685.
Ye H., Liu Y., Chen B., Liu Z., Zheng J., Pang Y., Chen J. Hybrid grid generation for viscous flow simulations in complex geometries // Adv. Aerodynamic. 2020. V. 2. № 1. P. 1–18.
Lo S.H. A new mesh generation scheme for arbitrary planar domains // Inter. J. Numer. Meth. Engineer. 1985. V. 21. № 8. P. 1403–1426.
Cai S., Tautges T.J. Surface mesh generation based on imprinting of s-t edge patches // Procedia Engineer. 2014. V. 82. P. 325–337.
Arya S., Mount D. Approximate nearest neighbor queries in fixed dimensions // Proceed. 4th Ann. ACM-SIAM Symp. Discrete Algorithm. Soc. Industr. Appl. Math. 1993. P. 271–280.
Murphy M., Skiena S. Ranger: a tool for nearest neighbor search in high dimensions // Proceed. 9th Ann. Symp. Comput. Geometry. ACM. 1993. P. 403–404.
Borouchaki H., Lo S.H. Fast delaunay triangulation in three dimensions // Comput. Meth. Appl. Mech. Engineer. 1995. V. 128. P. 153–167.
Guibas L.J., Stolfi J. Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams // Proceed. 15th Ann. ACM Symp. Theory of Comput. 1983. P. 74–123. Boston, Massachusetts, USA.
Mücke E.P., Saias I., Zhu B. Fast randomized point location without preprocessing in two- and three-dimensional delaunay triangulations // Comput. Geometry. 1999. V. 12. № 1. P. 63–83.
Shan J.L., Li Y.M., Guo Y.Q., Guan Z.Q. A robust backward search method based on walk-through for point location on a 3d surface mesh // Inter. J. Numer. Meth. Engineer. 2008. V. 73. № 8. P. 1061–1076.
Sundareswara R., Schrater P. Extensible point location algorithm // Inter. Conf. Geometric Model. Graphic. IEEE. 2003.
Devroye L., Mücke E.P., Zhu B. A note on point location in delaunay triangulations of random points // Algorithmica. 1998. V. 22. № 4. P. 477–482.
Hubbard P.M. Approximating polyhedra with spheres for time-critical collision detection // ACM Transact. Graphic. 1996. V. 15. № 3. P. 179–210.
Quadros W.R., Shimada K., Owen S.J. Skeleton-based computational method for the generation of a 3d finite element mesh sizing function // Engineer. Comput. 2004. V. 20. № 3. P. 249–264.
Fogg H.J., Armstrong C.G., Robinson T.T. New techniques for enhanced medial axis based decompositions in 2-d // Procedia Engineer. 2014. V. 82. P. 162–174.
Linardakis L., Chrisochoides N. Algorithm 870: A static geometric medial axis domain decomposition in 2d euclidean space // ACM Transact. Math. Software. 2008. V. 34. № 1. P. 1–28.
Price M.A., Armstrong C.G. Hexahedral mesh generation by medial surface subdivision : Part 2. solids and flat convex edges // Inter. J. Numer. Meth. Engineer. 1997. V. 40. № 1. P. 111–136.
Price M.A., Armstrong C.G., Sabin M.A. Hexahedral mesh generation by medial surface subdivision: Part 1. solids with convex edges // Inter. J. Numer. Meth. Engineer. 1995. V. 38. № 19. P. 3335–3359.
Yu X., Goldak J.A., Dong L. Constructing 3-d discrete medial axis // Proceed first ACM Symp. Solid Model. Foundat. and CAD/CAM Appl. ACM. P. 481–489.
Sheehy D.J., Armstrong C.G. Shape description by medial surface construction // Visualizat. Comput. Graph. IEEE Transact. 1996. V. 2. № 1. P. 62–72.
Reddy J.M., Turkiyyah G.M. Computation of 3d skeletons using a generalized delaunay triangulation technique // Computer-Aided Design. 1995. V. 27. № 9. P. 677–694.
Cao J., Zhao M., Yu F., Chang J., Guan Z. Efficient and reliable advancing divided-layer method for boundary layer mesh // J. Comput. Aided Design and Comput. Graphic. 2020. V. 32. № 8. P. 1199–1207.
Steinbrenner J.P. Construction of prism and hex layers from anisotropic tetrahedra // 22nd AIAA Comput. Fluid Dynamic. Conf. AIAA. 2015. P. 2296. Dallas, TX, USA.
Steinbrenner J.P., Abelanet J.P. Anisotropic tetrahedral meshing based on surface deformation techniques // 45th AIAA Aerospace Sci. Meet. and Exhibit. AIAA. 2007. P. 554. Reno, Nevada, USA.
Дополнительные материалы отсутствуют.
Инструменты
Журнал вычислительной математики и математической физики
Пн.-пт.: 10.00-19.00