Structures de données pour les complexes cellulaires généraux (non tétraédriques)

Pour les maillages polygonaux 2D, les représentations de structure de données QuadEdge et HalfEdge sont suffisantes pour stocker et permettre une interrogation efficace de toutes les informations topologiques et d'incidence. Existe-t-il des structures de données compactes et efficaces pour les maillages polyédriques 3D? Je sais qu'il y a eu des travaux récents sur les représentations compactes pour les maillages tétraédriques, comme par exemple SOT . Je n'en connais pas assez pour savoir s'ils se généralisent aux mailles non tétraédriques non structurées.

Je peux imaginer que les demi-arêtes pourraient se généraliser aux demi-faces avec les demi-arêtes associées, mais il semble que ce soit beaucoup de données à stocker, et il pourrait y avoir des représentations plus compactes. Je dois ajouter que je ne me soucie vraiment que de récupérer des informations sur les facettes (comme les facettes qui se trouvent sur la frontière, quelles facettes appartiennent à une certaine cellule); les informations sur l'incidence des bords ne sont pas aussi utiles.

Il existe une extension du demi-bord dans n'importe quelle dimension, appelée fléchettes dans les cartes combinatoires . Il existe deux packages dans CGAL permettant d'utiliser ces cartes combinatoires dans n'importe quelle dimension (voir ici pour combinatorialMaps et ici pour LinearCellComplex ).

Vous pouvez utiliser cette structure de données pour représenter n'importe quel objet 3D subdivisé orientable Quasi manifold . Citation de la page Web CGAL (section 2.4 Propriétés de la carte combinatoire):

Un objet quasi-multiple est défini comme:

Un quasi-collecteur dD est un objet obtenu en prenant des cellules d isolées et en permettant de coller des cellules d le long de cellules (d-1).

et orientable comme:

Il est orientable s'il est possible de l'intégrer dans l'espace euclidien et de définir une direction globale "gauche" et "droite" en chaque point de l'objet incorporé.