Метод сдвига крайних точек для построения триангуляции плоской области, заданной в obj-формате

DOI:

Пусть задан конечный набор точек { P _i } i= ₁ на плоскости R ² . Триангуляцией данного набора точек называется совокупность невырожденных треугольников Т = { T j } j'= ₁ такая, что

Отметим, что всякая точка P t является вершиной некоторого набора треугольников из триангуляции Т . Если сумма углов при вершине P _i по таким треугольникам равна 2п , то узел P _t будем называть внутренним узлом триангуляции. В противном случае узел назовем крайним.

Пусть Q ограниченная область в R ² . Триангуляцией области Q называется триангуляция произвольного конечного набора точек, лежащего в замыкании области Q . Известны различные подходы к построению расчетной треуго л ьной сетки (триангуляции). Например, берется конечное число точек, лежащих в Q , и формируется на их основе триангуляция одним из соотвествующих алгоритмов (см., например, [1–3]) Имеются и другие способы, в которых применяются либо вариационные принципы, либо разрезание (измельчение) области (или ее границы) на простые части, либо решение различных краевых задач, либо построение выпуклой триангуляции Делоне с последующим удалением лишних треугольников и т. д. (см., например, [4–15]).

В настоящей работе представлен метод, общая идея которго заключается в следующем. Строится начальная триагуляция области в виде набора треугольников, расчитан-ных по координатной сетке. После этого крайние узлы сдвигаются на границу области по определенному правилу. Данный способ применяется для областей, которые ограничены замкнутыми ломаными линиями, что позволяет их достаточно легко моделировать в среде Blender , сохранив в формате obj . Это, в свою очередь, даст возможность автоматизировать процесс триангуляции, не прибегая к трудоемкому шагу выписывания математических формул, задающих границу области. Отметим также, что подход, связанный со сдвигом крайних узлов на границу области не является новым. Например, он был применен для построения пространственной сетки в работе [16]. Отличие нашего алгоритма заключается в том, что в этой работе область задается одним неравенством и несколько иначе осуществляется сам сдвиг крайних узлов на границу области.

рмате

Рис. 1. Область, заданная набором замкнутых ломаных.

Рис. 2. Вид начальной (слева) и окончательной (справа) триангуляции Т * .

дующие действия. Во всех треугольниках Т _к , в которых есть вершины Р . , являющиеся крайними узлами триангуляции 7h , заменим эти вершины на точку Р . € д Q , которую будем определять следующим правилом. Найдем вначале ближайший отрезок L _k , в полосу которого попадает крайний узел, а затем найдем ближайшую вершину Vj ломаных линий r _s , s = 0,1, .,р . Тогда точка Р . € д Q определяется так

_р,    f Vj ,                                    если | V - Р. | < dist(P ; , L_k )

^Р    Qq € L _k : | Q - P . | = dist(P _! ,L ₄ ),   если | V j - P i \ >  dist^L t ).

Для упрощения процедуры вычисления точки Р ' мы строим векторное поле Е(х,у) , вдоль которого сдвигается точка P i до искомой точки Р - . Получаем новую триангуляцию Т * h (рисунок 2, правая часть), которая помимо внутренних точек области Q будет содержать узлы, лежащие на д Q .

Теперь поясним некоторые детали алгоритма, которые мы упомянули выше. Для определения принадлежности точки области Q мы воспользовались стандартным подходом, описанным, например, в [17]. Именно, вычисляется количество пересечений луча, выходящего из точки (х,у) и направленного вертикально вверх, с границей области. Если это количество четное, то считаем, что точка находится вне области Q . В противном случае точка принадлежит области.

Поясним теперь способ выбора диагонали, разбивающей квадраты на два треугольника. При построении начальной триангуляции может возникнуть ситуация, когда у некоторого треугольника все его вершины будут крайними узлами триангуляции. В этом случае, при сдвиге этих узлов на границу области, треугольник будет почти вырожденным для малых значений h . Чтобы избежать этого, мы будем проводить диагональ в квадрате следующим образом. Пусть точка Q является центром квадрата, а Q' - ближайшая к ней точка границы д Q , лежащая на отрезке L _k . Тогда возьмем ту диагональ квадрата, которая образует меньший угол с нормалью к L _k .

И, наконец, триангуляцию можно немного поправить с помощью стандартного метода, основанного на том, чтобы любой внутренний узел стал центром множества вершин многоугольника, составленного из треугольников, окружающих этот узел. Тогда сама поправка будет выглядеть так. Пробегаем по всем внутренним узлам P _i и для каждой из них определяем вершины P _i 1 , ...,P _{i r} , являющиеся соседними с P _i . После чего вершину P i заменяем на

1 ^{г P} i = - Е P ■

3=1

Данную процедуру (цикл по всем внутренним узлам триангуляции) делаем несколько раз, пока не будет достигнута необходимая точность. В итоге получается исправленная триангуляция с оптимизированной формой ячеек (рисунок 3)

2.    Описание алгоритма триангуляции

Приведем схему алгоритма описанной выше триангуляции. Мы считаем, что задан набор точек { V j } j=1 j , которые соединяются отрезками { L _k } ^l _{k =1} таким образом, что образуют набор ломаных замкнутых линий Г 0 , Г 1 , ..., Г _р . Предполагается, что каждая из этих линий ограничивает некоторый многоугольник на плоскости, при этом Г П Г = 0 для S = t .

• 1)    Рассмотрим квадрат [а,Ь] х [а,Ь] , который содержит область Q вместе со своей границей. В этом квадрате строится векторное поле Е(х,у) следующим образом (рисунок 4). Перебираем все отрезки L _k и среди них находим ближайший к точке (х,у) , который удовлетворяет условию

| а(х - х _с ) + в (у — У с ) 1 <  2 I B' - В "| У а ² + в ² ,

Рис. 3. Вид исправленной триангуляции Т * .

где точки В' = (х ' ,у ' ) , В ‘‘ = (х " ,у " ) являются концами отрезка L ^ ,

х' + х' '          у ' + у ''

^{Х с} =    2   ’   ^{У с} =   2

и а = х" - Х, в = (у' — У').

Если расстояние от точки (х, у) до найденного отрезка не превосходит расстояния до ближайшего узла V j = (х,у) , то полагаем

Е (^х,^у) = sgn( ^{e x} - ^{а у} + ^Y) (^=р, -^Х + в ) ,

где у = вх ' — ау ' . В противном случае,

^{Е ( х,}у) =

(

х — х             у — у

У (х - х) ² + (у - у) ² , У (х - х) ² + (у - у) ²

)

• 2)    Положим x_i= а + i(b- а)/п, уj = а+j(b-а)/п, где i,j = 0,1,.., п и A_i:- = (x_i, уj). Для каждого i,j = 0,1,..,п - 1 определяем принадлежность вершин (x_i,уj), (x_i+1,уj), (x_i,уj₊₁) и (x_i+1,уj₊₁) области Q. Если 3 из этих точек лежат в Q, а четвертая не принадлежит Q, то в триангуляцию добавляем треугольник, который образуют эти три вершины. Если все 4 точки лежат в Q, то в триангуляцию добавляем два треугольника, полученные разбиением квадрата A_ijA_i+1jA_i+1j₊₁A_ij₊₁ одной его диагональю. Диагональ определяется так. Пусть х₀= (x_i+1+ x_i)/2, у₀= (у_:'₊1 + уз)/2. Если для векторов е1 = (1,1), е₂= (-1,1) выполнено

3.    Примеры триангуляции областей, заданных в obj-формате

| X (х о ,у „ ),ё 1 )| >ЦЁ (х о ,у „ ),ё ₂ )| ,

Рис. 4. Векторное поле сдвига крайних узлов.

то выбираем диагональ A _i j A _{i +1} j ₊₁ . В противном случае, берем диагональ A _{i +1} j А^₊₁ . Тем самым будет получена начальная триангуляция (см. рисунок 2).

3) Проходим по всем крайним узлам (х, у) триангуляции T h и меняем их на ближайшую точку пересечения границы области dQ с лучом, входящим из узла (х,у) в направлении вектора Е(х,у) . Получаем новую триангуляцию T * -

Описание границы плоской области может быть дано в виде текстового файла формата obj , например так:

# Blender 4.4.0

# mtllib o B?zierCircle v -1.417338 0.000000 0.368239 v -1.453928 0.000000 0.343656 v -1.484190 0.000000 0.316054 v -1.508353 0.000000 0.285619 v -1.526646 0.000000 0.252536

l12

l23

l34

l45

l56

Строки, помеченные буквой « v » содержат координаты вершин замкнутой ломаной линии, а буквой « l » – номера этих вершин отдельного звена ломаной линии. Отметим, что основу алгоритма составляет шаг построения векторного поля Е(х,у ) , вдоль которого осуществляется сдвиг на границу области крайних точек начальной триангуляции. Для расчета этого векторного поля и сдвига крайних точек были написаны отдельные функции field() и move_to_bound() на языке Python , в которые передаются массивы вершин и звеньев ломаных линий, считанные из соответствующего obj -файла. Автору статьи были предоставлены два файла ( curves.obj и ring.obj ), полученные средствами программы Blender , в которых хранятся границы двух областей.

Рассмотрим первую область (рисунок 5). Данная область задана границей, образованной из двух замкнутых ломаных линий, которые состоят из 53 и 64 звеньев соответственно. Представленным в статье методом была получена триангуляция данной области, состоящая из 467 узлов, соединенных в 808 треугольников (рисунок 6).

Рис. 5. Первая (слева) и вторая (справа) области

Рассмотрим вторую область (рисунок 5). Данная область задана границей, образованной из двух замкнутых ломаных линий, которые состоят из 192 и 48 звеньев соответственно. Представленным в статье методом была получена триангуляция данной области, состоящая из 1851 узлов, соединенных в 3406 треугольников (рисунок 7).

4.    Заключение

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

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

Рис. 6. Триангуляция первой области (слева) и ее исправленный вариант (справа)