
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\def\udcs{519.6} %Здесь автор определяет УДК своей работы
\def\mscs{??X??} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{1}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
%     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {
      %\flushleft\it Том 16, стр. 144--144 (2019) 
      \hspace{65mm}{\rm\small УДК \udcs}}
%     \newline
%     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\usepackage{graphics}
\graphicspath{{Pictures/}}

\begin{document}
\renewcommand{\refname}{References}
\thispagestyle{empty}

\title[]{Ускорение подготовки задач аэро- и гидродинамики за счет упрощения поверхностных сеток в пакете программ Логос}
\author{Е.О. ЕВСТИФЕЕВА}%

\address{Elena Olegovna Evstifeeva  % Контактные данные всех авторов и место работы указываются только на английском языке
	\newline\hphantom{ask} Federal State Unitary Enterprise “Russian Federal Nuclear Center - All-Russian Research Institute of Experimental Physics” (FSUE “RFNC-VNIIEF”),
	\newline\hphantom{ask} Sarov, Russia}
\email{EOEvstifeeva@vniief.ru}%

\thanks{\sc Evstifeeva E.,
	Acceleration of CFD simulation preparation by surface mesh simplification in LOGOS software package}
\thanks{\copyright \ 2023 Евстифеева Е.О.}


%\thanks{\it Поступила XX января 2023 г., опубликована XX декабря 2023 г.}%

\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. }The article describes a new surface triangular mesh simplification algorithm. The simplification algorithm is applied as one of preparation stages of a high-quality surface mesh generation, which is a base for computational mesh generation in LOGOS software package. Simplification of the initial model represented as a set of triangular cells makes it possible to speed up the preparation of the final surface mesh without its quality degradation and, consequently, it leads eventually to faster computation mesh generation and simulation of physical processes. Simplification algorithm executes maximum allowable cells reduction to speed up the next stages of mesh generation. Introduced constraints enable the control over the surface curvature changes with the account for the user-set sizes, the deviation from the initial model, modified cells quality, etc. A new approach is proposed to simplify surface meshes in the context of computation model generation for CFD simulations with a possibility of parallel running using OpenMP means on given boundaries with preliminary simplification of sets of curves separating them. 

\medskip

\noindent{\bf Keywords:} LOGOS software package, preprocessor, surface triangular mesh generator, mesh simplification, curvature, quality of cells, feature curves
 \end{quote}
}


\section{Введение}

\subsection{Научный контекст}

В последние десятилетия происходит стремительное развитие областей промышленности, активно внедряющих и использующих в своем производственном цикле 3D-моделирование \cite{1}. Одной из важных прикладных областей применения численного моделирования является описание течений при решении задач аэро- и гидродинамики. Для проведения моделирования таких задач используется расчетная (объемная) дискретная модель, которая подготавливается с помощью генератора объемных сеток по исходным данным в виде поверхностной сетки.

Среди коммерческих пакетов c возможностью построения поверхностных и объемных сеток можно выделить зарубежные продукты, такие как ANSYS \cite{2}, Star CCM+ \cite{3}, Comsol Multiphysics \cite{4}, HyperMesh \cite{5}; среди открытого программного обеспечения – NetGen \cite{6}, библиотека CGAL \cite{7}. В России разрабатывается открытый код Ani3D \cite{8}, который производит построение тетраэдральных сеток с возможностью перестроения поверхностных треугольных сеток. Пакет программ «Логос» (далее – ПП «Логос») – отечественный инструмент для подготовки и проведения компьютерного моделирования с возможностью анализа результатов, разрабатываемый в ФГУП «РФЯЦ-ВНИИЭФ». Одним из его программных модулей является «Логос Аэро-Гидро», применяемый для численного моделирования физических процессов течения жидкости и газа при решении задач аэро-  и гидродинамики \cite{9,10}, в рамках которого реализованы генераторы объемных сеток \cite{11,12,13} и поверхностных треугольных сеток высокого качества \cite{14}, состоящих из ячеек (треугольников) заданного размера.

Построение поверхностной сетки производится, в частности, по исходной модели, описанной набором треугольников (модель в фасеточном представлении или поверхностная сетка), например, по модели, оцифрованной с помощью 3D-сканера, или по сетке, сгенерированной для CAD-модели спроектированного объекта. Тенденция к росту количества высоко детализированных моделей (более 1 млн. треугольников) и с нетривиальным описанием поверхностей (небольшие выступы, узкие регионы, «скругления», «полочки» и др. \cite{15}) предъявляет повышенные требования к скоростным характеристикам построения качественной поверхностной сетки как части составного процесса подготовки расчетной модели для проведения моделирования.

\subsection{Описание проблемы, постановка задачи}

Основной этап подготовки поверхностной сетки - этап перестроения - генерирует сетку Делоне в пространстве 2D методом подвижного фронта \cite{16} с последующим переносом в 3D. Наличие в исходной сетке ошибок (пересечений, наложений, зазоров, вырожденных элементов) или особенностей описания поверхности совместно с большим количеством ячеек может отразиться на производительности ввиду трудозатратного выполнения внутренних вычислительных операций алгоритма.

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

\subsection{Способ решения, предмет исследования}

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

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

\subsection{Обзор работ}

Тема упрощения сетки является широко исследуемой для применения в различных областях, таких как компьютерная графика, численное моделирование, виртуальная реальность и др. \cite{17,18,19}. Существует большое количество научных публикаций по алгоритмам упрощения сетки, поэтому далее обзор работ будет сужен до тех алгоритмов, которые подходят для применения в контексте подготовке сетки к численному моделированию.

Классификация методов \cite{20} по способу упрощения включает в себя следующие: объединение копланарных ячеек \cite{21}; итерационное сокращение сетки (вершин/ребер/ячеек) \cite{22,23,24,25}; оптимизация функции энергии \cite{26,27}; кластеризация вершин \cite{28,29,30,31,32} и др. \cite{33,34}. Некоторые методы не удовлетворяют требованию сохранения характерных особенностей модели и способны удалять небольшие конструктивные детали, например, метод кластеризации вершин \cite{28}. Другие методы, например, метод оптимизации, несмотря на свое преимущество в виде высокой точности результата, в противовес этому выполняется за относительно долгое время. Метод сокращения сетки обладает высокой производительностью, а сетки, полученные таким образом, характеризуются небольшим отклонением, что делает его в рассматриваемом контексте подготовки сеток к численному моделированию задач аэро- и гидродинамики наиболее подходящим.

Многие из существующих программных пакетов для упрощения сетки не доступны для общего использования и в лучшем случае предоставляют лишь описание используемых методов. В \cite{35} приводится обзор и сравнение программ с модулем упрощения сеток с точки зрения сохранения геометрического описания исходной модели, которое предусматривает, что упрощенная сетка аппроксимирует исходную модель с учетом некоторой величины отклонения от исходной поверхности. По результатам сравнения среднего расстояния между исходной моделью и сеткой после упрощения \cite{35} лидером является алгоритм из работы \cite{23}, который также показывает наилучшие результаты по производительности. Версия реализации алгоритма упрощения по данной работе предложена в пакете CGAL \cite{7}, однако его использование невозможно в контексте применения упрощения как одного из этапов подготовки поверхностной сетки до перестроения, поскольку не предоставляется возможность сохранять кривизну исходной поверхности с учетом заданных размеров треугольников для выделенных границ. Также можно отметить, что негативные последствия при построении сетки может вызвать появление ячеек низкого качества, что также не обработано в рассмотренных работах.

\subsection{Суть работы}

В данной работе предложен эффективный по производительности и скорости алгоритм упрощения поверхностной сетки с контролем изменения кривизны поверхности и отклонения от исходной модели с учетом заданных инженером размеров треугольников, а также не допускающий появления элементов низкого качества и потери топологической связности сетки. Предложен подход для упрощения сеток при подготовке к численному моделированию задач аэро- и гидродинамики, позволяющий сократить время упрощения за счет параллельного выполнения на выделенных инженером границах с предварительным перестроением наборов разделяющих их кривых. Представлены скоростные характеристики разработанного подхода, а также визуальные результаты алгоритма упрощения и численные значения отклонения полученных сеток от исходных моделей. Разработка ведется в рамках пакета программ «Логос» для решения задач аэро- и гидродинамики.

\section{Описание предложенного подхода к ускоренному упрощению сетки}
Основной целью внедрения алгоритма упрощения в цепочку этапов построения поверхностной треугольной сетки является сокращение общего времени подготовки поверхностной сетки и, как следствие, общего времени подготовки расчетной модели и проведения моделирования. Сам алгоритм упрощения должен быстро работать, чтобы обеспечить преимущество в общем времени подготовки сетки по сравнению со временем подготовки сетки без его использования.

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

{\bf 1.} Вычисление метрик в вершинах.

{\bf 2.} Упрощение характерных кривых.

{\bf 3.} Упрощение сетки границ.

Вычисление метрики производится для каждой вершины исходной сетки на основе кривизны исходной поверхности \cite{36}. Под метрикой в вершине будем подразумевать желаемый размер ребер, инцидентных данной вершине, при котором поверхность в окрестности данной вершины будет аппроксимирована согласно кривизне. Далее метрики ограничиваются минимальным и целевым значениями, заданными инженером для каждой из границ модели и набора характерных кривых.

Упрощение характерных кривых на втором этапе производится для следующих наборов ребер:

{\bf -} $C_f$ - набор ребер, описывающих характерные особенности модели (выделены по острому углу между треугольниками сетки);

{\bf -} $C_u$ - наборы ребер, отмеченных инженером;

{\bf -} $C_b$ - набор ребер, разделяющих границы сетки.

После упрощения характерных кривых обновленные наборы ребер $C_f^{'}$,  $C_u^{'}$,  $C_b^{'}$  остаются неизменными. Упрощение наборов характерных ребер на отдельном этапе дает весомые преимущества: во-первых, это позволяет производить последующее упрощение границ в параллельном режиме, что возможно при условии неизменности ограничивающих их ребер  $C_b^{'}$; во-вторых, для алгоритма упрощения ребер из наборов $C_f^{'}$ и $C_u^{'}$, можно задать более строгие ограничения, поскольку они описывают характерные особенности исходной модели.

Алгоритмы упрощения характерных кривых и сетки границ имеют одинаковую структуру и выполняют сокращение рассматриваемых ребер: в первом случае – ребер из наборов  $C_f$, $C_u$, $C_b$, во втором – всех ребер, принадлежащих треугольникам границы, за исключением наборов  $C_f^{'}$,  $C_u^{'}$,  $C_b^{'}$. Алгоритм упрощения в общем виде будет описан далее, для каждого из этапов будут выделены отличия.

\section{Алгоритм упрощения}

Общая идея алгоритма упрощения сетки взята из работы \cite{23}, на ее основе разработан оригинальный алгоритм. Входными данными алгоритма являются: исходная сетка, наборы характерных ребер  $C_f$, $C_u$, $C_b$, метрики в вершинах сетки.

Алгоритм упрощения является итерационным и состоит из следующих этапов:

{\bf Этап 1.} Поиск позиции вершины, заменяющей ребро, для каждого ребра из начального списка.

{\bf Этап 2.} Составление очереди из всех рассматриваемых ребер, сортированной по возрастанию веса ребра, вычисленного по определенному закону.

{\bf Этап 3.} Повторение итерации упрощения с операцией «схлопывания» ребра в заменяющую его вершину.

Для выбора позиции заменяющей вершины реализовано несколько режимов:

{\bf (1)} - в вершину с оптимальным положением (оптимальная вершина);

{\bf (2)} - в одну из вершин ребра.

Для упрощения сетки границ применяется первый режим, для характерных кривых - второй режим.

Поиск позиции оптимальной вершины $v$ для ребра в первом режиме заключается в решении системы линейных уравнений. Рассматривается более чем три ограничения, чтобы в случае линейной зависимости при добавлении нового ограничения $a_i^Tv = {b_i}$  сохранилась возможность получения оптимальной вершины. После того, как были найдены все ограничения, позиция вершины $v$ вычисляется по формуле (\ref{eq_1}):

\begin{equation}
\label{eq_1}
{v} = {A^{ - 1}}{b}
\end{equation}

Ограничение (\ref{eq_2}) для системы уравнений отвечает за сохранение объема исходной модели \cite{13}:

\begin{equation}
\label{eq_2}
\sum\nolimits_i {V(v,v_0^{{t_i}},v_1^{{t_i}},v_2^{{t_i}})}  = 0
\end{equation}

где $V(v,v_0^{{t_i}},v_1^{{t_i}},v_2^{{t_i}})$  - объем тетраэдра, полученного треугольником ${t_i}$ , описанного вершинами $v_0^{{t_i}},v_1^{{t_i}},v_2^{{t_i}}$, и оптимальной вершиной $v$.

Следующие ограничения получены решением задачи квадратичного программирования \cite{13}, а именно минимизацией квадратичной целевой функции $f(e,v)$ , которая в данном случае может быть приведена к форме (\ref{eq_3}):

\begin{equation}
\label{eq_3}
{f}({e},{v}) = \frac{1}{2}{v^T}Hv + {c^T}v + \frac{1}{2}k
\end{equation}

где $H$ - симметричный гессиан; $Hv + c$ - градиент функции $f$; $k$ - константа.

Вторым условием для системы уравнений является оптимизация объема, которое заключается в минимизации суммы объемов тетраэдров (\ref{eq_4}), образованных треугольниками, изменяемыми в результате операции схлопывания, и заменяющей вершиной $v$ \cite{13}:

\begin{equation}
\label{eq_4}
{f_V}(e,v) = \sum\nolimits_i {V{{(v,v_0^{{t_i}},v_1^{{t_i}},v_2^{{t_i}})}^2}}
\end{equation}

Третье условие направлено на оптимизацию формы треугольников \cite{13}, полученных в окрестности ребра после его схлопывания, целевая функция имеет вид (\ref{eq_5}):

\begin{equation}
\label{eq_5}
{f_S}(e,v) = \sum\nolimits_i {L{{(v,{v_i})}^2}}
\end{equation}

где правосторонняя часть выражения (\ref{eq_5}) есть сумма квадратов длин ребер, содержащих оптимальную вершину $v$.

Вес ребра вычисляется подстановкой найденной заменяющей вершины в целевую функцию (\ref{eq_4}). Выбор заменяющей вершины во втором режиме также осуществляется по минимальному весу подстановкой обеих вершин ребра в выражение (\ref{eq_4}).

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

\subsection{Итерация алгоритма упрощения}

Схема итерации третьего шага алгоритма упрощения показана на рисунке~\ref{fig:Picture1}.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture1}
	\caption{Схема итерации алгоритма упрощения}	
	\label{fig:Picture1}
\end{figure}

Операция схлопывания ребра применяется локально, после чего выполняется ряд проверок и только в случае их успешности изменения применяются к сетке и в очередь с новым весом заново вставляются обновленные ребра, которые были изменены на текущей итерации. Метрика $m$ для заменяющей вершины $v$  вычисляется по формуле (\ref{eq_6}):

\begin{equation}
\label{eq_6}
{m} = 0.5({m_1} + {m_2})
\end{equation}

где $m_1$, $m_2$  - метрики в вершинах ребра до операции схлопывания.

\subsection{Топологическая допустимость}

Проверка топологической допустимости контролирует сохранение корректного описания сетки, а именно в ней не должно появляться ребер, принадлежащих более чем двум треугольникам сетки, свободных ребер, принадлежащих лишь одному треугольнику сетки, несвязанных фрагментов сетки, не связанных между собой общими ребрами.

\subsection{Целевые ограничения}

В большинстве работ в качестве критерия остановки алгоритма предлагается задание конечного количества треугольников (числом или процентом от исходного количества) или достижение предельного отклонения от исходной поверхности.

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

Предложены следующие целевые ограничения:

1.	по качеству треугольника;

2.	по углу между нормалями смежных треугольников;

3.	по метрике в вершине;

4.	по отклонению от исходной поверхности модели.

\subsubsection{Ограничение по качеству треугольника}

Несмотря на то, что после алгоритма упрощения сетка будет перестроена, важно не допустить появление треугольников с качеством ниже порогового значения, поскольку такие треугольники вносят неустойчивость для некоторых вычислительных операций, например, для поиска нормали. Для определения качества треугольника используется формула (\ref{eq_7}):

\begin{equation}
\label{eq_7}
{q} = \frac{{2r}}{R}, {0} \le {q} \le {1}
\end{equation}

где  $r$ - радиус вписанной окружности; $R$  - радиус описанной окружности.

Выполнение условия (\ref{eq_8}) для каждого измененного треугольника на итерации гарантирует, что качество сетки не опустится ниже порогового значения $\varepsilon_q$:

\begin{equation}
\label{eq_8}
{q} \ge {\varepsilon _q}
\end{equation}

При реализации алгоритма было выбрано пороговое значение $\varepsilon _q = 0.01$

При невыполнении условия (\ref{eq_8}) проверяется, что значение для треугольника после выполнения операции понизилось относительно его значения до операции, и в таком случае производится откат операции.

\subsubsection{Ограничение по углу между нормалями смежных треугольников}

Данный критерий разработан для сохранения описания исходной поверхности с помощью контроля изменения углов между нормалями смежных треугольников сетки по формуле (\ref{eq_9}):

\begin{equation}
\label{eq_9}
\left| {\alpha  - \beta } \right| \le {\varepsilon _{\deg }}
\end{equation}

где $\alpha$ - угол между нормалями двух треугольников $t_1$ и $t_2$ до операции схлопывания;

$\beta$ - угол между нормалями двух смежных треугольников $t_1$ и $t_2$ после операции схлопывания;

$\varepsilon _{\deg}$- максимально допустимое значение изменения угла между нормалями смежных треугольников.

Значение $\varepsilon _{\deg}$  при реализации выбрано равным ${2^ \circ }$. Условие (\ref{eq_9}) проверяется для всех пар смежных треугольников после модификации сетки, в которых хотя бы один из треугольников был изменен.

\subsubsection{Ограничение по метрике в вершине}

Следующим целевым ограничением для проверки успешности итерации является соответствие размеров измененных ребер средним значениям метрик в их вершинах, как показано в формуле (\ref{eq_10}):

\begin{equation}
\label{eq_10}
{l} \le {b} \cdot \frac{{{m_1} + {m_2}}}{2}
\end{equation}

где $m_1$, $m_2$  - метрики в вершинах ребра;

$l$ - длина измененного ребра;

$b$ - масштабирующий коэффициент, допускающий отклонение размера.

Условие (\ref{eq_10}) гарантирует согласованность измененной сетки с кривизной исходной поверхности с учетом заданных инженером размеров, при его выполнении операция считается допустимой и производится переход к следующей итерации.

При невыполнении условия (\ref{eq_10}) в режиме упрощения сетки границ выполняется переход к дополнительным проверкам; в режиме упрощения характерных кривых производится откат операции, поскольку это может исказить пользовательские границы, как показано на рисунке~\ref{fig:Picture2}б, где бежевая граница исходной модели (рисунок~\ref{fig:Picture2}а) лежит в плоскости голубой границы. Фрагмент сетки с учетом метрики для ребер, разделяющих границы, показан на рисунке~\ref{fig:Picture2}в.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture2}
	\caption{Фрагмент сетки с границей (бежевый цвет), лежащей в плоскости другой границы (голубой цвет): а - до упрощения; б - после упрощения без учета метрики; в - после упрощения с учетом метрики}	
	\label{fig:Picture2}
\end{figure}

\subsubsection{Ограничение по отклонению от исходной поверхности модели}

Если условие (\ref{eq_10}) не выполнено при упрощении сетки границ, откат операции не производится и проверяется дополнительное ограничение по отклонению. Такое решение обосновано тем фактом, что метрики на плоских участках модели ограничиваются заданным размером, который может быть намного меньше размера, вычисленного по кривизне, однако, при упрощении таких участков потери кривизны не произойдет, поэтому допустимо произвести более сильное упрощение.

В начале алгоритма упрощения для каждого треугольника сетки инициализируется накопительная величина изменения объема $tol = 0.0$. На каждой операции схлопывания для модифицированного $k$-го треугольника проверяется условие (\ref{eq_11}):

\begin{equation}
\label{eq_11}
{tol_k} + {tol_{curr}^k} \le {\varepsilon _{tol}}
\end{equation}

$tol_{curr}^k$  - вызванное смещением треугольника изменение объема;

$\varepsilon _{tol}$ - глобальное пороговое значение отклонения, которое вычисляется по формуле (\ref{eq_12}):

\begin{equation}
\label{eq_12}
{\varepsilon_{tol}} = \frac{1}{6}{(k \cdot {m_{\min }})^3}
\end{equation}

где $m_{min}$  - минимальное значение метрики на границе;

$k$ - константа, при реализации экспериментальным путем выбрано значение 0.01;

Дополнительно значение $\varepsilon_{tol}$, полученное по формуле (\ref{eq_12}), ограничивается минимальным и максимальным значениями, чтобы удовлетворять формуле (\ref{eq_13}):

\begin{equation}
\label{eq_13}
{1e - 22} \le {\varepsilon_{tol}} \le {1e - 9}
\end{equation}

\section{Результаты и обсуждение}

\subsection{Варьирование целевых ограничений}

Использование целевого ограничения по углу позволяет максимально упростить плоские участки моделей, а также с помощью варьирования параметра $\varepsilon_{\deg }$  контролировать изменение угла между треугольниками. На рисунке~\ref{fig:Picture3}а приведен фрагмент исходной сетки ${S_{orig}}$ для модели летательного аппарата \cite{37}, количество ячеек ${N_{orig}=76}$ тыс. На рисунках~\ref{fig:Picture3} -~\ref{fig:Picture4} – сетки ${S_{simpl}}$ после упрощения с использованием только ограничения по углу с различными значениями $\varepsilon_{\deg }$.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture3}
	\caption{Фрагменты сеток для исходной модели (а) летательного аппарата, построенные с разными значения изменения угла $\varepsilon_{\deg }$  без учета остальных ограничений: б: ${\varepsilon_{\deg }} = {1^ \circ }$; в: $\varepsilon_{\deg } = {2^ \circ }$; г:  ${\varepsilon_{\deg }} = {3^ \circ }$; д:  ${\varepsilon_{\deg }} = {5^ \circ }$; е: ${\varepsilon_{\deg }} = {10^ \circ }$}	
	\label{fig:Picture3}
\end{figure}

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture4}
	\caption{Фрагменты сеток фюзеляжа для исходной модели (а) летательного аппарата, построенные с разными значения изменения угла $\varepsilon_{\deg }$  без учета остальных ограничений: б: ${\varepsilon_{\deg }} = {1^ \circ }$; в: $\varepsilon_{\deg } = {2^ \circ }$; г:  ${\varepsilon_{\deg }} = {3^ \circ }$; д:  ${\varepsilon_{\deg }} = {5^ \circ }$; е: ${\varepsilon_{\deg }} = {10^ \circ }$}	
	\label{fig:Picture4}
\end{figure}

Визуальные результаты показывают, что при увеличении параметра  $\varepsilon_{\deg }$ возрастает степень упрощения сетки, однако сохраняется ее конструктивное описание. Результаты по сокращению количества ячеек приведены в таблице~\ref{table:table_1}.

\begin{table}[h!]
	\caption{Количество ячеек ${N_{simpl}}$ в сетке ${S_{simpl}}$ в результате упрощения в зависимости от заданного значения $\varepsilon_{\deg }$}
	\begin{tabular}{|c|c|c|c|c|c|}
		\hline
		 & ${\varepsilon_{\deg }} = {1^ \circ }$ & ${\varepsilon_{\deg }} = {2^ \circ }$ & ${\varepsilon_{\deg }} = {3^ \circ }$ & ${\varepsilon_{\deg }} = {5^ \circ }$ & ${\varepsilon_{\deg }} = {10^ \circ }$\\
		\hline	
		${N_{simpl}}$ & 27056 & 14518 & 8444 & 4442 & 2562 \\
		\hline	
		${N_{simpl}}$/${N_{orig}}$ & 0,36 & 0,19 & 0,11 & 0,06 & 0,03 \\
		\hline	
	\end{tabular}
	\label{table:table_1}
\end{table}

Рассмотрим влияние целевого критерия по метрике при задании различных значений ${s_{\min }}$ и ${s_{\max }}$, отвечающих за минимальный и целевой размер соответственно. На рисунке~\ref{fig:Picture5}а представлен фрагмент исходной модели летательного аппарата, средняя длина ребра в областях без сгущений составляет 0.35м. На рисунках~\ref{fig:Picture5}б-~\ref{fig:Picture5}д – результаты упрощения данного фрагмента с разными заданными значениями параметров ${s_{\min }}$ и ${s_{\max }}$.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture5}
	\caption{Фрагменты сеток для исходной модели (а) летательного аппарата, построенные с разными заданными размерами ${s_{\min }}$ и ${s_{\max }}$ с целевым ограничением по метрике без учета остальных ограничений: б: ${s_{\min }} = 0.1,{s_{\max }} = 1.0$; в:  ${s_{\min }} = 0.1,{s_{\max }} = 5.0$; г: ${s_{\min }} = 1.0,{s_{\max }} = 5.0$; д: ${s_{\min }} = 5.0,{s_{\max }} = 5.0$}	
	\label{fig:Picture5}
\end{figure}

Поскольку поверхности крыльев летательного аппарата представляют собой более плоские участки по сравнению с фюзеляжем в результате упрощения размеры ребер там стремятся к значению ${s_{\max }}$. Результаты по сокращению количества ячеек приведены в таблице~\ref{table:table_2}.

\begin{table}[h!]
	\caption{Количество ячеек ${N_{simpl}}$ в сетке ${S_{simpl}}$ в результате упрощения в зависимости от заданных значений ${s_{\min }}$ и ${s_{\max }}$}
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		& ${s_{\min }} = 0.1$, ${s_{\max }} = 1.0$ & ${s_{\min }} = 0.1$, ${s_{\max }} = 5.0$ & ${s_{\min }} = 1.0$, ${s_{\max }} = 5.0$ & ${s_{\min }} = 5.0$, ${s_{\max }} = 5.0$\\
		\hline	
		${N_{simpl}}$ & 21790 & 21108 & 5708 & 3052  \\
		\hline	
		${N_{simpl}}$/${N_{orig}}$ & 0,29 & 0,28 & 0,08 & 0,04 \\
		\hline	
	\end{tabular}
	\label{table:table_2}
\end{table}

Рассмотрим общее влияние целевых ограничений на примере исходной сетки \cite{37} с рисунка~\ref{fig:Picture6}. Данная сетка состоит из 76 тыс. ячеек и является достаточно подробной, с наличием сгущений, не обоснованных конструктивными особенностями модели. Размеры для перестроения заданы таким образом, чтобы в результате получилась менее подробная сетка.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture6}
	\caption{Фрагмент исходной сетки}	
	\label{fig:Picture6}
\end{figure}

Результат упрощения сетки с рисунка~\ref{fig:Picture6} с применением всех целевых ограничений показан на рисунке~\ref{fig:Picture7}. Сетка после упрощения состоит из 26 тыс. ячеек.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture7}
	\caption{Фрагмент сетки после работы алгоритма упрощения с выполнением всех целевых ограничений}	
	\label{fig:Picture7}
\end{figure}

Визуальная оценка результата показывает, что сетка на плоскости (зеленая граница) максимально упрощена с учетом разбиения ребер между границами и с ограничением по качеству полученных треугольников. Сетка на конструкции летательного аппарата (крылья – оранжевая и синяя границы, фюзеляж – фиолетовая граница) упрощена, исходя из кривизны поверхности с учетом заданных размеров. Количество ячеек в результате упрощения сокращено на 66\%, при этом аппроксимация геометрической модели соответствует кривизне исходной поверхности. Качество треугольных ячеек было снижено, но при этом остается в допустимом диапазоне, вырожденных элементов не обнаружено. Такая сетка за счет сокращения размерности будет более эффективно обработана на дальнейшем этапе перестроения сетки методом подвижного фронта для получения ячеек высокого качества и нужного размера. Результат построения итоговой сетки, которая будет использована для подготовки расчетной модели, представлен на рисунке~\ref{fig:Picture8}.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture8}
	\caption{Фрагмент построенной сетки}	
	\label{fig:Picture8}
\end{figure}

\subsection{Результаты по скорости}

Для проверки достижения поставленных целей было проведено тестирование на моделях различной сложности, на примере выборки из шести моделей ${T_i},i = \overline {1,6} $ показаны основные результаты. Количество ячеек в исходной модели и сетке после упрощения приведены в таблице~\ref{table:table_3}.

\begin{table}[h!]
	\caption{Количество ячеек ${N_{orig}}$ в исходной сетке и ${N_{simpl}}$ в сетке после упрощения для тестовых моделей ${T_i},i = \overline {1,6} $}
	\begin{tabular}{|c|c|c|c|c|c|c|}
		\hline
		& ${T_1}$ & ${T_2}$ & ${T_3}$ & ${T_4}$ & ${T_5}$ & ${T_6}$ \\
		\hline	
		${N_{orig}}$ & 170164 & 170572 & 16382 & 665158 & 1355204 & 1334642  \\
		\hline	
		${N_{simpl}}$ & 84952 & 73978 & 12664 & 159920 & 580234 & 588220  \\
		\hline	
		${N_{simpl}}$/${N_{orig}}$ & 0,5 & 0,43 & 0,77 & 0,24 & 0,43 & 0,44 \\
		\hline	
	\end{tabular}
	\label{table:table_3}
\end{table}

Далее обратимся к диаграмме с рисунка~\ref{fig:Picture9}, на которой показано сравнение общего времени построения сетки с использованием алгоритма упрощения и без его использования. Над вторым столбцом пары указано относительное время построения сетки с использованием упрощения относительно времени построения без его использования ${t_i}$.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture9}
	\caption{Сравнение времени построения сеток для моделей ${T_i},i = \overline {1,6} $  различной сложности с использованием алгоритма упрощения и без его использования}	
	\label{fig:Picture9}
\end{figure}

Результаты, приведенные на рисунке~\ref{fig:Picture9}, демонстрируют, что с использованием алгоритма упрощения на представленной выборке задач время построения сокращено до 76\%. При этом время работы алгоритма упрощения занимает небольшую часть от общего времени выполнения, как показано на рисунке~\ref{fig:Picture10}, где значение над столбцом показывает время выполнения алгоритма упрощения относительно общего времени подготовки сетки.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture10}
	\caption{Диаграмма с общим временем подготовки сетки, в котором синим цветом в столбце выделено время выполнения алгоритма упрощения}	
	\label{fig:Picture10}
\end{figure}

Результаты временных замеров выполнения алгоритма упрощения в однопоточном и параллельном режимах (средствами OpenMP) представлены на рисунке~\ref{fig:Picture11}.

\begin{figure}[h!] 
	\centering
	\includegraphics[width=1.0\textwidth]{Picture11}
	\caption{Сравнение времени выполнения алгоритма упрощения в однопоточном и параллельном режимах на 8 потоках}	
	\label{fig:Picture11}
\end{figure}

При тестировании максимальное количество потоков было ограничено 8. По результатам с рисунка~\ref{fig:Picture11} стоит отметить, что небольшая разница времени выполнения алгоритма упрощения в однопоточном и параллельном режиме связана с разбиением на границы. В случае, когда модель выделена в одну границу, временные характеристики обоих режимов будут совпадать. Также небольшая разница возможна из-за неравномерного распределения по количеству треугольников в границах. Разделение границ на дополнительные области для более эффективного распараллеливания является одним из направлений дальнейшей работы.

\subsection{Результаты по отклонению}

Наряду со скоростными характеристиками сравнивалось отклонение результирующих сеток, построенных с использованием алгоритма упрощения и без его использования. Сравнение поверхностных сеток проводилось с помощью программы metro \cite{38}, измеряющей расстояние Хаусдорффа между парой сеток. По результатам сравнения на рассматриваемой выборке задач отклонение не превышает 0.04м в области сетки, где целевой размер задан равным  1.0м, а размер по кривизне вычислен около   0.4м, причем при использовании алгоритма упрощения в данной области исходная модель лучше аппроксимирована, чем без его использования.

\section{Заключение}

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

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

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

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


\bibitem{1} Погосян М.А., Савельевских Е.П., Шагалиев Р.М., Козелков А.С., Стрелец Д.Ю., Рябов А.А., Корнев А.В., Дерюгин Ю.Н., Спиридонов В.Ф., Циберев К.В.,
{\it Применение отечественных суперкомпьютерных технологий для создания перспективных образцов авиационной техники},
// Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов 2013. Вып.2. С. 3-18.

\bibitem{2}	ANSYS. http://www.ansys.com.

\bibitem{3}	STAR-CCM+ Siemens PLM Software. https://mdx.plm.automation.siemence.com/star-ccm-plus.

\bibitem{4}	Comsol Multiphysics. https: //www.comsol.ru.

\bibitem{5}	HyperMesh. https://www.altairhyperworks.com/hypermesh.

\bibitem{6}	Netgen Mesh Generator. http://sourceforge.net/projects/netgen-mesher.

\bibitem{7}	CGAL. http://www.cgal.org/download.html.

\bibitem{8} Advanced Numerical Instruments 3D. http://sourceforge.net/projects/ani3d

\bibitem{9} Kozelkov A.S., Krutyakova O.L., Kurulin V.V., Strelets D.Yu., Shishlenin M.A.,
{\it The accuracy of numerical simulation of the acoustic wave propagations in a liquid medium based on Navier-Stokes equations},
// Siberian Electronic Mathematical Reports, 2021. http://semr.math.nsc.ru

\bibitem{10} Kozelkov A.S., Struchkov A.V., Strelets D.Yu.,
{\it Two Methods to Improve the Efficiency of Supersonic Flow Simulation on Unstructured Grids},
// Fluids 2022, 7, 136. https://doi.org/10.3390/fluids7040136.

\bibitem{11}	Смолкина Д.Н., Борисенко О.Н., Черенкова М.В., Гиниятуллина А.Г., Кузьменко М.В., Чухманов Н.В, Потехина Е.В., Попова Н.В., Турусов М.Р.,
{\it Автоматический генератор неструктурированных многогранных сеток в препроцессоре пакета программ ЛОГОС},
// Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2018. Вып. 2. С. 25-39.

\bibitem{12} Попова Н.В, Борисенко О.Н., Корнеева И.И., Чухманов Н.В., Потехина Е.В., Лазарев В.В., Гиниятуллина А.Г.,
{\it Автоматический генератор неструктурированных тетраэдральных сеток с призматическими слоями в препроцессоре пакета программ «ЛОГОС»},
// Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. - 2020. - Вып. 1. - С. 43-57.

\bibitem{13} Попова Н.В.,
{\it Автоматический генератор неструктурированных многогранных сеток на основе тетраэдральных сеток с призматическими слоями},
// Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. - 2021. - Вып. 3. С. 70-83.

\bibitem{14} Лукичев А.Н., Цалко Т.В., Панкратов Д.М., Логинов Д.В., Белова А.И., Моськина Е.О.,
{\it Особенности построения триангуляционных сеток на поверхностях в аналитическом и фасеточном представлении},
// Сборник докладов 15ой научно-технической конференции «Молодежь в науке». Саров: ФГУП «РФЯЦ-ВНИИЭФ», 2017. С. 73-78.

\bibitem{15} Борисенко О.Н., Лукичев А.Н., Евстифеева Е.О., Панкратов Д.М., Цалко Т.В., Гиниятуллина А.Г.,
{\it Алгоритмы обработки особенностей геометрических моделей при построении поверхностных треугольных сеток в препроцессоре пакета программ ЛОГОС},
// Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов 2020. Вып.3. С. 40-52.

\bibitem{16} P.-L. George, H. Borouchaki,
{\it Delaunay Triangulation and Meshing},
// HERMES, 1998.

\bibitem{17}	R. Potamias, S. Ploumpis and S. Zafeiriou, 
{\it Neural Mesh Simplification},
// 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), New Orleans, LA, USA, 2022 pp. 18562-18571.

\bibitem{18} Liu, Z.; Zhang, C.; Cai, H.; Qv,W.; Zhang, S.
{\it A Model Simplification Algorithm for 3D Reconstruction},
// Remote Sens. 2022, 14, 4216. https://doi.org/10.3390/rs14174216

\bibitem{19} Song Y., Fellegara R., Iuricich F., De Floriani L.,
{\it Efficient topology-aware simplification of large triangulated terrains},
// Association for Computing Machinery, pp. 576–587, 2021.

\bibitem{20} Cignoni P., Montani C., Scopigno R.,
{\it A comparison of mesh simplification algorithms},
// 1997. 

\bibitem{21} Kalvin A.D., Taylor R.H.,
{\it Superfaces: Poligonal mesh simplification with bounded error},
// IEEE C.G.\& A., 16(3):64-77, 1996.

\bibitem{22} Hamann B.,
{\it A data reduction scheme for triangulated surfaces},
// Computer Aided Geometric Design, 11(2):197-214, 1994.

\bibitem{23} Lindstrom P., Turk G.,
{\it Fast and Memory Efficient Polygonal Simplification},
// Proc. Visualization ’98, IEEE Computer Soc. Press – Oct. 1998 – Pp. 279–286.

\bibitem{24} Hongle Li, SeongKi Kim,
{\it Triangular Mesh Simplification based on Surface Angle},
// MITA, Conference Paper, 2019.

\bibitem{25} Guangyou Zhou, Shangda Yuan, Sumei Luo,
{\it Mesh Simplification Algorithm Based on the Quadratic Error Metric and Triangle Collapse},
// IEEE Access, 2020.

\bibitem{26} Hoppe H., DeRose T., Duchamp T., McDonald J., Stuetzle W.,
{\it Mesh optimization},
// In ACM Computer Graphics Proc., Annual Conference Series, (Siggraph ‘93), pages 19-26, 1993.

\bibitem{27} Yongzhi Wang, Jianwen Zheng, Hui Wang,
{\it Fast Mesh Simplification Method for Three-Dimensional Geometric Models with Feature Preserving Efficiency},
// Hindawi, Scientific Programming, 2019.

\bibitem{28} Garland M., Heckbert P.S.,
{\it Surface simplification using quadric error metrics},
// In Comp. Graph. Proc. Annual Conf. Series (Siggraph ‘97), ACM Press, 1997.

\bibitem{29} Kanchan Bahirat, Chengyuan Lai, Ryan P. Mcmahan, Balakrishnan Prabhakaran,
{\it Designing and Evaluating a Mesh Simplification Algorithm for Virtual Reality},
// ACM Trans. Multimedia Comput. Commun. Appl. 14, 3s, Article 63 (June 2018), 26 pages.

\bibitem{30} Lin Zhang, Zhen Ma, Zhong Zhou, and Wei Wu,
{\it Laplacian-Based Feature Preserving Mesh Simplification},
// Springer-Verlag Berlin Heidelberg, pp. 378–389, 2012.

\bibitem{31} Li Yao, Shihui Huang, Hui Xu, and Peilin Li,
{\it Quadratic Error Metric Mesh Simplification},
// Hindawi Publishing Corporation, Mathematical Problems in Engineering, 2015.

\bibitem{32} Philip Trettner and Leif Kobbelt,
{\it Fast and Robust QEF Minimization using Probabilistic Quadrics},
// Computer Graphics Forum, 2020.

\bibitem{33} He T., Hong L., Varshney A., Wang S,
{\it Controlled topology simplification},
// IEEE Trans. On Visualization \& Computer Graphics, 2(2):171-183, 1996.

\bibitem{34} Eck M., De Rose T., Duchamp T., Hoppe H., Lounsbery M., Stuetzle W.,
{\it Multiresolution analysis of arbitrary meshes},
// In Computer Graphics Proc., Annual Conf. Series (Siggraph ’95), ACM Press, pages 173-181, Aug. 6-12 1995.

\bibitem{35} Surazhsky V., Gotsman C.,
{\it A Qualitative Comparison of Some Mesh Simplification Software Packages},
// s.l. : CMA/IFI, University of Oslo, 2005.

\bibitem{36} Белова А.И., Лукичев А.Н., Борисенко О.Н.,
{\it Вычисление кривизны дискретных поверхностей в генераторе поверхностных триангуляционных сеток Логос.Препост},
// Сборник докладов 15ой научно-технической конференции «Молодежь в науке». Саров: ФГУП «РФЯЦ-ВНИИЭФ», 2017. С. 34-40.

\bibitem{37}
{\it 3rd AIAA CFD Drag Prediction Workshop},
// San Francisco, June 2006. URL: http://aiaa-dpw.larc.nasa.gov/Workshop3/workshop3.html (дата обращения: 08.07.2021)

\bibitem{38} Cignoni P., Rocchini C., Scopigno R,
{\it Metro: Measuring Error on Simplified Surfaces},
// Technical Report B4–01–01–96, Istituto I. E. I.–C. N. R. – Pisa, Italy – January 1996.

\end{thebibliography}
\end{document}
