Коррекция первичной сетки

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

Рис. 4. Сетка, полученная на основе алгоритма "quadtree": вверху - по классическим шаблонам, внизу - по улучшенным.

Если в качестве входных данных передаются списки всех угловых точек, кривых и составляющих границу сплайнов[1] (типичный случай, когда область импортируется из CAD-системы), то проблема решается достаточно просто. Задается массив "особых точек", куда входят все "угловые" и другие характерные точки, в которых обязательно должны размещаться узлы триангуляции. Если в области есть ребра, которым не принадлежат никакие угловые точки (примером такого ребра может служить линия пересечения цилиндра с призмой), то в указанный массив следует добавить произвольную точку, лежащую на этом ребре. Далее процесс граничной коррекции можно разбить на этапы.

1) Для каждого элемента массива "особых точек" находится ближайший узел первичной сетки и передвигается в эту точку с сохранением всех связей.

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

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

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

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

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

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