Алгоритм Рапперта

Алгоритм построения 3D модели

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

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

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

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

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

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

Обзор существующих методов

Наиболее известные алгоритмы генерации сетки:

  1. Radial sweep algorithm.
  2. Recursive split algorithm (Алгоритм последовательного разбиения).
  3. Divide-and-conquer algorithm (Алгоритм деления и включения).
  4. Step-by-step algorithm.
  5. Modified hierarchical algorithm (Модифицированный иерархический алгоритм)
  6. Incremental algorithm.
  7. Incremental delete-and-build algorithm.
    Все эти алгоритмы не предназначены непосредственно для генерации конечно-элементной сетки. Они подразумевают наличие опорных точек, которые будут потом узлами сетки.
    К сетке для метода конечных элементов предъявляется ряд особых требований.
  8. Треугольники не должны быть сильно вытянутыми, т.к. наличие таких треугольников отрицательно сказывается на точности результатов расчета.
  9. Должен быть учтен характер работы конструкции и ее геометрия, т.е. в местах концентрации напряжений сетка должна сгущаться.

Алгоритм Рапперта

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

Терминология

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

Сегмент (segment) — это отрезок, соединяющий две соседние точки лежащие на границе области разбиения, другими словами этот отрезок принадлежит контурам области.

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

Включенная точка (encroached point) — любая вершина текущей сетки, которая находится внутри окружности, радиусом которой является любой сегмент.

«Неправильный треугольник» (bad triangle) — это треугольник не удовлетворяющий глобальным условиям, которые накладываются на генерируемую сетку.

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

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

  1. разбиение неправильного треугольника с введением нового узла
  2. разбиение сегмента, принадлежащего границе области разбиения с введением нового узла.

При разбиении треугольника происходит следующее:

  1. Вычисляются координаты центра окружности, описанной вокруг треугольника, подлежащего разбиению.
  2. В эту точку добавляется новый узел.
  3. Удаляется треугольник, подлежащий разбиению и прилегающие и добавляются новые.

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

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

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

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

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

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

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

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

  1. Производится поиск включенной (encroached) точки перебором всех точек и сегментов (только сегментов, но не граней).
  2. Если такая точка найдена то над сегментом, который включает ее выполняется процедура деления сегмента пополам и производится возврат на шаг 1. Если включенных точек не было найдено, то алгоритм переходит на следующий шаг.
  3. Производится поиск треугольника с минимальным углом.
  4. Если минимальный угол меньше заданного параметра, то над треугольником, его содержащем производится процедура деления и производится возврат на шаг 1. В противном случае происходит переход на следующий шаг.
  5. Производится поиск треугольника максимальной площадью.
  6. Если максимальная площадь больше заданного параметра, то над таким треугольником производится процедура деления и производится возврат на шаг 1. В противном случае происходит переход на следующий шаг.
  7. Все условия удовлетворены. Конец работы алгоритма

Существуют строгие математические доказательства, гарантирующие правильную работу алгоритма при минимальном угле α < 20◦.
Опытным путем было установлено, что углы α > 25◦ были недоступны для него.

Алгоритм построения первичного разбиения

Все, о чем говорилось выше, является не алгоритмом генерации сетки, а лишь алгоритмом ее улучшения (Delaunay Refinement Algorithm). Для него входными данными является уже готовое разбиение.

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

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

Схематично этот алгоритм можно описать так:

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

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

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

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

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

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

На грани также накладывается ограничение, треугольники формируются только от граней, которые принадлежат только одному треугольнику. Эти правила нарушаются только в одном случае — при генерации первого треугольника.

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *