Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
DEVICE FOR AIDING THE PRODUCTION OF A MESH OF A GEOMETRIC DOMAIN
Document Type and Number:
WIPO Patent Application WO/2012/004531
Kind Code:
A2
Abstract:
Device for aiding the production of a mesh, comprising a first data structure storing first numerical data defining a surface to be processed, a partitioner (304;306;318) calculating three-dimensional work cells on the basis of given initial points, each of these work cells being associated with a point in space, a tiling tool (302;318) actuating the partitioner (304;306;308) with a first set of initial points, defined with respect to the surface to be processed, so as to obtain a first set of work cells, an evaluator (310;312;318), calculating a cumulative quantity representing the sum of the moments of the points of the work cells with respect to their respective associated points, and an optimizer (318;314) iteratively actuating the tiling tool and the evaluator with on each occasion a set of initial points drawn from the previous sets, according to a rule calculated so as to tend to minimize said cumulative quantity. The moments are determined according to a chosen nonnative function, of order higher than or equal to two and/or according to an adaptation matrix representing an anisotropy field.

Inventors:
LEVY BRUNO (FR)
YANG LIU (CN)
Application Number:
FR2011/051608
Publication Date:
January 12, 2012
Filing Date:
July 06, 2011
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
INST NAT RECH INF AUTOMAT (FR)
LEVY BRUNO (FR)
YANG LIU (CN)
International Classes:
G06T17/20; G06F17/10; G06F17/50
Foreign References:
Other References:
D,-M', YAN, B. LÉVY, Y. LIU, F. SUN, W. WANG: "Isotropie remeshing with fast and exact computation of resiricted Voronoi diagrim", COMPUTER GRAPHICS FORUM, vol. 28, no. 5, 2009, pages 1445 - 1454
D. C. LIU, J. NOCEDAL: "On the Limited Momory Method for Large Scale Optimization", MATHEMATICAL PROGRAMMING B, vol. 45, no. 3, pages 503 - 528
R .H. BYRD, P. LU, J. NOCEDAL: "A limited Memory Algorithm for Bound Constrained Optimization", SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, vol. 16, no. 5, pages 1190 - 1208, XP009137721
S. MESHKAT, D. TALMOR: "Generating a Mixed Mesh of Hexahedra, Pentahedra and Tetrahedra from an Underlying Tetrahedral Mesh", INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, vol. 49, 2000, pages 17 - 30
P. ALLIEZ, D. COHEN-STEINER, O. DEVILLERS, B. LÉVY, M. DESBRUN: "Anisotropic Polygonal Remeshing", ACM TRANSACTIONS ON GRAPHICS, vol. 22, no. 3, July 2003 (2003-07-01), pages 485 - 493
D. COHEN-STEINER, P. ALLIEZ, M. DESBRUN: "Variational shape approximation", SIGGRAPH CONFERENCE PROCEEDINGS, 2004
Q. DU, D. WANG: "Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations", INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, vol. 56, 2003, pages 1355 - 1373
S. VALETTE, J.-M. CHASSERY, R. PROST: "Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams", IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, vol. 14, 2008, pages 369 - 381, XP011344465, DOI: doi:10.1109/TVCG.2007.70430
F. LABELLE, J. R. SHEWCHUK: "Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh génération", SCG'03 : PROCEEDINGS OF THE NINETEENTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY, 2003, pages 191 - 200, XP058235498, DOI: doi:10.1145/777792.777822
S.YAMAKAWA, K.SHIMADA: "Fully-Automated. Hex-Dominant Mesh Generation with Directionality Control via Packing Rectangular Solid Cells", INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, vol. 57, 2003, pages 2099 - 2129
J. DANIELS-II, C. T. SILVA, E. COHEN: "Localized Quadrilateral Coarsening", COMPUTER GRAPHICS FORUM, vol. 28, 2009, pages 1437 - 1444
T. ITOH, K. SHIMADA: "Automatic Conversion of Triangular Meshes into Quadrilateral Meshes with Directionality", INTERNATIONAL JOURNAL OF CAD/CAM, 2001
K.-F. TCHON, R. CAMAKERO: "Quad-Dominant Mesh Adaptation Using Specialized Simplicial Optimization", 15TH INTERNATIONAL MESHING ROUNDTABLE CONFERENCE PROCEEDINGS, 2006, pages 21 - 38
Y.-K. LAI, L. KOBBELT, S.-M. HU: "An Incremental Approach to Feature Aligned Quad Dominant Remeshing", ACM SPM CONFERENCE PROCEEDINGS, 2008, pages 137 - 45, XP058248656, DOI: doi:10.1145/1364901.1364921
S. DONG, P.-T. BREMER, M. GARLAND, V. PASCUCCI, J. C. HART, 2006: "Spectral surface quadrangulation", ACM TRANSACTIONS ON GRAPHICS, vol. 25, no. 3, pages 1057 - 1066
J. HUANG, M. ZHANG, J. MA, X. LIU, L. KOBBELT, H. BAO: "Spectral quadrangulation with orientation and alignment control", ACM TRANSACTIONS ON GRAPHICS, vol. 27, no. 147, 2008, pages 9
"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, vol. 5, no. 2, 2005
Y. TONG, P. ALLIEZ, D. COHEN-STEINER, M. DESBRUN: "Designing quadrangulations with discrete harmonic forms", SGP '06: PROCEEDINGS OF THE FOURTH EUROGRAPHICS SYMPOSIUM ON GEOMETRY PROCESSING, 2006
F. KALBERER, M. NIESER, K. POLTHIER: "Surface Parameterization using Branched Coverings", COMPUTER GRAPHICS FORUM, vol. 26, 2007
N. RAY, W. C. LI, B. LÉVY, A. SHEFFER, P. ALLIEZ: "Periodic global parameterization", ACM TRANSTICTIONS ON GRAPHICS, vol. 25, no. 4, 2006, pages 1460 - 1485, XP058157915, DOI: doi:10.1145/1183287.1183297
D.BOMMES, H.ZIMMER, I., KOBBELT: "Mixed-integer quadrangulation", ACM TRANSACTIONS ON GRAPHICS, vol. 28, no. 3, 2009, XP058145398, DOI: doi:10.1145/1531326.1531383
J. SHEPHERD, S. A. MITCHELL, P. KNUPP, D. WHITE: "Methods for Multisweep Automation", 9TH INTERNATIONAL MESHING ROUNDTABLE CONFÉRENCE PROCEEDINGS, 2000
M.L. STATEN, S. J. OWEN, T.D. BLACKER: "Unconstrained Paving and Plastering: A New Idea for All Hexahedral Mesh Génération", INTERNATIONAL MESHING ROUNDTABLE CONFERENCE PROCEEDINGS, 2005
L. MARÉCHAL: "Advances in octree-based all-hexahedral mesh generation: handling sharp features", 18TH INTERNATIONAL MESHING ROUNDTABLE CONFÉRENCE PROCEEDINGS, 2009
T. MARTIN, E. COHEN, M KIRBY: "Volumetric parameterization and trivariate B-spline fitting using harmonie functions", SPM'08: PROCEEDINGS OF THE 2008 ACM SYMPOSIUM ON SOLID AND PHYSICAL MODELING, 2008
V. VYAS, K. SHIMADA: "Tensor-Guided Hex-Dominant Mesh Generation with Targeted All-Hex Régions", 18TH INTERNATIONAL MESHING ROUNDTABLE CONFERENCE PROCEEDINGS, 2009
S. J. OWEN, S. SAIGAL: "H-Morph : An Indirect Approach to Advancing Front Hex Meshing", INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, vol. 49, 2000
S. YAMAKAWA, K. SHIMADA: "Anisotropic Tetrahedral Meshing via Bubble Packing and Advancing Front", INTEMALIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 2003
Attorney, Agent or Firm:
JACOBSON, Claude et al. (FR)
Download PDF:
Claims:
Revendications

1. 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,1 10);

- un outil de pavage (302 ;3.18), 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 (31 Q;3 i 2 ;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'adaptatio représentant un champ d'anisotropie;

- un optimiseur (318;3 i4) 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.

2. Dispositif selon la revendication l . dans lequel, le partitionneur (304;306;318) est agencé pour calculer un jeu de cellules de Voronoï à partir des points initiaux donnés et 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 à 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.

4. Dispositif selon la revendication 2, dans lequel l'outil de pavage (300) actionne le parti liormeur (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 travai l calculées correspondent à l'intersection dudii volume et des cellule* 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 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 œuvre une méthode d'optimisation de type descente de gradient, de type ewtonierme ou de type quasi-Newtonienne.

10. Dispositif selon l'une des revendications précédentes, comprenant en outre un déconiposeur (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 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. î 1. 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 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;3Û6) 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 VoronoL 14. Dispositif selon l'une des revendications 12 à 13 prise dans son rattachement à Tune 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 enjeu. 15. Dispositif selon l'une des revendications précédentes, comprenant un outil de posttraitement (316) agencé pour réaliser un maillage essentiellement hexaédrique sur la base du dernier jeu de points initiau calculé,

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 premier 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 desdiies 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 un champ d'anisotropie ; d) 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 :

) calculer un jeu de cellules de Voronoï à partir d'un premier jeu de points initiaux ; fa2) 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 revendicati on 17, dans lequel les points du premier jeu de points initiaux appartiennent chacun à la surfac à traiter, et dans lequel ladite restriction comprend l'intersection des cellules de Voronoï sur la surface à traiter,

19. Procédé selon la revendication 1 7, 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 i 6 à 19, dans lequel l'étape d) comprend les sous-étapes suivantes ;

d 1 ) calculer une grandeur cum uiative déri ée du gradient de ladite grandeur cumu lative 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 ;

d3) répéter itérativement l'étape b) et l'étape e) 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 œu vre une méthode de type descente de gradient, de type Newtonierme, ou de type quasi- Newtonierme.

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 37, 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 :

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 etv'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 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 essen .tellement tétraédrique sur la base du dernier jeu de points initiaux calculé.

Description:
Dispositif d'aide à la réalisation d'un ai age d'un domaine géométrique

L'invention a trait à un dispositif et à un procédé d'aide à la réalisation d'un maiilage 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 m e ou plusieurs surfaces, au moins partiellement, ou encore une combinaison de volumes ainsi définis.

Le maiilage consiste à découper le domaine en un jeu d'éléments géométriques, aussi appelés cellules. Chaque cellule et îe jeu de cellules dans son ensemble doivent satisfaire des conditions de validité prédéfinies, portant par exemple SOT 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 maiilage est destiné,

Il existe de nombreux procédés pour générer un maiilage 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 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 "Centwidal Voronoi Tessellation", ou "CVT') et la triangulation optimale de Delaimay ("Optimal Delauna Triangulation ' " ou "ΟΟ en anglais).

Les procédés variationneis permettent de générer efficacement et de manière robuste des maiOages isotropes à l'aide de ce que l'on appelle des complexes simpiiciaux. Ces procédés se révèlent particulièrement efficaces lorsqu'il s'agi de générer un maiilage isotrope à partir d'éléments triangulaires (maiilage d'une surface) ou tétraédriques (maiilage d'un volume).

Pour certaines applications cependant, il est nécessaire, ou du moins préférable, d'utiliser des maiîlages générés à partir d'éléments hexaédnques (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 raailîage hexaédrique permet à la fois d'obtenir une simulation plus fiable et mie 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 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 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 variatiomieis 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.

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 surface à traiter, ces premières données numériques étant organisées selon une première structure de données, un parti tionneur, 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 é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 rnaillage. 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 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.

Le dispositif et le procédé proposés permettent d'abord de générer un mailiage 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,

Un tel dispositif et un tel procédé autorisent en outre un niveau de contrôle élevé de l'opération de mailiage. 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 permetten également une génération complètement automatique du mailiage. Le mailiage 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 œuvre de méthodes numériques, le temps nécessaire à la génération d'un mailiage reste limité, même dans le cas d'un mailiage 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 mailiage; îa figure 2 représente un tableau illustrant une partie d'un structure de stockage de données pour ie 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 structure de stockage de données respectiv pour le dispositif de la figure 1 ; la figure 10 représente un schéma foncti onnel d'une partie du dispositi f de la figure

la figure 1 1 représente un ordinogramme illustrant mie fonction de contrôle pour le disposi tif de la fi gure 1 ; la figure 12 est analogue à la figure 1 pour un développement du dispositif de raailîage de cette figure 1 ; - les figures 13 à 15 présentent respectivement un tableau llustrant 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 1 1 pour le dispositif de mai liage de la figure 12; 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 1 A d'aide au raailîage d'un domaine, à usage, en particulier, lorsque le domaine en question prend la forme d'une ou plusieurs surfaces.

Le dispositif 1 A comprend de la mémoire 10, un ou plusieurs processeurs, désignés dans leur ensemble par îa référence 20, et une bibliothèque de fonctions 30. Les microprocesseurs 20 peuvent exécuter une ou plusieurs fonctions de ia 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 ira disque dur d'ordinateur, sur un support optique de données, sur de la mémoire vive d'ordinateur ou autres.

Le dispositif 1 A 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 5 qu'un ou plusieurs fichiers d'images, un ou plusieurs fichiers de maillages surfaciques, im 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.

10 Le dispositif 1 A comprend en outre un second stockage de données 102, organisé dans ia 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, 15 pour chaque triangle stocké, un identifi t 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 20 Â.1.1. Dans cette annexe, et dans ia suite de ia 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 25 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 Tabî , un second tableau 1002, ou tableau Tab2, et un troisième tableau 1004, ou tableau Tab3.

"¾ o

Chaque ligne du tableau Tabi (figure 2) maintient une relation entre un identifiant de point. n par exemple une valeur d'index, ou d'indice, génériquement noté qf, et des valeurs de coordonnées spatiales, par exemple en tant que projections sur les différents axes d'un repère ortbonormé. Ces valeurs de coordonnées sont génériquement et respectivement notées qjx, qj , et qfz pour' î.e point qf.

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 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.

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 Tabl, ou un pointeur vers les lignes correspondantes de ce tableau Tab 1. Par exemple, le triangle Tj a pour sommets les points qm, qn et qp, dont les coordonnées sont mémorisées dans le tableau Tabl.

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 ce tableau Tab2, et des valeurs de définition d'un plan support. Pour un triangle générique, noté Tj, 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 scal ire Bj.

Le dispositif l A comprend encore un troisième stockage de données 104, organisé dans la mémoire 10 et adapté pour stocker une représentation d'un ou plusieurs points de l'espace sous une forme numérique. 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 exemple une valeur d'index, noté génériquementA/, et des valeurs de coordonnées spatiales de ce oint, par exemple en tant que projections sur les axes d'un repère orthonormé, Pour un point générique Xj, ces coordonnées sont respectivement notées xj, yj et zj dans le tableau Tab4, Le dispositif 1 À 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 uns forme numérique.

Le quatrième stockage de données 106 est organisé selon une structure qui met en relation, 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. 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 TabS,

Chaque ligne du tableau Tab5 maintient une relation entre un identifiant de plan, par Q exemple une valeur d'index, génétiquement noté Pj, des valeurs de vecteur Nj en projection sur la base d'un repère orthonormé, respectivement notées Njx, Njy et Nj ' z, une valeur de scalaire premier identifiant de cellule Vk, et un second identifiant de cellule VI.

5 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, î 0 Le dispositif 1 A 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 V espace sous une forme numérique, ainsi que des données symboliques et des données de typage relative à chaque sommet de polygone.

15 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 ea tant que sous-ensemble des polygones stockés. La structure du cinquième stockage de données 108 maintient également une relation entre 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 1A S 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. 0 Chaque ligne du tableau Tab6 maintient une relation entre un identifiant de sommet, par exemple une valeur d'index, noté généiiquement Sj, des valeurs de coordonnées spatiales, par exemple en tant que valeurs de projection dans un repère orthonormé, notées Sjx, 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, îe 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 1 A 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 on plusieurs triangles de l'espace sous une forme numérique.

Le sixième stockage de données 1 10 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 1 10 sous la forme d'un huitième tableau 1014, ou tableau Tab?.

Chaque ligne du tableau Tab 7 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 Dk.

En variante, le sixième stockage 110 pourrait prendre une forme analogue aux réalisations des figures 2 à 4. 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àe triangles Tj en tant que découpage de ladite surface.

5 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.

10 La première foncti on 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.

15 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 trianguiation extérieure au dispositif 1 A.

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 30 chacun des triangles. Les données de localisation peuvent comprendre des valeurs de coordonnées dans un repère orthononné. Chaque plan support peut, être défini au moyen de données de définition d'un vecteur Nj et d'un scalaire Bj, conformément à l'équation de l'annexe A.1.1 .

La fonction génératrice 302 est adaptée pour établir des données de localisation pour chaque point de la collection, par exemple sons 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 à l'appel de la foncti on 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 du dis ositif d'aide au mai liage. 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. 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 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 «ne forme mathématique, les points sont générés de manière à appartenu" à la surface S, à une précision numérique près. Bien que les performances du dispositif 1A 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 ia surface à traiter ; cela améliore sensiblement les performances de calcul,

La bibliothèque 30 comprend une fonction de partitionne ent 304 adaptée pour établir un jeu de données représentant une collection de cellules spatiales sons 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.

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ï. 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 pian 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.

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 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 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. 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, îa 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 dune 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. 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 trois plans de l'espace.

L fonction d'intersection 306 est en outre adaptée à établir, pour chaque sommet de polygone, une donnée de fypage 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.

Lorsque la surface à traiter est représentée par un jeu de triangles, la données de typage est 5 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 "ïsotropic remeshing wiili fast and exact computation of restricied Voronoï 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 triangle, en particulier en sa section 3 intitulée "RVD computation". Le contenu de cet article, et en particulier sa section 3, sont intégrés à îa présente par référence. 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ù M T représente une matrice d'anisotropie, x<> correspond au 5 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 M ' r 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 norme0 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 5 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; G Dans le cas où la matrice d'anisotropie Μτ diffère de la matrice identité, la puissance entière p peut être prise égale ou supérieure à L Dans les autres cas, cette puissance entière p est prise supérieure ou égale à 2. De préférence, îa vaiem" de l'entier p est choisie paire pour simplifier les calculs, S 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 Fip(T) s'exprime alors selon la formule de l'annexe A.2.8, Dans le cas général d'un jeu Ω de cellules Q\ la fonction normative Flp(X) d'ordre infini s'exprime conformément à la formule de l'annexe A.2.7. 0 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 vaîeur 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'agît 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 À.2.4 sont définis à l'annexe À.l

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 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.9 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 œuvre toute méthode d'optimisation, en particulier de type descente de gradient, de type ne tonienne ou de type quasi-newtonienne, par exemple la méthode dite "BFGS" (pour méthode de BRQYDEN-FLET E -GOLDFARB- SHANNO") 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 Optimisation", D. C. LlU et J. NOCEDAL, Mathematical Programmîng B, 45, 3, pages 503 à 528;

"A limited Memory Algorithrn for Sound Constrained Optimization", R ,H. BYRD, P. Lu etJ. OCEDAL, SIÀM Journal on Scientific and Statistical Computing, 16, 5, pages 1190 à .1208.

La bibliothèque 30 comprend encore une fonction de post-traitement 316, qui sera explicitée pl us loin, et qui permet d'obtenir un maillage hexaédrique ou cubique à partir d'un jeu de points,

La bibiiothèque 30 comprend enfin une fonction d'optimisation 318 dont le fonctionnement est illustré sur la figure 10. À 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 fonct on de découpage 300 retourne un jeu T de triangles Tj qui est mémorisé dans le second stockage 102.

Ici, ropération 402 est représentée en irait tireté car elle est optionnelle.

Lorsque la surface à traiter est maintenue dans le premier stockage 100 sous une forme iriangulée, l'opération 402 peut être ignorée. Dans le cas où la surface à traiter a été définie sous une forme iriangulée cependant, l'opération 402 peut être mise en œuvre pour obtenir une triangulation différente de la surface à traiter, par exemple présentant une finesse (nombre total de triangles) différente. À l'opération 404, on appelle la fonction génératrice 302 pour le jeu 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 de points Xj (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 données 104 pour chaque point Xj.

A l'opération 406. on initialise une variable formant compteur de boucle, notée

À l'opération 408, on appelle la fonction de partitionnement 304 avec les données du troisième stockage 104. La fonction de partitionnement 304 retourne un jeu Ω de cellules de

Voronoï ûi 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 formant les centres respectifs des cellules en question, par exemple Xk et 27. 9 ' >

A l'opération 410, on appelle ia 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, ia fonction d'optimisation, ia fonction de parti tionnement 304 et la fonction d'intersection 306 agissent, en combinaison les unes des autres, à la manière d'un parti donneur, 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, à ia 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 obteni un premier jeu de cellules de travail A l'opération 412, on appelle Sa 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 Tj 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 Tab ' 7 avec pour" identifiant de sommet Cji l'identifiant Sj 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 associé respectif, les sommets chaque élément géométrique simple comprenant des sommets de ia 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 îa forme d'une variable F. La fonction d'optimisation 318 et la fonction de sommation 31.0 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.

A 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. A chaque fois le résultat d'un appel de la fonction de dérivation 312 est additionné au résultai des appels 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 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 d'amélioration 314, sert d'optimiseur agencé pour actionner itérativement l'outi 1 de pavage et l'évaluateiir avec à chaque fois un jeu de points initiaux tirés des jeux précédents, selon une régie 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 trait tireié car elle est facultative.

La figure 12 représente un dispositif 1B d'aide au mailîage d'un domaine en tant que développement du dispositif 1A. Le dispositif B est à usage, en particulier, lorsque le domaine en question prend la forme d'un volume Pau moins partiellement délimité par une surface .S.

Le dispositif I B se distingue d'abord du dispositif 1À en ce qu'il comprend en outre un septième stockage de données 1 12, 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,

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 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 TabÎ 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 : pour le point qj.

Chaque ligne du tableau Tab l O maintient en relation un identifiant de plan, tel qu'une valeur d'index, génétiquement noté Pj, des données de projection du vecteur Nj et du scalaire Bj selon la définition d'un pian Pj donnée en annexe A, 1.1 , notées Njx, Njy, Njz et Bj t et des données d'identifiant de cellule Mk, Chaque ligne du tableau Tabl 1 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 orfhonormé, à savoir qjx, qjy et qjz pour le point qj, et un identifiant de cellule, par exemple Mj pour le point qj ' . Dans ce mode de réalisation, le sixième stockage 1 10 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 ÎA é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 disp o sitif î A en ce que le jeu de données résultant de 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 ie volume délimité par la surface donnée. Cette surface peut être définie par un jeu 7'de triangles Tj, La donnée de lypage 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 IB, la fonction de décomposition 308 est modifiée de manière à établir 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 œuvre la formule de l'annexe A.2.2. dans laquelle Γ 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 ¾ Cl, C2, C3. La fonction d'intégration 310 peut alors calculer la grandeur cumulative en évaluant la formule de l'annexe À.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 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 41.0) et pour appeler l fonction sommation 310 sur les données contenues dans ce septième stockage (opération 412),

La fonction de post-traitement 316 est agencée pour calculer la triangulation de Deîaunay 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 ttiangulation de Deîaunay de manière à 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 Underlylng Tetrahedral Mesh" de S. MESHKAT et D, TAL OR, International Journal for Numericaî Methoàs in Engineering, volume 49, pages 17 à 30, 2000.

Dans une variante de réalisation, la fonction de post-traitement 316 est agencée pour calculer Se 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 1 À 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 à 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.

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/on selon une matrice d'adaptation représentant un champ d'amsotropîe.

Ces deux dernières étapes sont répétées itérati vement 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 œuvre 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. On cite maintenant quelques publications traitant de maillage anisotrope. "Anisotropic Polygonal Remeshing", P. ALLIEZ, D, COHEN-STEINER, O. DEVILLERS, B. LBVY, et M. D&SBRUN, 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~STEIN.BR, P. ALLIEZ et M. DESBRUN, S1GGRÂPH conférence proceedings, 2004. Dans ce document, on propose de minimiser directement l'erreur d'approximation,

"Tetrahedral mesh génération and optimization based on centroidal Voronoi iesseilatîons", Q, Du et D , W ANG. International Journal forN merical Methads 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 triangolar meshes with metric-dependent discrète Voronoi diagrams", S. VALETTE, J.-M. CHASSER Y et R. PROST, IEEE Transactions on Visnalization and Computer Graphics, volume 14, pages 369 à 381, 2008. Dans ce document, on utilise la même définition de l'anisotropie que dans ie document précédent. On propose cependant une approximation discrète fonctionnant sur la base d'une pré-triangulation du domaine. On utilise donc des cellules de Voronoï anisotropiques et approximatives. Elle nécessite de mettre en œuvre 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 guaratiteed-quality anisotropic mesh génération",

F. LABELLE, J. R. SHEWCHUK, SCG'03 ; Proceedings ofthe nineteenth ann al symposium on Comp tational geometry, pages 19.1 à 200, 2003. Ce document propose une généralisation des diagrammes de Voronoï en définissant une anisotropic attaché aux sommets.

"Fuiiy-Automated Hex-Dominant Mesh Génération with Direetionality Contrat via Packing Rectangular Solid Cells", S. YAMÂKAWA et K. SHI ADA, International Journal for N mencâl Methads 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 mailiage avec des éléments en forme de quadrilatères.

"Localized Quadrilatéral Coarsening", J. DANIBLS-H, C. T. SJLVA, et E. COHEN, Computer 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 Mesbes into Quadrilatéral Meshes with Directionality", T. ITOH et K, SHiMADA, International Journal o/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". "Quad-Dominant Mesh Adaptation Using Specialized Simplicial Optimisation", .-

F. TCHON et R. CAMAR RO, 15th International Meshing Roundtable conférence proceedmgs, pages 21 à 38, 2006 et "An Incrémental Approach to Feature Aîïgned Quad Dominant Remeshing", Y.-K. LAI, L. KOBBELT et S. -M. Hu, ACM SPM conférence proceedmgs, pages 137 à 145, 2008, proposent une adaptation d'un mailhige à éléments en 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. PASCUCCÎ, et L C. HARÏ, ACM Transactions on Graphics, volume 25, numéro 3 , pages 1057 à 1066, 2006, et "Spectral quadrangulation with orientation and alignaient control", J. HlfANG, M. ZHÀHG, 3. 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 Morse d'une fonction propre de Laplacien.

"Platiar Parameterization forCiosedManifold Genus-g Mesb.es Using AnyType of Positive Weig ts". D. STEINE et A FISCHER", Journal of Computing and Information Science Engeneering, volume 5, numéro 2, 2005, "Designing quadrangulations with discrète harmonie forms", Y. TONG, P. ALLIEZ, D, COHEN-STEÏ ER, et M. DESBRUN, SGP '06: Proceedings of the fourth Eurographics symposium on Geometry processing, 2006, et "Surface Parameterization using Branched Covermgs", F, KALBBRER, M. NïBSBR et . POLTHIER, Computer Graphics Forum, volume 26, 2007 proposent de réaliser des contours de lignes iso κ,ν d'une surface définie sous une forme paramétrique.

"Periodic global parameterization", N. RAY, W. C. LL B. LÉVY, A. S.HEFFER et P, ALLIEZ, ACM Transactions on Graphics, volume 25, numéro 4, pages 1460 à 1485, 2006, et "Mixed-integer quadrangulation", D. BOMMES, and H. ZI MBR, et L KOBBE ' LT, 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 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 trai tant du mai liage d'un volume avec des éléments hexaédriques.

"Methods for Multisweep Automation", J, SHEPHERD, S. A. MÎTCHELL, P. K LÎPP et D. WHITE, 9 ! " Internationa! Meshing Roundtable Conférence Proceedings, 2000, propose une méthode directe basée sur un balayage multiple.

"Unconstramed Paving and Flastering: A New Idea for Ail Hexabedtaî Mes Génération", M. L, STATEN, S. J. OWEN, et T .D, BLÀCKER, International Meshing Roundtable Conférence Proceedings, 2005, propose une méthode directe de pavage et de lissage.

"Advances in octree-based all-hexahedral mesh. génération: handling sharp featores",

L. MARÉCHAL, J8' k International Meshing Roundtahle Conférence Proceedings, .2009, propose une méthode directe à base de d'arbres octaircs.

''Volurnetric parameterization and trivariate B-splme fitting using harmonie fonctions", T. MARTIN, E. COHEN, et M IRBY, SPM'08: Proceedings ofthe 2008 ACM symposium on Solid andphysica! modeling, 2008, propose une méthode directe basée sur la realization d'un, contour d'un volume défini sous une forme paramétrique.

"Tensor-Guided Hex-Domiaant Mesh Génération with Targeted All-Hex Régions", V. VYAS et K. SHÎMADA , î 8 th .International Meshing Roimdtabie Conférence Proceedings, 2009, propose une méthode directe utilisant les surfaces de flux d'un champ de tenseurs.

"H-Morph : An Indirect Approach to Advancing Front Hex Meshing", S. J. Owen et S. SAÎGAL, International Journal for Numericaî Methods in Engineering, volume 49, 2000, propose une méthode indirecte prévoyant ia construction d'un maillage à éléments tétraédriques et de transformer ce maillage en un maillage hexaédrique- dominant en utilisant une approche frontale.

"Anisotropic Tetrahedral Meshing via Bubble Packing aud Advancing Front". S, YAMA AWA et K. SHIMADA, International Journal for Numericaî Methods in Engineering, 2003, propose de réaliser ce premier maillage en utilisant le procédé de "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 tonne analytique, aisée à calculer et assez peu sensible à une augmentation d'échelle, en vue notamment d'être utilisée en milieu industriel.

L'invention n'est pas limitée au modes de réalisation décrit ci-dessus, à titre d'exemple uniquement, mais eagiobe toutes les variantes que pourra envisager l'homme de Fart,

nexe 1 - Conventions de notation

A.l.l

A.1.2 V[x, y, z

A.1.3

A.1,5 Vi *V 2 — [»ia¾> -/-.½>¾<¾]

A.1.6 V* = V * V * ... * V(a times)

A.1.7 V ~ x - y z

A.1.8 V

A.1.9 MrfCi ~xo)

A.1,10

Λ.ί.ΙΙ Vjj2-niax{j: i>M} Annexe 2 ■■ Fonction objectif

A.2.1

A.2.2 F[ e = |M T (y - Xo)||^y

T

A.2.3

A.2.4 T| - 1/2 |N|

A.2.6 T! - 1/6 Ui · (U 3 x U s )

A, 2.8 M T (y - o)|j~d Annexe 3 - Gradient de fonction objectif

A.3.1

Α.3.

(U 2 - U 3 )f [N x (U 3 -- Ui)] 4 [ x (Ui - U 2 )j<

A.3.5 - 1/6 ([U 2 x U 3 f ]U 3 x U, ! ! [IL x U 2 j*)

dFT

A.3.8 dC ίίΝ,ΐ' ί [C-xo]* 0

V 0 i> .-xçs]' \ ■■■ > [C- ii]* [xi-Ci* 0

A.3.9 dC (xa~xo]* } [C-xof 0 [x 2 -C

A.3.10 cfC ~