FR 3039685 A1 20170203 FR 1501664 A 20150801 INRIA 180 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 3039685 2 INRIA 180 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 3039685 3 INRIA 180 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 O. 3039685 4 INRIA 180 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 SI, 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 du 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. - Un raffinement, qui vise à définir un maillage primaire, de topologie correcte, dans le volume de tolérance, et L'étape B peut comprendre la sous-étape d'échantillonner les limites du volume de 20 tolérance selon une densité d'échantillonnage choisie cy, ce qui fournit 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 comprend alors la génération itérative 25 de la triangulation canonique, en insérant un point à la fois, sur au 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. 30 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. 3039685 5 INRIA 180 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. peut comprendre les opérations suivantes : Dl. déterminer si des opérations de modification de triangulation sont valides, c'est-à- 5 dire préservent la topologie du maillage et préservent la condition de classification de l'ensemble 5 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 10 fusions d'arêtes et/ou des fusions de demi-arêtes. 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 15 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 20 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. 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 : 25 - Les figures 1-a à 1-e illustrent schématiquement un premier exemple d'application de l'invention ; - 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, 30 - la figure 5 est un dessin illustrant la définition de ratios barycentriques, 3039685 6 INRIA 180 - la figure 6 est un diagramme de flux qui détaille une réalisation préférentielle de 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, 5 - 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, - les figures 9 sont des dessins illustrant un cas particulier d'application de l'invention, - les figures 10 sont des représentations d'éléphants montrant la robustesse du procédé selon l'invention, 10 - les figures 11 illustrent schématiquement d'autres exemples d'application de l'invention, sur le même objet que les figures 1, - 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 15 diagrammes des figures 12 et 13, - les figures 15 sont des représentations comparables à celle de la figure 3, permettant 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, et 20 - 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. 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 présente invention, mais aussi contribuer à sa définition, le cas échéant. La nature de 25 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 annexes font partie intégrante de la description. 30 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. 3039685 7 INRIA 180 La figure 1-a illustre le point de départ, à savoir un volume de tolérance f2 relatif à une pièce mécanique mesurée par un scanner laser, avec une tolérance d'entrée 8 de 0,6 %. La figure 1-b illustre ce qu'on obtient après l'étape de raffinement (203, figure 2). Le 5 résultat est une fonction linéaire par morceaux Z, correspondant à un maillage surfacique du volume de tolérance f2 de la figure 1. Le nombre de sommets est 20,4k (20.400). 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 10 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 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 15 est descendu encore à 752 sommets. On observe, à l'oeil, que, même simplifié, le maillage de la figure 1-e représente bien l'objet défini par les figures précédentes. 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. 20 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 f2 est défini par une forme curviligne boudinée, dont la zone frontière an présente deux bordures ani et d1.22, dans une vue en coupe en plan. 25 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. 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 30 centrées sur tous les points s de S recouvrent intégralement la zone frontière df2 du volume de tolérance n. En pratique, o est une fraction de l'épaisseur 6 de n. 3039685 8 INRIA 180 Dans le cas le plus simple, celui de la figure 3, la zone frontière clO n'a que deux composantes connexes de surfaces de bord, à savoir (301 (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 dO. Cela peut se faire formellement, en affectant à 5 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 mi, et F(s) = -1 si le point s est sur ô02. Cette valeur F(s) peut être vue comme une représentation de l'index (ou "indice") de la 10 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 maille M (triangle ou tétraèdre), et des coordonnées barycentriques du point x 15 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, ai est positif ou nul, et la somme des at est 1. Les valeurs de ai se définissent par exemple comme indiqué sur la figure 5 : 20 Pour un point X situé dans une maille triangulaire ABC, l'un des a, 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 : f(x,M) = aA(X) F(A) + aB(X) F(B) + ac(X) F(C) 25 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 XBCD au volume du tétraèdre ABCD. Et la formule devient : 30 f(x,M) = aA(X) F(A) + aB(X) F(B) + ac(X) F(C) + aD(X) F(D) 3039685 9 INRIA 180 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 s'impose au cours du raffinement. On en donnera des exemples plus loin, en référence 5 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 (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 10 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. 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). 15 On considère un paramètre a, avec (0 On considérera d'abord la figure 7.8. 3039685 16 INRIA 180 Au terme du maillage par triangulation qui constitue le raffinement, on a un ensemble de tétraèdres. On appelle la "tolérance simplicielle", notée I-, l'union des tétraèdres qui constituent une approximation maillée (triangulée) du volume de tolérance O. Ces tétraèdres ont des sommets avec des étiquettes différentes. 5 Le bord de cette "tolérance simplicielle" est noté al' (sur la Figure 7.8). En 3D, ce bord est composé des triangles qui sont les faces libres des tétraèdres du maillage. C'est une représentation triangulée de la frontière du domaine de tolérance. Le trait mixte sur la figure 7.8 illustre celles des arêtes de cette représentation triangulée qui sont dans le plan de la figure. 10 A partir de là, la simplification de la représentation maillée des figures 7.7 ou 7.8 peut s'effectuer essentiellement en utilisant un processus dit "fusion d'arêtes" (en anglais "edge collapse"). La nature de ce processus sera maintenant décrite en référence aux figures 16, qui sont en 2D. 15 La figure 16.0 indique les extrémités A et B d'une arête que l'on peut fusionner (on en verra plus loin les conditions). L'opérateur général de fusion supprime l'arête qui joint les sommets, l'un au moins de ces deux sommets, et les faces ou tétraèdres adjacents à l'arête supprimée (Figure 16.2). La position du sommet P résultant de la fusion (sommet cible) est un degré de 20 liberté (continu) de cet opérateur, sous condition de préserver la topologie et de bien classifier tous les points. Dans le cas où ces deux contraintes (topologie et classification) peuvent être satisfaites, il existe une ou plusieurs régions de l'espace (région de validité) où le sommet cible P peut être placé. On peut le placer arbitrairement dans cette région, 25 mais il est préférable de choisir un point optimum. Pour cela, on peut utiliser un calcul d'erreur en un point. L'erreur est par exemple la somme des carrés des distances de ce point aux plans support des facettes de l'isosurface Z, ces facettes étant sélectionnées dans un voisinage local à l'arête considérée. Ce voisinage local peut comprendre les facettes de l'isosurface qui sont 30 localisées à une distance 2 de l'arête dans le graphe de la triangulation (ce que l'on appelle « 2-ring »). On recherche le point Q optimum qui minimise cette erreur. Ce calcul d'erreur sert de critère d'optimisation. En effet, comme point P préféré, on peut alors prendre le point situé dans la région de validité, et qui se trouve le plus près possible du point Q optimum qui minimise ladite erreur. 3039685 17 INRIA 180 Il est à noter que ce mode de calcul d'erreur et de détermination du point P préféré est particulièrement pertinent pour des surfaces planaires par partie ; on peut cependant imaginer d'autres solutions en fonction de la nature des surfaces en entrée. Par exemple pour les surfaces courbes par parties, on peut imaginer choisir non plus des 5 plans mais des surfaces paramétriques de type quadriques ou cubiques, et prendre comme erreur la somme des carrés des distances à ces surfaces. En pratique, pour augmenter la rapidité du traitement, il est intéressant d'utiliser aussi, en variante, un opérateur purement combinatoire que l'on appelle « opérateur de fusion de demi-arête » : dans cette variante moins générale, l'opérateur est contraint à 10 fusionner un sommet de l'arête sur l'autre. Sur la figure 16.1, on fusionne ainsi le sommet A sur le sommet B. Et le critère d'optimisation est défini par la distance entre le point cible (ici le point B) et le point Q optimum calculé comme ci-dessus. Cet opérateur de fusion de demi-arête est moins puissant que l'opérateur de fusion d'arête qui admet de placer le sommet résultant de la fusion à une position générale P 15 dans l'espace, mais il est beaucoup plus rapide à simuler, puisque l'on connaît directement le point cible B, sans avoir à rechercher le meilleur point P. L'opérateur de fusion de demi-arête est dit combinatoire dans le sens où il existe un nombre fini de degrés de liberté : 2 E fusions possibles, où E représente le nombre d'arêtes de la triangulation. Ensuite lorsqu'aucune fusion de demi-arête n'est possible, 20 on a recours à l'opérateur plus général de fusion d'arêtes. Il convient de bien comprendre la différence entre les deux phases : raffinement et simplification. Pendant le raffinement on insère des points de l'échantillon dans une triangulation canonique (dont la connectivité est déterminée par les positions des points). Donc, 25 dans cette phase de raffinement, les degrés de liberté ne sont qu'en termes de choix de points. Pendant la simplification, on va voir que les opérateurs de fusion agissent par arêtes ou demi-arêtes, donc une queue de priorité trie les opérateurs qui sont valides (qui préservent la topologie et classification des points), suivant un score qui dépend d'un 30 critère d'optimisation. Le but final est de simplifier le plus possible, et on observe que certaines positions de points après fusion sont propices à une simplification plus importante, intuitivement en préparant mieux les simplifications futures car davantage d'opérateurs de fusion seront valides par la suite. 3039685 18 INRIA 180 On précisera maintenant les contraintes (topologie et classification) qui vont permettre de déterminer si un opérateur de fusion en cours de simulation est applicable (« valide ») ou non. Pour la contrainte de préservation de la topologie, on peut utiliser trois notions : 5 - Une « link condition », décrite dans [Ref21], pour la propriété D-manifold. En 2D cette condition assure que tout voisinage d'un point est homéomorphe (topologiquement équivalent) à un disque ou à un demi-disque. Sur le plan topologique cette condition impose que chaque arête est adjacente à exactement une ou deux faces triangulaires, et que chaque sommet est adjacent à une seule 10 composante connexe. En 3D cette condition assure que tout voisinage d'un point est homéomorphe (topologiquement équivalent) à une boule ou une demi-boule. - La détermination d'un noyau de polyèdres pour vérifier que le plongement est valide [Ref27]. En 3D le noyau d'un polyèdre est le lieu des points qui voient tout le bord du polyèdre. Dans le cas général le noyau est soit vide, soit un polyèdre 15 convexe. Le polyèdre considéré pour le calcul du noyau est le polyèdre formé par l'union des tétraèdres adjacents aux deux sommets de l'arête. Lorsque le noyau est non vide on peut fusionner l'arête en plaçant le sommet cible dans le noyau : la triangulation reste valide, c'est-à-dire sans chevauchement ni retournement de tétraèdres. Lorsque le noyau est vide on ne peut pas fusionner l'arête sans créer 20 une triangulation invalide. Dans notre contexte on utilise la construction du noyau pour délimiter une zone de recherche de points qui classifient bien (c'est le point ci-après). - La préservation de la classification des points de l'échantillon, qui se fait comme précédemment, et que l'on reverra ci-après. 25 Un opérateur de fusion en cours de simulation sera donc considéré comme valide si : - La « link condition » est vérifiée, La condition de plongement valide est vérifiée, - la classification des points de l'échantillon est préservée. Le processus de simplification peut être conforme à la figure 17. 30 On considère une à une toutes les arêtes existant dans différentes parties de la triangulation, en commençant par le bord de la tolérance simplicielle, comme on le verra. 3039685 19 INRIA 180 Pour chaque arête, l'étape 1701 simule d'abord la fusion de cette arête, pour déterminer si cette fusion est possible (« valide »). Comme déjà indiqué, on essaiera d'abord un opérateur de fusion de demi-arête, puis un opérateur de fusion d'arête générale. La simulation se fait sur la base de l'état courant de la triangulation. 5 Si l'opérateur de fusion en cours de simulation est valide, l'étape 1703 en stocke la définition dans une queue dynamique de priorité. L'ordre de priorité est défini par le critère d'optimisation précité. A l'étape 1705, on applique le premier opérateur de fusion, dans l'ordre de la queue de priorité. 10 Après cela, l'étape 1707 met à jour la queue de priorité : suppression des opérateurs qui n'ont plus de raison d'être, car ils portent sur une arête supprimée par l'opérateur de fusion qui vient d'être exécuté. Re-simulation des opérateurs modifiés, que l'on remet dans la queue, avec leur critère d'optimisation recalculé. Un opérateur est « modifié » lorsque l'opérateur 15 de fusion qui vient d'être exécuté a modifié les parties de la triangulation qui sont adjacentes aux deux sommets de l'arête sur laquelle il porte. Les sous-étapes 2072 à 2076 de l'étape 207 de la figure 4 montrent que l'on opère en trois temps. A chaque temps, on considérera d'abord des fusions de demi-arête, puis des fusions d'arête générales. 20 Ici, une triangulation réciproque (décrite en détail plus loin) s'effectue dans l'étape 2074, au sein de la phase de simplification. Il serait concevable d'effectuer cette triangulation réciproque juste après avoir fait le raffinement. Autrement dit, on peut imaginer simplifier toutes les arêtes possibles après avoir fait tout le raffinement, y compris la triangulation réciproque. Le procédé proposé est considéré comme plus 25 parcimonieux, car il permet une plus faible complexité de la triangulation. Ainsi, le Demandeur estime actuellement qu'il est préférable de simplifier la triangulation du volume de tolérance (la tolérance simplicielle) avant de lancer la triangulation réciproque, puis le reste de la simplification. L'idée est de réduire la taille de la triangulation avant de la simplifier car le nombre d'opérateurs à utiliser est 30 fonction de cette taille. A noter aussi le point suivant : dans le raffinement, la triangulation 3D proposée est celle de Delaunay ; elle est commode, car canonique pour un ensemble de points, et on sait prouver la terminaison du raffinement. Mais c'est « verbeux » : car c'est à points fixés une triangulation la plus isotrope possible- autant dire peu parcimonieuse 3039685 20 I NRIA 180 (en points) aux endroits ou la géométrie est anisotrope. L'idée est donc de réduire la taille de la triangulation avant de la simplifier car le nombre d'opérateurs à utiliser est fonction de cette taille. La simplification sera maintenant illustrée, en référence aux figures 8.0 à 8.11. 5 La figure 8.0 reprend le maillage, en son état de la figure 7.7, dont la figure 7.8 a montré qu'il s'agissait de la tolérance simplicielle r. On sait que l'isosurface Zset est contenue dans ce volume de "tolérance simplicielle" noté r. La simplification porte d'abord sur le bord ar de la "tolérance simplicielle" (étape 2072 de la figure 4). 10 Sur la figure 8.0, deux des points sont reliés par une arête SF1, illustrée en gras, pour indiquer qu'ils peuvent être fusionnés. Comme déjà indiqué, la fusion entre deux sommets adjacents fait disparaitre l'arête qui les joint, l'un de ces deux sommets, et les faces ou tétraèdres adjacents à l'arête supprimée. 15 Lorsque l'on fusionne deux sommets en 3D, on va aussi fusionner (effondrer l'une sur l'autre) deux arêtes situées entre ces deux points et un troisième (qui n'est pas dans le plan de la figure). Par conséquent, il faut considérer l'ensemble des primitives (triangles en 2D ou tétraèdres en 3D) qui sont adjacentes aux sommets de l'arête supprimée. Les points de 20 l'échantillon qui sont situés dans ces primitives sont appelés ici "points concernés par la fusion". Il faut alors que, au voisinage des arêtes à effondrer, l'erreur c en tous les points concernés par la fusion vérifie la condition précitée : = 2/ (Ga). 5 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 naturellement résolus. Comme autres facteurs perturbateurs du raffinement, on peut aussi rencontrer des 10 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, 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 15 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 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 20 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 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). 25 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) 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 30 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 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ù 3039685 25 INRIA 180 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. L'invention a été mise au point en utilisant la base informatique suivante : 5 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 Grasse, France, Bibliothèque INTEL "Threading Building Blocks library" pour la parallélisation. Il est 10 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. Les figures 11 reprennent la pièce des figures 1. La figure 11.0 est le volume de 15 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 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. 20 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 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. 25 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 : 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é 30 Geometry Factory déjà citée, 3039685 26 INRIA 180 - 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], - MMGS-A, qui est une variante du même logiciel MMGS avec l'option anisotropie de mailles, 5 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. 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 10 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 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, 15 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. 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. 20 Les figures 12 et 13 ont pour entrée un maillage de surface brut des images des figures 14 (environ 14 000 sommets). 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 8, indiquées dans le rectangle de légende. En abscisse, on a les 25 différentes étapes du traitement, à savoir : - Raffinement, - Simplification par fusions de demi-arêtes de la frontière al" de la tolérance simplicielle, Simplification par fusions d'arêtes de la frontière ÔF de la tolérance simplicielle, 30 - Triangulation mutuelle et fusions de demi-arêtes du zeroSet Z, - Fusions d'arêtes du zeroSet Z, 3039685 27 INRIA 180 - Simplification de tous les bords. 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. 5 3039685 28 INRIA 180 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 : "tolerance 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, et, corrélativement, plusieurs composantes connexes de ses surfaces de bord. 30 3039685 29 INRIA 180 Annexe 2 - Références [Refl]. 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., CHOI, 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. [RefS]. 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. [Ref8]. 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. [Ref27]. 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 f2, 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 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 dense du volume de tolérance, et D. simplifier 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 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 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, sur au 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, 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. 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. 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 : 3039685 31 INRIA 180 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 l'ensemble S de points échantillons, et D2. effectuer les opérations de modification de triangulation valides dans un ordre déterminé. 5 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 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 10 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 simplicielle", Et en ce que les étapes D1 et D2 sont effectuées : - D'abord sur le bord du volume dit "tolérance simplicielle", 15 - Ensuite sur le fruit d'une triangulation mutuelle entre l'isosurface (Zset) et le volume dit "tolérance simplicielle", cette triangulation mutuelle ajoutant des 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. 20 10. Produit-programme d'ordinateur comprenant des portions de code de programme pour mettre en oeuvre le procédé selon l'une des revendications 1 à 9, lorsque le programme est exécuté sur un ordinateur.