6CAD-CAE-21 Делоне, Рапперт (1014140), страница 3
Текст из файла (страница 3)
К каждому возможному варианту необходимо предъявлять ряд требований. Во-первых, это адекватность этого критерия, т.е. улучшает ли он свойства сетки на самом деле, и если да, то с какими оговорками. Может случится, что способ хорош внешне, прост, не трудоемок, но работет при ряде ограничений. Эти ограничения и могут свести на нет все преимущества предлагаемого метода. Во-вторых, необходимо учитывать машинную трудоемкость выбираемого метода. И в-третьих, эффективность его будет зависеть еще и от сложности алгоритма, реализующего предлагаемый метод.
Первый, возможно самый очевидный критерий — это длина диагонали (см. рис. 10-Р). Действительно, зрительно, диагональ ac кажется гораздо более удачной диагонали bd для минимального угла двух треугольников и поменяв эту диагональ мы, вероятно, добьемся улучшения свойств сетки. У этого способа, к тому же, есть преимущества: он не трудоемок в вычислительном плане и его просто запрограммировать. Но есть у него и критический недостаток — он неадекватен. На рисунке 10-Р показан случай, где использование критерия минимальной длины диагонали может привести к серьезному ухудшению свойств сетки.
Диагональ bd короче диагонали ac, поэтому, по критерию минимальной длины диагонали, диагональ ac надо поменять на bd. Но это приведет к появлению очень тонкого треугольника, а их появление крайне нежелательно, а часто и вовсе становится критическим. Этот случай уже не так просто формализуется, и запрограммировав его, легко убедиться, что это дополнительное условие сильно "утяжеляет" алгоритм, сводя на нет все его преимущества.
Следующий очевидный критерий можно получить сравнивая минимальные углы в двух треугольниках до и после смены диагонали, для предсказания эффективности этого действия (см. рис. 11-Р). Такой критерий является абсолютно адекватным, т.к. он совпадает с основным глобальным критерием сетки — критерием минимального угла и это его существенное преимущество.
Применение такого критерия действительно кажется заманчивым в силу его объективности, но у него есть один специфический недостаток — трудоемкость. Для него необходимо вычислить 6 углов, а по объему операций трудоемкость этого превосходит более чем в 10 раз вычисление двух длин отрезков.
Действие вычисления площади по трудоемкости сравнимо с нахождением одного угла. Поэтому третьим критерием является сравнение площадей двух треугольников, точнее не сравнение самих площадей, а сравнение с единицей отношения площадей до и после смены диагонали. Сравниваться должна нормализованная величина отношения площадей до и после смены диагонали. Другими словами величина этого отношения дожна быть меньше 1, если она получается больне 1, то сравнивается ее обратная величина. Более близкое к единице значение отношений означает более равномерное распределение площадей. Этот критерий теоретически не обоснован, он больше интуитивный, эмпирический, но тем не менее, на практике работает довольно хорошо.
Но все же, сравнивая качество работы второго и третьего критерия преимущество во многих случаях остаётся за вторым. И, прежде всего, из-за своего совпадения с глобальным критерием качества сетки, вследствие чего он показывает более стабильную работу всего алгоритма в целом.
Выше было упомянуто о существовании исключения, при котором нарушается локальность изменения положения диагонали внутри четырехугольника. На рисунке 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. Если для всех граней точка находится с одной стороны, то точка находится внутри треугольника. Математически это определяется довольно просто. Достаточно записать каноническое уравнение прямой на которой лежит грань
ax1 +by2 +c > 0 или ax1 +by2 +c < 0, подставить в него координаты проверяемой точки и сравнить полученные знаки для каждой грани. Если знаки одинаковые, то и точка находится с одной стороны от всех отрезков.
Малые углы между гранями.
Существует еще одна любопытная подробность, которая даже упомянута у Рапперта. При существовании в исходной геометрии острых углов, т.е. если существует малый угол между соседними сегментами, происходит зацикливание на процедуре деления сегмента (см. рис. 15-Р).
Для ликвидации подобных ситуаций автор алгортима предложил эвристическое правило: делить в таких случаях сегмент не посередине, а на ближайшей точке пересечения этого сегмента и концентрических окружностей с центрами в вершине угла (см. рис. 16-Р). Радиус каждой последующей окружности ровно вдвое больше радиуса предыдущей, а первая окружность берется произвольно, но достаточно малой, например r0 = 0.01. То есть радиус каждой i-ой окружности равен ri = r0 2 i.
Безусловно, эту схему надо применять только там, где это действительно необходимо. Поэтому, чтобы ее применить, требуется проверить, надо ли ее проверять. Здесь программисту тоже дается свобода в выборе такой схемы проверки. Можно все же предложить такую схему: сначала проверяется, является ли угол достаточно малым; затем проверяется площадь треугольника, подлежащего разбиению. Если площадь меньше площади, задаваемой как параметр для алгоритма, т.е. критерия максимальной площади, умноженного на какой-то коэффициент, который можно подобрать (0 > k ≥ 1), то тогда необходимо использовать способ концентрических окружностей.
Если в нашей конструкции к вершине такого угла приложена сосредоточеная сила, то в окрестности этой точки возникают резкие изменения напряжений и деформаций. Задав коэффициент k достаточно малым, мы добьемся более густого разбиения в таких углах.
Все эти усовершенствования касаются самого алгоритма улучшения сетки. Они объективно позволяют улучшить стабильность работы и качество генерируемой сетки, хотя в нем все же есть небольшие недостатки. Но они не критичны, самым заметным из них является появление неоправданных сгущений сетки. Такие сгущения появляются не всегда, но если и появляются то их можно ликвидировать изменив параметры (минимальный угол или максимальная площадь) и сгенерировав заново сетку. А при разумных установках этих параметров, алгоритм всегда сходится, т.е. достигает этих параметров. Безусловно при более тщательном его исследовании можно добиться еще лучших результатов.
9.9.3. Алгоритм построения первичного разбиения.
Ранее говорилось об алгоритме генерации сетки, но по сути все, о чем говорилось выше, является не алгоритмом генерации сетки, а лишь алгоритмом ее улучшения (Delaunay Refinement Algorithm). Для него входными данными является уже готовое разбиение. Первоначальное разбиение полигональной фигуры производится другим алгоритмом. Входными данными для него являются массивы точек (координаты, нагрузка, закрепление) и граней полигонов, в терминологии Рапперта — сегментов, соединяющих эти точки. Выходные данные — это массив вершин без изменений, массив граней треугольников и массив собственно треугольников, заполняющих весь объем конструкции.
Схематично этот алгоритм можно описать так:
Выбирается начальный сегмент (любой) на внешнем полигоне исходной геометрии. (см. рис. 17-Р)
Из всех вершин выбирается такая, из которой лучи, соединяющие эту вершину и концы текущего сегмента образуют максимальный угол.
Добавляется полученный таким образом треугольник и текущим сегментом становится одна из созданных сторон этого трегольника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
