Поиск контуров граничных кромок в сетке треугольника с половинным краем

Question

Я работаю над проектом, который требует, чтобы суп треугольника был преобразован в реальную структурированную сетку, чтобы применить операции к сетке. Меш-объект представляет собой структуру типа полуребро со следующими пунктами:

Vertex { vec3 position, int edge /* any half edge leaving the vertex */} 
HalfEdge {int vertex, int pair} 
Triangle {int vertex[3], int normal[3]} 
BoundaryEdge {int vertex, int pair, int next, int prev} 

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

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

Что я до сих пор знаю, что каждый раз, когда такое соединение встречается, код в основном рассматривает все возможные назначения для следующих и предыдущих индексов для полуребер, выходящих и входящих в вершину, соответственно, и находит первый что делает это так, что, начиная с любого полуребра, оставляя вершину, каждый другой такой полуребро (и только эти ребра) можно посещать, используя edge.pair.next, чтобы перейти к следующему полуповерхности. В настоящее время решение не слишком эффективно (я не думаю), и я даже не знаю, правильно оно это или нет, и та же проблема существует и для добавления треугольников, смежных с 1 или менее треугольниками.

Что мне было интересно, если.) Это мое решение, на самом деле работающее, и б). Есть ли еще одно широко известное/используемое решение для поиска этих контуров краев, которые я еще не смог найти?

Answer 1

Я столкнулся с подобной проблемой. Мой случай состоит в том, что несколько областей (представленных как набор треугольников) пересекаются в вершинах/вершинах, и они являются границами. Цель состоит в том, чтобы найти границу каждой области. Я обнаружил, что использование однокольцевой окрестности (т. Е. Edge.pair.next) является трудным и неэффективным.

То, что я сделал, это то, что для каждого региона я продумал все треугольники и искал граничные края. Всякий раз, когда я нахожу граничный край, я записываю start_vertex и end_vertex в хэш-карту (map [start_vertex] = end_vertex, map [end_vertex] = start_vertex). После того, как вы пройдете все треугольники в этом регионе, вы начинаете с граничной вершины и используете хэш-карту для построения границы.

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