Решеточные методы

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

По всей видимости, первым решеточным методом был метод Такера и его коллег [150]. Согласно этому методу на объект накладывается треугольная решетка, причем все точки решетки, оказывающиеся вне объекта, удаляются, в результате чего получается зигзагообразная граница. Точки на этой границе перемещаются на границу объекта, что дает готовую сетку. Кикучи [84] расширил этот метод для создания сеток, состоящих главным образом из четырехугольников, однако содержащих некоторое количество треугольников. Он использовал прямоугольную решетку (рис. 8.19). Одним из недостатков обоих методов является исчезновение мелких деталей, размеры которых сравнимы с расстоянием между линиями решетки. В других методах точки на границе решетки не перемещаются на границу объекта. Вместо этого между зигзагообразной границей решетки и границей объекта создаются треугольные элементы, для чего используется алгоритм триангуляции.

Решеточные методы

Йерри и Шипхард [ 164] для создания сеток воспользовались квадрантным деревом Квадрантное дерево представляет собой двумерный аналог октантного, о котором говорилось в главе 5. Это дерево позволяет представить двумерный объект (рис. 8.20, а) в виде набора квадрантов различного размера путем рекурсивною деления исходного квадранта, содержащего данный объект. Процесс деления объекта иллюстрирует рис. 8.20, б, а квадрантное дерево, описывающее процесс деления, изображено на рис. 8.20, в. Сетка строится следующим образом.

Решеточные методы

1.  Создается исходный (корневой) квадрант, содержащий объект целиком внутри себя. Этот квадрант делится на четыре квадранта путем деления каждой его стороны пополам. Затем квадранты классифицируются по положению относительно объекта. Если квадрант не лежит целиком внутри или снаружи объекта, он делится дальше. Процесс деления продолжается до тех пор, пока не будет удовлетворено требование к плотности сетки, после чего берутся квадранты, либо лежащие целиком внутри объекта, либо имеющие с ним общие точки. Если рассматриваются квадранты, имеющие с объектом общие точки, их приходится модифицировать таким образом, чтобы они содержали только внутренние части объекта. Объект, состоящий из квадрантов, лежащих целиком внутри него, а также модифицированных квадрантов, имеющих с ним общие точки, будет выглядеть так, как показано на рис. 8.21, а.

Решеточные методы

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

3.  Положения узлов корректируются так, чтобы улучшить форму ячеек. Результат сглаживания сетки демонстрирует рис. 8.21, в. Метод сглаживания будет описан позже.

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

Джан и Ли [82] предложили новый метод, согласно которому нужно начинать с треугольного корня (или тетраэдрического в трехмерном случае). Это позволяет избежать описанных выше затруднений. В этом случае квадрантное дерево будет аппроксимацией объекта треугольниками, а октантное дерево — тетраэдрами. Деление треугольного корня на четыре маленьких треугольника показывает рис. 8.22, а, а деление тетраэдрического корня на восемь тетраэдров — рис. 8.22,6.

Решеточные методы

Смотрите также