6CAD-CAE-21 Делоне, Рапперт (1014140), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Если существует подходящий текущий сегмент, то на шаг 2.

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

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

Если существует подходящий текущий сегмент, то на шаг 2.

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

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

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

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

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

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

Все вышеперечисленные процедуры и формируют алгоритм генерации сетки.

Заметим, что для получения первичного разбиения при реализации алгоритма генерации сетки можно использовать упрощенный вариант алгоритма step-by-step (см. п. 5) с использованием в качестве точек вершин полигонов исходной геометрии.

Выводы

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

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

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

Характеристики

Список файлов лекций