Я ищу концепцию для хранения (в 3-мерном евклидовом пространстве) граней, ребер и вершин, чтобы
- информация (об отношении) не дублируется
- Запросы для примыкающих и соседних граней / ребер / вершин выполняются быстро
- сетка не ограничена соединенными гранями одной и той же обмотки
Определения
- сосед лица: лицо, которое имеет грань с этим лицом
- сосед вершины: вершина, которая находится на другом конце ребра, разделяющего эту вершину
- adjecent edge: ребро, которое разделяет ту же вершину конечной точки с этим ребром
Я рассмотрел структуру данных Half-Edge, но запросы к ней действительно работают, только когда все связанные грани имеют одинаковую обмотку.
Например, рассмотрите этот псевдокод для доступа к таким связанным объектам:
face.neighbors #the neighboring faces
face.edges #the edges shared by this face (in the right winding order)
face.verts #the vertex of that face (in the right winding order)
edge.v1, edge.v2 #the two vertex making up an edge
vertex.edges #the edges this vertex shares
vertex.neighbors # the neighbors of this vertex along each shared edge