Modélisation géométrique à base topologique

La modélisation à base topologique vise à proposer des structures pour représenter graphiquement des objets sur ordinateur. Ces structures permettent de représenter, manipuler et modifier des objets géométriques structurés en différente dimensions. La diversité de ces structures est due à l’existence de plusieurs classes d’objets à représenter dans différents domaines d’applications comme l’architecture, la géologie, la mécanique, le domaine médical, les jeux vidéo… En modélisation géométrique à base topologique, on différencie la topologie de l’objet de sa géométrie. La structure topologique est la décomposition de l’objet en un ensemble de cellules topologiques (sommets, arêtes, faces…). Une cellule de dimension i est appelée i-cellule, où i est inférieur ou égal à la dimension de l’objet considéré. Par exemple pour un objet de dimension 3, on peut définir les volumes en tant que 3-cellules, les faces comme 2-cellules, les arêtes comme 1-cellules et finalement les sommets comme 0-cellules. Par ailleurs, dans le cas des objets fermés, pour tout i ≥ 1, les bords d’une i-cellule sont des cellules de dimension i − 1. Ces derniers constituent sa frontière. Citons par exemple un volume de dimension 3 qui est délimité par des faces, en d’autres termes des 2-cellules. Ces cellules sont liées par des relations de voisinage. Deux types de relations topologiques peuvent se présenter : • les relations d’incidence : ces relations relient deux cellules voisines avec des dimensions différentes (i.e relient une cellule aux cellules de son bord). Par exemple, les arêtes sont incidentes à la face à laquelle elles appartiennent. • les relations d’adjacence : ces relations relient deux cellules voisines de même dimension n qui partagent un bord (par exemple deux faces voisines qui sont liées par une arête ou deux volumes reliées par un sommet) Le modèle géométrique de l’objet vise alors à compléter le modèle topologique en lui ajoutant une forme, une position, etc. Dans la littérature, il existe deux grandes familles de modèles généralement utilisés pour représenter les objets : les modèles de construction géométrique de solides (CSG) et les modèles de représentation par les bords (B-Rep). 

Les modèles de construction géométrique de solides (CSG)

Le modèle de construction géométrique de solides a été introduit par Laidlaw et al. [LTH86]. Il représente un objet par un arbre dont les feuilles sont les composantes élémentaires et les nœuds sont les opérations booléennes (la différence, l’union, l’intersection…) comme l’illustre la figure 3.1. Il aide à construire rapidement la forme d’un objet, mais son inconvénient est qu’il ne représente pas explicitement l’objet construit mais uniquement son processus de construction. De plus, la représentation d’un objet avec cette méthode n’est pas unique, plusieurs constructions pouvant aboutir au même objet. Les CSG sont généralement utilisés pour modéliser un objet via son processus constructif. Cela peut être utile en modélisation, voire en conception et usinage par ordinateur, mais ce modèle se révèle inadapté pour la simulation de solides déformables. 

Les modèles de représentation par les bords 

Au contraire des modèles CSG, la représentation par les bords (B-rep) sert à représenter un objet par le bord qui le délimite, c’est à dire sa surface en 3D, ou sa courbe en 2D. Souvent, ces modèles sont décomposés en deux parties, une partie topologique définie par les faces, les arêtes, les sommets et leurs relations d’adjacence et d’incidence et une partie géométrique définie par les points, les courbes et les surfaces. Un exemple de représentation d’un objet par les bords est donné à la figure 3.2.Par rapport au modèle CSG qui utilise uniquement les composantes de l’objet et des opérations booléennes, les modèles B-rep sont plus flexibles et offrent plusieurs types d’opérations (chanfreinage, extrusion…). Les modèles de représentation par les bords les plus utilisés sont les modèles cellulaires (voir la figure 3.3). Ils autorisent la représentation d’un objet en utilisant des cellules régulières ou quelconques. Les modèles qui consistent à décomposer un objet en un ensemble de cellules régulières (plus particulièrement des triangles) dans des dimensions différentes (i.e sommets, arêtes, triangles, tétraèdres…) sont appelés les modèles simpliciaux (voir la figure 3.3(a)). Au contraire, il existe les modèles cellulaires généraux (voir la figure 3.3(b)) qui permettent la décomposition d’un objet en un ensemble de cellules quelconques de dimensions différentes (i.e sommet, arête, face, volume…). Dans le reste de ce manuscrit nous nous intéressons uniquement aux modèles cellulaires, seuls modèles utilisés par notre approche. En effet, nous avons choisi de travailler avec un modèle cellulaire parce que l’un des objectifs de cette thèse est de créer une plate-forme générale qui permet de simuler des objets déformables représentés par différents types de maillages, potentiellement hétérogènes, c’est à dire avec différents types de n-cellules en dimension n. En utilisant des modèles simpliciaux, il est impossible de représenter directement des maillages rectangulaires en 2D, hexaédriques en 3D et, en conséquence tout maillage mélangeant les éléments, hormis en re-subdivisant chaque élément en simplexes (triangles, tétraèdres, etc.). Nous introduisons dans la suite quelques modèles cellulaires : les graphes d’incidence, puis les cartes combinatoires orientées, puis finalement, les cartes généralisées que nous avons exploitées dans notre travail.

Modèles topologiques cellulaires 

 Modèles de représentation explicite de cellules 

Graphes d’incidence Le graphe d’incidence est un modèle cellulaire général qui permet de représenter des objets en tant que graphes orientés sans cycle. C’est un graphe dans lequel les nœuds correspondent aux cellules topologiques et les arcs du graphe correspondent aux relations d’incidences qui lient une cellule de dimension i à ses bords de dimension (i − 1). Un exemple de graphe d’incidence est donné par la figure 3.4. Les faces F1 et F2, qui sont des 2-cellules, ont comme filles les arêtes (1-cellules) (a, b, c, d, e et f) qui leur sont incidentes. De même les arêtes ont comme fils les sommets (0-cellules) qui leur sont incidents. Par exemple, la face F1 est incidente à l’arête b (b est l’une des arêtes de la face F1) qui est elle-même incidente au sommet A (A est une extrémité de b). Les relations d’adjacence se déduisent par les relations d’incidence à une même cellule : par exemple, les arêtes a et b sont incidentes à un même sommet A, donc elles sont adjacentes l’une de l’autre. Les relations d’incidence entre cellules de dimensions non consécutives se retrouvent par transitivité des relations du graphe d’incidence : la face F1 est incidente au sommet A, par l’intermédiaire des arêtes a et b. Cependant, l’exemple présenté par la figure 3.5 montre qu’un même graphe d’incidence peut représenter plusieurs objets ayant des topologies différentes parce qu’il ne présente pas d’une manière explicite l’ordre dans lequel les cellules sont placées les unes par rapport aux autres. Ainsi, sur la figure, les parcours de la face F1 dans le sens trigonométrique de l’objet 1 (figure 3.5(a)) puis dans l’objet 2 (figure 3.5(b)), fournissent respectivement les deux suites d’arêtes suivantes : (a, c, e, d, f, b) et (a, c, f, d, e, b). Comme on peut le remarquer ces deux suites sont différentes. On obtient également deux suites de sommets différents. Cette différence n’apparaît malheureusement pas dans le graphe de la figure 3.5(c). Le modèle n’est pas ordonné, il en résulte des ambiguïtés. Or, pour l’implantation de certains modèles mécaniques, nous avons besoin de connaître l’ordre des sommets, en particulier pour le modèle des éléments finis. Pour cette raison, dans ce document, nous avons choisi de nous placer dans le cadre des modèles ordonnés.

Graphes d’incidence indicés

Les graphes d’incidences indicés sont une implantation particulière des graphes d’incidence sous une forme ordonnée. Ce modèle est très répandu : on le trouve dans des formats de fichiers graphiques comme OBJ par exemple. Il est à la base de la plupart des fichiers de description de maillages d’éléments finis comme, par exemple, le format msh utilisé par GMsh [GR09]. Il est également utilisé par les Vertex Arrays proposés dans la bibliothèque graphique OpenGL. Il est, enfin, le modèle topologique de base proposé dans la bibliothèque SOFA [Sof], car c’est un modèle potentiellement très rapide. Ceci est dû à la structure en tableau qui évite l’éparpillement mémoire et une utilisation efficace des caches des processeurs. Dans ce modèle, chaque cellule est désignée par un indice dans un tableau dédié aux cellules de sa dimension. Il y a donc autant de tableaux que de dimensions de cellules utiles à l’application. Pour chaque cellule, le tableau contient les relations d’incidence, voire d’adjacence, dont l’application a besoin, en désignant les cellules voisines par leur indice. Des informations géométriques peuvent être adjointes à chaque type de cellule. La plupart du temps, on associe au moins une position à chaque sommet. Á titre d’exemple, la figure 3.6 illustre une structure de base où sont d’abord énumérés les sommets (lignes démarrant par « v »pour vertex), essentiellement caractérisés par leur coordonnées de position. L’indice des sommets correspond à leur ordre d’apparition dans le fichier (en démarrant à 1). Ces sommets sont suivis par les faces triangulaires (lignes démarrant par « f »), définies seulement par les liens d’incidence avec leurs sommets (désignés par leur indice). Notons que l’ordre des sommets est important puisqu’il définit l’orientation de la face (le modèle est ainsi effectivement ordonné). Nous voyons que ce type de modèle est assez souple et peut s’adapter aux divers besoins de l’application, tant sur le plan des relations d’incidence/adjacence (on ajoute des indices supplémentaires dans les propriétés des cellules) que concernant les informations non topologiques à associer aux cellules (tout type d’information peut être ajouté aux cellules, à l’image des coordonnées des sommets). On peut le trouver sous une forme très épurée, comme dans le fichier OBJ (voir figure 3.6), ou sous une forme beaucoup plus riche. Cette souplesse se paye néanmoins par un compromis : toute information de voisinage non explicitement stockée dans la structure mais nécessaire à l’application doit être reconstituée. Pour cela, il faut, la plupart du temps, recourir à des algorithmes de recherche (sans tri) de complexité linaire en nombre de cellules. Par exemple, dans le cas de la structure OBJ, pour trouver tous les triangles incidents à un sommet, il est nécessaire de parcourir l’intégralité de la liste des triangles pour trouver tous ceux qui référencent l’indice du sommet. Pour éviter ces recherches, il est possible d’enrichir la structure afin de pré-stocker l’information de voisinage. Cependant, ce stockage pose deux problèmes. D’abord, il n’est pas de taille définie a priori, ce qui impose le recours à des structures à allocation dynamique (type tableaux de taille non fixe ou listes). Par exemple, le nombre de triangles autour de chaque sommet dépend du sommet considéré. Le second problème concerne le maintien de la cohérence des informations après une modification de la structure. Les graphes d’incidence indicés ne proposent, en effet, aucune contrainte de cohérence, a priori. Par exemple, sans contrôle de cohérence spécifique, un sommet pourrait potentiellement référencer une face comme incidente, alors qu’il n’est pas listé comme sommet de cette face. Plus la structure est complexe (i.e. avec de nombreux liens d’adjacence et d’incidence additionnels), plus il faut ajouter des contrôles de cohérence dédiés. Ces contrôles visent à assurer la réciprocité des relations d’adjacence et d’incidence, mais aussi les relations obtenues par composition. Par exemple, si un sommet est incident à une arête qui est elle-même incidente à une face, alors le sommet est incident à la face. Ou, comme autre exemple, si deux faces sont incidentes à une même arête, elles sont adjacentes. Ainsi, l’exhaustivité des contraintes de cohérence est difficile à garantir. Par ailleurs, les graphes d’incidence indicés n’offrent aucune contrainte sur le type d’objet constructible (hormis le fait d’être un assemblage de cellules). Il est alors facile d’obtenir, par exemple après une modification topologique, des assemblages non obligatoirement désirés, comme, par exemple, deux faces ou deux volumes reliés par un seul sommet. Dans [FDA05], Forest et al. recensent un nombre important de cas topologiquement dégénérés mais codables dans le modèle, qui nécessitent des traitements supplémentaires pour être évités. Finalement, on peut également critiquer le fait que les graphes d’adjacence indicés ne séparent pas nettement les informations d’ordre topologique des autres informations (tout est stocké dans un même tableau). Or, en cas de modification topologique, ce sont, d’abord et avant tout, les informations topologiques qu’il faut modifier et gérer de façon cohérente. Les autres informations peuvent être traitées dans un stade ultérieur où les nouvelles relations d’incidence et d’adjacence pourront être exploitées pour les mises à jour. Il semble ainsi assez clair qu’un modèle plus rigoureux autant sur le plan des objets modélisables que de la cohérence des relations de voisinages est nécessaire sitôt que les modifications topologiques du modèle sont fréquentes. La suite de ce chapitre présente, à ce titre, des modèles beaucoup plus solides sur le plan topologique, évitant les écueils que nous venons d’exposer : les diverses familles de cartes combinatoires.