Триангуляция двумерных областей

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

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

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

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

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

    Более того, любой треугольник можно  разбить на треугольники, подобные ему (на 4, 9, 16 и т.д.). Тетраэдр в общем  случае нельзя разбить на подобные тетраэдры. Это является основным препятствием на пути использования методов дробления, эффективно применяющихся в двумерном  случае.

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

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

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

    2. Прямые методы

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

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

    Таким образом, несмотря на все ограничения, прямые методы все равно находят  свое применение в дискретизации  пространственных областей.

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

    Рассмотрим, например, так называемую "кубическую сетку", то есть сетку, полученную разбиением исходного параллелепипеда на равные "кубы" (слово "куб" здесь  употребляется исключительно в  топологическом смысле, поскольку ребра  у такого "куба" необязательно  строго равны). Если размеры куба - hx, hy, hz, и он ориентирован по осям координат, то узел с индексами i,j,k  имеет координаты (Ox + i*hx, Oy + j*hy, Oz + k*hz), а его соседями являются узлы с индексами (i ± 1, i, k), (i, j ± 1, k) и (i, j, k ± 1).

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

    Рис. 3. Кубическая сетка