Estruturas de dados para complexos celulares gerais (não tetraédricos)

Para malhas poligonais 2D, as representações da estrutura de dados QuadEdge e HalfEdge são suficientes para armazenar e permitir a consulta eficiente de todas as informações topológicas e de incidência. Existem estruturas de dados compactas e eficientes para malhas poliédricas 3D? Eu sei que tem havido algum trabalho recente sobre representações compactas para malhas tetraédricas, como, por exemplo, SOT . Não sei o suficiente sobre eles para saber se eles generalizam para malhas não-tetraédricas não estruturadas.

Eu posso imaginar que as semi-arestas podem generalizar para semi-faces com as semi-arestas associadas, mas parece que existem muitos dados para armazenar e pode haver representações mais compactas. Devo acrescentar que realmente me importo apenas em recuperar informações de facetas (como quais facetas estão no limite, quais facetas pertencem a uma determinada célula); as informações de incidência da borda não são tão úteis.

Há uma extensão de meia borda em qualquer dimensão, chamada de dardos em mapas combinatórios . Existem dois pacotes no CGAL que permitem usar esses mapas combinatórios em qualquer dimensão (veja aqui para combinatorialMaps e aqui para LinearCellComplex ).

Você pode usar essa estrutura de dados para representar qualquer objeto 3D subdividido orientado a várias tubulações . Citando a partir da página da CGAL (seção 2.4 Propriedades do mapa combinatório):

Um objeto quase múltiplo é definido como:

Um quasi-múltiplo dD é um objeto obtido através da tomada de algumas células-d isoladas e permitindo a colagem de células-d ao longo de células (d-1).

e orientável como:

É orientável se for possível incorporá-lo no espaço euclidiano e definir uma direção global "esquerda" e "direita" em cada ponto do objeto incorporado.