Brevet FR3039686A1 — publié le 20170203

INRIA 180PI.FRD Traitement de données géométriques, avec approximation isotopique dans un volume de tolérance. L'invention concerne les techniques informatiques de construction ou reconstruction de surfaces géométriques. A la base, une surface ou une forme peut être représentée par un ensemble de points dans l'espace. On parle alors d'un "nuage de points". Pour en permettre un traitement informatique en tant que surface, une surface à deux dimensions est souvent représentée par un maillage à base de primitives triangulaires. De même, un volume à trois dimensions peut être représenté informatiquement par un maillage tétraédrique. Les expressions "maillage triangulaire" et triangulation couvrent l'ensemble de ces cas. Une représentation de surfaces par "maillage triangulaire" ou surfaces paramétriques peut être imparfaite, le plus souvent en raison des limites des capteurs utilisés pour l'établir et des algorithmes de reconstruction de surfaces à partir de mesures. Les défauts peuvent être par exemple des trous, ou encore des auto-intersections (car il est rare qu'une surface du monde réel se traverse elle-même). L'expression "soupe de triangles" est utilisée pour viser une triangulation qui peut être imparfaite. Réaliser une approximation fidèle de formes complexes avec des mailles triangulaires (que l'on appelle aussi simplicielles, de l'anglais "simplicial") est un problème à facettes multiples, qui fait intervenir la géométrie, la topologie, et leur discrétisation (découpage en primitives). Ce problème a suscité un intérêt considérable, du fait de sa vaste gamme d'applications, et de la disponibilité toujours croissante de capteurs géométriques. Il en découle une disponibilité nettement accrue de modèles géométriques scannés, ce qui ne signifie pas que leur qualité croît : alors que de nombreux praticiens ont accès à des systèmes d'acquisition de haute précision, la tendance récente est à remplacer ces outils coûteux par une combinaison hétérogène de dispositifs d'acquisition du niveau grand public. Les mesures engendrées par ces derniers sont insusceptibles d'un 3039686 2 traitement direct. C'est encore plus vrai si l'on cherche à fusionner les données hétérogènes provenant de différents capteurs grand public. De même, la diversité des outils de traitement géométrique se traduit par une augmentation du nombre de défauts dans les données : la conversion de et vers différentes représentations 5 géométriques a souvent pour effet de perdre en qualité par rapport au signal d'entrée. Rares sont les algorithmes qui procurent, sur leur sortie, des garanties de qualité meilleures que leurs exigences en termes de signal d'entrée. On a recours à des discrétisations de plus en plus fines, pour capturer des formes géométriques complexes. Ceci fait que le souci devient dominant d'offrir des garanties 10 géométriques strictes, pour être robustes à l'apparition d'artefacts et rendre possible la certification des algorithmes. Par "garanties géométriques", on entend la fixation d'un maximum aux erreurs de l'approximation géométrique, et l'absence d'auto-intersections. 15 Il s'y ajoute des garanties topologiques, comme l'homotopie, l'homéomorphisme ou l'isotopie. Ces notions sont définies plus loin. En l'occurrence, l'isotopie signifie qu'il existe une déformation continue qui déforme 20 une forme sur une autre, tout en maintenant un homéomorphisme entre ces deux formes. Des maillages de surface offrant ces garanties sont requis pour obtenir un rendu sans artefact, pour l'ingénierie numérique, pour l'ingénierie inverse, pour la fabrication, et 25 pour l'impression 3D. La simplification géométrique permet de réduire le nombre de primitives. La simplification topologique peut réparer des trous et des dégénérescences présents dans les discrétisations existantes. Ces deux types de simplifications peuvent être 3039686 3 utilisés en combinaison pour reconstruire des formes propres à partir de données géométriques brutes telles que des nuages de points, ou des soupes de triangles. De nombreuses techniques ont été proposées au fil des ans pour réaliser des approximations informatiques de formes. Peu d'entre elles procurent une limite 5 supérieure des erreurs. Le Document [Ref1] (Annexe 2) a proposé une méthode d'approximation en temps polynomial, avec une garantie de descendre à un nombre minimal de sommets pour une tolérance d'erreur maximale donnée. Mais ce résultat est purement théorique, et ce document n'offre pas d'algorithme pratique de mise en oeuvre. 10 L'approximation à erreur maximale a été recherchée également par regroupement ("clustering") dans [Ref18], par décimation de mailles [Ref9], [Ref15], [Ref10], [Ref28] ou encore par une combinaison de ces deux techniques [Ref24]. En général, la métrique d'erreur considérée est la distance de Hausdorff unidirectionnelle qui remonte au maillage d'entrée, mais certains ont utilisé la distance 15 bidirectionnelle [Ref 9]. De façon générale, ces approches ne sont pas suffisamment génériques pour travailler sur des données d'entrée hétérogènes et imparfaites. Et elles ne permettent pas de garantir une sortie dénuée d'intersections. On peut éviter de créer des intersections pendant la décimation de mailles ([Ref26]), 20 mais cela ne suffit pas dans le cas de données d'entrées qui comprennent elles-mêmes des auto-intersections, et ces évitements impliquent une fin prématurée de la phase de simplification, et ce qui se traduit au bout du compte par des maillages trop complexes. De façon générale, il est important d'engendrer en sortie un maillage qui soit 25 isotopique aux données d'entrée, et se contente d'un faible nombre de triangles (ou de sommets). En 2D, ceci s'appelle le problème des polygones inscrits minimaux ("minimum nested polygons"), et a été bien étudié dans le cas convexe [Ref22]. En 3D cela devient le problème des polyèdres inscrits minimaux, dont on a montré qu'il est de difficulté N-P. Bien que ce problème soit ancien, il n'existe toujours pas de solution robuste et pratique qui réponde à ce défi scientifique et technique. La présente invention vient y remédier. Le procédé proposé à cet effet part, comme données d'entrée, d'un volume de tolérance Q. 3039686 4 Ce volume de tolérance peut être déterminé, dans le cadre d'un pré-traitement, à partir de données géométriques brutes de départ, par exemple sur la base d'un nuage de points ou d'une soupe de triangles, ou encore à partir de n'importe quel ensemble de données géométriques, même hétérogènes. 5 Le procédé proposé comprend les étapes suivantes : A. recevoir un volume de tolérance S2, relatif à des données géométriques brutes de départ, B. initier une triangulation canonique dans le volume de tolérance, à partir d'un jeu S de points échantillons pris aux limites de ce volume de tolérance, et de 10 points situés à l'extérieur de celui-ci, C. raffiner cette triangulation canonique, jusqu'à classifier les points de l'échantillon, ce qui fournit un maillage primaire dense, de topologie correcte, pour le volume de tolérance, et D. simplifier ce maillage dense par des opérations de modification de 15 triangulation, en préservant la topologie et la classification des points de l'échantillon. Est également proposé un dispositif de traitement de données géométriques, comprenant : - Une mémoire de données géométriques, pour recevoir des données graphiques 20 représentant un volume de tolérance, Un organe d'initialisation, agencé pour réaliser une première triangulation canonique entre le bord du volume de tolérance et des points situés à l'extérieur de celui-ci, Un organe de raffinement, agencé pour préciser ladite première triangulation 25 jusqu'à fournir un maillage dense du volume de tolérance, qui préserve une condition de classification des points de la triangulation, - Un organe de simplification, agencé pour simplifier ledit maillage dense, en préservant la topologie et la classification de ses points, et un pilote qui actionne successivement l'organe d'initialisation, l'organe de 30 raffinement, et l'organe de simplification, pour des données graphiques en évolution à partir du même volume de tolérance. 3039686 5 D'autres caractéristiques sont également proposées, pour le procédé comme pour le dispositif correspondant. L'étape B d'initialisation peut comprendre la sous-étape d'échantillonner les limites du volume de tolérance selon une densité d'échantillonnage choisie a, ce qui fournit 5 l'ensemble S de points échantillons. L'étape B peut comprendre le marquage de chaque point échantillon de l'ensemble S par une valeur-étiquette qui représente l'index de la composante connexe de bord de ce point, dans le volume de tolérance. L'étape C de raffinement comprend alors la génération itérative de la triangulation canonique, en insérant un point à la fois, sur au 10 moins une partie de l'ensemble S de points, jusqu'à ce que tous les points concernés vérifient une condition de classification, appuyée sur la valeur d'une fonction F elle-même dépendant de leur valeur d'index, et sur son interpolation par une fonction d'interpolation f appliquée à chaque maille de la triangulation 3D. Ainsi, il peut être fait usage d'un opérateur de classification de point, qui reçoit la 15 désignation d'un point à traiter, et détermine une fonction d'interpolation f sur la base de la maille entourant ce point à traiter, et de valeurs-étiquettes relatives aux sommets de cette maille, pour fournir une étiquette interpolée, et comparer celle-ci à une étiquette courante du point à traiter, ce qui permet de déterminer une condition de classification du point à traiter. 20 L'étape C peut se compléter par la construction d'une isosurface linéaire par morceaux Zset, à l'aide des points où la fonction d'interpolation f possède une même valeur intermédiaire choisie, en particulier nulle, cette isosurface Zset étant une surface fermée, qui forme une approximation surfacique du volume de tolérance. De préférence, la triangulation canonique est une triangulation de Delaunay. 25 Les données géométriques brutes de départ peuvent être des données 2D ou des données 3D. De son côté, l'étape D. de simplification peut comprendre les opérations suivantes : Dl. déterminer si des opérations de modification de triangulation sont valides, c'est-à-dire préservent la topologie du maillage et préservent la condition de classification de 30 l'ensemble S de points échantillons, et D2. effectuer les opérations de modification de triangulation valides dans un ordre déterminé. De préférence, les opérations de modification de triangulation comprennent des fusions d'arêtes et/ou des fusions de demi-arêtes. 3039686 6 L'ordre peut être déterminé en fonction d'un critère d'optimisation. Dans un mode de réalisation, l'étape D. porte sur un volume dit "tolérance simplicielle" qui approche le volume de tolérance par une union de mailles de la triangulation canonique, l'isosurface Zset étant contenue dans ce volume dit "tolérance 5 simplicielle", Les étapes D1 et D2 peuvent alors être effectuées : - D'abord sur le bord du volume dit "tolérance simplicielle", Ensuite sur le fruit d'une triangulation mutuelle entre l'isosurface (Zset) et le volume dit "tolérance simplicielle", cette triangulation mutuelle ajoutant des 10 sommets, des arêtes et des mailles dans la triangulation, sur l'isosurface, - Enfin, avec d'autres arêtes contenues dans le volume dit "tolérance simplicielle", jusqu'à couvrir toutes les arêtes possibles. L'invention vise également un produit-programme d'ordinateur comprenant des portions de code de programme pour mettre en oeuvre le procédé ou le dispositif 15 précités, lorsque le programme est exécuté sur un ordinateur. D'autres caractéristiques et avantages de l'invention apparaîtront à l'examen de la description détaillée ci-après, et des dessins annexés, sur lesquels : - Les figures 1-a à 1-e illustrent schématiquement un premier exemple d'application de l'invention ; 20 - la figure 2 est le diagramme de flux général du mécanisme proposé selon l'invention, - la figure 3 illustre un exemple de début d'application de l'invention. - la figure 4 est un diagramme de flux qui détaille celui de la figure 2, - la figure 5 est un dessin illustrant la définition de ratios barycentriques, - la figure 6 est un diagramme de flux qui détaille une réalisation préférentielle de 25 l'étape de raffinement 203 des figures 2 et 4, - les figures 7 montrent différents état de la triangulation pendant la phase de raffinement, sur un autre exemple, très géométrique, d'application de l'invention, - les figures 8 montrent différents état de la triangulation pendant la phase de simplification, sur le même exemple, très géométrique, d'application de l'invention, 30 - les figures 9 sont des dessins illustrant un cas particulier d'application de l'invention, 3039686 7 - les figures 10 sont des représentations d'éléphants montrant la robustesse du procédé selon l'invention, - les figures 11 illustrent schématiquement d'autres exemples d'application de l'invention, sur le même objet que les figures 1, 5 - la figure 12 est un diagramme, illustrant certains avantages de l'invention, - la figure 13 est un autre diagramme, illustrant certains avantages de l'invention, - la figure 14 est une autre représentation, dite « fertilité », sur laquelle portent les diagrammes des figures 12 et 13, - les figures 15 sont des représentations comparables à celle de la figure 3, permettant 10 de mieux comprendre la sous-phase de triangulation mutuelle, dans la phase de simplification, - les figures 16 illustrent deux mécanismes de fusion d'arêtes et de demi-arêtes, - la figure 17 est un diagramme de flux qui détaille une réalisation préférentielle pour l'étape de simplification 207 des figures 2 et 4, 15 - la figure 18 est le schéma de principe d'un dispositif selon l'invention, et - la figure 19 est le schéma de principe d'un opérateur de classification utilisé selon l'invention. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la 20 présente invention, mais aussi contribuer à sa définition, le cas échéant. La nature de l'invention fait que certaines caractéristiques ne s'expriment complètement que par le dessin. La description est suivie d'une Annexe 1 comportant des définitions, et d'une Annexe 2 regroupant les coordonnées des documents auxquels il est fait ici référence. Ces 25 annexes font partie intégrante de la description. On examinera d'abord les figures la à le, pour une description très générale de l'invention, faite en référence à la figure 2, qui illustre les grandes étapes de fonctionnement du procédé proposé, et à la figure 4, qui détaille la figure 2. La figure 1-a illustre le point de départ, à savoir un volume de tolérance S2 relatif à une 30 pièce mécanique mesurée par un scanner laser, avec une tolérance d'entrée Ô de 0,6 %. 3039686 8 La figure 1-b illustre ce qu'on obtient après l'étape de raffinement (203, figure 2). Le résultat est une fonction linéaire par morceaux Z, correspondant à un maillage surfacique du volume de tolérance S2 de la figure 1. Le nombre de sommets est 20,4k (20.400). 5 On procède ensuite à des simplifications, conformément à l'étape 207 (figure 2). La figure 1-c illustre le même maillage que la figure 1.b, mais après qu'il ait subi une première simplification (simplification du bord dr de la tolérance "simplicielle" F, étape 2072, figure 4), qui le fait descendre à 5,3 k sommets. La figure 1-d illustre le même maillage, après triangulation mutuelle et simplification 10 de Z (étape 2074, figure 4), qui le fait descendre à 1,01 k sommets. Enfin, la figure 1-e illustre le maillage en fin de simplification (étape 2076, figure 4) qui est descendu encore à 752 sommets. On observe, à l'ceil, que, même simplifié, le maillage de la figure 1-e représente bien l'objet défini par les figures précédentes. 15 Il est maintenant fait référence à la figure 3, qui utilise un volume de tolérance curviligne symbolique, plus simple que celui des figures 1. On a vu que la figure 2 illustre les grandes étapes de fonctionnement du procédé proposé. La figure 4 illustre certaines étapes du procédé de façon plus détaillée. Sur la figure 3, le volume de tolérance S2 est défini par une forme curviligne boudinée, 20 dont la zone frontière dS2 présente deux bordures dS21 et dS22, dans une vue en coupe en plan. L'étape 201 des figures 2 et 4 est une initialisation. Comme indiqué en 2011 (Figure 4), l'initialisation comprend d'abord un échantillonnage du bord (ou de la frontière) du volume de tolérance. 25 On obtient un ensemble S de points échantillons s, stocké à l'étape 2013 (figure 4). Cet échantillonnage est en principe "a-dense". Cela signifie que des boules de rayon a centrées sur tous les points s de S recouvrent intégralement la zone frontière dS2 du volume de tolérance Q En pratique, o est une fraction de l'épaisseur 6 de Q Dans le cas le plus simple, celui de la figure 3, la zone frontière an n'a que deux 30 composantes connexes de surfaces de bord, à savoir an,. (frontière externe) et dO2 (frontière interne). Dans ce cas, on distingue facilement l'intérieur et l'extérieur d'un bout à l'autre de la zone frontière an. Cela peut se faire formellement, en affectant à 3039686 9 chaque échantillon s de l'ensemble S une valeur d'étiquette (ou label) F(s) qui est, par exemple: F(s) = 1 si le point s est sur an', et F(s) = -1 si le point s est sur dO2. 5 Cette valeur F(s) peut être vue comme une représentation de l'index (ou "indice") de la composante connexe de bord du point s considéré, dans le volume de tolérance. Une autre fonction 'f' est construite : Pour un point x, présent dans une maille M (triangulaire en 2D, tétraédrique en 3D), on calcule une fonction d'interpolation linéaire f(x, M), définie sur la base des valeurs F(s) aux trois ou quatre sommets de la 10 maille M (triangle ou tétraèdre), et des coordonnées barycentriques du point x considéré, par rapport aux sommets de la maille. Plus précisément, f(x, M) est une combinaison linéaire convexe des valeurs de F aux sommets vi de la maille M : où pour tout i, al est positif ou nul, et la somme des al est 1. Les valeurs de al se 15 définissent par exemple comme indiqué sur la figure 5 : Pour un point X situé dans une maille triangulaire ABC, l'un des al est la valeur a pour X par rapport au sommet A du triangle, notée aA(X), qui est le rapport de la surface du triangle XBC à la surface du triangle ABC. On aura donc : 20 f(x,M) = aA(X) F(A) + as(X) F(B) + ac(X) F(C) C'est la même chose avec une maille tétraédrique, qui comporte un sommet de plus, et où les surfaces deviennent des volumes. Pour un point X situé dans une maille tétraédrique ABCD, la valeur a pour X par rapport au sommet A du tétraèdre, notée aA(X), est le rapport du volume du tétraèdre 25 XBCD au volume du tétraèdre ABCD. Et la formule devient : f(x,M) = aA(X) F(A) + as(X) F(B) + ac(X) F(C) + au(X) F(D) En 3D, dans le cas de tétraèdres, la fonction interpolée f(x, M) est contrainte à être une fonction qui vérifie la condition dite de Lipschitz (avoir une dérivée limitée). L'homme du métier sait comment mettre en oeuvre cette condition supplémentaire, qui 3039686 10 s'impose au cours du raffinement. On en donnera des exemples plus loin, en référence aux figures 9. D'autres informations sur ces calculs barycentriques sont disponibles dans [Ref25]. A côté de cela, l'ensemble des points p où f(p) = 0 correspond à une ligne polygonale 5 (une surface en 3D) dite ZeroSet. Cette ligne polygonale ZeroSet, également notée Z en abrégé, est une surface linéaire par parties, qui se place à l'intérieur du volume de tolérance. On utilise aussi une grandeur d'erreur E, qui peut être définie comme suit : E (s) = I f(s, M) - F(s) I, où la notation I x I vise la fonction valeur absolue de x. 10 Faisant partie de l'ensemble S, le point s possède une valeur F(s). Dans la maille M du maillage qui contient ce point s, celui-ci reçoit une valeur interpolée f(s, M). On considère un paramètre a, avec (0 = 2/ (cra). C'est une manière de faire en sorte que la fonction d'interpolation f vérifie le critère de Lipschitz, suivant lequel la valeur absolue du gradient de cette fonction f est bornée. Un choix convenable de a fait ainsi que les problèmes de tétraèdre plat ("sliver") sont 5 naturellement résolus. Comme autres facteurs perturbateurs du raffinement, on peut aussi rencontrer des problèmes d'orientation (direction des perpendiculaires ou "normales") dans des zones complexes. Ils peuvent être résolus en utilisant ce qui précède. De préférence, et optionnellement, 10 on vérifiera aussi pour chaque tétraèdre qu'une extension de la fonction linéaire par morceau en dehors du tétraèdre, classifie bien aussi des points de l'échantillon pas seulement dans le tétraèdre, mais aussi en dehors. On dira alors que la fonction d'interpolation f classifie la "géométrie locale". La valeur à choisir pour a dépend de la nature des données d'entrée. La valeur a = 0.2 15 convient bien, au moins comme valeur de départ. Il est maintenant fait référence aux figures 10, qui illustrent en partie haute des représentations brutes d'un éléphant (de gauche à droite : un nuage de points sans bruit, une soupe de triangles sans bruit, un nuage de points avec bruit, et une soupe de triangles avec bruit), et en partie basse la triangulation obtenue selon l'invention. Pour 20 chaque exemple les données brutes sont converties en un volume de tolérance en calculant un sous-niveau de la fonction distance aux données (points ou triangles). A gauche (figure 10 A), l'image de départ est un nuage de points qui n'ont pas d'effet notable sur la surface finale triangulée. Plus à droite (figure 10 B), les données de départ formes une soupe de triangles non organisés (avec des intersections, des trous) 25 qui n'ont pas non plus d'effet notable sur la qualité de la surface finale triangulée. Encore plus à droite (figure 10 C), les données de départ sont un nuage de points avec un fort niveau de bruit (incertitude sur leurs coordonnées) qui n'a pas non plus d'effet notable sur la qualité de la surface finale triangulée. Enfin, tout à fait à droite (figure 10 D), les données de départ forment une soupe de triangles très irrégulière et bruitée qui 30 n'a pas non plus d'effet notable sur la qualité de la surface finale triangulée. On note simplement que la triangulation est moins détaillée sur les figures 10 C et 10 D, là où les données de départ ont un fort niveau de bruit, et pour lesquelles un plus grand volume de tolérance est choisi. Ces exemples illustrent bien la robustesse de la technique selon l'invention. 3039686 26 L'invention a été mise au point en utilisant la base informatique suivante : - Machine INTEL Intel 2.4GHz à 16 coeurs avec 128 Gigaoctets de mémoire vive, Pour les structures de données de triangulation, bibliothèque CGAL, disponible auprès de la société Geometry Factory, 20, Avenue Yves Emmanuel Baudoin, 06130 5 Grasse, France, Bibliothèque INTEL "Threading Building Blocks library" pour la parallélisation. Il est observé que les traitements "atomiques" sur les tétraèdres et les points échantillons sont indépendants, et peuvent donc facilement être conduits en parallèle. 10 Les figures 11 reprennent la pièce des figures 1. La figure 11.0 est le volume de tolérance. Les figures 11.1 à 11.4 illustrent le maillage final obtenu, avec des conditions de traitement différentes, en ce qui concerne le facteur 6, qui est la distance de séparation entre les frontières du volume de tolérance, exprimée en pourcentage. Le 15 tableau suivant indique les valeurs de 6, le temps de traitement avec l'équipement indiqué plus haut, la figure avec le maillage final, et le nombre de sommets de celui-ci. Valeur 6 (%) Temps total de traitement Maillage final Nombre final de sommets 1,5 34 mn Fig. 11.4 254 0,9 Fig. 11.3 493 0,35 Fig. 11.2 1015 0,15 Environ 7 heures Fig. 11.1 3020 Il apparaît que le temps de calcul diminue quand la tolérance augmente. De façon 20 générale, le processus est lent, ce qui est une contrepartie de sa robustesse. Les performances obtenues par l'invention sont illustrées sur la figure 12. On observera qu'une comparaison stricte à l'art antérieur n'est pas possible puisque les contraintes du problème posé ici sont différentes. L'invention peut cependant se comparer aux propositions suivantes : 25 Lindstrom-Turk, qui est le procédé décrit dans [Ref19], qui peut être mis en oeuvre à l'aide de la bibliothèque CGAL version 4.6, commercialisée par la société Geometry Factory déjà citée, - MMGS, qui est le procédé décrit dans [Ref7], mis en oeuvre par un logiciel MMGS version 2.0a, transmis directement par Pascal Frey, second auteur de [Ref7], 3039686 27 - MMGS-A, qui est une variante du même logiciel MMGS avec l'option anisotropie de mailles, - Open Flipper, qui est le procédé décrit dans [Ref20], avec un logiciel disponible en téléchargement sur le site www.openflipper.org/, version 2.1. 5 - Simplification Envelopes, qui est [Ref9], avec un logiciel version 1.2, transmis par email par le premier auteur. La distance de Haussdorf mesure la dissemblance entre deux formes géométriques. La distance unidirectionnelle Haussdorf(A,B) est définie par le maximum de la distance euclidienne entre la forme A et la forme B, pour tout point de A, et vice-versa pour 10 Haussdorf(B,A). La variante symétrique est le maximum de Haussdorf(A,B) et Haussdorf(B,A). L'échelle des ordonnées de la figure 12 correspond à la distance de Hausdorff H10_>1, qui est la distance de Hausdorff unidirectionnelle entre la sortie et l'entrée. L'échelle des abscisses correspond au nombre de sommets en sortie. 15 Cette figure 12 montre que l'invention est meilleure que les autres techniques par des distances de Haussdorf plus faibles, avec des nombres de sommets en finale moins élevés, en plus de la robustesse déjà montrée plus haut. Les figures 12 et 13 ont pour entrée un maillage de surface brut des images des figures 14 (environ 14 000 sommets). 20 La figure 13 porte sur les temps de traitement. Elle illustre l'évolution de la complexité du maillage en fonction du traitement et du temps pour différentes valeurs de la tolérance d'entrée Ô, indiquées dans le rectangle de légende. En abscisse, on a les différentes étapes du traitement, à savoir : - Raffinement, 25 - Simplification par fusions de demi-arêtes de la frontière ar de la tolérance simplicielle, - Simplification par fusions d'arêtes de la frontière ar de la tolérance simplicielle, - Triangulation mutuelle et fusions de demi-arêtes du zeroSet Z, - Fusions d'arêtes du zeroSet Z, 30 - Simplification de tous les bords. 3039686 28 L'invention permet également de traiter des surfaces ayant des trous, par exemple lorsqu'elles sont obtenues par balayage laser qui tangente des zones concaves. Les trous peuvent être supprimés, dès lors que le volume de tolérance les englobe. L'invention peut également être définie comme un dispositif. 5 La figure 18 reprend les éléments de la figure 4, dont les étapes sont réalisées par des opérateurs. Dans les références numériques, le chiffre le plus significatif est 2 pour les étapes, contre 3 pour les opérateurs. Ainsi l'étape d'initialisation 201 de la figure 4 est réalisée par l'opérateur d'initialisation 301 de la figure 18. Il part du volume de tolérance, mémorisé en 310. A l'intérieur de 10 cette initialisation, l'étape 2011 de la figure 4 est réalisée par l'opérateur 3011 d'échantillonnage de contour de la figure 18. La figure 19 illustre un opérateur de classification de points, référencé 1900. Pour un point à classifier, on part des données suivantes (au moins en partie, certaines données étant déductibles des autres): 15 - les coordonnées de ce point, - l'étiquette ou label de ce point, - la maille qui entoure ce point, avec les coordonnées et étiquettes des sommets de cette maille. Un opérateur 1901 calcule la fonction f d'interpolation, comme décrit plus haut en 20 référence à la figure 5. Il fournit une étiquette calculée pour ce point. L'opérateur 1902 en déduit si le point est bien classifié ou non, comme déjà décrit. On observera que cette figure 19 ne reflète pas les cas d'exception, comme celui où tous les sommets de la maille ont la même valeur étiquette. Cet opérateur de classification de points, 1900, est appelé à de nombreuses reprises, 25 notamment par les opérateurs 3013 et 3032 de la figure 18, ainsi que par l'opérateur de simulation 1701 de la figure 17, dans la mesure où celui-ci doit vérifier que la classification des points est préservée. 3039686 29 Annexe 1- Définitions Isomorphisme En mathématiques, un isomorphisme entre deux ensembles structurés est une application bijective qui préserve la structure et dont la réciproque préserve aussi la 5 structure (Pour beaucoup de structures en algèbre, cette seconde condition est automatiquement remplie ; mais ce n'est pas le cas en topologie par exemple où une bijection peut être continue, sans que sa réciproque ne le soit). Hom(é)omorphisme (en anglais : "homomorphism") En topologie, un homéomorphisme est une application bijective continue, d'un espace 10 topologique dans un autre, dont la bijection réciproque est elle aussi continue. Au vu de ce qui précède, c'est un isomorphisme entre deux espaces topologiques. Lorsque l'on dit que deux espaces topologiques sont homéomorphes, cela signifie qu'ils sont « le même », vu différemment. Cela ne tombe pas toujours sous le sens. On montre par exemple qu'une tasse (avec anse) est homéomorphe à un tore, car il existe 15 une transformation qui fait passer de l'une à l'autre : combler le corps de la tasse de matière, puis le déformer progressivement, avec son anse, pour que l'ensemble forme un tore. La transformation réciproque redonne la tasse. Isotopie La notion d'isotopie est notamment importante en théorie des noeuds : deux noeuds 20 sont considérés identiques s'ils sont isotopes, c'est-à-dire si on peut déformer l'un pour obtenir l'autre sans que la « corde » ne se déchire ou ne se pénètre. Cette notion d'isotopie ne doit pas être confondue avec l'isotopie en chimie, ni avec l'isotropie en physique des matériaux. Volume de tolérance (en anglais : "tolérance volume") 25 Cela s'applique à un composant à trois dimensions. Le volume de tolérance pour un composant est le volume compris entre sa plus grande et sa plus petite surface extérieure admissible. En pratique, il peut y avoir plusieurs composantes connexes du volume de tolérance. Il peut aussi y avoir plusieurs composantes connexes de ses surfaces de bord, même si le 30 volume de tolérance n'a lui-même qu'une seule composante connexe. 3039686 30 Annexe 2 - Références [Ren]. AGARWAL, P. K., AND SURI, S. 1998. Surface approximation and geometric partitions. Journal of Computing 27, 4, 1016-1035. 5 [Ref2]. AMENTA, N., AND BERN, M. 1998. Surface reconstruction by voronoi filtering. Discrete and Computational Geometry 22, 481-504. [Ref3]. AMENTA, N., CHot, S., DEY, T. K., AND LEEKHA, N. 2000. A simple algorithm for homeomorphic surface reconstruction. In Proceedings of ACM Symposium on Computational Geometry, 213-222. [Ref4]. BISCHOFF, S., PAVIC, D., AND KOBBELT, L. 2005. Automatic restoration of polygon models. ACM 10 Transactions on Graphics 24, 1332-1352. [Ref5]. BOISSONNAT, J.-D., AND CAZALS, F. 2000. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In Proceedings of ACM Symposium on Computational Geometry, 223-232. [Ref6]. BOISSONNAT, J.-D., AND OUDOT, S. 2005. Provably good sampling and meshing of surfaces. 15 Graphical Models 67, 5, 405-451. [Ref7]. BOROUCHAKI, H., AND FREY, P. 2005. Simplification of surface mesh using hausdorff envelope. Computer Methods in Applied Mechanics and Engineering 194, 48-49, 4864 - 4884. [Ref£3]. CHAZAL, F., AND COHEN-STEINER, D. 2004. A condition for isotopic approximation. In Proceedings of ACM Symposium on Solid Modeling and Applications, 93-99. 20 [Ref9]. COHEN, J., VARSHNEY, A., MANOCHA, D., TURK, G., WEBER, H., AGARWAL, P., BROOKS, F., AND WRIGHT, W. 1996. Simplification envelopes. In Proceedings of ACM Conference on Computer Graphics and Interactive Techniques, 119-128. [Ref10]. COHEN, J., MANOCHA, D., AND OLANO, M. 2003. Successive mappings: An approach to polygonal mesh simplification with guaranteed error bounds. International Journal of Computational Geometry 25 and Applications 13, 1, 61-96. [Ref11]. DEY, T. K., AND GOSWAMI, S. 2003. Tight cocone: A watertight surface reconstructor. In Proceedings of ACM Symposium on Solid Modeling and Applications, 127-134. [Ref12]. DEY, T. K., AND SUN, J. 2005. An adaptive mis surface for reconstruction with guarantees. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing. 30 [Ref13]. DEY, T. K., LI, K., RAMOS, E. A., AND WENGER, R. 2009. Isotopic reconstruction of surfaces with boundaries. Computer Graphics Forum 28, 5, 1371-1382. [Ref14]. DEY, T. K. 2006. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press. [Ref15]. GUEZIEC, A. 1996. Surface simplification inside a tolerance volume. Tech. Rep. 20440. IBM 35 Research Report RC 20440. [Ref16]. HORNUNG, A., AND KOBBELT, L. 2006. Robust reconstruction of watertight 3d models from non- uniformly sampled point clouds without normal information. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing, 41-50. [Ref17]. Ju, T. 2004. Robust repair of polygonal models. ACM Transactions on Graphics 23, 3, 888- 895. [Ref18]. KALVIN, A. D., AND TAYLOR, R. H. 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE Computer Graphics and Applications 16, 3. [Ref19]. LINDSTROM, P., AND TURK, G. 1999. Evaluation of memoryless simplification. IEEE Transactions on Visualization and Computer Graphics 5, 2, 98-115. [Ref20]. MOBIUS, J., AND KOBBELT, L. 2012. Openflipper: An open source geometry processing and rendering framework. In Proceedings of International Conference on Curves and Surfaces, SpringerVerlag, 488-500. [Ref21]. Tamal K Dey, Anil N. Hirani, Baia Krishnamoorthy, Gavin Smith. Edge Contractions and Simplicial Homology. arXiv:1304.0664. [Ref22]. AGGARWAL, A., BOOTH, H., O'ROURKE, J., SURI, S., AND YAP, C. K. 1985. Finding minimal convex nested polygons. In Proceedings of ACM Symposium on Computational Geometry, 296-304. [Ref23]. BOISSONNAT, J.-D., AND YVINEC, M. 1998. Algorithmic Geometry. Cambridge University Press. [Ref24]. CIAMPALINI, A., CIGNONI, P., MONTANI, C., AND SCOPIGNO, R. 1997. Multiresolution decimation based on global error. The Visual Computer 13. [Ref25]. COXETER, H. S. M. 1969. Introduction to geometry (2nd ed.). John Wiley and Sons. [Ref26]. GUMHOLD, S., BORODIN, P., AND KLEIN, R. 2003. Intersection free simplification. International Journal of Shape Modeling 9, 2. [Ref271. Lee, D. T.; Preparata, F. P. (1979), "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM 26 (3): 415-421, doi:10.1145/322139.322142. [Ref28]. ZELINKA, S., AND GARLAND, M. 2002. Permission grids: Practical, error-bounded simplification. ACM Transactions on Graphics 21, 2, 207-229. REVENDICATIONS1. Procédé de traitement de données géométriques, comprenant les étapes suivantes : A. recevoir un volume de tolérance S2, relatif à des données géométriques brutes de départ, B. initier (201) une triangulation canonique dans le volume de tolérance, à partir d'un jeu S de points échantillons pris aux limites de ce volume de tolérance, et de points situés à l'extérieur de celui-ci, C. raffiner (203) cette triangulation canonique, jusqu'à classifier les points de l'échantillon, ce qui fournit un maillage dense du volume de tolérance, et D. simplifier (207) ce maillage dense par des opérations de modification de triangulation, en préservant la topologie et la classification des points de l'échantillon. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape B comprend la sous-étape (2011) d'échantillonner les limites du volume de tolérance selon une densité d'échantillonnage choisie a, ce qui fournit l'ensemble S de points échantillons. 3. Procédé selon la revendication 2, caractérisé en ce que l'étape B comprend le marquage (2013) de chaque point échantillon de l'ensemble S par une valeur- étiquette qui représente l'index de la composante connexe de bord de ce point, dans le volume de tolérance, et en ce que l'étape C comprend la génération itérative de la triangulation canonique, en insérant un point à la fois (2031), sur au moins une partie de l'ensemble S de points, jusqu'à ce que tous les points concernés (2033) vérifient une condition de classification (2032), appuyée sur la valeur d'une fonction F elle-même dépendant de leur valeur d'index, et sur son interpolation par une fonction d'interpolation f appliquée à chaque maille de la triangulation 3D, et la construction d'une isosurface linéaire par morceaux Zset, à l'aide des points où la fonction d'interpolation f possède une même valeur intermédiaire choisie, en particulier nulle, cette isosurface Zset étant une surface fermée, qui forme une approximation surfacique du volume de tolérance. 3039686 32 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que la triangulation canonique est une triangulation de Delaunay. 5. Procédé selon l'une des revendications précédentes, caractérisé en ce que les données géométriques brutes de départ sont des données 3D. 5 6. Procédé de traitement de données géométriques selon l'une des revendications précédentes, caractérisé en ce que l'étape D. comprend les opérations suivantes : Dl. déterminer (1701) si des opérations de modification de triangulation sont valides, c'est-à-dire préservent la topologie du maillage et préservent la condition de 10 classification de l'ensemble S de points échantillons, et D2. effectuer (1703-1709) les opérations de modification de triangulation valides dans un ordre déterminé. 7. Procédé selon la revendication 6, caractérisé en ce que les opérations de modification de triangulation comprennent des fusions d'arêtes et/ou des 15 fusions de demi-arêtes. 8. Procédé selon l'une des revendications 6 et 7, caractérisé en ce que l'ordre est déterminé en fonction d'un critère d'optimisation. 9. Procédé selon l'une des revendications 6 et 7, caractérisé en ce que l'étape D. porte sur un volume dit "tolérance simplicielle" qui approche le volume de 20 tolérance par une union de mailles de la triangulation canonique, l'isosurface Zset étant contenue dans ce volume dit "tolérance simplicielle", Et en ce que les étapes D1 et D2 sont effectuées : D'abord (2072) sur le bord du volume dit "tolérance simplicielle", Ensuite sur le fruit (2074) d'une triangulation mutuelle entre l'isosurface (Zset) et le 25 volume dit "tolérance simplicielle", cette triangulation mutuelle ajoutant des sommets, des arêtes et des mailles dans la triangulation, sur l'isosurface, Enfin (2076), avec d'autres arêtes contenues dans le volume dit "tolérance simplicielle", jusqu'à couvrir toutes les arêtes possibles. 10. Dispositif de traitement de données géométriques, comprenant : 30 - Une mémoire de données géométriques, pour recevoir des données (310) représentant un volume de tolérance, 3039686 33 Un organe d'initialisation (301), agencé pour réaliser une première triangulation canonique entre le bord du volume de tolérance et de points situés à l'extérieur de celui-ci, Un organe de raffinement (303), agencé pour préciser ladite première triangulation 5 jusqu'à fournir un maillage dense du volume de tolérance, qui préserve une condition de classification des points de la triangulation, Un organe de simplification (307), agencé pour simplifier ledit maillage dense, en préservant la topologie et la classification de ses points, et Un pilote (300) qui actionne successivement l'organe d'initialisation (301), l'organe 10 de raffinement (303), et l'organe de simplification (307), pour des données graphiques en évolution à partir du même volume de tolérance. 11. Dispositif selon la revendication 10, caractérisé en ce qu'il comprend : un opérateur de classification de point (1900), qui reçoit la désignation d'un point à traiter, et détermine une fonction d'interpolation sur la base de la maille entourant 15 ce point à traiter, et de valeurs-étiquettes relatives aux sommets de cette maille, pour fournir une étiquette interpolée, et comparer celle-ci à une étiquette courante du point à traiter, ce qui permet de déterminer une condition de classification du point à traiter. 12. Produit-programme d'ordinateur comprenant des portions de code de 20 programme pour mettre en oeuvre le procédé selon l'une des revendications 1 à 9, ou le dispositif selon l'une des revendications 10 et 11, lorsque le programme est exécuté sur un ordinateur.