| title | seoTitle | seoDescription | datePublished | cuid | slug | cover |
|---|---|---|---|---|---|---|
Как разбить полигональную сетку плоскостью |
Как разбить полигональную сетку плоскостью |
В статье рассмотрен один из подходов к разбиению триангуляционной сетки плоскостью |
Thu Mar 30 2023 10:20:35 GMT+0000 (Coordinated Universal Time) |
clfuyt79j000909mifnxb2jnv |
kak-razbit-poligonalnuyu-setku-ploskostyu |
В статье рассмотрен один из подходов к разбиению триангуляционной сетки плоскостью. Это не какой-то новый подход к разбиению, а лишь вариант алгоритма, построенный на базе уже существующих.
Рассмотрим триангуляционную сетку M некоторой геометрической модели и плоскость S (выделена синим) в трехмерном пространстве. Допускаем, что сетка M не имеет самопересечений.
![Пример исходных данных](https://cdn.hashnode.com/res/hashnode/image/upload/v1680081672315/a74c4fd4-9fd5-4abb-9c41-6a21e362c24e.png align="center")
Выбор структуры данных для представления сетки триангуляции зависит от поставленных задач. Мы применим структуру «Узлы, ребра и треугольники» [1, с17]. В силу своей полноты она несколько упрощает реализацию алгоритма разбиения плоскостью, но в то же время усложняет собственную поддержку. С другими типами структур можно ознакомиться здесь [1, с12].
На схеме ниже показаны основные этапы алгоритма разбиения сетки плоскостью. Основная идея заключается в рассечении исходной сетки плоскостью с последующим заполнением образовавшихся пустот новой триангуляцией.
![Схема алгоритма разбиения](https://cdn.hashnode.com/res/hashnode/image/upload/v1680082086395/e2054bc2-4271-4650-a8d9-7f72823991df.png align="center")
Далее мы рассмотрим каждый этап подробнее. Но для начала вспомним как вычислить точку пересечения отрезка и плоскости в пространстве.
Точка пересечения отрезка, образованного точками P0 и P1, и плоскости S с нормалью N вычисляется по следующей формуле (1) из [2, с2]:
где - d0 расстояние от точки P0 до плоскости S, d1 - расстояние от точки P1 до плоскости S.
![Схема пересечения отрезка и плоскости](https://cdn.hashnode.com/res/hashnode/image/upload/v1680092631072/42b1d3f0-e6c4-4cff-bdf9-4c0cf740c08a.png align="center")
Расстояние d от точки до плоскости вычисляем по следующей формуле (2), где Ps - это некоторая точка на плоскости S:
Если d>0, то точка P находится с лицевой стороны плоскости S. Если d<0, то точка P находится с тыльной стороны плоскости S. Если d=0, то точка P лежит на плоскости S.
На начальном этапе алгоритма разбиения промаркируем узлы сетки M в соответствии с их положением относительно секущей плоскости S. Узлы могут оказаться с лицевой стороны плоскости, с ее тыльной стороны или лежать на плоскости. Лицевая сторона плоскости определяется по направлению ее нормали N.
![Схема маркировки узлов](https://cdn.hashnode.com/res/hashnode/image/upload/v1680082373788/08d94d5a-5c32-43bd-be30-06a0db824390.png align="center")
Для каждого узла вычисляется его расстояние d до плоскости (формула 2 выше) и выбирается одно из трех положений: лицевая область (рисунок ниже, узлы со знаком "+"), тыльная область (узлы со знаком "-") или положение на секущей плоскости (узлы со знаком "0"). Так как для обозначения координат узлов используются вещественные числа, равенство следует проверять с учетом некоторой погрешности ε. Тогда для узлов, лежащих на плоскости, справедливо неравенство:
Если в конечном итоге оказывается, что сетка M не имеет узлов с тыльной или лицевой стороны плоскости, то мы делаем вывод, что плоскость S не пересекает сетку M.
На следующем этапе алгоритма выполняем обход по всем треугольникам сетки (или ребрам, или узлам — зависит от выбранной структуры данных) и вычисляем точки пересечения их ребер с секущей плоскостью. При этом каждый треугольник получает один из следующих маркеров:
-
"1" — треугольник находится с лицевой стороны плоскости;
-
"0" — треугольник пересекается плоскостью;
-
"-1" — треугольник находится с тыльной стороны плоскости.
![Схема маркировки треугольников](https://cdn.hashnode.com/res/hashnode/image/upload/v1680094477543/7ae988ce-fa31-4dbb-9736-94fec4b9a298.png align="center")
После того, как треугольники промаркированы, начинается сборка результирующей сетки M' с перестроением треугольников в местах пересечения, то есть треугольников с маркером "0". Результирующей может быть сетка как с лицевой стороны секущей плоскости, так и с тыльной. В зависимости от требуемого результата, соответствующие треугольники с маркерами "1" или "-1" будут добавляться в новую сетку без изменений.
Для рассеченных треугольников необходимо выполнить перестроения геометрии. На рисунке ниже показаны частные случаи перестроения треугольников, где e, e1 и e2 - добавляемые ребра с новыми узлами в местах пересечения.
![Варианты перестроения треугольников](https://cdn.hashnode.com/res/hashnode/image/upload/v1680094722490/ce3bafd9-e2e1-47d3-a11d-a7b710a9a862.png align="center")
После выполнения этого шага мы получаем отсеченную часть исходной сетки с пустотой в месте рассечения.
![Результат отсечения исходной сетки](https://cdn.hashnode.com/res/hashnode/image/upload/v1680094779885/5253b5dc-442b-421f-bfd0-03a70247fec3.png align="center")
Пустоту, образовавшуюся в области рассечения, требуется заполнить триангуляцией. Так как все узлы и ребра в месте рассечения лежат в одной плоскости, упростим задачу и представим такую область в виде двумерного полигона. Полигон состоит из одного внешнего и множества внутренних контуров, имеющих определенный порядок обхода узлов.
Выделим четыре основных варианта полигонов в области рассечения сетки:
-
Один полигон без внутренних контуров;
-
Один полигон с одним или несколькими внутренними контурами;
-
Несколько полигонов без внутренних контуров;
-
Несколько полигонов, содержащих внутренние контуры.
![Виды полигонов](https://cdn.hashnode.com/res/hashnode/image/upload/v1680100896809/2ffd4657-230f-4f3c-9852-d35a5f857dda.png align="center")
Определим алгоритм выделения таких двумерных полигонов из рассеченной сетки, полученной на предыдущем этапе. Он включает в себя два основных этапа:
-
Поиск всех контуров в месте рассечения;
-
Компоновка полигонов из полученных контуров.
Каждый треугольник, граничащий с местом рассечения, отличается от остальных тем, что он не имеет с одной из своих сторон соседа. Узлы и ребра, находящиеся на границе рассечения, как раз и формируют будущий контур.
Собирать контуры будем путем движения фронта по треугольникам вдоль границы рассечения, пока он не будет замкнут на начальном треугольнике (см. схему ниже). Каждый пройденный треугольник помечаем. Последовательность шагов выглядит следующим образом:
-
Поиск первого граничного треугольника T0;
-
Добавление граничных узлов треугольника <ni, nj>, которые еще не были добавлены в контур;
-
Пометка текущего треугольника;
-
Переход к соседнему граничному треугольнику Ti. Если следующий треугольник найден и он не T0, то идем в п.2, иначе завершаем построение контура.
После построения контура необходимо обойти оставшиеся треугольники сетки и проверить их на наличие граничных ребер. Если граничный треугольник будет найден, то повторить процедуру для построения следующего контура.
![Схема обхода граничных треугольников сетки](https://cdn.hashnode.com/res/hashnode/image/upload/v1680101569844/37e32f75-12fc-4e14-9a3a-704981733b22.png align="center")
При добавлении в контур первого узла n0 нужно запомнить вектор D0 нормали треугольника (рисунок ниже). Этот вектор поможет определить ориентацию контура в будущем полигоне: внутренний или внешний.
![Схема вектора ориентации контура](https://cdn.hashnode.com/res/hashnode/image/upload/v1680101790447/a031c220-f45b-4991-8d1d-266e545b20a7.png align="center")
Пусть точка ND0 - это некоторая точка на векторе D0 (рисунок ниже). Если рассматриваемый контур - внешний, то при обходе контура по часовой стрелке точка ND0 будет находится слева от него, а при обходе контура против часовой — справа. Все остальные контуры автоматически обозначаем как внутренние, так как внешний контур у полигона может быть только один.
Определить направление обхода контура можно по его трем последовательным точкам [3, с 95]. При этом в качестве средней из трех точек на контуре лучше выбрать самую правую по координате x, а если таких несколько, то самую верхнюю из них (с наибольшей координатой y). Положение точки ND0 (слева или справа) можно определить относительно ребра (n0, n1) [3, с 96].
![Схема определения ориентации контура](https://cdn.hashnode.com/res/hashnode/image/upload/v1680102172284/88e18b84-6180-451b-98bf-21540166a2ba.png align="center")
Наконец, сформируем из полученного множества контуров полигоны. Каждый внешний контур определяет один полигон. Для внутренних контуров требуется понять в какой из внешних они попадают и соответственно связать их в одну структуру данных. Так как все контуры множества не пересекаются, то для определения принадлежности внутреннего контура достаточно проверить положение любой его точки относительно всех ребер рассматриваемого внешнего контура (рисунок ниже). При обходе внешнего контура по часовой стрелке внутренняя точка всегда находится справа, при обходе против часовой — слева.
![Схема определения принадлежности внутренних контуров](https://cdn.hashnode.com/res/hashnode/image/upload/v1680102320795/6916fdd6-c698-4e99-8c68-ba5e510fa9ca.png align="center")
Существуют разные способы создания триангуляции для множества точек на плоскости. Наша задача заключается в создании триангуляции полигона, который может включать внутренние контуры. Наиболее простым и в то же время достаточно эффективным является семейство итеративных алгоритмов триангуляции. Об этих алгоритмах подробно рассказано в работе [1].
В общем случае триангуляция полигона итеративным алгоритмом включает следующие этапы:
-
Построение триангуляции по всем точкам полигона без учета его ребер.
-
Вставка в триангуляцию всех ребер полигона, называемых структурными отрезками.
-
Удаление из триангуляции треугольников, находящихся за пределами полигона.
Рассмотрим простой итеративный алгоритм триангуляции с ограничениями. Ограничениями в триангуляции называются структурные ребра полигона.
Шаг 1. Построение суперструктуры [1, c 32]. Суперструктура охватывает все точки данного полигона (рисунок ниже, слева). Поэтому каждая новая точка, добавляемая в триангуляцию, всегда будет попадать на какой-либо из существующих треугольников. В качестве суперструктуры используем прямоугольник. Его легко построить и определить начальную триангуляцию в виде двух треугольников (рисунок 13, справа).
![Суперструктура](https://cdn.hashnode.com/res/hashnode/image/upload/v1680102801400/8530c376-e9e0-494b-bae4-f10079948e6b.png align="center")
Шаг 2. Вставка всех точек полигона в триангуляцию [1, c 31]. Для каждой точки полигона находим треугольник, в который она попадает [1, c 33], и разбиваем его на три новых треугольника. В результате получаем триангуляцию полигона без учета структурных отрезков. Поиск треугольника, в который попадает точка, может быть реализовано по-разному. Самым простым в реализации мне показался способ 3 в [1, c 34].
![Триангуляция по суперструктуре](https://cdn.hashnode.com/res/hashnode/image/upload/v1680102921842/b4d38000-5e85-4ab8-9b54-db9ea5aba557.png align="center")
Шаг 3. Вставка всех структурных ребер полигона (рисунок ниже). Выберем способ вставки «Удаляй и строй» [1, c 74]. При вставке ребра сначала удаляются все треугольники, которые оно пересекает, а затем образовавшийся в месте удаления ребер многоугольник разбивается вставляемым ребром на два и полученные многоугольники заполняется триангуляцией. Неплохой способ заполнения триангуляцией левой и правой частей многоугольника указан в этом же разделе [1, c 74].
![Триангуляция с добавленными ребрами](https://cdn.hashnode.com/res/hashnode/image/upload/v1680103048132/1f797b0e-c0ac-402a-9fe1-746e31c9cbe1.png align="center")
Шаг 4. Удаление треугольников, выходящих за пределы полигона. На данном этапе решается задача классификации треугольников по признаку попадания внутрь области полигона ([1, c 78] или [4, с 4]). Делая обход триангуляции, начиная с любого треугольника, лежащего внутри полигона, (рисунок ниже, слева) помечаем все треугольники, не выходя за пределы, ограниченные структурными отрезками. Остальные треугольники отбрасываются из структуры (рисунок ниже, справа). Начальный треугольник можно определить по структурному ребру внешнего контура. Так как ребро содержит информацию о примыкающих треугольниках и нам известно направление обхода контура, то можно определить с какой стороны от ребра находятся каждый из двух треугольников.
![Итоговая триангуляция полигона](https://cdn.hashnode.com/res/hashnode/image/upload/v1680103614842/246ff3c1-5cc6-4a6e-a9e3-4aa299ce61b2.png align="center")
При вставке триангуляции полигона в итоговую сетку M' будут добавлены новые ребра и треугольники. Сетка станет пространственно замкнутой. Новые узлы при этом не добавляются, так как триангуляция полигона строилась исключительно с использованием существующих узлов на границе среза. Наиболее простой на мой взгляд в реализации способ объединения двух триангуляций — с помощью таблиц ассоциаций индексов элементов (узлов и ребер). Тогда для каждого полигона мы имеем ассоциации «индекс узла сетки — индекс узла полигона» и «индекс ребра сетки — индекс ребра полигона». Двигаясь по треугольникам полигона, мы можем точно знать в какое место его следует поместить в итоговой сетке. На рисунке 17 показаны ассоциации <ei, Ej> для ребер и <ni, Nj> для узлов, где i - индексы элементов полигона, j - индексы элементов сетки.
![Схема совмещения триангуляции полигона с моделью](https://cdn.hashnode.com/res/hashnode/image/upload/v1680103871286/9b70aa42-aaa7-47ca-b932-80117606b938.png align="center")
На рисунке ниже показаны несколько примеров разбиений триангуляционных сеток описанным алгоритмом. Стоит сказать, что алгоритм может строить вытянутые, или "игольчатые", треугольники. Однако в нашем случае это не имеет значения, так как на данный момент сетка используется только для визуализации и никаких дальнейших вычислительных операций над ней не производится. При необходимости можно выполнить перестроения [1].
![Примеры разбиений](https://cdn.hashnode.com/res/hashnode/image/upload/v1680104030629/7213933e-3665-45f6-b9e5-4a401f96ea0d.png align="center")
