Журнал вычислительной математики и математической физики, 2019, T. 59, № 12, стр. 2024-2044

Построение гибридных расчетных сеток вороного. алгоритмы и нерешенные проблемы

В. А. Гаранжа^1, 2, *, Л. Н. Кудрявцева^1, 2, 3, В. О. Цветкова³

¹ ВЦ ФИЦ ИУ РАН
119333 Москва, ул. Вавилова, 40, Россия

² МФТИ
141701 Долгопрудный, М.о., Институтский пер., 9, Россия

³ ИПМ им. Келдыша
125047 Москва, Миусская пл., 4, Россия

^* E-mail: garan@ccas.ru

Поступила в редакцию 26.06.2019
После доработки 26.06.2019
Принята к публикации 05.08.2019

DOI: 10.1134/S004446691912007X

Полный текст (PDF)

Аннотация

Рассмотрена задача построения расчетной сетки Вороного, в которой строится объединение ячеек Вороного, аппроксимирующее область с кусочно-гладкой границей. В двумерном случае гладкие участки границы приближаются ребрами Вороного, а в острые граничные вершины помещаются вершины Вороного. Для построения такой сетки предложен алгоритм самоорганизации, который покрывает границу области почти структурированной полосой многоугольных ячеек Делоне. Эта полоса состоит из четырехугольников Делоне на гладких участках и из выпуклых многоугольников вокруг вершин острых углов. В целом сетка Вороного является гибридной и состоит из достаточно округлых выпуклых многоугольников в ядре области и из ортогональных сеточных слоев вблизи границы. В работе предложены схемы доразбиения пристеночных слоев Вороного, в том числе около острых углов. В самом простом случае, когда граница области задается явно как набор параметризованных кривых, а не как изолиния неявной функции, предложен алгоритм построения сеток Вороного, основанный на покрытии границы области кругами. Рассматриваются проблемы, связанные с обобщением предложенного алгоритма на трехмерный случай. Идеи этого алгоритма и возникающие проблемы проиллюстрированы на примере простых трехмерных тестовых задач. Библ. 19. Фиг. 33.

Ключевые слова: сетки Делоне–Вороного, ортогональные слои Вороного, многоугольные сетки, полиэдральные сетки.

1. ВВЕДЕНИЕ

Построение гибридно-полидральных сеток в тремерных областях сложной формы – это активно развивающийся раздел вычислительной математики и численной геометрии. Достаточно хорошо проработаны алгоритмы, основанные на предварительном построении тетраэдральной сетки и на ее приближенной дуализации [1], [2]. Подавляющее большинство полиэдральных ячеек сетки при использовании таких алгоритмов обладают высоким качеством. Для оценки качества используют такие критерии, как округлость ячеек, степень центроидальности (близости центра ячейки и центра ее тяжести ), мера неплоскости граней, мера неортогональности грани и двойственного ей ребра, мера уклонения точки пересечения плоскости грани и двойственной вершины от идеального положения. С точки зрения таких критериев идеальной ячейкой является округлая центроидальная ячейка Вороного. Однако в указанных выше алгоритмах возникает заметное количество усеченных приграничных ячеек, качество которых совершенно неудовлетворительно. Эти ячейки нуждаются в дополнительной оптимизации, причем с учетом того, что критерии оптимальности во многом противоречивы, приходится использовать методы многокритериальной оптимизации с непредсказуемым результатом. Можно предположить, что построение неусеченных ячеек Вороного вблизи границы и является тем самым искомым квазиоптимальным решением. Нам неизвестны публикации с описанием подобных алгоритмов. Таким образом, цель работы состоит в том, чтобы построить алгоритм, который решает эту задачу в двумерном случае, по крайней мере в практическом смысле, и рассмотреть пути ее решения и возникающие проблемы в трехмерном случае. Представленная статья – это расширенная версия работы из трудов конференции [3].

Заметим, что задача аппроксимации областей при помощи диаграмм Вороного и их обобщений имеет достаточно богатую историю, особенно в контексте задач реконструкции поверхности [4]. Для построения и оптимизации сеток Вороного было предложено большое число алгоритмов, в частности [5], [7]–[9]. Однако эти алгоритмы не годятся для построения регулярных сеточных слоев Вороного около границ, что и является предметом данной работы.

1.1. Неявное задание мультиматериальной области

Рассмотрим ограниченную область $\Omega $, которая разбита на $N$ подобластей ${{\Omega }_{i}}$, $i = 0,\; \ldots ,\;N - 1$. Интуитивно можно представить себе тело, склеенное из различных материалов. Мы предполагаем, что граница каждой подобласти кусочно-гладкая и непрерывная по Липшицу. Простейший случай такой области основан на двух предположениях: а) граница каждой подобласти – это многообразие, б) отсутствуют мультиматериальные вершины, лежащие на границе более чем двух материалов. Пример такой области показан на фиг. 1а.

Фиг. 1.

Примеры мультиматериальных областей.

Задача построения расчетной сетки в такой мультиматериальной области эквивалентна задаче построения сетки в биматериальной области, показанной на фиг. 1б. Такую область можно моделировать скалярной неявной функцией $u(x):{{\mathbb{R}}^{d}} \to \mathbb{R}$, которая отрицательна в одном материале, т.е. внутри ${{\Omega }_{1}}$, положительная в другом, т.е. в ${{\Omega }_{0}}$, и нулевая изолиния этой функции задает границу области. При этом удобно погружать расчетную область в область простой формы, аппроксимация границы которой не нужна.

Пример более сложной области показан на фиг. 1в. Здесь показаны две мультиматериальных вершины $A$, $B$ и нелипшицева вершина $C$. Алгоритм построения сеток, описанный ниже, потенциально может быть применен и в этом случае, но таких тестов в работе не проводилось.

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

Предполагается, что функция $u(x)$ – кусочно-гладкая, непрерывна по Липшицу, и ее производные вдоль некоторого векторного поля, трансверсального к внутренней границе $\Gamma $, не равны нулю в некотором конечном слое около границы. Предполагается, что норма величины $\nabla u(x)$, там где она определена, ограничена сверху и снизу в этом слое. Внешняя граница в данном случае не представляет интереса.

1.2. Расчетная сетка Вороного в неявной области

Рассмотрим плоскую сетку $\mathcal{D}$, состоящую из выпуклых многоугольников ${{D}_{i}}$, вписанных в круги ${{B}_{i}}$, как показано на фиг. 3б. Многогранник ${{D}_{i}}$ – выпуклая оболочка точек, лежащих на $\partial {{B}_{i}}$. Каждый круг является пустым в том смысле, что внутри него нет вершин сетки. Такая сетка называется сеткой Делоне или разбиением Делоне. Выпуклая оболочка всех центров ${{c}_{i}}$ кругов ${{B}_{i}}$, проходящих через вершину Делоне ${{p}_{k}}$, есть ячейка Вороного ${{V}_{k}}$. Множество ячеек Вороного составляет разбиение, которое в англоязычной литературе называют диаграммой Вороного. Поскольку в нашем подходе внешняя граница объемлющей области не представляет интереса, мы удаляем все неограниченные ячейки Вороного. Полученный объект будем называть сеткой Вороного. Внутренние границы можно аппроксимировать ребрами Делоне, как показано на фиг. 3а, либо ребрами Вороного, как показано на фиг. 3б.

Фиг. 2.

Модель “колесо” построена из примитивов посредством булевых операций.

Фиг. 3.

а – Граница области приближается ребрами Делоне, б – границы области приближаются ребрами Вороного.

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

Типичная структура сетки Делоне-Вороного вокруг острой вершины показана на фиг. 4. Регулярные полосы Делоне, составленные из четырехугольников, стыкуются через выпуклые многоугольные ячейки Делоне вокруг острых вершин. Количество вершин этого многоугольника определяется углом излома при вершине.

Фиг. 4.

Полоса многоугольных ячеек Делоне и двойственных ребер Вороного на границе области.

2. АЛГОРИТМ ПОСТРОЕНИЯ СЕТОК ВОРОНОГО, ОСНОВАННЫЙ НА ПРИНЦИПЕ САМООРГАНИЗАЦИИ УПРУГОЙ СЕТИ

Для построения разбиений Вороного в областях с негладкой границей была использована адаптация алгоритма [11], который изначально разрабатывался для построения сеток Делоне в двумерных и трехмерных областях с кусочно-гладкой границей. Неизвестными величинами в представленном алгоритме выступают вершины сетки Делоне, которые рассматриваются как система материальных точек, отталкивающих друг друга, и тем самым моделирующих упругую среду. Расталкивающие силы действуют на пары вершин, соединенных ребрами Делоне, т.е. ребрами с описанными кругами, не содержащими других вершин. Каждое ребро Делоне представимо в виде упругой распорки заданной длины. На каждом шаге строится дуальная сетка Вороного и разделяется на две подобласти в соответствии со значением неявной функции в вершинах Делоне. Сетка Делоне разделяется на три подобласти: подобласть $0$, подобласть $1$, и слой, покрывающий границу. Все треугольники Делоне с центрами описанных окружностей, близких к $\Gamma $, добавляются в слой. Конструируется ломаная, аппроксимирующая границу сетки Вороного. Далее, после достижения локального минимума энергии применяется дополнительное разбиение. Целью данного разбиения является попытка устранения длинных ребер Вороного, неортогональных границе. Эта идея объяснена на фиг. 5.

Фиг. 5.

а – Фрагмент сетки Вороного с неортогональными ребрами, б – корректная связность достигается добавлением новых вершин Делоне.

С каждым ребром Вороного ассоциированы обостряющая энергия и граничный потенциал притяжения. Граничный потенциал притяжения используется в качестве штрафного члена для условия того, что каждое граничное ребро Вороного тангенциально $\Gamma $ и касается ее в определенной точке касания. Энергия обострения достигает минимума, когда граничное ребро Вороного $e$ ортогонально вектору $\nabla u$ в точке касания ребра. Для одного шага минимизации полной энергии используется специальный вариант предобусловленного градиентного спуска. Удобно называть векторы направления минимизации упругими силами, хотя физического смысла они, конечно, не несут. Если под воздействием упругих сил ребро утрачивает свойство Делоне, это ребро должно быть исключено из набора распорок, и список ребер Делоне должен быть перестроен. Следовательно, сетка Вороного также должна быть перестроена. Эти шаги повторяются до тех пор, пока граница не оказывается аппроксимирована с достаточной точностью, а корректная связность приграничных слоев не выстроена. Результат этого алгоритма – это некоторая равновесная сетка, где суммарное воздействие расталкивающих сил на каждую вершину равно нулю. Как предложено в [10], ребра равновесной сетки в среднем слегка сжаты.

2.1. Упругий потенциал

Предположим, что задана система вершин $\mathcal{E} = {\text{\{ }}{{p}_{1}},{{p}_{2}},\; \ldots ,\;{{p}_{n}}{\text{\} }}$ в ${{\mathbb{R}}^{2}}$. Триангуляция Делоне этой системы обозначается через $\mathcal{T}(\mathcal{E})$. Пусть ${{\mathcal{T}}_{e}}$ – множество ребер триангуляции, а ${{\mathfrak{F}}_{b}}$ – множество ребер Делоне, пересекающих $\Gamma $. Все вершины составляют матрицу $P$ размерности $2 \times n$, где $i$-й столбец соответствует вектору ${{p}_{i}}$. Обозначим через ${{P}_{\Gamma }}$ множество приграничных вершин Делоне. Разбиение Вороного, дуальное к $\mathcal{T}$, обозначим через $\mathcal{V}$, а множество ребер Вороного, формирующих ломаную, задающую текущее приближение к $\Gamma $, через ${{\mathcal{E}}_{{v}}}$.

С сеткой $\mathcal{T}$ ассоциирован упругий потенциал вида

(1)

$W(P) = {{\theta }_{r}}{{W}_{r}}(P) + {{\theta }_{s}}{{W}_{s}}(P) + {{\theta }_{a}}{{W}_{a}}(P),$

где ${{W}_{r}}(P)$ – потенциал расталкивания, ${{W}_{s}}(P)$ – потенциал обострения, который позволяет выстраивать граничные ребра Вороного вдоль изолинии функции $u$, а ${{W}_{a}}(P)$ – потенциал притяжения к границе.

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

${{W}_{r}}(P) = \sum\limits_{e \in {{\mathcal{T}}_{e}}} {{{w}_{r}}(e)} ,$

${{w}_{r}}(e) = \left\{ \begin{gathered} L_{0}^{2}\left( {\frac{L}{{{{L}_{0}}}} - 1 - log\left( {\frac{L}{{{{L}_{0}}}}} \right)} \right),\quad L < {{L}_{0}}, \hfill \\ 0,\quad L \geqslant {{L}_{0}}, \hfill \\ \end{gathered} \right.$

где

$L = \left| {{{p}_{i}} - {{p}_{j}}} \right|,$

длина ребра $e$, а ${{L}_{0}}(e)$ – целевая длина этого ребра, определенная как

${{L}_{0}}(e) = Mh\left( {\frac{1}{2}({{p}_{i}} + {{p}_{j}})} \right).$

В этой формуле $h( \cdot )$ – функция относительного размера, которая является безразмерной, а скалярный множитель $M$ задает характерную длину. Как было предложено в [10], параметр $M$ определяется как средняя длина сеточного ребра и может незначительно меняться в процессе самоорганизации сетки.

На практике используется ${{L}_{0}}(e) = M\tfrac{1}{2}(h({{p}_{i}}) + h({{p}_{j}}))$, чтобы уменьшить число вызовов функции размера.

Обостряющий функционал записывается следующим образом:

${{W}_{s}}(P) = \sum\limits_{{{e}_{{v}}} \in {{\mathcal{E}}_{{v}}}} {{{w}_{s}}({{e}_{{v}}}),} $

где вклад граничного ребра Вороного ${{e}_{{v}}}$ с вершинами ${{c}_{1}}$, ${{c}_{2}}$ имеет вид

${{w}_{s}}({{e}_{{v}}}) = \frac{1}{2}\left| {{{c}_{1}} - {{c}_{2}}} \right|{{({{n}^{{\text{т}}}}({{c}_{2}} - {{c}_{1}}))}^{2}},$

где

(2)

$n = \frac{1}{{\left| {\nabla u({v}{\kern 1pt} *)} \right|}}\nabla u({v}{\kern 1pt} *),$

и ${v}{\kern 1pt} {\text{*}}$ – текущая аппроксимация точки касания границы для ребра Вороного ${{e}_{{v}}}$. Наиболее простым выбором ${v}{\kern 1pt} {\text{*}}$ является проекция средней точки

$c = \frac{1}{2}({{c}_{1}} + {{c}_{2}})$

ребра ${{e}_{{v}}}$ на $\Gamma $.

Член, отвечающий за притяжение коротких ребер, записывается как

${{W}_{a}}(P) = \sum\limits_{{{e}_{{v}}} \in {{\mathcal{E}}_{{v}}}} {{{w}_{a}}({{e}_{{v}}})} ,$

где

${{w}_{a}}({{e}_{{v}}}) = \frac{1}{2}\mathop {\left( {\frac{{{{L}_{0}}}}{L}} \right)}\nolimits^2 {{u}^{2}}(c).$

Здесь $L$ – длина ребра Делоне, дуального к ${{e}_{{v}}}$. Таким образом, энергия, соответствующая более коротким ребрам Делоне, больше. Тогда неустойчивые ребра Делоне, которые триангулируют предположительные граничные многоугольники Делоне, как правило длиннее,чем устойчивые ребра, а значит, дают меньший вклад в общую энергию и мало влияют на положение вершин.

2.2. Упругие силы и итерационный алгоритм

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

Эти “силы” вводятся следующим образом:

(3)

$\begin{gathered} \delta p_{i}^{k} = - \frac{{{{\theta }_{r}}}}{{\mathop {{{d}_{r}}}\nolimits_i^k }}\frac{{\partial {{W}_{r}}}}{{\partial {{p}_{i}}}}({{P}^{k}}) - \frac{{{{\theta }_{s}}}}{{\mathop {{{d}_{s}}}\nolimits_i^k }}\frac{{\partial {{W}_{s}}}}{{\partial {{p}_{i}}}}({{P}^{k}}) - \frac{{{{\theta }_{a}}}}{{\mathop {{{d}_{a}}}\nolimits_i^k }}\frac{{\partial {{W}_{a}}}}{{\partial {{p}_{i}}}}({{P}^{k}}) = \\ = \;{{F}_{r}}(p_{i}^{k}) + {{F}_{s}}(p_{i}^{k}) + {{F}_{a}}(p_{i}^{k}), \\ \end{gathered} $

здесь $k$ – номер итерации, ${{p}_{i}}$ есть $i$-я вершина в сетке Делоне ${{P}^{k}}$, $\mathop {{{d}_{r}}}\nolimits_i^k $, $\mathop {{{d}_{s}}}\nolimits_i^k $, $\mathop {{{d}_{a}}}\nolimits_i^k $ – весовые коэффициенты.

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

Для того, чтобы представить точную формулу расчета сил, необходимо ввести следующие обозначения: ${\text{sta}}{{{\text{r}}}_{e}}({{p}_{i}})$ обозначает множество сеточных ребер, выходящих из вершины ${{p}_{i}}$, а ${\text{star}}({{p}_{i}})$ – множество всех вершин этих ребер за исключением ${{p}_{i}}$. Во всех случаях предполагается, что граничная звезда упорядочена, т.е. ее вершины пронумерованы против часовой стрелки относительно ${{p}_{i}}$, если смотреть снаружи области. Далее верхний индекс $k$ опускается.

Для внутренней вершины ${{p}_{i}}$ – сила расталкивания – запишется в виде

${{F}_{r}}({{p}_{i}}) = - \frac{{{{\theta }_{r}}}}{{{{d}_{i}}}}\sum\limits_{{{p}_{j}} \in {\text{star}}\,{{p}_{i}}} {{{\phi }_{r}}} ({{p}_{i}},{{p}_{j}})({{p}_{i}} - {{p}_{j}}),\quad \mathop {{{d}_{r}}}\nolimits_i = \sum\limits_{{{p}_{j}} \in {\text{star}}\,{{p}_{i}}} {{{\phi }_{r}}({{p}_{i}},{{p}_{j}})} ,$

где

${{\varphi }_{r}}({{p}_{i}},{{p}_{j}}) = \left( {\frac{{{{L}_{0}}}}{L} - 1} \right)\frac{{{{L}_{0}}}}{L},\quad L = \left| {{{p}_{i}} - {{p}_{j}}} \right|,\quad {{L}_{0}} = Mh\left( {\frac{1}{2}({{p}_{i}} + {{p}_{j}})} \right).$

Обостряющая сила представляется следующим образом:

${{F}_{s}}({{p}_{i}}) = - \frac{{\sum\limits_{{{e}_{v}}:{{p}_{i}} \in {\text{dual}}{{e}_{v}}} {{{\Pi }_{r}}} (q\left| {{{c}_{1}} - {{c}_{2}}} \right|{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}}))}}{{\sum\limits_{{{e}_{v}}:{{p}_{i}} \in {\text{dual}}{{e}_{v}}} {\left| {{{c}_{1}} - {{c}_{2}}} \right|} {{{\left| q \right|}}^{2}}}},$

здесь ${{c}_{1}}$, ${{c}_{2}}$ – вершины ребра ${{e}_{{v}}}$, $c = \tfrac{1}{2}({{c}_{1}} + {{c}_{2}})$, вектор $n$ определен в (2), и

$q = {{({{C}_{2}} - {{C}_{1}})}^{{\text{т}}}}n,\quad {{C}_{1}} = \frac{{\partial {{c}_{1}}}}{{\partial {{p}_{i}}}},\quad {{C}_{2}} = \frac{{\partial {{c}_{2}}}}{{\partial {{p}_{i}}}}.$

Чтобы записать выражение для матрицы ${{C}_{1}}$, рассматривается треугольник Делоне ${{T}_{1}}$, где вершины ${{p}_{i}}$, ${{p}_{j}}$, ${{p}_{k}}$ упорядочены против часовой стрелки, а ${{c}_{1}}$ – центр описанной окружности треугольника ${{T}_{1}}$. Тогда имеем

$C_{1}^{{\text{т}}} = ({{c}_{1}} - {{p}_{i}}{{c}_{1}} - {{p}_{i}}){{({{p}_{j}} - {{p}_{i}}{{p}_{k}} - {{p}_{i}})}^{{ - 1}}}.$

Формула для ${{C}_{2}}$ аналогична.

Нелинейный оператор ${{\Pi }_{r}}$ отвечает за взаимодействие между силами расталкивания и силами обострения.

Рассмотрим вклад в ${{F}_{s}}({{p}_{i}})$ от ребра Вороного ${{e}_{{v}}}$. Введем обозначение $e = ({{p}_{j}} - {{p}_{i}}){\text{/}}\left| {{{p}_{j}} - {{p}_{i}}} \right|$, где ${{p}_{i}}$, ${{p}_{j}}$ – вершины ребра Делоне, дуального к ${{e}_{{v}}}$. Если

${{e}^{{\text{т}}}}{{F}_{r}}({{p}_{i}}){{e}^{{\text{т}}}}q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}}) < 0,$

тогда

${{\Pi }_{r}}(q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}})) = q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}}) - e{{e}^{{\text{т}}}}q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}})$

иначе

${{\Pi }_{r}}(q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}})) = q{{n}^{{\text{т}}}}({{c}_{1}} - {{c}_{2}}).$

После локальной коррекции членов обострения результирующая сила обострения, действующая на вершину ${{p}_{i}}$, используется для коррекции силы расталкивания ${{F}_{r}}$:

${{F}_{r}} \leftarrow {{F}_{r}} - \frac{1}{{2{{{\left| {{{F}_{s}}} \right|}}^{2}}}}{{F}_{s}}\left( {F_{s}^{{\text{т}}}{{F}_{r}} - \left| {F_{s}^{{\text{т}}}{{F}_{r}}} \right|} \right).$

Сила притяжения записывается в виде

${{F}_{a}}({{p}_{i}}) = - \sum\limits_{{{e}_{v}}:{{p}_{i}} \in {\text{dual}}{{e}_{v}}} {\frac{1}{2}} \mathop {\left( {\frac{{{{L}_{0}}}}{L}} \right)}\nolimits^2 u(c){{({{C}_{1}} + {{C}_{2}})}^{{\text{т}}}}\frac{{\nabla u(c)}}{{\left| {\nabla u(c)} \right|}}.$

Сдвиг вершин Делоне проходит в два шага. Первый шаг записывается в виде

$\mathop {\tilde {p}}\nolimits_i^0 = p_{i}^{k} + {{w}_{r}}{{\tau }_{r}}{{F}_{r}} + {{w}_{s}}{{\tau }_{s}}{{F}_{s}},\quad {{w}_{r}} = \frac{1}{{20}},\quad {{w}_{s}} = \frac{1}{2},$

${{\tau }_{r}} = min\left( {1,\frac{{{{L}_{0}}}}{{5{{w}_{r}}{{F}_{r}}}}} \right),\quad {{\tau }_{s}} = min\left( {1,\frac{{{{L}_{0}}}}{{5{{w}_{s}}{{F}_{s}}}}} \right).$

После этого сдвига добавляются $M$ итераций, используя силы притяжения, для проекции ребер Вороного на границу

$\tilde {p}_{i}^{{m + 1}} = \mathop {\tilde {p}}\nolimits_i^m + {{\tau }_{a}}{{F}_{a}}(\mathop {\tilde {p}}\nolimits_m^l ),\quad {{\tau }_{a}} = \frac{1}{{10}}.$

И, наконец,

$p_{i}^{{k + 1}} = \mathop {\tilde {p}}\nolimits_i^M .$

2.3. Численные эксперименты

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

Численные эксперименты показали, что алгоритм приближенно восстанавливает границы области за несколько итераций. Однако это приближение содержит дефекты аппроксимации и топологические ошибки, когда приграничные ребра Вороного не ортогональны границе. Причина этих ошибок проста: у вершины Делоне нет соответствующей зеркальной вершины с другой стороны границы. Таким образом, топологические ошибки могут быть устранены добавлением новых вершин Делоне, как показано на фиг. 5. Рассматривается многоугольник $P$, наилучшим образом приближающий многоугольник Делоне, построенный на двух устойчивых ребрах Делоне ${{e}_{1}}$ и ${{e}_{2}}$, пересекающих границу. На этих двух ребрах строится четырехугольная ячейка, и в середины виртуальных противоположных ребер добавляются новые вершины.

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

Фиг. 6 иллюстрирует процесс изменения сетки Вороного для увеличенного фрагмента модели Колесо.

Фиг. 6.

Фрагмент начальной сетки Вороного, результат после нескольких итераций и устойчивая сетка Вороного.

Фиг. 7 и 8 демонстрируют, что удаление коротких ребер Вороного не приводит к ухудшению качества аппроксимации границы. На этом этапе близкие круги Делоне склеиваются, а новое расположение вершин Делоне находится как пересечение откорректированных кругов Делоне. Можно назвать короткие граничные ребра Вороного с плохой ориентацией “сбросами Вороного” по аналогии с геологическим термином. После исключения сбросов получается окончательная сетка, где внутренние границы аппроксимированы ребрами Вороного, а нормали к границе аппроксимированы дискретными нормалями.

Фиг. 7.

Исключение сбросов Вороного (увеличенный вид).

Фиг. 8.

Исключение сбросов Вороного (увеличенный вид).

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

Фиг. 9.

а – Сетка Вороного до коррекции угловых многоугольников, в – сетка Вороного после коррекции угловых многоугольников, б – наложение сеток.

На фиг. 10б показан фрагмент конечной сетки Вороного с граничными кругами Делоне, а справа представлен слой ячеек Делоне.

Фиг. 10.

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

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

• новые пары вершин добавляются симметрично на каждом ребре Делоне, пересекающем границу;

• для угловых многоугольников Делоне применяются специальные схемы разбиения;

• строятся новые ячейки Вороного, граничные ребра Вороного проецируются на границу;

• эта процедура доразбиения, направленная вовнутрь, повторяется до тех пор, пока не будет достигнуто требуемое сгущение сетки;

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

• около изломов границы применяется процедура склеивания кругов Делоне с ограничениями.

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

Детализированный вид доразбитой сетки приведен на фиг. 11–13 .

Фиг. 11.

а – Анизотропный слой сетки Вороного, в – дуальная анизотропная сетка Делоне слоя, б – наложение сеток.

Фиг. 12.

Схема разбиения углового треугольника Делоне: а – анизотропный слой сетки Вороного, в – дуальная анизотропная сетка Делоне слоя, б – наложение сеток.

Фиг. 13.

Схема разбиения углового многоугольника Делоне: а – анизотропный слой сетки Вороного, в – дуальная анизотропная сетка Делоне слоя, б – наложение сеток.

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

На фиг. 14 показан большой фрагмент гибридной сетки Вороного до и после исключения сбросов.

Фиг. 14.

Сетка Вороного после разбиения и после коррекции.

Следует заметить, что схемы доразбиения для угловых многоугольников Делоне, показанные на фиг. 12, а также для угловых треугольников (см. фиг. 13), создают “пузыри” вокруг вершин углов на сетке Вороного. Схему анизотропного доразбиения Делоне/Вороного, которая могла бы избежать таких пузырей, избегая доразбиения по всем направлениям сразу, построить не удалось. Можно отметить, что такая проблема характерна только для ячеек Вороного, в то время как ребра Делоне гладко и плавно скругляют острый угол. Фиг. 15, 16 иллюстрируют поведение схем разбиения, изотропных около угла. Здесь сбросы Вороного не исключены для того, чтобы показать отклонения от структурированной сетки, привнесенные схемой разбиения. Заметим, что при такой схеме доразбиения для получения конечной сетки требуется достичь плавного перехода от вершины каждого угла к основной сетке Вороного.

Фиг. 15.

а – Сетка Делоне после изотропного разбиения, процедура удаления сбросов Вороного не применена, б – сетка Вороного.

Фиг. 16.

а – Сетка Делоне после разбиения, процедура удаления сбросов Вороного не применена, б – сетка Вороного.

Подобные схемы разбиения треугольников, четырехугольников и пятиугольников Делоне идейно очень близки к известным схемам измельчения блочно-структурированных сеток, когда блоки склеены между собой с использованием хорошо известных топологических типов “C” или “H”.

3. ПОСТРОЕНИЕ СЕТОК ВОРОНОГО ПРИ ПОМОЩИ ЗАДАНИЯ СИСТЕМЫ КРУГОВ

Когда граница расчетной области задается в явном виде как набор параметризованных кривых, можно использовать следующий простой и эффективный алгоритм построения сетки Вороного. Рассмотрим упрощенную тестовую задачу, в которой внутренняя граница – это замкнутый контур, который приближенно задается набором последовательных вершин ${{p}_{i}}$. Присвоим $i$-й вершине контура круг ${{B}_{i}}$ с радиусом ${{r}_{i}}$, заданным формулой

(4)

${{r}_{i}} = \frac{1}{{2\sqrt 2 }}\left( {\left| {{{p}_{i}} - {{p}_{{i - 1}}}} \right| + \left| {{{p}_{i}} - {{p}_{{i + 1}}}} \right|} \right).$

Для гладкого контура система кругом считается корректной, если круг ${{B}_{i}}$ пересекает только смежные круги ${{B}_{{i - 1}}}$ и ${{B}_{{i + 1}}}$. Этот набор кругов определяет полосу четырехугольных ячеек Делоне, покрывающих контур. Для прямолинейного участка границы и равномерного распределения центров кругов выпуклая оболочка точек пересечения на каждом круге – это квадрат.

Фигура 17а показывает контур морского конька, который использовался в работе [6] как тестовая задача для алгоритма построения сеток Вороного. На фиг. 17б показан начальный набор кругов. Как можно убедиться, есть много некорректных пересечений кругов.

Фиг. 17.

а – Контур морского конька, б – начальный набор кругов.

Для исправления размещения кругов используется следующий алгоритм оптимизации. Определяются все пары пересекающихся несмежных кругов. Заметим, что если один круг находится внутри другого, гарантируется, что эти круги имеют несмежные пересечения. Для каждой пары плохих кругов наибольший “разбивается”, т.е. заменяется парой кругов меньшего размера. Пусть ${{B}_{i}}$ – это круг, помеченный для разбиения. Вершина ${{p}_{i}}$ удаляется и заменяется двумя новыми вершинами $a$ и $b$ с координатами

$a = \frac{1}{3}{{p}_{{i - 1}}} + \frac{2}{3}{{p}_{i}},\quad a = \frac{1}{3}{{p}_{{i + 1}}} + \frac{2}{3}{{p}_{i}}.$

Радиусы новых кругов ${{B}_{a}}$ и ${{B}_{b}}$ определяются общей формулой (4). Затем положения вершин на контуре слегка сглаживаются при помощи нескольких итераций сглаживания по Лапласу вдоль длины дуги контура. Процедура разбиения/сглаживания повторяется до тех пор, пока не будут удалены все некорректные пересечения кругов.

Результаты работы описанного алгоритма показаны на фиг. 18. Увеличенный фрагмент сетки для тестовой задачи показан на фиг. 19. Заметим, что побочным эффектом данного алгоритма является адаптация размещения кругов к кривизне контура.

Фиг. 18.

а – Начальное покрытие кругами, б – исправленный набор кругов.

Фиг. 19.

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

Для того, чтобы построить корректную двумерную сетку Вороного, достаточно распределить вершины Делоне по расчетной области, и выбросить те из них, которые попали в систему кругов ${{B}_{i}}$. Добавляя к этому набору точки пересечения кругов, мы получаем начальный набор вершин. Сетка Делоне, построенная на этом наборе вершин, будет содержать слой, покрывающий границу, и ребра Вороного будут соединять центры последовательных кругов. Построенная сетка показана на фиг. 20а. В этом примере фоновая сетка Вороного – это просто декартова сетка.

Фиг. 20.

а – Начальная сетка Вороного, б – сетка после оптимизации.

Начальная сетка оптимизируется согласно следующим критериям: а) все треугольники Делоне должны иметь достаточно хорошую форму, б) ячейки Вороного должны быть близки к центроидальным. В частности, мы требуем, чтобы для каждого треугольника Делоне отношение радиуса описанного круга к длине минимального ребра было бы меньше $\sqrt 2 $, и центр масс каждой ячейки Вороного близок к ее генератору (вершине Делоне). Для исправления форм треугольников Делоне мы используем вариант доразбиения сетки Делоне, напоминающий алгоритм Рупперта [19] с несколькими промежуточными шагами алгоритма Ллойда [18], который итеративно смещает каждую вершину Делоне в центр масс своей ячейки Вороного и используется для исправления формы ячеек Вороного.

Согласно логике алгоритма Рупперта, на каждом шаге создается список вершин-кандидатов на добавление в сетку Делоне. Этот список содержит все центры описанных кругов треугольников плохой формы, исключая те центры, которые попали в систему кругов, покрывающих границу. Если центр описанного круга треугольника оказывается внутри защитного круга ${{B}_{i}}$, то этот круг помечается для разбиения. После добавления всех новых вершин на границу и внутрь области, применяется алгоритм сглаживания по Лапласу для системы граничных кругов. Строится сетка Вороного, и к ней применяется несколько итераций метода Ллойда с ограничениями, которые возникают из-за наличия граничных защитных кругов. Любая вершина Делоне, смещенная внутрь защитного круга, удаляется. Таким образом, аппроксимация границы не разрушается.

Фигура 21 показывает, что структурированный слой Делоне корректно адаптируется к кривизне границы. Фигура 22 иллюстрирует способность представленного алгоритма построения сетки Вороного получать результаты высокого качества.

Фиг. 21.

а – Фрагмент начальной сетки Вороного, б – фрагмент сетки после оптимизации.

Фиг. 22.

Фрагмент конечной сетки Вороного со структурированным слоем Делоне, покрывающим границу.

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

Заметим, что в представленном варианте алгоритма мы ставим вершины Вороного на границу области. Другой вариант алгоритма основан на двойственной аппроксимации границы, когда ребро Вороного касается контура в точке пересечения с двойственным ребром Делоне.

4. ОБСУЖДЕНИЕ АЛГОРИТМА ПОСТРОЕНИЯ ТРЕХМЕРНЫХ СЕТОК ВОРОНОГО

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

На первый взгляд, обобщение алгоритма построения сеток Вороного на трехмерный случай очевидно. Рассмотрим мультиматериальную область с кусочно-гладкой внутренней границей. Обработка острых ребер на поверхности интуитивно очевидна: на каждом остром ребре можно построить набор шаров с центрами на ребре так, что каждый шар пересекает только два смежных шара, и пересечение является мелким в том смысле, что угол пересечения меньше $\pi {\text{/}}2$. Можно создать наборы призм Делоне, покрывающих ребра, посредством размещения по крайней мере трех вершин Делоне на каждом круге, который является пересечением двух смежных шаров. Вокруг конических вершин, в том числе тех, где сходятся острые ребра, необходимо ставить шары и строить отдельные многогранники Делоне. Также отдельный шар и многогранник Делоне необходимо строить вокруг точки на остром ребре там, где должен меняться тип призм Делоне.

Фигура 23а показывает набор защитных шаров около острых ребер и конических вершин для простой области с кусочно-линейной границей.

Фиг. 23.

а – Шары Делоне и грани Делоне, двойственные острым граничным ребрам Вороного, б – шары Делоне, покрывающие границу области.

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

На фиг. 24 показана граница области, составленная из граней Вороного и трехмерная сетка Вороного.

Фиг. 24.

Граница из граней Вороного и разрез сетки Вороного.

К сожалению, в общем случае задачу построения сетки Вороного нельзя считать решенной ни с теоретической, ни с практической точки зрения. Она тесно связана с задачей приближения кусочно-гладких поверхностей полиэдральными поверхностями. Для решения задачи приближения было предложено много алгоритмов, которые можно отнести к классу “двойственных”, поскольку в них поверхности локально аппроксимируются гранями, двойственными либо определенным ребрам, либо вершинам. Двойственные методы очень удобны для аппроксимации кусочно-гладких поверхностей. Среди этого класса методов хорошо известны такие методы, как “метод двойственных контуров” [16], а также прямо-двойственный алгоритм оптимизации поверхностной сетки с обострением [17]. Двойственные грани в этих алгоритмах могут быть неплоскими. В алгоритме, предложенном в [12], достаточно общие поверхности приближаются полиэдральными поверхностями. Плоские грани этих поверхностей могут быть невыпуклыми. В работе [13] прямая и двойственная аппроксимации поверхности комбинируются для построения дискретного аналога сферического отображения и его градиента. В этой работе показано, что поведение двойственных граней для поверхностей положительной гауссовой кривизны ($K > 0$), и отрицательной гауссовой кривизны ($K < 0$) принципиально разное. Рассмотрим поверхностную триангуляцию, вершины которой лежат на регулярной поверхности строго положительной кривизны. Предполагается, что триангуляция регулярна в том смысле, что она задает строго выпуклую поверхность, как показано на фиг. 25а.

Фиг. 25.

Прямая (а) и двойственная (б) аппроксимация для выпуклой поверхности.

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

Фиг. 26.

Аппроксимация Вороного выпуклой поверхности и фрагмент наложенной двойственной поверхности и поверхности Вороного.

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

Фиг. 27.

Поверхность Вороного, интегрированная с трехмерной сеткой Вороного и ее увеличенный фрагмент.

Более сложная задача связана с седловыми поверхностями ($K < 0$). В работе [13] показано, что в случае, когда седловая поверхность аппроксимируется корректной седловой триангуляцией, то каждая регулярная двойственная грань в этом случае – это плоский четырехугольник, четыре стороны которого – это ломаные, выпуклые вовнутрь, как показано на фиг. 28.

Фиг. 28.

Прямая и двойственная полиэдральная аппроксимация седловой поверхности.

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

Фиг. 29.

а – Аппроксимация Вороного выпуклой поверхности, б – фрагмент наложенной двойственной поверхности и поверхности Вороного.

Фиг. 30 показывает, как поверхность Вороного интегрируется с трехмерной сеткой Вороного, и показаны увеличенные фрагменты этой сетки.

Фиг. 30.

Аппроксимация Вороного седловой поверхности и трехмерная сетка Вороного.

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

Заметим, что в случае, когда седловая поверхность аппроксимируется седловой триангуляцией, единственная возможность получить выпуклые двойственные грани – это построить двойственные четырехугольники с прямыми ребрами, что требует специального размещения порождающих вершин на поверхности. Фиг. 31а показывает двойственную сетку, которая состоит из плоских выпуклых четырехугольников (pq-сетка, “planar-quadrilateral mesh”, см. [15]).

Фиг. 31.

а – Двойственная сетка из плоских четырехугольников, б – поверхность Вороного, в – их наложение.

Прямая сетка в этом примере тоже является pq-сеткой, но ее четырехугольники заметно скошены, так что поверхность Вороного (фиг. 31б) сильно отличается от двойственной поверхности. Сбросы в этом примере нельзя удалить простым объединением близких шаров Делоне.

Потенциальный кандидат для построения поверхности Вороного без сбросов – это циркулярная pq-сетка [15], в которой каждая грань – это четырехугольник, вписанный в круг. Аппроксимации таких сеток могут быть построены на основе построения семейств линий кривизны. Фигура 32 показывает двойственную поверхность, состоящую из выпуклых четырехугольников, ребра которых аппроксимируют линии кривизны.

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

Фиг. 32.

Двойственная сетка, построенная на линиях кривизны, поверхность Вороного и их наложение.

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

Фиг. 33.

Поверхность Вороного, интегрированная в трехмерную сетку, и ее увеличенный фрагмент.

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

ЗАКЛЮЧЕНИЕ

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

Список литературы

Garimella R., Kim J., Berndt M. Polyhedral mesh generation and optimization for non-manifold domains // Proc. of the 22nd Internat. Meshing Roundtable. Springer, Cham. 2014. P. 313–330.
Lee S.Y. Polyhedral mesh generation and a treatise on concave geometrical edges // Procedia Engng. 2015. V. 124. P. 174–186.
Garanzha V.A., Kudryavtseva L.N., Tsvetkova V.O. Structured orthogonal near-boundary Voronoi mesh layers for planar domains // In: Lecture Notes in Computational Science and Engineering, V. 131 Numerical Geometry, Grid Generation and Scientific Computing. Eds. Garanzha V.A., Kamenski, Lennard, Si, Hang. Springer, 2019.
Amenta N., Bern M. Surface reconstruction by Voronoi filtering // Discrete Comput. Geometry. 1999. V. 22. № 4. P. 481–504.
Liu Y., Wang W., Levy B., Sun F., Yan D.M., Lu L., Yang C. On centroidal Voronoi tessellation – energy smoothness and fast computation // ACM Trans. Graphics. 2009. V. 28. № 4. P. 101.
Yan D.M., Levy B., Liu Y., Sun F., Wang W. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram // Computer graphics forum. 2009. V. 28. № 5. P. 1445–1454.
Budninskiy M., Liu B., De Goes F., Tong Y., Alliez P., Desbrun M. Optimal Voronoi tessellations with hessian-based anisotropy // ACM Trans. on Graphics, Proc. of SIGGRAPH Asia. 2016. V. 12.
Tournois J., Alliez P., Devillers O. 2D centroidal Voronoi tessellations with constraints // Numerical Math. Theory Meth. and Appl. 2010. V. 3. № 2. P. 212–222.
Levy B., Liu Y. Lp Centroidal Voronoi Tessellation and its applications // ACM Trans. on Graphics. 2010. V. 29. № 4. Art. 119.
Persson P.-O., Strang G. A simple mesh generator in MATLAB // SIAM Rev. 2004. V. 46. № 2. P. 329–345.
Гаранжа В.А., Кудрявцева Л.Н. Построение трехмерных сеток Делоне по слабоструктурированным и противоречивым данным // Ж. вычисл. и матем. физ. 2012. Т. 52. № 3. С. 499–520.
Cohen-Steiner D., Alliez P., Desbrun M. Variational shape approximation // ACM Trans. on Graphics. 2004. V. 23. № 3. P. 905–914.
Garanzha V.A. Discrete extrinsic curvatures and approximation of surfaces by polar polyhedra // Comput. Math. and Math. Phys. 2010. V. 50. № 1. P. 65–92.
Gunther F., Jiang C., Pottmann H. Smooth polyhedral surfaces // arXiv preprint arXiv:1703.05318, 2017.
Liu Y., Pottmann H., Wallner J., Yang Y.L., Wang W. Geometric modeling with conical meshes and developable surfaces // ACM Trans. on Graphics. 2006. V. 25. № 3. P. 681–689.
Ju T., Losasso F., Schaefer S., Warren J. Dual contouring of hermite data // ACM Trans. on Graphics. 2002. V. 21. № 3. P. 339–346.
Ohtake Y., Belyaev A. Dual/primal mesh optimization for polygonized implicit surfaces // In Proc. of the 7th ACM Symposium on Solid Modeling and Appl. (SMA’02). New York, NY: ACM, 2002. P. 171–178.
Lloyd S.P. Least squares quantization in PCM // IEEE Trans. Inform. Theory. 1982. V. 28. № 2. P. 129–137.
Ruppert J. A Delaunay refinement algorithm for quality 2-dimensional mesh generation // J. of Algorithms. 1995. V. 18. № 3. P. 548–585.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал