Сравнение с методом марширующих кубов

\includegraphics[scale=0.68, angle=0, clip=true]{new_figs/lens1.ps}
Fig. 4.
Область задана как результат пересечения двух эллипсоидов с последующим скручиванием.
\includegraphics[scale=0.7, angle=0, bb = 10 0 220 530, clip=true]{new_figs/lens2.ps}
Fig. 5.
Минимальный двугранный угол 12.5. Максимальный двугранный угол 159.2.
\includegraphics[scale=0.82, angle=0, clip=true]{new_figs/marching_cubes-new.eps}
Fig. 6.
Реконструкция изоповерхности марширующими кубиками.

Алгоритм марширующих кубов (Лоренсен, 1987) не справляется с задачей восстановления острых ребер.

Методы задания неявных областей

Рассмотрим ограниченную область $ \Omega \subset \mathbb{R}^3$ с кусочно-гладкой границей.

Пусть задана некоторая функция $ u(x): \mathbb{R}^3 \to \mathbb{R}$ такая, что во внутренних точках области выполнено $ u(x)<0$ , а в дополнении области справедливо $ u(x)>0$ , как показано на рис. 1.

\includegraphics[scale=1.0, angle=0]{new_figs/var_implicit_domain.eps}
Fig. 1. Пример неявного задания двумерной области $ \Omega$ .

Предполагается, что функция $ u(x)$ непрерывна по липшицу, представима в виде разности выпуклых функций, является кусочно-гладкой, и ее производные вдоль некоторого невырожденного векторного поля, транверсального к $ \partial \Omega$ , существуют и не равны нулю в некотором конечном слое $ S$ около $ \partial \Omega$ .

  • приближенное построение функции расстояния со знаком
    • поверхностная триангуляция;
    • облако точек;
    • набор плоских сечений;
    • воксельная решетка;
    • модель САПР, заданная одновременно $ B$ -сплайнами и тесселяцией
  • использование неполных и противоречивых данных при помощи метода радиальных базисных функций;
  • булевы операции над областями.

Построение тетраэдральных сеток в неявных областях

  • область задается посредством "оракула" как точка пересечения нулевой изоповерхности с произвольным отрезком прямой. Шевчук, 2007 - алгоритм для построения тетраэдральных сеток в областях с гладкой границей, Boissonat J.-D., Cohen-Steiner D., Mourrain B., Rote G., Vegter G., 2007 - описание алгоритма из пакета CGAL
  • область задается посредством неявной функции со знаком (Перссон, Стренг, 2004)

Построение неявной функции с использованием булевых операций

Примеры примитивов

сфера:

$\displaystyle u(x)=(x^2_1 + x^2_2 + x^2_3)^{\frac12}-1, $

куб:

$\displaystyle u(x)=\max(\vert x_{1}\vert-1,\vert x_{2}\vert-1,\vert x_{3}\vert-1), $

конечный круговой цилиндр:

$\displaystyle u(x)=\max((x^2_1 + x^2_2)^\frac12-R, \vert x_{3}\vert-1) $

Пусть $ u_1(x)$ и $ u_2(x)$ - неявные функции, задающие области $ \Omega_1$ и $ \Omega_2$ . Тогда, в зависимости от способа задания области $ \Omega_3$ , функция $ u_3(x)$ будет выглядеть следующим образом:

\begin{displaymath}\begin{array}{lcl} \Omega_3 = \Omega_1 \cup \Omega_2 & \Long... ..._2 & \Longrightarrow & u_3(x)=\max(u_1(x),-u_2(x)) \end{array}\end{displaymath} (1)

Построение неявной функции с использованием РБФ Аппроксимант неявной функции по набору отрезков $ S_1, \dots, S_n$ ищется в следующем виде (Шевчук, 2004)


$\displaystyle u_\epsilon(x) = \frac{\sum_k l_k \theta_k(x)}{\sum_k l_k\Theta_k(x)},$ (2)


где $ l_k$ - длина ребра $ S_k$ , а $ \theta_{k}(x)$ и $ \Theta_{k}(x)$имеют вид

$\displaystyle \theta_k (x)=\int\limits^1_0 {\frac{(\phi(b_k)-\phi(a_k)) t +\phi... ...-q_k )^T n_k }{(\vert(b_k-a_k) t + a_k -x\vert^2+\varepsilon ^2)^2}} d t $

$\displaystyle \Theta_k (x)=\int\limits^1_0 {\frac{1}{(\vert(b_k-a_k) t + a_k -x\vert^2 + \varepsilon ^2)^2}} dt $

где $ q$ - произвольная внутренняя точка отрезка $ S_k = [a_k, b_k]$ , а $ n_k$- единичная нормаль к ориентированному ребру, которая задает целевое значение градиента неявной функции. .

а) б)
\includegraphics[scale=0.36, angle=0, clip=true]{new_figs/wiresh.ps} \includegraphics[scale=0.36, angle=0, clip=true]{new_figs/wire1sh.ps}
в) г)
\includegraphics[scale=0.36, angle=0, clip=true]{new_figs/wire1sh02.ps} \includegraphics[scale=0.36, angle=0, clip=true]{new_figs/wire3sh02.ps}
Fig. 2. а) Точное задание контура. Построена интерполирующая функция. б) Контур с самопересечением. Точный интерполянт образует нежелательные петли. в) По контуру с самопересечением построен аппроксимант. г) Входные данные зашумлены. Аппроксимант сглаживает разрывы и самопересечения.

Введение

Руководитель направления: д.ф.-м.н. В.А. Гаранжа

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

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

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

Методы и алгоритмы построения расчетных сеток

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

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

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

  • задание областей посредством неявных функций;
  • построение тетраэдральных сеток в неявных областях;
  • самоорганизация вершин сетки путем расталкивания;
  • проекция вершин на границу области;
  • "проявление" острых ребер границы;
  • оптимизация для удаления плоских тетраэдров.

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

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

Текущий статус разработки сеткостроителя и программы визуализации, планы работ и перспективы развития в области построения сеток

  • В 2011 реализована полная технологическая цепочка построения сеток: модель в формате STEP ? тесселированная модель → модель, разрезанная на блоки → построитель поверхностных сеток → построитель объемных сеток;
  • для обработки моделей САПР используется геометрическое ядро OpenCascade;
  • в текущей версии рассматриваются удлиненные тела вращения с элементами управления (рули, крылья и т.д.), разрезание на блоки производится плоскостями;
  • в текущей версии реализовано внутреннее блочное представление сеток, вычислительное ядро построителя поддерживает блочную структуру;
  • адаптация сеток к кривизне находится в исследовательской фазе;
  • программа визуализации позволяет показывать сетки, расчетные поля, изолинии, изоповерхности, в том числе в стереорежиме с очками.

Первоочередные задачи разработки построителя сеток и визуализатора.

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

Литература

  1. Гаранжа В.А., Капорин И.Е. Регуляризация барьерного вариационного метода построения расчетных сеток // Ж. вычисл. матем. и матем. физ. 1999. Т.39. 9. С.1489-1503.
  2. Garanzha V.A. Discrete extrinsic curvatures and approximation of surfaces by polar polyhedra // Ж. вычисл. матем. и матем. физ. 2010. Т.50. 1. С.71-98. Гаранжа В.А. Барьерный метод построения квазиизометрических сеток // Ж. вычисл. матем. и матем. физ. 2000. Т.40, 11. С.1685-1705.
  3. Гаранжа В.А. Управление метрическими свойствами пространственных отображений // Ж. вычисл. матем. и матем. физ. 2003. Т.43. 6. С.818-829.
  4. Гаранжа В.А., Замарашкин Н.Л. Пространственные квазиизометричные отображения как решения задачи минимизации поливыпуклого функционала // Ж. вычисл. матем. и матем. физ. 2003. Т.43. 3, С.854-865.
  5. Гаранжа В.А., Капорин И.Е. О сходимости градиентного метода минимизации функционалов теории упругости с конечными деформациями и барьерных сеточных функционалов // Ж. вычисл. матем. и матем. физ. 2005. Т.45. 8. С.1450-1465.
  6. Гаранжа В.А. Теоремы существования и обратимости для вариационного построения квазиизометричных отображений со свободными границами // Ж. вычисл. матем. и матем. физ. 2005. Т.45. 3. С.484-494.
  7. Гаранжа В.А. Поливыпуклые потенциалы, обратимые деформации и термодинамически согласованная запись уравнений нелинейной теории упругости // Ж. вычисл. матем. и матем. физ. 2010. Т.50. 9. C.1-29.
  8. Garanzha V.A. Barrier variational generation of quasi-isometric grids // Num. Linear Algebra Appl. 2001. V.8. 5. P.329-353.
  9. Branets L.V., Garanzha V.A. Distortion measure for trilinear mapping. Application to 3-D grid generation // Num. Linear Algebra Appl. 2002. V.9. 6-7. P.511-526.
  10. Garanzha V.A. Maximum norm optimization of quasi-isometric mappings // Num. Linear Algebra Appl. 2002. V.9 6-7. P.493-510.
  11. Garanzha V.A. Variational principles in grid generation and geometric modeling: theoretical justifications and open problems // Num. Linear Algebra Appl. 2004. V.11. P. 535-563.
  12. Garanzha V.A., Kaporin I.E., Konshin I.N. Truncated Newton type solver with application to grid untangling problem // Num. Linear Algebra Appl. 2004. V.11, 5-6. P.525-533.
  13. Garanzha V.A. Quasi-isometric surface parameterization // Appl. Num. Math. 2005. V.55. 3. P.295-311.
  14. Garanzha V.A. Computation of discrete curvatures based on polar polyhedra theory. Proceedings of International Conference "Numerical geometry, grid generation and scientific computing", Moscow, 10-13 June 2008, M.: Folium, 2008. P.182-189.
  15. Garanzha V.A. Approximation of the curvature of Alexandrov surfaces using dual polyhedra // Rus. J. Numer. Analys. Modeling. 2009. V.24. 5. P.409-423.
  16. Garanzha V.A. Discrete extrinsic curvatures and approximation of surfaces by polar polyhedra // Ж. вычисл. матем. и матем. физ. 2010. Т.50. 1. С.71-98.