Я работаю над проектом, который требует преобразования супа треугольников в реальную структурированную сетку, чтобы применить операции к ней. Сетчатый объект представляет собой структуру с половинным краем со следующими элементами:
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 для перехода к следующему такому полуребру. В настоящее время решение не слишком эффективно (я не думаю), и я даже не знаю, правильно оно или нет, и такая же проблема существует и для добавления треугольников, которые примыкают к одному или меньшему количеству треугольников.
Что мне было интересно, а) действительно ли мое решение будет работать, и б) есть ли другое более широко известное / используемое решение для поиска этих краевых петель, которое я еще не смог найти?
