FR 2962582 A1 20120113 FR 1002920 A 20100709 INRIAl2O.FRD.Ddf 1 Dispositif d'aide à la réalisation d'un maillage d'un domaine géométrique L'invention a trait à un dispositif et à un procédé d'aide à la réalisation d'un maillage d'un domaine géométrique défini spatialement. Le domaine à mailler peut comprendre une surface, ou une combinaison de plusieurs surfaces, et/ou un volume délimité par une ou plusieurs surfaces, au moins partiellement, ou encore une combinaison de volumes ainsi définis. Le maillage consiste à découper le domaine en un jeu d'éléments géométriques, aussi appelés cellules. Chaque cellule et le jeu de cellules dans son ensemble doivent satisfaire des conditions de validité prédéfinies, portant par exemple sur la forme géométrique des cellules (carré, triangle, tétraèdre, hexaèdre, cube, etc.) ou sur des valeurs d'angle aux sommets (respect de valeurs d'angles minimales/maximales). Ces conditions prédéfinies dépendent en grande partie de l'application à laquelle le maillage est destiné. Il existe de nombreux procédés pour générer un maillage d'un domaine. On connaît en particulier les procédés basés sur l'optimisation d'une fonction objective dépendant des coordonnées aux sommets des cellules. De tels procédés sont parfois 2 0 désignés "procédés variationnels". Pour définir la fonction objective, ces procédés utilisent le pavage barycentrique de Voronoï (en anglais "Centroidal Voronoi Tessellation", ou "CVT") et la triangulation optimale de Delaunay ("Optimal Delaunay Triangulation" ou "ODT' en anglais). 2 5 Les procédés variationnels permettent de générer efficacement et de manière robuste des maillages isotropes à l'aide de ce que l'on appelle des complexes simpliciaux. Ces procédés se révèlent particulièrement efficaces lorsqu'il s'agit de générer un maillage isotrope à partir d'éléments triangulaires (maillage d'une surface) ou tétraédriques (maillage d'un volume). 3 0 Pour certaines applications cependant, il est nécessaire, ou du moins préférable, d'utiliser des maillages générés à partir d'éléments hexaédriques (volume), ou en forme de quadrilatères (surface). C'est le cas par exemple de certaines simulations par éléments finis ou analyses numériques, en particulier dans les domaines de la dynamique des fluides, de la conception de réservoirs pour l'exploration pétrolière ou encore de la mécanique dans les domaines plastique ou fortement élastique. Dans les applications de ce type, l'utilisation d'un maillage hexaédrique permet à la fois d'obtenir une simulation plus fiable et une réduction du nombre d'éléments sur lesquels porte la simulation. Par "maillage hexaédrique", ou plus exactement "maillage hexaédrique dominant", on entend un maillage comprenant principalement des éléments de forme hexaédrique. Un maillage hexaédrique dominant peut également comprendre des éléments de forme différente, en particulier tétraédriques, pourvu que les éléments hexaédriques soient supérieurs en nombre et/ou en volume aux éléments de forme différente. Par ailleurs, certaines applications peuvent nécessiter la génération d'un maillage 15 anisotrope, c'est-à-dire qui présente des éléments qui diffèrent les uns des autres en taille et/ou en orientation, dans des zones prédéfinies du domaine. À ce jour, il n'existe aucun procédé permettant de générer des maillages à partir d'éléments hexaédriques, ou en forme de quadrilatère, qui donne pleinement satisfaction. Les procédés 2 0 actuels nécessitent une intervention manuelle au cours de l'opération de maillage. En outre, ces procédés présentent un temps de calcul important, très supérieur aux procédés variationnels classiques (de plusieurs ordres de grandeurs), qui les rend presque inutilisables en pratique. En outre, ils ne permettent pas de définir une anisotropie dans le maillage. 25 L'invention vise à améliorer la situation. On propose un dispositif d'aide à la réalisation d'un maillage, comprenant un ou plusieurs calculateurs et une mémoire stockant de premières données numériques définissant une 3 0 surface à traiter, ces premières données numériques étant organisées selon une première structure de données, un partitionneur, capable de calculer des cellules tridimensionnelles de travail à partir de points initiaux donnés, ces cellules de travail étant associées chacune à un point de l'espace, et représentées par de secondes données numériques organisées selon une seconde structure de données, un outil de pavage, capable d'actionner le partitionneur avec un premier jeu de points initiaux, définis par rapport à la surface à traiter, pour obtenir un premier jeu de cellules de travail, un évaluateur, agencé pour calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport à leurs points associés respectifs, ces moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie, et un optimiseur agencé pour actionner itérativement l'outil de pavage et l'évaluateur avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une règle calculée pour tendre à minimiser ladite grandeur cumulative. On propose également un procédé d'aide à la réalisation d'un maillage, comprenant les étapes suivantes : i. stocker de premières données numériques définissant une surface à traiter; ii. calculer un premier jeu de cellules tridimensionnelles de travail à partir d'un premier jeu de points initiaux, ces cellules de travail étant associées chacune à un point de l'espace ; iii. calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport aux points associés respectifs desdites cellules, ces 2 0 moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie ; iv. répéter itérativement l'étape ii. et l'étape iii. avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une règle calculée pour tendre à minimiser ladite grandeur cumulative. 25 Le dispositif et le procédé proposés permettent d'abord de générer un maillage hexaédrique-dominant de manière robuste, c'est-à-dire sans dégénérescences et/ou singularités, que l'on rencontre fréquemment, par exemple les triangles non-conformes, les frontières artificielles, les triangles dégénérés, les plis et les auto-intersections. 30 Un tel dispositif et un tel procédé autorisent en outre un niveau de contrôle élevé de l'opération de maillage. Il devient possible de définir un champ d'anisotropie en arrière plan, qui permet de spécifier l'orientation et les dimensions des cellules. Cela peut s'avérer indispensable pour certaines modélisations par éléments finis. Le dispositif et le procédé proposés permettent également une génération complètement automatique du maillage. Le maillage peut être généré à partir de données brutes, sans nécessité d'aucune entrée de la part de l'utilisateur, en particulier aucun étiquetage des données initiales. L'optimiseur tendant à minimiser la grandeur cumulative grâce, en particulier, à la mise en oeuvre de méthodes numériques, le temps nécessaire à la génération d'un maillage reste limité, même dans le cas d'un maillage de grande taille (entre 500 000 et 1 million de cellules). D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée ci-après, et des dessins sur lesquels : - la figure 1 représente un schéma fonctionnel d'un dispositif d'aide au maillage; 2 0 - la figure 2 représente un tableau illustrant une partie d'un structure de stockage de données pour le dispositif de la figure 1; - la figure 3 représente un tableau illustrant une autre partie de la structure de stockage de données de la figure 2; - la figure 4 représente un tableau illustrant une autre partie encore de la structure de stockage de données de la figure 2; les figures 5 à 9 représentent respectivement un tableau illustrant une partie d'une 3 0 structure de stockage de données respective pour le dispositif de la figure 1; 25 la figure 10 représente un schéma fonctionnel d'une partie du dispositif de la figure 1; la figure 11 représente un ordinogramme illustrant une fonction de contrôle pour le 5 dispositif de la figure 1; la figure 12 est analogue à la figure 1 pour un développement du dispositif de maillage de cette figure 1; 10 - les figures 13 à 15 présentent respectivement un tableau illustrant une partie d'une structure de stockage de données respective pour le dispositif de la figure 12; la figure 16 est analogue à la figure 11 pour le dispositif de maillage de la figure 12; 15 Les dessins annexés pourront non seulement servir à compléter l'invention, mais aussi contribuer à sa définition, le cas échéant. La figure 1 représente un dispositif lA d'aide au maillage d'un domaine, à usage, en particulier, lorsque le domaine en question prend la forme d'une ou plusieurs surfaces. Le dispositif lA comprend de la mémoire 10, un ou plusieurs processeurs, désignés dans leur ensemble par la référence 20, et une bibliothèque de fonctions 30. Les microprocesseurs 20 peuvent exécuter une ou plusieurs fonctions de la bibliothèque 30, tout en interagissant avec la mémoire 10 lorsque cela est nécessaire. La bibliothèque 30 peut être maintenue, au moins partiellement, sur tout dispositif à mémoire, morte ou vive, amovible ou non, inscriptible ou non. La bibliothèque 30 peut par exemple être maintenue en partie sur un disque dur d'ordinateur, sur un support optique de données, sur de la mémoire vive d'ordinateur ou autres. 20 25 30 Le dispositif lA comprend un premier stockage de données 100, organisé dans la mémoire 10 et adapté pour stocker une représentation d'une surface à traiter sous une forme numérique. Numériquement, cette surface à traiter peut être définie sous de multiples formes, telles qu'un ou plusieurs fichiers d'images, un ou plusieurs fichiers de maillages surfaciques, un ou plusieurs fichiers issus de logiciels de conception assistée par ordinateur, d'une ou plusieurs équations paramétriques, d'un fichier comprenant les coordonnées d'un ensemble de points ou autres. Le dispositif 1A comprend en outre un second stockage de données 102, organisé dans la mémoire 10 et adapté pour stocker une représentation d'un ou plusieurs triangles dans l'espace sous une forme numérique. Le second stockage de données 102 est organisé selon une structure qui met en relation, pour chaque triangle stocké, un identifiant de triangle, des données de définition d'un plan support de ce triangle, et des valeurs de coordonnées spatiales pour chacun des sommets du triangle en question. Ici, chaque plan support est défini par une équation du type de celle indiquée en annexe 2 0 A.1.1. Dans cette annexe, et dans la suite de la présente description, Nj est un vecteur de dimension trois et Bj un scalaire, qui définissent en combinaison l'un de l'autre un plan de l'espace. Le plan défini par le vecteur Nj et par le scalaire Bj sera désigné Fj. Dans le second stockage de données 102, les données de définition d'un plan support Fj 2 5 peuvent comprendre les données de définition du vecteur Nj et du scalaire Bj. Les figures 2 à 4 montrent un exemple de réalisation de la seconde structure de données 102 sous la forme d'un ensemble comprenant un premier tableau 1000, ou tableau Tabl, un second tableau 1002, ou tableau Tab2, et un troisième tableau 1004, ou tableau Tab3. 30 Chaque ligne du tableau Tabl (figure 2) maintient une relation entre un identifiant de point, par exemple une valeur d'index, ou d'indice, génériquement noté qj, et des valeurs de coordonnées spatiales, par exemple en tant que projections sur les différents axes d'un repère orthonormé. Ces valeurs de coordonnées sont génériquement et respectivement notées qjx, qjy, et qjz pour le point qj. En pratique, le repère en question est choisi de manière à correspondre aux données contenues dans les fichiers de définition de la surface, le cas échéant. Ici, comme dans le reste de la présente description, il faut comprendre que le stockage des 10 données d'identification, par exemple les valeurs d'index ou d'indices, est optionnel. Ces données ont été mentionnées ici, et portées sur les dessins, pour aider à la compréhension de l'invention. En pratique, les cases des tableaux représentés sont contiguës en mémoire : ceci rend implicite le schéma d'indice et rend pratiquement inutile le stockage des données d'identification, et plus généralement de valeurs d'indices, en mémoire. 15 Chaque ligne du tableau Tab2 (figure 3) maintient une relation entre un identifiant de triangle, par exemple une valeur d'index, génériquement noté Tj, et les identifiants de chacun des points formant un sommet de ce triangle tels que stockés dans le tableau Tab 1, ou un pointeur vers les lignes correspondantes de ce tableau Tab 1. Par exemple, le triangle 2 0 Tj a pour sommets les points qm, qn et qp, dont les coordonnées sont mémorisées dans le tableau Tab 1. Chaque ligne du tableau Tab3 (figure 4) maintient une relation entre un identifiant de triangle, tel que stocké dans le tableau Tab2, ou un pointeur vers la ligne correspondante de 2 5 ce tableau Tab2, et des valeurs de définition d'un plan support. Pour un triangle générique, noté Ti, ces valeurs comprennent des valeurs de vecteur Nj en projection sur la base d'un repère orthonormé, respectivement notées Njx, Njy et Njz, et une valeur de scalaire Bj. Le dispositif lA comprend encore un troisième stockage de données 104, organisé dans la 3 0 mémoire 10 et adapté pour stocker une représentation d'un ou plusieurs points de l'espace sous une forme numérique.5 Le troisième stockage de données 104 est organisé selon une structure qui met en relation, pour chaque point stocké, un identifiant de point, par exemple une valeur d'index, et un jeu de coordonnées spatiales de ce point. La figure 5 montre un exemple de réalisation du troisième stockage de données sous la forme d'un quatrième tableau 1006, ou tableau Tab4. Chaque ligne du tableau Tab4 maintient une relation entre un identifiant de point, par 10 exemple une valeur d'index, noté génériquementXj, et des valeurs de coordonnées spatiales de ce point, par exemple en tant que projections sur les axes d'un repère orthonormé. Pour un point générique X , ces coordonnées sont respectivement notées xj, yj, et zj dans le tableau Tab4. 15 Le dispositif 1A comprend de plus un quatrième stockage de données 106, organisé dans la mémoire 10 et adapté pour stocker une représentation d'une ou plusieurs cellules spatiales sous une forme numérique. Le quatrième stockage de données 106 est organisé selon une structure qui met en relation, 2 0 pour chaque cellule, un identifiant de cellule, des données de définition de chacun des plans limitant la cellule dans l'espace. En option, la structure du quatrième stockage de données 106 met en outre en relation chaque identifiant de cellule avec des valeurs de coordonnées d'un point de l'espace. 25 Les données de définition d'un plan peuvent comprendre des données de définition d'un vecteur et d'un scalaire, conformément à l'équation de l'annexe A.1.1. La figure 6 montre un exemple de réalisation du quatrième stockage de données 106 sous la forme d'un cinquième tableau 1008, ou tableau Tab5. 30 Chaque ligne du tableau Tab5 maintient une relation entre un identifiant de plan, par exemple une valeur d'index, génériquement noté Pj, des valeurs de vecteur N] en projection sur la base d'un repère orthonormé, respectivement notées Njx, Njy et Njz, une valeur de scalaire Bj, un premier identifiant de cellule Vk, et un second identifiant de cellule Vl. En option, un tableau complémentaire (non représenté) peut, en chacune de ses lignes, maintenir une relation entre un identifiant de cellule et les coordonnées d'un point de l'espace, ou l'identifiant d'un point dont les coordonnées spatiales sont maintenues dans un autre stockage. Le dispositif lA comprend en outre un cinquième stockage de données 108, organisé dans la mémoire 10 et adapté pour stocker une représentation d'un ou plusieurs polygones dans l'espace sous une forme numérique, ainsi que des données symboliques et des données de typage relative à chaque sommet de polygone. Le cinquième stockage de données 108 est organisé selon une structure qui met en relation, pour chaque polygone, un identifiant de polygone, une définition de chaque sommet de ce polygone, une définition du plan support de ce polygone, et, en option, une données d'appartenance à un jeu de polygone en tant que sous-ensemble des polygones stockés. La structure du cinquième stockage de données 108 maintient également une relation entre 2 0 chaque identifiant de sommet et un jeu de données symboliques d'une part et au moins une donnée de typage d'autre part. Le stockage de la définition du plan support est optionnel : à chaque fois ce plan support peut être déduit des autres données stockées. En pratique, cependant, le dispositif lA 2 5 présente une efficacité améliorée (temps de calcul) lorsque ce plan support est mémorisé. La figure 7 montre un exemple de réalisation du cinquième stockage de données 108 sous la forme d'un sixième tableau 1010, ou tableau Tab6. 3 0 Chaque ligne du tableau Tab6 maintient une relation entre un identifiant de sommet, par exemple une valeur d'index, noté génériquement Sj, des valeurs de coordonnées spatiales, par exemple en tant que valeurs de projection dans un repère orthonormé, notées Six, Sjy et Sjz pour un sommet Sj, un identifiant de polygone Lk, une donnée de typage Rj, et un jeu de données symboliques Symbj, ou un pointeur vers de telles données. Selon une option illustrée sur la figure 8, le cinquième stockage de données 108 comprend en outre un septième tableau 1012, ou tableau Tab 7, dont chaque ligne maintient une relation entre un identifiant de polygone Lj et un identifiant de point Xi valant pointeur vers des valeurs de coordonnées de ce point dans l'espace. Le dispositif lA comprend encore un sixième stockage de données 110, organisé dans la mémoire 10 et adapté pour stocker une représentation d'un ou plusieurs triangles de l'espace sous une forme numérique. Le sixième stockage de données 110 est organisé selon une structure qui met en relation, pour chaque triangle, une donnée d'identification de triangle, des données de coordonnées spatiales de chacun des sommets de ce triangle, des données de définition d'un plan support de ce triangle et des valeurs de coordonnées d'un point de l'espace. La figure 9 montre un exemple de réalisation du sixième stockage de données 110 sous la 2 0 forme d'un huitième tableau 1014, ou tableau Tab7. Chaque ligne du tableau Tab7 maintient une relation entre un identifiant de triangle, par exemple une valeur d'index, génériquement noté Tj, les identifiant de trois points formant sommets, notés Cjl , Cj2 et Cj3 pour un triangle Tj et un identifiant de point supplémentaire 2 5 Dk. En variante, le sixième stockage 110 pourrait prendre une forme analogue aux réalisations des figures 2 à 4. 3 0 La bibliothèque 30 comprend une fonction de découpage 300 adaptée pour établir un jeu de données représentant une collection d'éléments géométriques plans en tant que décomposition d'une surface tridimensionnelle. La première fonction de découpage 300 est adaptée pour établir des données définissant une collection T de triangles Tj en tant que découpage de ladite surface. Ici, ces données de définition comprennent un jeu de valeurs de coordonnées pour chacun des sommets de chaque triangle Tj, ainsi que des données de définition du plan support de chacun de ces triangles. La première fonction de découpage 300 peut être vue ici comme une fonction de triangulation. La première fonction de découpage 300 peut être appelée avec une donnée de paramètre m définissant le nombre de triangles Tj du jeu T. La valeur de l'entier m peut être fournie à l'appel de la fonction de découpage 300 et/ou être établie à une valeur par défaut. La valeur de l'entier m contribue à la définition de la finesse du découpage de la surface à traiter. Dans une variante de réalisation, la première fonction de découpage 300 est agencée de manière à appeler une fonction de découpage ou de triangulation extérieure au dispositif 1A. En outre, la première fonction de découpage 300 peut être optionnelle dans certains cas. La bibliothèque 30 comprend en outre une fonction génératrice 302 adaptée pour établir un jeu de données de localisation d'une collection de points à partir de données représentant une surface. Ces données de localisation sont établies de manière que les points soient distribués aléatoirement, ou pseudo-aléatoirement, sur la surface en question. 25 Dans une forme de réalisation, la fonction génératrice 302 est adaptée pour recevoir des données représentant une collection de triangles en tant que données de définition de la surface à traiter. Ces données peuvent comprendre des données de localisation de chacun des sommets de chaque triangle ainsi que des données représentant un plan-support pour 3 0 chacun des triangles. Les données de localisation peuvent comprendre des valeurs de coordonnées dans un repère orthonormé. Chaque plan support peut être défini au moyen de20 données de définition d'un vecteur Nj et d'un scalaire Bj, conformément à l'équation de l'annexe A.l.l. La fonction génératrice 302 est adaptée pour établir des données de localisation pour 5 chaque point de la collection, par exemple sous la forme d'un jeu de valeurs de coordonnées. La fonction génératrice 302 accepte en tant que paramètre une valeur d'entier, notée n, déterminant le nombre points de la collection. La valeur du paramètre n peut être fournie à 10 l'appel de la fonction génératrice 302 ou être établie à une valeur par défaut prédéterminée. Chaque point généré est tel qu'il appartient à l'un des plans supports et se trouve à l'intérieur du triangle correspondant à ce plan-support. La valeur de l'entier n est un paramètre de la fonction génératrice 302, et plus généralement 15 du dispositif d'aide au maillage. Elle détermine un ordre de grandeur du nombre de mailles souhaitées. La valeur de l'entier n peut être passée en tant que paramètre à l'appel de la fonction génératrice 302. Pour la plupart des applications du dispositif 1A, la valeur du paramètre n est supérieure à la valeur du paramètre m. 2 0 Dans une autre forme de réalisation, de remplacement ou de complément, la fonction génératrice 302 est adaptée pour générer la collection de point à partir d'une ou plusieurs équations paramétriques en tant que définition de surface. En variante, la fonction génératrice 302 peut être adaptée pour permettre une définition 2 5 manuelle de certains au moins des points de la collection, par exemple par entrée de coordonnées, ou pointage sur une représentation graphique de la surface à traiter au moyen d'une interface graphique d'utilisateur. Lorsque la surface S est définie sous une forme mathématique, les points sont générés de 3 0 manière à appartenir à la surface S, à une précision numérique près. Bien que les performances du dispositif lA soient assez largement indépendantes de la collection de points, il est préférable que ces points soient distribués de manière sensiblement uniforme sur la surface à traiter : cela améliore sensiblement les performances de calcul. La bibliothèque 30 comprend une fonction de partitionnement 304 adaptée pour établir un jeu de données représentant une collection de cellules spatiales sous une forme numérique, à partir d'un jeu de données représentant une collection de points de l'espace sous une forme numérique. 10 La collection de cellules correspond ici à la décomposition de l'espace en cellules dites de Voronoï calculée à partir de la collection de points. Chacun de ces points forme le centre d'une cellule de Voronoï. 15 La fonction de partitionnement 304 peut être adaptée pour calculer des données définissant l'ensemble des plans limites de chaque cellule de Voronoï sous une forme numérique. Ces données peuvent comprendre les données nécessaires à une définition cartésienne de chaque plan limite, par exemple les valeurs d'un vecteur Nj en projection sur la base d'un repère et d'un scalaire Bj, conformément à l'équation d'un plan donnée en l'annexe A.1.1. 20 La bibliothèque 30 comprend en outre une fonction d'intersection 306, adaptée pour établir un jeu de données représentant le résultat de l'intersection d'une collection de cellules spatiales et d'une surface de l'espace, sous une forme numérique. Autrement dit, la fonction d'intersection 306 est adaptée pour déterminer un jeu de cellules restreint par rapport à une 2 5 surface donnée, à partir d'un jeu de cellules donné. La fonction d'intersection 306 peut être adaptée pour recevoir un jeu de données définissant une collection de triangles en tant que surface de l'espace, d'une part, et un jeu de données définissant une collection de cellules spatiales, d'autre part, et pour établir, sur la base de 3 0 ces jeux de données, un jeu de données définissant une collection de polygones de l'espace en tant qu'intersection de la collection de triangles et de la collection de cellules spatiales.5 Chaque triangle de la collection peut être défini par des données définissant son plan-support, par exemple par exemple les valeurs d'un vecteur Nj en projection sur la base d'un repère et d'un scalaire Bj, des données de localisation de ses sommets, par exemple des valeurs de coordonnées dans un repère orthonormé. Chaque cellule de la collection peut être définie par des données définissant ses plans limites et des données de localisation de son centre. Pour chaque point formant un sommet de polygone, la fonction d'intersection 306 est adaptée pour établir une ou plusieurs équations définissant localisation de ce point en fonction de données de localisation d'un ou plusieurs sommets d'un triangle et de données de localisation du centre d'une cellule. Ces données de localisation comprennent par exemple des valeurs de coordonnées dans un même repère orthonormé. Plus généralement, la fonction d'intersection 306 est adaptée pour déterminer une ou plusieurs équations déterminant des données de localisation de chaque point se trouvant à l'intersection de la surface à traiter et d'une cellule spatiale. 2 0 La fonction d'intersection 306 est également adaptée pour déterminer de manière exacte la position de chacun des sommets de polygones, c'est-à-dire pour résoudre les équations déterminant les données de localisation Chaque sommet d'un polygone peut être défini au moyen d'un jeu d'équations définissant 2 5 trois plans de l'espace. La fonction d'intersection 306 est en outre adaptée à établir, pour chaque sommet de polygone, une donnée de typage dont la valeur dépend de la configuration de ce sommet par rapport à la surface à traiter d'une part, et aux cellules spatiales, d'autre part. 30 Lorsque la surface à traiter est représentée par un jeu de triangles, la données de typage est susceptible de prendre une première valeur, ou valeur "A", lorsque le sommet correspond à un sommet de l'un des triangles, une seconde valeur, ou valeur "B", lorsque le sommet est localisé à l'intersection d'une arête de triangle et d'un segment reliant deux centres de cellules appartenant à un même triangle de Delaunay, une troisième valeur, ou valeur "C", lorsque le sommet est localisé sur le plan support d'un triangle, à l'intérieur de ce triangle, et de deux segments reliant respectivement trois de cellules appartenant à un même triangle de Delaunay. L'article "Isotropie remeshing with fast and exact computation of restricted Voronoi diagram", de D.-M. YAN, B. LÉVY, Y. LIU, F. SUN, et W. WANG, Computer Graphics Forum 28,5, 1445-1454 (2009) expose un procédé pour calculer exactement un diagramme de Voronoï restreint sur une surface définie par un ensemble de triangles, en particulier en sa section 3 intitulée "RVD computation". L'invention n'est pas limitée à cette méthode de calcul du diagramme de Voronoï restreint : elle englobe toutes les méthodes connues et à venir. La bibliothèque 30 comprend encore une fonction de décomposition 308 adaptée pour établir un jeu de données représentant une collection de triangles en tant que décomposition d'un polygone. Chaque sommet du polygone correspond à l'un au moins des triangles de la collection, et chaque sommet d'un triangle de la collection correspond à un sommet du polygone. Le dispositif comprend une fonction sommation 310 adaptée pour établir, à partir de données représentant un élément surfacique de l'espace, et de données représentant un point de l'espace, une grandeur représentant la somme des moments des points appartenant à l'élément surfacique par rapport audit point de l'espace, ces moments étant déterminés selon une fonction normative choisie, éventuellement avec application d'une matrice d'adaptation représentative d'un champ d'anisotropie sur l'élément surfacique. La fonction normative choisie est d'ordre supérieur ou égal à un lorsqu'on applique une matrice d'adaptation non identitaire, et d'ordre strictement supérieur à deux dans le cas contraire. La fonction sommation 310 est adaptée pour calculer la grandeur Flp(T) définie par la formule de l'annexe A.2.2, où MT représente une matrice d'anisotropie, xo correspond au point par rapport auquel les différents moments sont calculés et T désigne l'élément surfacique sur lequel travaille la fonction sommation 310. La matrice MT augmente le poids de certaines composantes, c'est-à-dire privilégie certaines directions de l'espace par rapport à d'autres. Le moment est défini à l'aide d'une norme particulière, définie en annexe A.1.8. Cette norme est définie sur la base la somme de la distance projetée sur différents axes formant un repère orthogonal, élevée à une puissance entière p. Autrement dit, la fonction sommation est capable de calculer la somme de moments de points de cellules de travail par rapport à des points respectivement associés à ces cellules de travail, ces moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie; 2 0 Dans le cas où la matrice d'anisotropie MT diffère de la matrice identité, la puissance entière p peut être prise égale ou supérieure à 1. Dans les autres cas, cette puissance entière p est prise supérieure ou égale à 2. De préférence, la valeur de l'entier p est choisie paire pour simplifier les calculs. 2 5 La fonction normative peut être d'ordre infini, c'est-à-dire considérée comme limite d'une fonction normative d'ordre p, lorsque p tend vers l'infini. La fonction Flp(T) s'exprime alors selon la formule de l'annexe A.2.8. Dans le cas général d'un jeu 12 de cellules ni la fonction normative Flp(X) d'ordre infini s'exprime conformément à la formule de l'annexe A.2.7. 30 Chaque élément géométrique d'intégration peut être découpé en secteurs, sur chacun desquels l'une des coordonnées x, y ou z est supérieure aux autres en valeur absolu, ce qui facilite grandement le calcul de la grandeur cumulative. Par exemple, chaque simplexe d'intégration sera divisé en 4 secteurs, lorsqu'il s'agit d'un élément en deux dimensions, en 8 secteurs lorsqu'il s'agit d'un élément en trois dimensions. Lorsque l'élément surfacique T prend la forme d'un triangle, la fonction sommation 310 établit en tant que grandeur cumulative correspondant à cet élément, le résultat de l'évaluation de la formule de l'annexe A.2.3, en combinaison de la formule de l'annexe A.2.4. Ci est un vecteur de dimension 3 représentant des valeurs de coordonnées d'un sommet i du triangle T exprimées dans le même repère orthonormé que les coordonnées du point xo. Pour le reste, les éléments des formules A.2.3 et A.2.4 sont définis à l'annexe A.1 La bibliothèque 30 comprend encore une fonction de dérivation 312 adaptée pour évaluer une valeur de gradient de la grandeur cumulative par rapport à un jeu de points, pour un élément géométrique de l'espace, à partir des coordonnées et des équations de chacun des sommets de cet élément. La fonction de dérivation 312 peut être adaptée pour traiter des éléments triangulaires. La fonction dérivation calcule alors le gradient défini à l'annexe A.3.1 en appliquant les formules des annexes A.3.2 à A.3.4 et A.3.6 à A.3.10. Pour chacun des sommets Cl, C2 et C3 d'un triangle T, la fonction applique l'une des 2 5 formules des annexes A.3.8, A.3.9 et A. 3.10 en fonction de données de typage associées à ce sommet, conformément au tableau suivant : Valeur de la donnée de typage Formule du gradient A Néant B A.3.8 C A.3.920 La bibliothèque 30 comprend en outre une fonction d'amélioration 314 adaptée pour, sur la base de données représentatives d'un jeu de points de l'espace, d'une donnée de valeur de fonction objectif correspondant à ce jeu de point, et d'une donnée de valeur d'un gradient de cette fonction objective relative à ce jeu de point, établir des données représentant un jeu de points amélioré, c'est-à-dire susceptible de faire évoluer ladite grandeur cumulative d'une manière déterminée, pour tendre à minimiser cette grandeur cumulative. La fonction amélioration 314 peut mettre en oeuvre toute méthode d'optimisation, en particulier de type descente de gradient, de type newtonienne ou de type quasi-newtonienne, par exemple la méthode dite "BFGS" (pour méthode de BROYDEN-FLETCHER-GOLDFARBSHANNO") ou la méthode "L-BFGS" (pour "limited memory BFGS" ou méthode BGFS à mémoire limitée). Pour plus d'informations sur la méthode L-BFGS, on pourra se reporter aux publications suivantes : - "On the Limited Memory Method for Large Scale Optimization", D. C. Liu et J. NOCEDAL, Mathematical Programming B, 45, 3, pages 503 à 528; "A limited Memory Algorithm for Bound Constrained Optimization", R .H. BYRD, P. Lu 2 0 et J. NOCEDAL, SIAMJournal on Scientifac and Statistical Computing, 16, 5, pages 1190 à 1208. La bibliothèque 30 comprend encore une fonction de post-traitement 316, qui sera explicitée plus loin, et qui permet d'obtenir un maillage hexaédrique ou cubique à partir 2 5 d'un jeu de points. La bibliothèque 30 comprend enfin une fonction d'optimisation 318 dont le fonctionnement est illustré sur la figure 10. 3 0 À l'opération 400, on initialise la fonction d'optimisation. Les variables internes sont mises à la valeur nulle, et les différentes structures de stockage de la mémoire 10 sont vidées des données qu'elles contiennent. À l'opération 402, on appelle la fonction de découpage 300 avec les données contenues dans le premier stockage 100. La fonction de découpage 300 retourne un jeu T de triangles 5 Tj qui est mémorisé dans le second stockage 102. Ici, l'opération 402 est représentée en trait tireté car elle est optionnelle. Lorsque la surface à traiter est maintenue dans le premier stockage 100 sous une forme 10 triangulée, l'opération 402 peut être ignorée. Dans le cas où la surface à traiter a été définie sous une forme triangulée cependant, l'opération 402 peut être mise en oeuvre pour obtenir une triangulation différente de la surface à traiter, par exemple présentant une finesse (nombre total de triangles) différente. 15 À l'opération 404, on appelle la fonction génératrice 302 pour le jeu T de triangles Tj contenus dans le second stockage 102. En option, une valeur d'entier naturel m est passée en tant que paramètre. La fonction génératrice 302 retourne un jeu X de points X (j étant une valeur entière susceptible de varier de 1 à m) générés aléatoirement et appartenant chacun à au moins un triangle Ti du jeu T. Un enregistrement est crée dans le troisième stockage de 2 0 données 104 pour chaque point Xj. À l'opération 406, on initialise une variable formant compteur de boucle, notée i. À l'opération 408, on appelle la fonction de partitionnement 304 avec les données du 2 5 troisième stockage 104. La fonction de partitionnement 304 retourne un jeu Q de cellules de Voronoï Shi qui est mémorisé dans le quatrième stockage de données 106. Par exemple, on crée une ligne dans le tableau Tab5 pour chaque plan limite Pj. On enregistre en tant qu'identifiants de cellules associés au plan Pj les identifiants des points 3 0 formant les centres respectifs des cellules en question, par exemple Xk et Xl. 19 À l'opération 410, on appelle la fonction d'intersection 306 avec les données du second stockage 102 et les données du quatrième stockage 106. La fonction d'intersection 306 retourne un jeu R de polygones Ri, qui est mémorisé dans le cinquième stockage de données 110. En particulier, les équations déterminant les coordonnées de chacun des sommets Sj de chacun des polygones Ri sont stockées en tant que données symboliques dans le cinquième stockage de données 108. Les données de typage sont également mémorisées. Dans les opérations 406 à 410, la fonction d'optimisation, la fonction de partitionnement 304 et la fonction d'intersection 306 agissent, en combinaison les unes des autres, à la manière d'un partitionneur, capable de calculer des cellules tridimensionnelles de travail à partir de points initiaux donnés, ces cellules de travail étant associées chacune à un point de l'espace, et représentées par des données numériques organisées selon une structure de données. Dans les opérations 404 à 410, la fonction d'optimisation et la fonction génératrice 302 agissent, en combinaison l'une de l'autre, à la manière d'un outil de pavage, capable d'actionner le partitionneur avec un premier jeu de points initiaux, définis par rapport à la surface à traiter, pour obtenir un premier jeu de cellules de travail. 2 0 À l'opération 412, on appelle la fonction de décomposition 308 avec les données du cinquième stockage 108. La fonction de décomposition 308 retourne un jeu T de triangles Ti dont chaque sommet correspond à un sommet du jeu R de polygones Ri. Le jeu T est mémorisé dans le sixième stockage de données 110. Par exemple, on crée une ligne pour chaque triangle Tj dans le tableau Tab7 avec pour identifiant de sommet Cji l'identifiant Sj 2 5 de l'un des sommets du polygone maintenu dans le tableau Tab6. Comme identifiant de point complémentaire Dk, on stocke l'identifiant Xj du point formant le centre de la cellule de Voronoï correspondante. La fonction d'optimisation 318 et la fonction de décomposition 308, en combinaison l'une de l'autre agissent à la manière d'un décomposeur, capable de calculer des éléments géométriques simples à partir d'une cellule de travail et de son point 3 0 associé respectif, les sommets chaque élément géométrique simple comprenant des sommets de la cellule de travail ou le point associé respectif, et chaque sommet de la cellule de travail appartenant à un élément géométrique simple. À l'opération 414, on appelle la fonction de sommation 310 avec les données du sixième stockage 110. À chaque fois le résultat d'un appel est additionné au résultat des appels précédents. Le résultat est mémorisé sous la forme d'une variable F. La fonction d'optimisation 318 et la fonction de sommation 310 agissent t alors comme un évaluateur, agencé pour calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport à leurs points associés respectifs, ces moments étant déterminés selon une fonction normative choisie. À l'opération 416, on évalue une condition de sortie de boucle. Cette condition peut porter sur un nombre d'itérations déjà effectuée, par exemple un nombre d'itération égal à une valeur prédéfinie, sur l'atteinte d'une limite de puissance de calcul, et/ou sur la valeur de F, par exemple sur le fait que la valeur de F soit inférieure ou non à une valeur plancher Fmin ou que la norme du gradient de F soit inférieure à une valeur plancher Epsilon. Si la condition de l'opération 416 n'est pas vérifiée, alors, à l'opération 418, on appelle la fonction de dérivation 312 avec les données du sixième stockage 110. À chaque fois le résultat d'un appel de la fonction de dérivation 312 est additionné au résultat des appels 2 0 précédents. Le résultat est stocké sous la forme d'une variable gradF. À l'opération 420, on appelle la fonction d'amélioration 314 avec le contenu du troisième stockage, les valeurs de F et de gradF. La fonction d'amélioration 314 retourne un jeu de points amélioré qui est mémorisé dans le troisième stockage 104, en remplacement du jeu 2 5 précédent. On incrémente le compteur de boucle à l'opération 422. Et l'on retourne à l'étape 408. En d'autres termes, la fonction d'optimisation 318, en combinaison de la fonction 3 0 d'amélioration 314, sert d'optimiseur agencé pour actionner itérativement l'outil de pavage et l'évaluateur avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une règle calculée pour tendre à minimiser ladite grandeur cumulative. Lorsque la condition de l'opération 416 est vérifiée, on peut appeler la fonction de post-traitement 316 avec les données du troisième stockage 104. Cette opération est indiquée en 5 trait tireté car elle est facultative. La figure 12 représente un dispositif 1B d'aide au maillage d'un domaine en tant que développement du dispositif 1A. Le dispositif 1B est à usage, en particulier, lorsque le domaine en question prend la forme d'un volume Vau moins partiellement délimité par une 10 surface S. Le dispositif 1B se distingue d'abord du dispositif lA en ce qu'il comprend en outre un septième stockage de données 112, organisé dans la mémoire 10, et capable de stocker une représentation d'une ou plusieurs cellules de l'espace sous une forme numérique. 15 Le septième stockage de données 1.12 est organisé selon une structure qui met en relation, pour chaque cellule, une donnée d'identification de cellule, des données de coordonnées spatiales de chacun des sommets de cette cellule, des données de définition de chacun des plans limites de cette cellule et des données de coordonnées d'un point de cette cellule ou 2 0 un pointeur vers de telles données. La figure 12 montre un exemple de réalisation du septième stockage de données sous la forme d'un neuvième tableau 1016, ou tableau Tab9, d'un dixième tableau 1018, ou tableau TablO, et d'un onzième tableau 1020, ou tableau Tabl 1. Chaque ligne du tableau Tab9 maintient en relation un identifiant de point, tel qu'une valeur d'index, génériquement noté qj, des valeurs de coordonnées de ce point dans un repère orthonormé, à savoir qjx, qjy et qjz pour le point qj, et un identifiant de cellule, par exemple Mk pour le point qj. 25 30 Chaque ligne du tableau Tab 10 maintient en relation un identifiant de plan, tel qu'une valeur d'index, génériquement noté Pj, des données de projection du vecteur Nj et du scalaire Bj selon la définition d'un plan Pj donnée en annexe A.1.1, notées Njx, Njy, Njz et Bj, et des données d'identifiant de cellule Mk. Chaque ligne du tableau Tab 11 maintient en relation un identifiant de point, tel qu'une valeur d'index, génériquement noté qj, des valeurs de coordonnées de ce point dans un repère orthonormé, à savoir qjx, qjy et qjz pour le point qj, et un identifiant de cellule, par exemple M pour le point qj. Dans ce mode de réalisation, le sixième stockage 110 maintient un identifiant de point de cellule, ce qui permet de mémoriser une représentation de tétraèdres sous une forme numérique en tant que dual des cellules de Voronoï. Le dispositif 1B diffère du dispositif 1A également en ce que les points générés par la fonction génératrice 302 sont aléatoirement distribués à l'intérieur du volume délimité, au moins partiellement, par une surface représentée sous une forme numérique. Cette surface peut être définie par un jeu de triangles. Le dispositif 1B diffère également du dispositif 1A en ce que le jeu de données résultant de 2 0 la fonction d'intersection 306 correspond à l'intersection d'un ensemble de cellules spatiales et du volume délimité par une surface donnée. L'intersection correspond à un ensemble de cellules spatiales restreint par le volume délimité par la surface donnée. Cette surface peut être définie par un jeu T de triangles Tj. 2 5 La donnée de typage attribuée à chaque sommet de la cellule résultat est susceptible de prendre une quatrième valeur, ou valeur "D", lorsque le sommet correspond à un sommet d'une cellule spatiale initiale. Dans le dispositif 1B, la fonction de décomposition 308 est modifiée de manière à établir 30 un jeu de données représentant une collection de tétraèdres à partir d'un jeu de données représentant une cellule spatiale associée à un point de cette cellule. La collection de tétraèdre correspond à une décomposition de la cellule spatiale : chaque tétraèdre présente un sommet formé par le point associé à la cellule et trois sommets formés par des sommets de cette cellule, chaque sommet de la cellule formant un sommet d'au moins un tétraèdre. La fonction d'intégration 310 est modifiée de manière à mettre en oeuvre la formule de l'annexe A.2.2, dans laquelle T désigne maintenant un élément volumique. Dans le cas où la surface à traiter est représentée sous une forme triangulée, l'élément volumique prend la forme du tétraèdre comprenant les sommets xo, Cl, C2, C3. La fonction d'intégration 310 peut alors calculer la grandeur cumulative en évaluant la formule de l'annexe A.2.5, qui doit être considérée en combinaison de la formule de l'annexe A.2.6. La fonction de dérivation 312 peut dans ce cas évaluer la formule de l'annexe A.3.1 en combinaison des formules des annexes A.3.2, A.3.3 et A.3.5 à A3.3.10. Cette dernière 15 formule s'applique lorsque la donnée de typage du sommet C prend la valeur "D". Comme le montre la figure 16, la fonction d'optimisation 318 est modifiée de manière à stocker le résultat de l'appel de la fonction d'intersection 306 dans la septième structure de données (opération 410) et pour appeler la fonction sommation 310 sur les données 2 0 contenues dans ce septième stockage (opération 412). La fonction de post-traitement 316 est agencée pour calculer la triangulation de Delaunay correspondant à un jeu de points donné. La fonction de post-traitement est en outre agencée pour regrouper les tétraèdres (ou triangles) issus de la triangulation de Delaunay de manière 2 5 à former un nombre maximum d'hexaèdres (ou quadrilatères), tout en respectant les angles minimaux admissibles. Ceci peut être réalisé au moyen du procédé décrit dans l'article " Generating a Mixed Mesh of Hexahedra, Pentahedra and Tetrahedra from an Underlying Tetrahedral Mesh" de S. MESHKAT et D. TALMOR, International Journal for Numerical Methods in Engineering, volume 49, pages 17 à 30, 2000. 30 Dans une variante de réalisation, la fonction de post-traitement 316 est agencée pour calculer le diagramme de Voronoï tridimensionnel correspondant à un jeu de points donnés, puis pour agencer les cellules ainsi obtenues en éléments cubiques. L'invention vient d'être décrite en relation avec les dispositifs lA et 1B. Il apparaît que cette invention peut également être exprimée sous la forme d'un procédé d'aide à la réalisation d'un maillage, qui peut être illustré par la figure 10 notamment. Ce procédé comprend une étape de stockage de données numériques définissant une surface 10 à traiter, par exemple correspondant à l'opération 402. Dans l'étape suivante, correspondant par exemple aux opérations 404 à 410, on calcule un premier jeu de cellules tridimensionnelles de travail à partir d'un premier jeu de points initiaux, ces cellules de travail étant associées chacune à un point de l'espace. 15 L'opération 414 s'apparente à une étape de calcul d'une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport aux points associés respectifs desdites cellules, ces moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant 2 0 un champ d'anisotropie. Ces deux dernières étapes sont répétées itérativement avec à chaque fois un jeu de points initiaux tirés des jeux précédents, conformément à l'opération 420, selon une règle calculée pour tendre à minimiser la grandeur cumulative en question. Les étapes du procédé peuvent être mise en oeuvre par une suite d'instructions, par exemple sous la forme d'un produit de programme informatique. Ce produit peut être mémorisé sur tout support de données, en particulier de type optique. 25 3 0 On cite maintenant quelques publications traitant de maillage anisotrope. "Anisotropic Polygonal Remeshing", P. ALLIEZ, D. COHEN-STEINER, O. DEVILLERS, B. LÉvY, et M. DESBRUN, ACM Transactions on Graphics, volume 22, numéro 3, pages 485-493, juillet 2003. Dans ce document, on propose de dessiner les lignes de courbure. "Variational shape approximation", D. COHEN-STEINER, P. ALLIEZ et M. DESBRUN, SIGGRAPH conference proceedings, 2004. Dans ce document, on propose de minimiser directement l'erreur d'approximation. "Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations", Q. Du et D. WANG, International Journal for Numerical Methods in Engineering, volume 56, pages 1355 à 1373, 2003. Dans ce document, on propose de généraliser la notion de CVT avec un champ continu d'anisotropie. Cette notion n'a été expérimentée qu'en deux dimensions. "Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams", S. VALETTE, J.-M. CHASSERY et R. PROST, IEEE Transactions on Visualization and Computer Graphics, volume 14, pages 369 à 381, 2008. Dans ce document, on utilise la même définition de l'anisotropie que dans le document précédent. On propose cependant une approximation discrète fonctionnant sur la base d'une pré-triangulation du domaine. On 2 0 utilise donc des cellules de Voronoï anisotropiques et approximatives. Elle nécessite de mettre en oeuvre une méthode de relaxation pour faire converger la fonction objective. Elle ne permet pas d'obtenir de maillage tétraédrique-dominant. "Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation", 2 5 F. LABELLE, J. R. SHEWCHUK, SCG'03 : Proceedings of the nineteenth annual symposium on Computational geometry, pages 191 à 200, 2003. Ce document propose une généralisation des diagrammes de Voronoï en définissant une anisotropie attaché aux sommets. 3 0 "Fully-Automated Hex-Dominant Mesh Generation with Directionality Control via Packing Rectangular Solid Cells", S. YAMAKAWA et K. SHIMADA, International Journal for Numerical Methods in Engineering, volume 57, pages 2099 à 2129, 2003. Ce document propose une méthode heuristique dite du "bubble packing" ou "emballage de bulles" en français, qui s'avère pratiquement inefficace lors d'un passage à l'échelle industrielle (augmentation du nombre de mailles entre 500 000 et 1 million). On cite également quelques publications sur le maillage avec des éléments en forme de quadrilatères. "Localized Quadrilateral Coarsening", J. DANIELS-II, C. T. SILVA, et E. COHEN, Computer 10 Graphics Forum, volume 28, pages 1437 à 1444, 2009, propose de transformer directement, et d'optimiser, des maillages réalisés avec des éléments en forme de quadrilatères "Automatic Conversion of Triangular Meshes into Quadrilateral Meshes with 15 Directionality", T. ITOH et K. SHIMADA, International Journal of CAD/CAM, 2001, propose d'adapter la méthode du "bubble packing" pour optimiser les quadrilatères sur des surfaces. Cette méthode souffre, entre autres, des mêmes inconvénients que celle du "bubble packing". 20 "Quad-Dominant Mesh Adaptation Using Specialized Simplicial Optimization", K.-F. TCHON et R. CAMARERO, 15th International Meshing Roundtable conference proceedings, pages 21 à 38, 2006 et "An Incremental Approach to Feature Aligned Quad Dominant Remeshing", Y.-K. LAI, L. KOBBELT et S.-M. Hu, ACM SPM conference proceedings, pages 137 à 145, 2008, proposent une adaptation d'un maillage à éléments en 25 forme de quadrilatères à partir de maillages triangulaires de très haute définition. "Spectral surface quadrangulation", S. DONG, P.-T. BREMER, M. GARLAND, V. PASCUCCI, et J. C. HART, ACM Transactions on Graphics, volume 25, numéro 3, pages 1057 à 1066, 2006, et "Spectral quadrangulation with orientation and alignment control", J. HUANG, 3 0 M. ZHANG, J. MA, X. LIU, L. KOBBELT, et H. BAO, ACM Transactions on Graphics, volume 27, article numéro 147, page 9, 2008, proposent d'utiliser l'ensemble de Morse5 d'une fonction propre de Laplacien. "Planar Parameterization for Closed Manifold Genus-g Meshes Using Any Type of Positive Weights", D. STEINER et A FISCHER", Journal of Computing and Information Science Engeneering, volume 5, numéro 2, 2005, "Designing quadrangulations with discrete harmonic forms", Y. TONG, P. ALLIEZ, D. COHEN-STEINER, et M. DESBRUN, SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, 2006, et "Surface Parameterization using Branched Coverings", F. KALBERER, M. NIESER et K. POLTHIER, Computer Graphics Forum, volume 26, 2007 proposent de réaliser des contours de lignes iso u,v d'une surface définie sous une forme paramétrique. "Periodic global parameterization", N. RAY, W. C. LI, B. LÉvY, A. SHEFFER et P. ALLIEZ, ACM Transactions on Graphics, volume 25, numéro 4, pages 1460 à 1485, 2006, et "Mixed-integer quadrangulation", D. BOMMES, and H. ZIMMER, et L KOBBELT, ACM Transactions on Graphics, volume 28, numéro 3, 2009, proposent d'utiliser des fonctions périodiques et une optimisation partiellement en nombres entiers. Tous les procédés proposés dans ces documents traitent des objets présentant des arêtes vives, ce qui nécessite que l'utilisateur définisse manuellement certaines contraintes. Au 2 0 contraire, le dispositif proposé reconstruit lui-même de telles arêtes, sans intervention de l'utilisateur, en particulier d'étiquetage des données. On cite enfin quelques publications traitant du maillage d'un volume avec des éléments hexaédriques. "Methods for Multisweep Automation", J. SHEPHERD, S. A. MITCHELL, P. KNUPP et D. WHITE, 9`h International Meshing Roundtable Conference Proceedings, 2000, propose une méthode directe basée sur un balayage multiple. 3 0 "Unconstrained Paving and Plastering: A New Idea for All Hexahedral Mesh Generation", M. L. STATEN, S. J. OwEN, et T .D. BLACKER, International Meshing Roundtable 28 25 Conference Proceedings, 2005, propose une méthode directe de pavage et de lissage. "Advances in octree-based all-hexahedral mesh generation: handling sharp features", L. MARÉCHAL, 18`h International Meshing Roundtable Conference Proceedings, 2009, 5 propose une méthode directe à base de d'arbres octaires. "Volumetric parameterization and trivariate B-spline fitting using harmonic functions", T. MARTIN, E. COHEN, et M KIRBY, SPM'08:- Proceedings of the 2008ACMsymposium on Solid and physical modeling, 2008, propose une méthode directe basée sur la realization 10 d'un contour d'un volume défini sous une forme paramétrique. "Tensor-Guided Hex-Dominant Mesh Generation with Targeted All-Hex Regions", V. VYAS et K. SHIMADA, 18m International Meshing Roundtable Conference Proceedings, 2009, propose une méthode directe utilisant les surfaces de flux d'un champ de tenseurs. 15 "H-Morph : An Indirect Approach to Advancing Front Hex Meshing", S. J. Owen et S. SAIGAL, International Journal for Numerical Methods in Engineering, volume 49, 2000, propose une méthode indirecte prévoyant la construction d'un maillage à éléments tétraédriques et de transformer ce maillage en un maillage hexaédrique-dominant en 2 0 utilisant une approche frontale. "Anisotropic Tetrahedral Meshing via Bubble Packing and Advancing Front", S. YAMAKAWA et K. SHIMADA, International Journal for Numerical Methods in Engineering, 2003, propose de réaliser ce premier maillage en utilisant le procédé de 2 5 "paquet de bulles" ("bubble packing" en anglais) avec des cellules cubiques. Il s'agit d'une méthode essentiellement heuristique, difficile à calculer et qui passe mal à l'échelle. Au contraire, le dispositif proposé utilise une fonction objective définie sous une forme analytique, aisée à calculer et assez peu sensible à une augmentation d'échelle, en vue notamment d'être utilisée en milieu industriel. 30 L'invention n'est pas limitée aux modes de réalisation décrit ci-dessus, à titre d'exemple uniquement, mais englobe toutes les variantes que pourra envisager l'homme de l'art. Annexe 1 - Conventions de notation A.1.2 A.1.3 A.1.1 A.1.4 V2 [x2, Y2, z2] A.1.5 Vl * V2 = [xlx2, Y1Y2, zlz2]t A.1.6 Va=V*V*...*V(catimes) V =x+y+z llvilp = I xI P + I yI P + IzIP Ui = MT(Ci - xo) dA/dB = (aai/ab, )z,~ A.1.11 IIVIC = max {IxI, Iyl, Izl} A.1.7 A.1.8 A.1.9 A.1.10 31 Annexe 2 - Fonction objectif A.2.1 FLP(x) = > f 1IMy[Y - xz]IIPdy ainsi A.2.2 FP= f IIMT(Y - xo)IIpdY T Fp= (ITI) Ua*2*3 2 a+/3+7-P ET Lp A.2.4 ITI = 1/2 INII ITI 14' * U2 * U3 0+p \ 3 a+/3+ry=p ET Lp A.2.6 ITI = 1/6 U1 - (U2 x U3) A.2.7 FLP(x) = E f IIMy[Y - x2]II: dy S2inn A.2.8 Fr = f IIMT(Y - xo) II~ dY T A.2.3 A.2.5 32 Annexe 3 - Gradient de fonction objectif A.3.1 dFP (xo, C1, C2, C3) _ dX dF p dFLp dCi dFP dC2 dFP dC3 dxo + dC1 dX + dC2 dX + dC3 dX A.3.2 dFP = d(IT1 Ep) = EpdIT1 + 1TIdEp oéUi-1**U3- t 7 a+/3+y=p;a>1 A.3.3 dFLp = ,3U1 * U3--1 * U3 dUlU2U3 a+p+y=p;Q>l 1 1/U1' *Ua*U3-1 _a+/3+y=p;y> 1 _ A.3.4 dUlU2U3 -1 [N x (U2 - U3)]t [N x (U3 - U1)]t [N x (U1 - U2)]t A.3.5 dU1U U3 = 1/6 ([U2 x U3]t [U3 x U1]t [U1 x U2]» 2 dFP - dFPMT dCi dUi dFP dFP dFLp dF P dxo dCl dC2 dC3 ([C-xo]t [xi-C]A.3.8 dC = ([xi_xo}t)_1 [C ô o]` o o 2111 A.3.6 A.3.7 33 [xi-xo]t -1 [C-xo]t [x1-c], 0 A.3.9 dC = C [x2-xo]t J ([c-xolt o [x2-clt [Nl]t \ 0 0 0 [xi-xo]t 1 1 [C-xolt [xi-C]t 0 0 A.3.10 dC = C [x2-xolt J f [c-xo]t o [x2-c], o I [x3-xo]t \ [C-xo]t 0 0 [x3-c], 34 REVENDICATIONS1. Dispositif d'aide à la réalisation d'un maillage, comprenant un ou plusieurs calculateurs et une mémoire stockant : - de premières données numériques définissant une surface à traiter, ces premières données numériques étant organisées selon une première structure de données (100); - un partitionneur (304;306;318), capable de calculer des cellules tridimensionnelles de travail à partir de points initiaux donnés, ces cellules de travail étant associées chacune à un point de l'espace, et représentées par de secondes données numériques organisées selon une seconde structure de données (108,110); - un outil de pavage (302;318), capable d'actionner le partitionneur (304;306;308) avec un premier jeu de points initiaux, définis par rapport à la surface à traiter, pour obtenir un premier jeu de cellules de travail; - un évaluateur (310;312;318), agencé pour calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport à leurs points associés respectifs, ces moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie; - un optimiseur (318;314) agencé pour actionner itérativement l'outil de pavage et 2 0 1'évaluateur avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une règle calculée pour tendre à minimiser ladite grandeur cumulative. 2. Dispositif selon la revendication 1, dans lequel le partitionneur (304;306;318) est agencé pour calculer un jeu de cellules de Voronoï à partir des points initiaux donnés et 2 5 pour calculer les cellules de travail en tant que restriction du jeu de cellules de Voronoï par rapport à la surface à traiter selon des règles prédéfinies. 3. Dispositif selon la revendication 2, dans lequel l'outil de pavage actionne le partitionneur (304;306;308) avec un premier jeu de points initiaux appartenant à la surface 3 0 à traiter, et dans lequel les cellules de travail calculées par le partitionneur (304;306;308) correspondent à l'intersection des cellules de Voronoï sur la surface à traiter. 35 4. Dispositif selon la revendication 2, dans lequel l'outil de pavage (300) actionne le partitionneur (304;306;308) avec un premier jeu de points initiaux compris dans un volume au moins partiellement délimité par la surface à traiter, et dans lequel les cellules de travail calculées correspondent à l'intersection dudit volume et des cellules de Voronoï. 5. Dispositif selon l'une des revendications précédentes, dans lequel la fonction normative est d'ordre pair. 6. Dispositif selon l'une des revendications précédentes, dans lequel la fonction normative est d'ordre infini. 7. Dispositif selon l'une des revendications précédentes, dans lequel l'évaluateur (310;312) est agencé pour calculer une grandeur cumulative dérivée représentant un gradient de ladite grandeur cumulative par rapport aux points respectifs des cellules de travail. 8. Dispositif selon la revendication 7, dans lequel l'optimiseur (314;318) est agencé pour actionner l'outil de pavage (318;302) et l'évaluateur (310;312) avec à chaque fois un 2 0 jeu de points initiaux résultant d'une fonction d'amélioration (314) prenant en compte ladite grandeur cumulative, le jeu de points précédent et la grandeur cumulative dérivée. 9. Dispositif selon la revendication 8, dans lequel la fonction d'amélioration (314) met en oeuvre une méthode d'optimisation de type descente de gradient, de type Newtonienne ou 2 5 de type quasi-Newtonienne. 10. Dispositif selon l'une des revendications précédentes, comprenant en outre un décomposeur (308;318) capable de calculer des éléments géométriques simples à partir d'une cellule de travail et de son point associé respectif, les sommets chaque élément 3 0 géométrique simple comprenant des sommets de la cellule de travail ou le point associé respectif, et chaque sommet de la cellule de travail appartenant à un élément géométriquesimple. 11. Dispositif selon la revendication 9, dans lequel l'évaluateur est agencé pour appeler le décomposeur (308) avec l'ensemble des cellules de travail, et pour calculer la grandeur 5 cumulative sur chaque élément géométrique simple retourné par le décomposeur (308;318). 12. Dispositif selon l'une des revendications précédentes, dans lequel le partitionneur (304;306) est agencé pour associer à chaque sommet d'une cellule de travail une donnée de typage en fonction de la position de ce sommet par rapport à la surface à traiter. 13. Dispositif selon la revendication 12 prise dans son rattachement à l'une des revendications 2 à 4, dans lequel la donnée de typage associée à chaque sommet est également fonction de la position de ce sommet par rapport aux cellules de Voronoï. 15 14. Dispositif selon l'une des revendications 12 à 13 prise dans son rattachement à l'une des revendications 7 à 9, dans lequel l'évaluateur (310;312) est agencé pour calculer une partie au moins de la grandeur cumulative dérivée à l'aide d'une fonction choisie selon la donnée de typage associée au sommet mis en jeu. 2 0 15. Dispositif selon l'une des revendications précédentes, comprenant un outil de post-traitement (316) agencé pour réaliser un maillage essentiellement hexaédrique sur la base du dernier jeu de points initiaux calculé. 2 5 jeu de points initiaux, ces cellules de travail étant associées chacune à un point de l'espace ; c) calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport aux points associés respectifs desdites cellules, ces 3 0 moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie ; 37 10 16. Procédé d'aide à la réalisation d'un maillage, comprenant les étapes suivantes : a) stocker de premières données numériques définissant une surface à traiter; b) calculer un premier jeu de cellules tridimensionnelles de travail à partir d'un premierd) répéter itérativement l'étape b) et l'étape c) avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une règle calculée pour tendre à minimiser ladite grandeur cumulative. 17. Procédé selon la revendication 16, dans lequel l'étape b) comprend les sous-étapes : bl) calculer un jeu de cellules de Voronoï à partir d'un premier jeu de points initiaux ; b2) calculer, en tant que les cellules de travail, une restriction du jeu de cellules de Voronoï par rapport à la surface à traiter selon des règles prédéfinies. 18. Procédé selon la revendication 17, dans lequel les points du premier jeu de points initiaux appartiennent chacun à la surface à traiter, et dans lequel ladite restriction comprend l'intersection des cellules de Voronoï sur la surface à traiter. 19. Procédé selon la revendication 17, dans lequel le premier jeu de points initiaux est compris dans un volume au moins partiellement délimité par la surface à traiter, et dans lequel ladite restriction comprend l'intersection dudit volume et des cellules de Voronoï. 20. Procédé selon l'une des revendications 16 à 19, dans lequel l'étape d) comprend les sous-étapes suivantes : 2 0 dl) calculer une grandeur cumulative dérivée du gradient de ladite grandeur cumulative par rapport aux points respectifs des cellules de travail ; d2) calculer un jeu de points initiaux résultant d'une fonction d'optimisation prenant en compte ladite grandeur cumulative, le jeu de points précédent et la grandeur cumulative dérivée ; 2 5 d3) répéter itérativement l'étape b) et l'étape c) avec à chaque fois un jeu de points initiaux tirés le l'étape d2). 21. Procédé selon la revendication 20, dans lequel la fonction d'optimisation met en oeuvre une méthode de type descente de gradient, de type Newtonienne, ou de type quasi- 3 0 Newtonienne. 22. Procédé selon l'une des revendications 16 à 21, dans lequel l'étape c) comprend les sous-étapes suivantes : cl) calculer des éléments géométriques simples à partir de chaque cellule de travail et de son point associé respectif, les sommets chaque élément géométrique simple comprenant des sommets de la cellule de travail ou le point associé respectif, et chaque sommet de la cellule de travail appartenant à un élément géométrique simple ; c2) calculer la grandeur cumulative sur chaque élément géométrique simple de l'étape cl). 23. Procédé selon la revendication 17, dans lequel l'étape b2) comprend les opérations suivantes : b2.1) calculer les coordonnées de chaque sommet de chaque cellule de travail, en tant que restriction du jeu de cellules de Voronoï par rapport à la surface à traiter selon des règles prédéfinies ; b2.2) associer à chaque sommet une donnée de typage en fonction de la position de ce sommet par rapport à la surface à traiter. 24. Procédé selon la revendication 23, dans lequel l'étape c) comprend la sous-étape suivante : 2 0 cl) calculer une grandeur cumulative représentant la somme des moments des points des cellules de travail par rapport à leurs points associés respectifs, ces moments étant déterminés selon une fonction normative choisie, d'ordre supérieur ou égal à deux et/ou selon une matrice d'adaptation représentant un champ d'anisotropie ; c2) calculer une grandeur cumulative dérivée à l'aide d'une fonction choisie selon la 25 donnée de typage associée au sommet mis en jeu. 25. Procédé selon l'une des revendications 16 à 24, comprenant en outre l'étape suivante : e) réaliser un maillage essentiellement tétraédrique sur la base du dernier jeu de points 3 0 initiaux calculé.