LEC-24 (1014368), страница 2

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

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

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

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

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

Теперь необходимо установить в каком порядке включать эту процедуру. Самым простым решением будет проверять циклом каждую грань триангуляции на каждом шаге и, если необходимо, производить смену диагонали. Но известно, что в треугольной сетке граней больше чем треугольников и узлов в 1,5–1,6, поэтому тотальная проверка всех граней стала бы трудоемкой.

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

Исходя из этого может быть применена другая технология — технология распространяющегося "вируса смены диагонали". Суть ее заключается в следующем. После выполнения одной из базовых процедур точно известно, какие треугольники сетки подверглись изменениям, т.е. известна область, которая подверглась изменениям. Грани в этой области могут нуждаться в перемене своего направления и эти грани становятся «зараженными». Они помещаются в очередь для проверки — линейный массив индексов. Каждая грань в очереди проверяется и если проверяемая грань нуждалась в изменении, то все остальные грани двух треугольников, содержащих проверяемую грань также становятся зараженными и помещаются в очередь. Другими словами, меняя диагональ, мы изменяем область, состоящую из этих треугольников. Границами этой области будут остальные четыре грани этих двух треугольников. Каждая такая грань как граница измененной области нуждается в проверке. Если же грань не нуждается в изменениях, то она удаляется из очереди. Такой процесс продолжается до тех пор, пока очередь не станет пустой.

Такой подход существенно ускоряет работу алгоритма в целом. Например, в одном контрольном примере, для случая с тотальной проверкой время работы на Celeron 266 (333) составило около 18 секунд, а для второго случая время составило менее 10 секунд — сокращение трудоемкости более чем на 45%.

Дополнительные замечания к реализации алгоритма.

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

Правильная геометрия фигуры

П
ервый недочет состоял в том, что алгоритм не работает правильно с симметричными или правильными геометрическими формами, которые часто возникают из-за того, что область которую необходимо разбить на элементы является правильной. На рисунке 13-Р видно, при попытке разбить равнобедренный треугольник bcd с прямым углом по базовой процедуре образуются треугольники нулевой площади (см. рис. 13-Р). В данном случае процедура разобьет треугольник на три: dce, bec, bde. Центр описанной окружности треугольника bcd находится точно на отрезке bd, поэтому треугольник bde имеет нулевую площадь. При попытке вычислить координаты центра его описанной окружности происходит деление на ноль.

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

Очень вытянутые треугольники с удаленным центром.

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

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

ax₁ +by₂ +c > 0 или ax₁ +by₂ +c < 0, подставить в него координаты проверяемой точки и сравнить полученные знаки для каждой грани. Если знаки одинаковые, то и точка находится с одной стороны от всех отрезков.

Малые углы между гранями.

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

Д
ля ликвидации подобных ситуаций автор алгортима предложил эвристическое правило: делить в таких случаях сегмент не посередине, а на ближайшей точке пересечения этого сегмента и концентрических окружностей с центрами в вершине угла (см. рис. 16-Р). Радиус каждой последующей окружности ровно вдвое больше радиуса предыдущей, а первая окружность берется произвольно, но достаточно малой, например r₀ = 0.01. То есть радиус каждой i-ой окружности равен r_i = r₀ 2 i.

Безусловно, эту схему надо применять только там, где это действительно необходимо. Поэтому, чтобы ее применить, требуется проверить, надо ли ее проверять. Здесь программисту тоже дается свобода в выборе такой схемы проверки. Можно все же предложить такую схему: сначала проверяется, является ли угол достаточно малым; затем проверяется площадь треугольника, подлежащего разбиению. Если площадь меньше площади, задаваемой как параметр для алгоритма, т.е. критерия максимальной площади, умноженного на какой-то коэффициент, который можно подобрать (0 > k ≥ 1), то тогда необходимо использовать способ концентрических окружностей.

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

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

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

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

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

1. Выбирается начальный сегмент (любой) на внешнем полигоне исходной геометрии. (см. рис. 17-Р)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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