TREATMENT OF GEOMETRIC DATA WITH ISOTOPIC APPROXIMATION IN A VOLUME OF TOLERANCE

专利摘要:
The geometric data processing starts from a tolerance volume Ω, relative to raw geometric data of departure. We initiate (201) a canonical triangulation in the tolerance volume, from a set S sample points taken at the limits of this tolerance volume, and points LBB located outside thereof. This canonical triangulation (203) is refined to classify the points of the sample, which provides a dense mesh of tolerance volume. And we simplify (207) this dense mesh by triangulation modification operations, preserving the topology and the classification of the points of the sample.
公开号:FR3039686A1
申请号:FR1557674
申请日:2015-08-11
公开日:2017-02-03
发明作者:Pierre Alliez；David Cohen-Steiner；Manish Mandad
申请人:Institut National de Recherche en Informatique et en Automatique INRIA；
IPC主号:

专利说明:

où pour tout i, ai est positif ou nul, et la somme des ai est 1. Les valeurs de ai se définissent par exemple comme indiqué sur la figure 5 :
Pour un point X situé dans une maille triangulaire ABC, l'un des ai 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) 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 : f(x,M) = aA(X) F(A) + aB(X) F(B) + ac(X) F(C) + aD(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 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 (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 ε, qui peut être définie comme suit : ε (s) = | f(s, M) - F(s) |, où la notation | x | 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).
On considère un paramètre a, avec (0 < a < 1). La valeur par défaut de a peut être fixée à 0,2. On dira alors : si ε (s) <= (1 - a), que le point s est bien classifié avec la marge a,
Sinon, que le point s est mal classifié.
Une valeur ε proche de 1 indique que le maillage doit être raffiné.
Ce raffinage se fait en ajoutant à l'ensemble Sp (ensemble des points qui font l'objet de la triangulation) un point x de l'ensemble S qui ne fait pas encore partie de Sp. Ce point x inséré dans le maillage possède une valeur-étiquette F(x). On refait alors le calcul de classification, et de l'erreur ε, pour tous les points non insérés de l'ensemble S (c'est-à-dire pour tous les points de l'ensemble S qui ne font pas partie de l'ensemble Sp).
En théorie du moins, il serait possible de procéder dans un ordre arbitraire. On préfère actuellement commencer par les points qui donnent l'erreur la plus grande, et faire une itération ensuite. C'est ce que l'on décrira plus loin, en référence au mécanisme illustré sur la figure 6.
On observe que ce mécanisme converge quel que soit le mode de sélection des points ajoutés: dans le pire des cas on ajouterait tous les points de l'échantillon, et ils sont alors tous bien classifiés.
Dans le cadre d'un raffinement de Delaunay, les points que l'on ajoute à l'ensemble courant d'échantillons à trianguler (Sp) sont appelés "points de Steiner." (A ne pas confondre avec le point de Fermât d'un triangle, que certains appellent aussi "point de Steiner").
Quand ceci est terminé, et que tous les points sont correctement classifiés, c'est-à-dire que l'erreur est partout <= (1 - a), on dispose d'un maillage primaire correct, mais compliqué.
On recommencera maintenant la description sur la base des figures 7, qui sont très géométriques, ce qui facilite la compréhension. Ces figures illustrent le traitement en deux dimensions, que l'homme du métier saura transposer en trois dimensions. Seule l'illustration 2D est possible ; en effet, des figures en 3D seraient illisibles, car tout se superposerait à l'écran.
La figure 7.0 montre un volume de tolérance tel quel.
La figure 7.1 montre la phase d'initialisation, dans laquelle apparaissent les points s de l'échantillonnage S des bordures de la zone frontière du volume de tolérance. A l'extérieur, pour l'étiquette F(s) = 1, ces points sont des ronds creux. A l'intérieur, pour l'étiquette F(s) = -1, ce sont des ronds pleins.
La figure 7.2 fait apparaître une enveloppe dite boîte englobante élargie LBB. Cette boîte englobante élargie LBB (ou "Loose Bounding Box") peut être construite en calculant la boite englobante stricte du volume de tolérance, à l'aide du minimum et du maximum des coordonnées en x,y,z des points du volume de tolérance. Cette boîte LBB est agrandie par homothétie d'un facteur 1.5, par exemple.
La boîte englobante élargie LBB comprend les points LBB1 à LBB4 visibles sur la figure 7.2. En 2D, la boîte englobante est formée par seulement 4 points, contre 8 points en 3D. On peut utiliser d'autres moyens permettant de définir des points externes dont la propriété d'englobement est garantie.
On considère alors un autre ensemble Sp de points sp. Au départ vide, cet ensemble Sp reçoit d'abord tous les points de la boîte englobante élargie LBB. A l'étape 2015 de la figure 4, on commence par réaliser une triangulation T à partir de ces premiers points de la LBB placés dans Sp, mais qui ne sont pas des points de S.
Les segments de droite qui forment les limites des mailles sont illustrés en trait tireté long et fin, sur les figures 7.
On donne aux points de la LBB des valeurs étiquettes spéciales, qui dépendent de leur distance par rapport au bord du volume de tolérance. Ces valeurs étiquettes spéciales peuvent être supérieures à 1.
Par exemple : on assigne la valeur-étiquette 1 au bord le plus externe du volume de tolérance, et l'étiquette 'd+1' aux sommets de la LBB, où d représente la distance normalisée entre un sommet de la LBB et le point du bord externe du volume de tolérance qui est le plus proche du sommet de la LBB. La normalisation est fonction de l'épaisseur du volume de tolérance, qui est déterminée à la valeur 2 (la différence entre -1 et +1).
On fait alors le calcul de classification, et de l'erreur ε, pour tous les points non insérés de l'ensemble S, auxquels s'ajoutent les points de la boîte englobante élargie qui sont dans l'ensemble Sp.
Ce calcul souffre une exception dans le cas où un point de l'échantillon est localisé dans une maille où la fonction est homogène, c'est-à-dire avec des valeur-étiquettes identiques aux sommets de la maille. Dans ce cas si la fonction a le même signe que le label du point de l'échantillon alors il est bien classifié, et mal classifié sinon, sans qu'on se serve de l'erreur ε.
Comme déjà indiqué, tous les points s de l'ensemble S se sont vu affecter une valeur étiquette F(s). La fonction d'interpolation f est construite, comme précédemment, pour chaque maille (triangle en 2D, tétraèdre en 3D) : Pour un point x de l'ensemble Sp, présent dans une maille tétraédrique, on calcule une fonction d'interpolation linéaire f(x, M), définie sur la base des valeurs étiquette F(s) aux sommets de la maille tétraèdre M, et des coordonnées barycentriques du point x considéré, par rapport aux sommets de la maille. Et l'on calcule à chaque fois la grandeur d'erreur ε, qui indique si le point x est ou non bien classifié.
Sur la figure 7.2, un point bien classifié est représenté par un carré. Un point mal classifié est représenté par une croix.
On observe que la fonction interpolée sur les deux triangles LLB1-LBB2-LBB3, ainsi que LLB1-LBB3-LBB4 est ici homogène et positive en tous points, puisque les sommets de la LBB ont tous une étiquette 'd+1' qui est nettement positive.
On est donc dans le cadre de l'exception précitée.
Les ronds creux de la figure 7.1 ont un label positif + 1. Ils sont donc de même signe que la fonction interpolée sur les deux triangles, et par conséquent bien classifiés. Par conséquent, ces ronds creux de la figure 7.1 deviennent des carrés sur la figure 7.2.
De leur côté, les ronds pleins de la figure 7.1 ont un label négatif - 1. Ils sont donc de signe contraire à la fonction interpolée sur les deux triangles, et par conséquent mal classifiés. Par conséquent, ces ronds pleins de la figure 7.1 deviennent des croix sur la figure 7.2.
Commence ensuite le raffinement proprement dit (étape 203 de la figure 2, et cadre 203 de la figure 4). A l'étape 2031 de la figure 4, on ajoute un premier point de Steiner SP1 dans la triangulation. Ce point SP1 est ajouté à l'ensemble Spdes points à trianguler.
Ce point SP1 peut être celui dont l'erreur ε est maximum, comme indiqué ici par ailleurs.
Sur la figure 7.3, ce premier point de Steiner SP1 se trouve par hasard être proche de la diagonale L1 de l'enveloppe LBB. L'étiquette de SP1 est F(SP1) = -1.
On refait alors le calcul de classification, et de l'erreur ε, pour tous les points de l'ensemble S, et pour le point SP1 ajouté (étape 2032 de la figure 4).
Les deux points extrêmes LBB1 et LBB3 de la diagonale L1 font partie de la LBB. Cela détermine une version "SP1" de la fonction f, calculée comme indiqué plus haut, dans les 4 mailles triangulaires LBB1-LBB2-SP1, LBB2-LBB3-SP1, LBB1-LBB4-SP1, LBB3-LBB4-SP1. On obtient finalement f(SPl) = -1, ce qui classifie bien le point ajouté SP1.
Autour du point SP1 est alors définie une isosurface IS1, où f = 0. Cette isosurface est illustrée par une ligne brisée noire en traits gras, presque carrée, sur la figure 7.3.
Considérons le triangle LBB1-LBB2-SP1. La fonction interpolée vaut -1 en SP1, et une valeur positive plus grande que 1 en LBB1 et LBB2, disons 5. Le long de l'arête SP1-LBB1 la fonction varie donc linéairement de -1 à 5, et on trouve donc le niveau zéro de la fonction interpolée f près de SP1, au dessus.
Considérons maintenant le triangle LBB3-LBB4-SP1. Par symétrie, on trouve un autre niveau zéro de la fonction interpolée f près de SP1, au dessous, cette fois.
Les deux segments verticaux de IS1 s'expliquent de la même manière, en considérant les triangles LBB2-LBB3-SP1 et LBB1-LBB4-SP1. L'analyse en 2D faite ci-dessus peut s'extrapoler vers le 3D de la manière suivante : En 3D, la fonction interpolée f est toujours linéaire par morceau, mais évolue dans l'espace donc il y a une profondeur en plus ; et l'isosurface zeroset (ou Zset) n'est plus un segment dans un triangle, mais un polygone planaire dans un tétraèdre, à savoir un triangle ou un quadrilatère.
On observe que, sur la ligne horizontale de points contenue au centre de IS1, les points sont maintenant bien classifiés, et les croix sont devenues des carrés, avec F(s) = 1. Au contraire, les points situés à l'extérieur de IS1 sont restés des croix, avec F(s) = -1, donc mal classifiés.
On observe que la partie basse du contour IS1 est à mi-chemin entre la ligne horizontale de points contenue dans IS1, et la ligne de croix située en dessous.
Les autres éléments du contour IS1 dépendent de la version "SP1" de la fonction f, comme on l'a expliqué plus haut. L'isovaleur IS1 représente le niveau zéro de la fonction interpolée, qui est donc positive d'un côté de IS1, et négative de l'autre côté de IS1. Les points de l'échantillon sont bien classifiés lorsqu'ils sont situés du côté de IS1, qui correspond au signe de leur label ou valeur-étiquette. D'autres informations utiles pour construire une triangulation de Delaunay pourront être trouvées dans [Ref23], Ces informations sont à considérer comme incorporées à la présente description.
Il est à noter que, pour des points en position générale (en 2D, pas plus de 3 points cocirculaires, et en 3D pas plus de 4 points co-sphériques), il existe une seule triangulation de Delaunay, qui est donc canonique. Une propriété est en 2D que les cercles circonscrits aux triangles ne contiennent aucun autre point; de même, en 3D, les sphères circonscrites aux tétraèdres du réseau (constitués par des points du sous-ensemble Sp de S) sont vides, et ne contiennent aucun autre point que les sommets du tétraèdre.
La triangulation de Delaunay est terminée quand tous les points de l'ensemble S sont correctement classifiés (étape 2033 de la figure 4).
Si ce n'est pas le cas, on répète les étapes 2031 à 2033 de la figure 4, en insérant un nouveau point de Steiner. C'est ce qui est fait avec le point SP2 de la figure 7.4, qui est ajouté à l'ensemble Spdes points à trianguler.
On refait alors le calcul de classification, et de l'erreur ε, pour tous les points de l'ensemble S, et pour les points SP1 et SP2 ajoutés (étape 2032 de la figure 4). Il en découle une version dite "SP2" de la fonction f.
Les points où cette version "SP2" de la fonction f est nulle définissent une nouvelle isosurface IS2, qui englobe les points SP1 et SP2. Sur les segments CC20 et CC22 du contour du volume de tolérance, les points restent mal classifiés (des croix). Par contre, au voisinage de SP2, les segments CC21 et CC23 contenus dans IS2 comprennent maintenant des points bien classifiés.
De même, le segment en équerre CC24 devient bien classifié, contrairement aux segments alignés sur lui, mais extérieurs à IS2.
Inversement, les segments en équerre CC25 et CC26 deviennent mal classifiés, contrairement aux segments alignés sur eux, mais extérieurs à IS2. A l'étape de test 2033 de la figure 4, certains points de l'ensemble S restent mal classifiés.
On répète donc les étapes 2031 à 2033 de la figure 4, en insérant un nouveau point de Steiner SP3, comme illustré sur la figure 7.5.
On refait alors le calcul de classification, et de l'erreur ε, pour tous les points de l'ensemble S, et pour les points SP1, SP2 et SP3 ajoutés (étape 2032 de la figure 4). Il en découle une version "SP3" de la fonction f.
Les points où cette version "SP3" de la fonction f est nulle définissent une nouvelle isosurface IS3, qui englobe les points SP1, SP2 et SP3.
Comme précédemment, on observe que les points qui sont à l'intérieur de IS3 n'ont pas la même classification que les points situés sur la même ligne qu'eux, mais à l'extérieur de IS3. A l'étape de test 2033 de la figure 4, certains points de l'ensemble S restent mal classifiés.
On va répéter plusieurs fois les étapes 2031 à 2033 de la figure 4, en insérant à chaque fois un nouveau point de Steiner. Cela donne la figure 7.6, où les points de Steiner sont de gros ronds noirs, si leur valeur-étiquette est négative, ou bien de gros cercles intérieurement blancs, si leur valeur-étiquette est positive. L'isosurface obtenue se rapproche de la forme générale du volume de tolérance, mais il reste des points mal classifiés.
On va encore répéter plusieurs fois les étapes 2031 à 2033 de la figure 4, en insérant à chaque fois un nouveau point de Steiner. Cela aboutit à la figure 7.7, où l'isosurface est entièrement contenue dans le volume de tolérance, et il n'y a plus de croix (de points mal classifiés). A l'étape de test 2033 de la figure 4, on a maintenant atteint la fin du raffinement.
On passe donc à la phase 207 de simplification (ou décimation), des figures 2 et 4.
On a ainsi décrit l'étape 203 des figures 2 et 4, qui est dite "raffinement". L'un des buts de ce raffinement est d'arriver à un maillage sans intersection de surface, qui corresponde à la topologie du volume de tolérance. Comme l'indique le mot "raffinement", on fait évoluer le maillage "de-grossier-à-fin", à l'aide des points successivement insérés.
Le maillage lui-même peut se faire en utilisant une triangulation de Delaunay, dont les structures de données n'acceptent pas d'intersection de surfaces. On peut utiliser d'autres techniques pour construire des triangulations canoniques qui ne s'intersectent pas. Le Demandeur préfère actuellement une triangulation utilisant la propriété de Delaunay, avec la preuve de terminaison et la garantie de topologie qu'elle permet.
Comme indiqué, la sélection des points de Steiner insérés peut se faire en fonction de la grandeur d'erreur ε. Ceci peut être réalisé sur la base du mécanisme de la figure 6, que l'on décrira maintenant, en version 3D. A l'étape 601, on maintient, pour chaque tétraèdre de la triangulation T, une liste de ceux des points échantillons s de l'ensemble S qui sont contenus dans ce tétraèdre. Chaque point est accompagné de son étiquette, et de son erreur ε. Les points de l'ensemble Sp qui sont déjà inclus dans la triangulation ne sont pas dans cette liste. A l'étape 603, on maintient une queue dynamique de priorité, pour chaque tétraèdre de la triangulation T, contenant les points d'erreur maximale dans les tétraèdres, triés par erreur décroissante. A l'étape 605, qui correspond à l'étape 2031 de la figure 4, on ajoute dans la triangulation T le point d'erreur maximale en tête de queue, qui peut être alors supprimé de la queue. A l'étape 607, qui correspond à l'étape 2032 de la figure 4, les calculs d'erreur sont mis à jour. Un test 609, qui correspond à l'étape 2033 de la figure 4, examine si la topologie est correcte, i.e. si l'ensemble S est complètement classifié. Si ce n'est pas le cas, on retourne en 601. Sinon, on peut passer à la phase suivante de simplification du maillage.
En fin de raffinement, la représentation maillée des figures 7.6 et 7.7 est correcte, en ce sens notamment qu'elle ne comprend pas d'intersections, et qu'elle est isotopique. Par contre, elle est trop dense, et contient un nombre excessif de mailles (ou de sommets). On va donc la simplifier, comme on le verra plus loin.
On considérera d'abord la figure 7.8.
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 Γ, l'union des tétraèdres qui constituent une approximation maillée (triangulée) du volume de tolérance Ω. Ces tétraèdres ont des sommets avec des étiquettes différentes.
Le bord de cette "tolérance simplicielle" est noté ST (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. 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.
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 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, 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 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.
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 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 à 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 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, 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, 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 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.
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 :
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 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 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 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.
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.
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.
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.
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é.
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 de fusion qui vient d'être exécuté a modifié les parties de la triangulation qui sont adjacentes à l'un au moins des deux sommets de l'arête sur laquelle il porte (ou aux deux sommets).
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.
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 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 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 (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.
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 Γ. On sait que l'isosurface Zset est contenue dans ce volume de "tolérance simplicielle" noté Γ.
La simplification porte d'abord sur le bord ST de la "tolérance simplicielle" (étape 2072 de la figure 4).
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 disparaître 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.
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 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 ε en tous les points concernés par la fusion vérifie la condition précitée : ε <= (1- a) autrement dit que tous les points concernés par la fusion soient bien classifiés (symbolisés par des carrés) après la fusion. C'est ce qu'on appelle préserver la condition de classification des points de l'ensemble S.
Comme indiqué, on détermine à l'avance quels sont les opérateurs de fusion qui préservent la classification et la topologie en les « simulant », sans les appliquer. Seuls les opérateurs de fusion retenus comme convenables (« valides ») après simulation sont rangés dans la queue de priorité dynamique de l'étape 1703.
Dans le but d'accélérer les traitements, on effectue d'abord les fusions de demi-arête (half-edge collapse), dont les opérateurs sont beaucoup plus rapides à simuler. Ensuite lorsqu'aucune fusion demi-arête n'est possible on considère les opérateurs plus généraux de fusion d'arêtes.
On peut dire aussi que les mailles de Delaunay concernées doivent être homogènes en ce qui concerne la bonne classification des points. A noter qu'au niveau de la simplification, il n'est pas vérifié que le maillage continue à satisfaire les conditions de Delaunay.
Le résultat après cette première fusion de de demi-arêtes et/ou d'arêtes est illustré sur la figure 8.1.
On a refait le calcul de classification, et de l'erreur ε, pour ceux des points de l'ensemble S qui sont concernés par la fusion. On a également recalculé l'isosurface.
Sur la figure 8.2, deux des points sont reliés par une arête SF2, illustrée en gras, pour indiquer qu'ils peuvent être fusionnés eux aussi.
Le résultat après cette autre fusion est illustré sur la figure 8.3.
Ceci est répété avec tous les points qui peuvent être fusionnés. Quand il n'y a plus d'arêtes à fusionner (de points qui peuvent être fusionnés) au niveau du bord de la tolérance simplicielle 0Γ, on aboutit au résultat de la figure 8.4.
En résumé, jusqu'à présent, la simplification a comporté les étapes suivantes : hl. Délimiter un volume dit "tolérance simplicielle", noté Γ. Il est constitué d'une union de mailles de la triangulation de Delaunay 3D, choisies pour constituer une approximation maillée du volume de tolérance. C'est illustré en 2D sur la figure 7.8, où le trait mixte indique le bord 0Γ de cette tolérance simplicielle. h2. Effectuer des fusions d'arêtes dans 0Γ, en vérifiant la préservation de la condition de classification de S (Figures 8.1 à 8.4).
On continue comme suit : h3. Effectuer une triangulation mutuelle entre l'isosurface (Zset) et le volume dit "tolérance simplicielle", tel que modifié à l'opération h2 (étape 2074 de la figure 4).
Cette triangulation mutuelle (parfois appelée triangulation réciproque) ajoute des sommets avec la valeur F(v)=0 (où v désigne un sommet), des arêtes et des mailles dans la triangulation 3D, sur l'isosurface.
Par cette opération de triangulation mutuelle de l'étape h3, on va en quelque sorte intégrer l'isosurface Z à la triangulation générale du volume de "tolérance simplicielle", noté Γ.
En 2D la triangulation mutuelle entre une triangulation 2D T et une ligne polygonale L (dont les sommets coïncident avec les arêtes de la triangulation) consiste à insérer tous les sommets de L dans T, toutes les arêtes de L dans T, puis conformer la triangulation en ajoutant des arêtes à T pour n'obtenir que des triangles.
Le fonctionnement de la triangulation mutuelle est illustré par les figures 15, sur un objet de même allure que celui de la figure 3 :
Au début (figure 15.1), on a la triangulation existante (au point où elle en est rendue) en traits hachurés, et l'isosurface Zset en traits gras.
La figure 15.2 illustre la triangulation réciproque de la courbe Zset et de la triangulation existante : apparaissent de nouveaux sommets (petits disques noirs) sur la ligne Zset, de nouvelles arêtes, et de nouveaux triangles. La courbe Zset est maintenant représentée sous la forme d'une chaîne d'arêtes de la triangulation.
Enfin, sur la figure 15.3, les triangles sont classifiés en fonction du signe de la fonction interpolée (blanc = positive, gris = négative).
Pour l'exemple des figures 8, le résultat est illustré sur la figure 8.5. On y voit des arêtes ajoutées à la triangulation en traits hachurés, et des nouveaux sommets (petits disques noirs). h4. Effectuer des fusions d'arêtes sur cette isosurface Z, qui prend sa configuration définitive, après ces simplifications. (Figures 8.6 à 8.8). h5. Continuer à effectuer des fusions d'arêtes, sur toutes les arêtes possibles dans le volume de "tolérance simplicielle", en vérifiant notamment la préservation de la condition de classification de l'ensemble S de points échantillons (étape 2076 de la figure 4).
Le processus continue, tant qu'il reste des arêtes à fusionner, du côté intérieur de Z. Il s'arrête lorsqu'aucune arête ne peut être fusionnée sans violer les conditions de classifications des points et de topologie.
Dans ce qui précède, la simplification utilise des opérateurs de fusion d'arête comme opérateurs de modification de triangulation. Il est concevable d'utiliser d'autres opérateurs de modification de triangulation, au moins en partie, par exemple : les opérateurs continus (déplacement de sommets), les opérateurs combinatoires, qui, outre la fusion « half-edge », déjà citée, comprennent des opérateurs comme ceux dits « 4-4 flips », ou encore « edge-removal », comme visibles sur la figure 1 depuis http://graphics.berkeley.edu/papers/Klingner-ATM-2007-10/Klingner-ATM-2007- 10.pdf et les opérateurs mixtes dont la fusion d'arête générale est un exemple.
Sont également utilisables des combinaisons d'opérateurs (par exemple fusion d'arête générale, suivie d'un flip 4-4, puis d'un edge-removal).
Le mode de réalisation décrit évite des besoins excessifs en termes de complexité mémoire et calcul. Son résultat final est illustré sur la figure 8.10. La Figure 8.11 est semblable à la figure 8.10, mais débarrassée des symboles illustrant la classification des points.
Dans le contour final de la figure 8.11, l'isosurface Zset s'inscrit exactement à l'intérieur du volume de tolérance.
En finale, l'isosurface Zset forme une approximation surfacique maillée du volume de tolérance. On peut considérer que Zset et 0Γ se sont rejoints, lors de la triangulation mutuelle.
Le mécanisme qui vient d'être décrit (raffinement + simplification) fonctionne bien dans le cas général. Il peut devoir être aménagé dans des situations particulières.
Certains facteurs pourraient compromettre la phase de raffinement de la topologie.
Tout d'abord, il se peut que l'isosurface Zset traverse δΩ entre deux échantillons, par exemple en raison de la présence d'un tétraèdre plat ("sliver").
Cela est au moins en partie évité en utilisant le paramètre a précité, dans la classification. On a vu qu'un point s est considéré comme bien classifié si ε (s) <= (1 - a)
On considère alors les tétraèdres hétérogènes, qui sont ceux dont les sommets ont des valeurs étiquettes F(s) différentes. On considère aussi une grandeur ou "hauteur" h, qui est la distance entre les triangles de dimension maximale, formés par les sommets du tétraèdre qui ont la même valeur étiquette.
Sur la figure 9A, les trois sommets B, C et D ont la même étiquette, et h est la distance minimale entre le sommet A et le plan support de la face BCD.
Sur la figure 9B, les sommets A et B ont la même étiquette. De même, les sommets C et D ont la même étiquette, h est la distance minimale entre la droite support de AB et la droite support de CD.
Et l'on contraint ces tétraèdres hétérogènes de sorte que h >= 2/ (σα). 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 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 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 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). 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 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ù 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 :
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 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 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 δ, 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 δ, le temps de traitement avec l'équipement indiqué plus haut, la figure avec le maillage final, et le nombre de sommets de celui-ci.
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.
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 [Refl9], qui peut être mis en œuvre à 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 œuvre 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,
Open Flipper, qui est le procédé décrit dans [Ref20], avec un logiciel disponible en téléchargement sur le site www.openfiipper.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 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 H|o->i, 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.
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 δ, indiquées dans le rectangle de légende. En abscisse, on a les différentes étapes du traitement, à savoir :
Raffinement,
Simplification par fusions de demi-arêtes de la frontière ST de la tolérance simplicielle,
Simplification par fusions d'arêtes de la frontière ST de la tolérance simplicielle, Triangulation mutuelle et fusions de demi-arêtes du zeroSet Z,
Fusions d'arêtes du zeroSet Z,
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. L'invention peut également être définie comme un dispositif.
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 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): 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 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, 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.
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 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 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 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 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")
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 volume de tolérance n'a lui-même qu'une seule composante connexe.
Annexe 2 - Références [Refl], Agarwal, P. K, and Suri, S. 1998. Surface approximation and géométrie partitions. Journal of Computing 27, 4,1016-1035.
[Ref2], Amenta, N., and Bern, M. 1998. Surface reconstruction by voronoi filtering. Discrète 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 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. 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.
[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 Conférence on Computer Graphics and Interactive Techniques, 119-128.
[ReflO], 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 and Applications 13,1, 61-96.
[Refll], 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.
[Refl2], Dey, T. K., and Sun, J. 2005. An adaptive mis surface for reconstruction with guarantees. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing.
[Refl3], 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.
[Refl4], Dey, T. K. 2006. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis [Cambridge Monographs on Applied and Computational MathematicsJ. Cambridge University Press.
[Refl5], Gueziec, A. 1996. Surface simplification inside a tolérance volume. Tech. Rep. 20440. IBM Research Report RC 20440.
[Refl6], 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.
[Refl 7], Ju, T. 2004. Robust repair of polygonal models. ACM Transactions on Graphics 23, 3, 888-895.
[Refl8], Kalvin, A. D., and Taylor, R. H. 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE Computer Graphics and Applications 16, 3.
[Refl9], 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 Conférence on Curves and Surfaces, Springer-Verlag, 488-500.
[Ref21], Tamal K. Dey, Anil N. Hirani, Bala 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 décimation based on global error. The Visual Computer 13.
[Ref25], Coxeter, H. S. M. 1969. Introduction to geometry (2nd ed.J. 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. [1979J, "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM 26 [3J: 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.
Geometric data processing, with isotopic approximation in a tolerance volume. The invention relates to computer techniques for constructing or reconstructing geometric surfaces. At the base, a surface or shape can be represented by a set of points in space. This is called a "point cloud".
To enable computer processing as a surface, a two-dimensional surface is often represented by a mesh based on triangular primitives. Similarly, a three-dimensional volume can be represented by a tetrahedral mesh. The expressions "triangular mesh" and triangulation cover all of these cases.
A representation of surfaces by "triangular mesh" or parametric surfaces can be imperfect, most often because of the limits of the sensors used to establish it and the algorithms of surface reconstruction from measurements. Faults can be eg holes, or auto-intersections (because it is rare that a surface of the real world crosses itself). The expression "soup of triangles" is used to aim for a triangulation that may be imperfect. Realizing a faithful approximation of complex shapes with triangular meshes (also called simplicial) is a multifaceted problem, which involves geometry, topology, and their discretization (division into primitive).
This problem has attracted considerable interest because of its wide range of applications and the ever-increasing availability of geometric sensors. This results in significantly increased availability of scanned geometric models, which does not mean that their quality is increasing: while many practitioners have access to high precision acquisition systems, the recent trend is to replace these expensive tools with heterogeneous combination of consumer level acquisition devices. The measures generated by the latter are insusceptible of a direct treatment. This is even more true if you want to merge heterogeneous data from different consumer sensors. Similarly, the diversity of geometric processing tools results in an increase in the number of defects in the data: the conversion to and from different geometrical representations often has the effect of losing quality in relation to the input signal. Few algorithms provide better quality guarantees on their output than their input signal requirements.
More and more discretizations are used to capture complex geometric shapes. This makes the concern become dominant to offer strict geometric guarantees, to be robust to the appearance of artifacts and make possible the certification of algorithms.
"Geometric guarantees" means the fixing of a maximum to the errors of the geometric approximation, and the absence of auto-intersections.
In addition, there are topological guarantees, such as homotopy, homeomorphism or isotopy. These notions are defined below.
In this case, isotopy means that there is a continuous deformation that deforms one form over another, while maintaining a homeomorphism between these two forms.
Surface meshes with these warranties are required for artifact-free rendering, digital engineering, reverse engineering, manufacturing, and 3D printing.
Geometric simplification reduces the number of primitives. Topological simplification can repair holes and degenerations present in existing discretizations. These two types of simplifications can be used in combination to reconstruct eigen forms from raw geometric data such as point clouds, or triangle soups.
Numerous techniques have been proposed over the years to make computer approximations of shapes. Few of them provide an upper limit for errors.
Document [Refl] (Appendix 2) proposed a method of approximation in polynomial time, with a guarantee of going down to a minimum number of vertices for a given maximum error tolerance. But this result is purely theoretical, and this document does not offer a practical algorithm for implementation. The maximum error approximation has been sought also by clustering in [Refl8], by mesh decimation [Ref9], [Refl5], [ReflO], [Ref28] or by a combination of these two techniques. [Ref24]
In general, the error metric considered is the unidirectional Hausdorff distance that goes back to the input mesh, but some have used bidirectional distance [Ref 9],
In general, these approaches are not generic enough to work on heterogeneous and imperfect input data. And they do not guarantee an exit without intersections.
One can avoid creating intersections during the decimation of meshes ([Ref26]), but this is not enough in the case of input data which themselves include auto-intersections, and these avoidances imply an early end to the simplification phase, which ultimately results in complex meshes.
In general, it is important to output a mesh that is isotopic to the input data, and is content with a small number of triangles (or vertices). In 2D, this is called the problem of minimal registered polygons ("minimum nested polygons"), and has been well studied in the convex case [Ref22], In 3D this becomes the problem of minimal inscribed polyhedra, which has been shown he is of difficulty NP.
Although this problem is old, there is still no robust and practical solution to this scientific and technical challenge. The present invention provides a remedy.
The method proposed for this purpose leaves, as input data, a tolerance volume Ω.
This tolerance volume can be determined, as part of a pre-treatment, from raw geometric raw data starting, for example on the basis of a cloud of points or a soup of triangles, or from any set of geometric data, even heterogeneous.
The proposed method comprises the following steps: A. receiving a tolerance volume Ω, relative to raw geometrical data of departure, B. initiating a canonical triangulation in the tolerance volume, from a set S of sample points taken at limits of this volume of tolerance, and of points situated outside it, C. refine this canonical triangulation, until classifying the points of the sample, which provides a dense primary mesh, of correct topology, for the tolerance volume, and D. simplify this dense mesh by triangulation modification operations, preserving the topology and the classification of the points of the sample.
Also provided is a geometric data processing device comprising:
A geometric data memory, for receiving graphic data representing a tolerance volume,
An initialization member, arranged to perform a first canonical triangulation between the edge of the tolerance volume and points located outside thereof,
A refinement organ, arranged to specify said first triangulation to provide a dense mesh of the tolerance volume, which preserves a classification condition of the points of the triangulation,
A simplification element, arranged to simplify said dense mesh, preserving the topology and the classification of its points, and a pilot which successively actuates the initialization member, the refinement member, and the simplification member, for changing graphic data from the same tolerance volume. Other features are also proposed, for the process as for the corresponding device. The initialization step B may comprise the sub-step of sampling the limits of the tolerance volume according to a selected sampling density σ, which provides the set S of sample points. Step B may include marking each sample point of the set S with a tag value that represents the index of the edge connected component of that point in the tolerance volume. The refinement step C then comprises the iterative generation of the canonical triangulation, by inserting one point at a time, on at least a part of the set S of points, until all the points concerned verify a condition of classification, based on the value of a function F itself dependent on their index value, and on its interpolation by an interpolation function f applied to each mesh of the 3D triangulation.
Thus, it is possible to make use of a point classification operator, which receives the designation of a point to be treated, and determines an interpolation function f on the basis of the mesh surrounding this point to be processed, and of values labels relating to the vertices of this mesh, to provide an interpolated label, and to compare it with a current label of the point to be treated, which makes it possible to determine a condition of classification of the point to be treated. Step C can be completed by the construction of a piecewise linear isosurface Zset, using the points where the interpolation function f has the same selected intermediate value, in particular zero, this Zset isosurface being a closed surface. , which forms a surface approximation of the volume of tolerance.
Preferably, the canonical triangulation is a Delaunay triangulation.
The raw geometric raw data can be 2D data or 3D data.
For its part, the simplification step D. can comprise the following operations:
Dl. determine whether triangulation modification operations are valid, that is to say preserve the topology of the mesh and preserve the classification condition of the set S of sample points, and D2. perform valid triangulation modification operations in a specified order.
Preferably, the triangulation modification operations comprise edge fusions and / or half-edge fusions. The order can be determined according to an optimization criterion.
In one embodiment, step D. relates to a so-called "simple tolerance" volume that approaches the tolerance volume by a mesh of the canonical triangulation, the Zset isosurface being contained in this volume called "simplistic tolerance" ,
The steps DI and D2 can then be performed: First on the edge of the volume called "simplistic tolerance",
Then on the fruit of a mutual triangulation between the isosurface (Zset) and the volume called "simplistic tolerance", this mutual triangulation adding vertices, edges and meshes in the triangulation, on the isosurface,
Finally, with other edges contained in the volume called "simplistic tolerance", to cover all possible edges. The invention also provides a computer program product comprising portions of program code for implementing the above method or device when the program is run on a computer. Other features and advantages of the invention will emerge on examining the following detailed description, and the attached drawings, in which: FIGS. 1-a to 1-e schematically illustrate a first example of application of FIG. the invention; FIG. 2 is the general flow diagram of the proposed mechanism according to the invention; FIG. 3 illustrates an example of the beginning of application of the invention. FIG. 4 is a flow diagram which details that of FIG. 2; FIG. 5 is a drawing illustrating the definition of barycentric ratios; FIG. 6 is a flow diagram which details a preferred embodiment of the step of FIG. Refinement 203 of Figures 2 and 4, - Figures 7 show different state of the triangulation during the refinement phase, in another example, very geometric application of the invention, - Figures 8 show different state of the triangulation during the simplification phase, on the same example, very geometric application of the invention, - Figures 9 are drawings illustrating a particular application of the invention, - Figures 10 are representations of elephants showing the robustness of the method according to the invention; - FIGS. 11 diagrammatically illustrate other examples of application of the invention, on the same object as FIG. 1; FIG. 12 is a diagramm; e, illustrating certain advantages of the invention, - Figure 13 is another diagram, illustrating certain advantages of the invention, - Figure 14 is another representation, called "fertility", on which the diagrams of Figures 12 and 13, - Figures 15 are representations similar to that of Figure 3, to better understand the sub-phase of mutual triangulation, in the simplification phase, - Figures 16 illustrate two mechanisms of fusion of edges and half FIGS. 17 is a flow diagram which details a preferred embodiment for the simplification step 207 of FIGS. 2 and 4; FIG. 18 is the block diagram of a device according to the invention, and Figure 19 is the block diagram of a classification operator used according to the invention.
The drawings and the description below contain, for the most part, elements of a certain character. They can therefore not only serve to better understand the present invention, but also contribute to its definition, if any. The nature of the invention means that certain characteristics can only be fully expressed by the drawing.
The description is followed by an Appendix 1 with definitions, and an Appendix 2 containing the coordinates of the documents referred to here. These appendices form an integral part of the description.
FIGS. 1a to 1e will firstly be examined for a very general description of the invention, with reference to FIG. 2, which illustrates the major operating steps of the proposed method, and FIG. 4, which details the FIG. 2.
Figure 1-a illustrates the starting point, namely a tolerance volume Ω relative to a mechanical part measured by a laser scanner, with an input tolerance δ of 0.6%.
Figure 1-b illustrates what is obtained after the refinement step (203, Figure 2). The result is a piecewise linear function Z, corresponding to a surface mesh of the tolerance volume Ω of FIG. 1. The number of vertices is 20.4k (20,400).
Simplifications are then carried out in accordance with step 207 (FIG. 2).
FIG. 1-c illustrates the same mesh as FIG. 1b, but after it has undergone a first simplification (simplification of the edge 0Γ of the "simple" tolerance Γ, step 2072, FIG. 4), which makes it go down to 5 , 3k vertices.
FIG. 1-d illustrates the same mesh, after mutual triangulation and simplification of Z (step 2074, FIG. 4), which makes it go down to 1.01 k vertices.
Finally, FIG. 1-e illustrates the mesh at the end of simplification (step 2076, FIG. 4), which is further reduced to 752 vertices.
It is observed, in the eye, that, even simplified, the mesh of Figure 1-e represents the object defined by the previous figures.
Reference is now made to FIG. 3, which uses a symbolic curvilinear tolerance volume, simpler than that of FIGS.
It has been seen that FIG. 2 illustrates the major operating steps of the proposed method. Figure 4 illustrates some process steps in more detail.
In FIG. 3, the tolerance volume Ω is defined by a spiral curvilinear shape, whose 0Ω boundary zone has two borders όΩι and 0Ω2, in a sectional view in plan. Step 201 of Figures 2 and 4 is an initialization. As indicated in 2011 (Figure 4), the initialization first includes a sampling of the edge (or the border) of the tolerance volume.
We obtain a set S of sample points s, stored in step 2013 (Figure 4). This sampling is in principle "σ-dense". This means that balls of radius σ centered on all points s of S completely cover the 0Ω boundary zone of the tolerance volume Ω. In practice, σ is a fraction of the thickness δ of Ω.
In the simplest case, that of FIG. 3, the 0Ω boundary zone has only two connected components of edge surfaces, namely δi (external boundary) and 0Ω2 (internal boundary). In this case, it is easy to distinguish the inside and the outside from one end to the other of the 0Ω border zone. This can be done formally, by assigning to each sample s of the set S a tag value (or label) F (s) which is, for example: F (s) = 1 if the point s is on όΩι, and F (s) = -1 if the point s is 0Ω2.
This value F (s) can be seen as a representation of the index (or "index") of the connected edge component of the considered point s, in the tolerance volume.
Another function 'f' is constructed: For a point x, present in a mesh M (triangular in 2D, tetrahedral in 3D), one calculates a function of linear interpolation f (x, M), defined on the basis of the values F (s) at the three or four vertices of the mesh M (triangle or tetrahedron), and the barycentric coordinates of the point x considered, with respect to the vertices of the mesh. More precisely, f (x, M) is a convex linear combination of the values of F at the vertices vi of the mesh M:
where for all i, ai is positive or zero, and the sum of ai is 1. The values of ai are defined for example as shown in Figure 5:
For a point X in a triangular mesh ABC, one of the is the value a for X with respect to the vertex A of the triangle, denoted aA (X), which is the ratio of the area of the triangle XBC to the surface of the triangle. triangle ABC.
We will thus have: f (x, M) = aA (X) F (A) + aB (X) F (B) + ac (X) F (C) It is the same thing with a tetrahedral mesh, which comprises one more vertex, and where the surfaces become volumes.
For a point X in a tetrahedral lattice ABCD, the value a for X with respect to the vertex A of the tetrahedron, denoted aA (X), is the ratio of the volume of the tetrahedron XBCD to the volume of the tetrahedron ABCD. And the formula becomes: f (x, M) = aA (X) F (A) + aB (X) F (B) + ac (X) F (C) + aD (X) F (D)
In 3D, in the case of tetrahedra, the interpolated function f (x, M) is constrained to be a function that satisfies the so-called Lipschitz condition (having a limited derivative). The skilled person knows how to implement this additional condition, which is required during refinement. Examples will be given later, with reference to FIGS. 9. Further information on these barycentric calculations is available in [Ref25]. Beside this, the set of points p where f (p) = 0 corresponds to a polygonal line (a 3D surface) called ZeroSet. This ZeroSet polygonal line, also abbreviated as Z, is a linear part-line, which is placed within the tolerance volume.
We also use an error quantity ε, which can be defined as follows: ε (s) = | f (s, M) - F (s) |, where the notation | x | aims the function absolute value of x.
As part of the set S, the point s has a value F (s). In the mesh M of the mesh which contains this point s, this one receives an interpolated value f (s, M).
We consider a parameter a, with (0 <a <1). The default value of a can be set to 0.2. We will say then: if ε (s) <= (1 - a), that the point s is well classified with the margin a,
Otherwise, the point s is misclassified.
A value ε close to 1 indicates that the mesh must be refined.
This refining is done by adding to the set Sp (set of points which are the subject of the triangulation) a point x of the set S which is not yet part of Sp. This point x inserted in the mesh has a value-label F (x). We then redo the classification calculation, and the error ε, for all the non-inserted points of the set S (that is to say for all the points of the set S that are not part of the 'set Sp).
In theory at least, it would be possible to proceed in an arbitrary order. It is currently preferred to start with the points that give the greatest error, and then to iterate. This is what will be described later, with reference to the mechanism illustrated in FIG.
It is observed that this mechanism converges whatever the mode of selection of the added points: in the worst case one would add all the points of the sample, and they are then all well classified.
As part of a Delaunay refinement, the points that are added to the current set of samples to be triangulated (Sp) are called "Steiner points." (Not to be confused with the Fermat point of a triangle, which some also call "Steiner's point").
When this is complete, and all the points are correctly classified, ie the error is everywhere <= (1 - a), we have a correct, but complicated, primary mesh.
We will now begin the description based on Figures 7, which are very geometric, which facilitates understanding. These figures illustrate the two-dimensional treatment, which the skilled person can transpose in three dimensions. Only the 2D illustration is possible; indeed, 3D figures would be illegible because everything would be superimposed on the screen.
Figure 7.0 shows a tolerance volume as is.
Figure 7.1 shows the initialization phase, in which the points S of the sampling S of the edges of the border zone of the tolerance volume appear. On the outside, for the label F (s) = 1, these points are hollow circles. Inside, for the label F (s) = -1, they are solid circles.
Figure 7.2 shows a so-called extended bounding box envelope LBB. This expanded bounding box LBB (or "Loose Bounding Box") can be constructed by calculating the strict bounding box of the tolerance volume, using the minimum and maximum coordinates in x, y, z points of the tolerance volume. . This box LBB is enlarged by homothety by a factor 1.5, for example.
The expanded bounding box LBB includes the points LBB1 to LBB4 shown in Figure 7.2. In 2D, the bounding box is formed by only 4 points, against 8 points in 3D. Other means can be used to define external points whose embedding property is guaranteed.
We then consider another set Sp of points sp. Initially empty, this set Sp first receives all the points of the extended bounding box LBB. In step 2015 of FIG. 4, one starts by making a triangulation T from these first points of the LBB placed in Sp, but which are not points of S.
The line segments that form the boundaries of the stitches are shown in long dashed lines in FIGS.
The points of the LBB are given special label values, which depend on their distance from the edge of the tolerance volume. These special tag values can be greater than 1.
For example: the label-value 1 is assigned to the outermost edge of the tolerance volume, and the label 'd + 1' to the vertices of the LBB, where d is the normalized distance between a vertex of the LBB and the point the outer edge of the tolerance volume that is closest to the top of the LBB. Normalization is a function of the tolerance volume thickness, which is determined at value 2 (the difference between -1 and +1).
We then make the classification calculation, and the error ε, for all the non-inserted points of the set S, to which are added the points of the extended bounding box which are in the set Sp.
This calculation suffers an exception in the case where a point of the sample is located in a mesh where the function is homogeneous, that is to say with labels identical to the vertices of the mesh. In this case if the function has the same sign as the label of the point of the sample then it is well classified, and badly classified otherwise, without using the error ε.
As already indicated, all the points s of the set S have been assigned a label value F (s). The interpolation function f is constructed, as before, for each cell (2D triangle, 3D tetrahedron): For a point x of the set Sp, present in a tetrahedral cell, a linear interpolation function f (x, M), defined on the basis of the label values F (s) at the vertices of the tetrahedron mesh M, and the barycentric coordinates of the point x considered, with respect to the vertices of the mesh. And each time the error quantity ε is calculated, which indicates whether the point x is or is not well classified.
In Figure 7.2, a well-classified point is represented by a square. A badly classified point is represented by a cross.
It is observed that the interpolated function on the two triangles LLB1-LBB2-LBB3, as well as LLB1-LBB3-LBB4 is here homogeneous and positive in all points, since the vertices of the LBB all have a label 'd + 1' which is clearly positive.
We are therefore within the framework of the above exception.
The hollow circles of Figure 7.1 have a + 1 positive label. They are therefore of the same sign as the interpolated function on the two triangles, and therefore well classified. Therefore, these hollow circles in Figure 7.1 become squares in Figure 7.2.
For their part, the full circles of Figure 7.1 have a negative label - 1. They are therefore of opposite sign to the interpolated function on the two triangles, and therefore poorly classified. As a result, these solid circles in Figure 7.1 become crosses in Figure 7.2.
Then begins the refinement itself (step 203 of Figure 2, and frame 203 of Figure 4). In step 2031 of FIG. 4, a first point of Steiner SP1 is added in the triangulation. This point SP1 is added to the set Spdes points to triangulate.
This point SP1 may be the one whose error ε is maximum, as indicated here elsewhere.
In figure 7.3, this first point of Steiner SP1 happens to be close to the diagonal L1 of the envelope LBB. The label of SP1 is F (SP1) = -1.
We then redo the classification calculation, and the error ε, for all the points of the set S, and for the added point SP1 (step 2032 of FIG. 4).
The two extreme points LBB1 and LBB3 of the diagonal L1 are part of the LBB. This determines a version "SP1" of the function f, calculated as indicated above, in the 4 triangular meshes LBB1-LBB2-SP1, LBB2-LBB3-SP1, LBB1-LBB4-SP1, LBB3-LBB4-SP1. We finally obtain f (SPl) = -1, which classifies well the added point SP1.
Around point SP1 is then defined an isosurface IS1, where f = 0. This isosurface is illustrated by a black broken line in bold lines, almost square, in figure 7.3.
Consider the triangle LBB1-LBB2-SP1. The interpolated function is -1 in SP1, and a positive value greater than 1 in LBB1 and LBB2, say 5. Along the edge SP1-LBB1 the function therefore varies linearly from -1 to 5, and so we find the Zero level of the interpolated function f near SP1, above.
Now consider the triangle LBB3-LBB4-SP1. By symmetry, we find another zero level of the interpolated function f near SP1, below, this time.
The two vertical segments of IS1 are explained in the same way, considering the triangles LBB2-LBB3-SP1 and LBB1-LBB4-SP1. The 2D analysis made above can be extrapolated to 3D in the following way: In 3D, the interpolated function f is always linear per piece, but evolves in space so there is a depth in addition; and the isosurface zeroset (or Zset) is no longer a segment in a triangle, but a planar polygon in a tetrahedron, namely a triangle or a quadrilateral.
We observe that, on the horizontal line of points contained in the center of IS1, the points are now well classified, and the crosses have become squares, with F (s) = 1. On the contrary, the points situated outside IS1 remained crosses, with F (s) = -1, therefore misclassified.
It is observed that the lower part of the contour IS1 is halfway between the horizontal line of points contained in IS1, and the line of cross below.
The other elements of the contour IS1 depend on the "SP1" version of the function f, as explained above. The isovalue IS1 represents the zero level of the interpolated function, which is therefore positive on one side of IS1, and negative on the other side of IS1. The points of the sample are well classified when they are located on the side of IS1, which corresponds to the sign of their label or value-label. Other useful information to build a Delaunay triangulation can be found in [Ref23], This information is to be considered as incorporated in the present description.
It should be noted that, for points in general position (in 2D, no more than 3 co-circular points, and in 3D no more than 4 co-spherical points), there exists only one Delaunay triangulation, which is therefore canonical. A property is in 2D that the circles circumscribed to the triangles contain no other point; similarly, in 3D, the spheres circumscribed in the network tetrahedra (consisting of points of the subset Sp of S) are empty, and contain no point other than the vertices of the tetrahedron.
The Delaunay triangulation is completed when all the points of the set S are correctly classified (step 2033 of FIG. 4).
If this is not the case, steps 2031 to 2033 of FIG. 4 are repeated, inserting a new Steiner point. This is done with the point SP2 in Figure 7.4, which is added to the set Spds points to triangulate.
We then redo the classification calculation, and the error ε, for all the points of the set S, and for the points SP1 and SP2 added (step 2032 of FIG. 4). This results in a so-called "SP2" version of the function f.
The points where this "SP2" version of the function f is zero define a new isosurface IS2, which includes the points SP1 and SP2. On the CC20 and CC22 segments of the tolerance volume contour, the points remain poorly classified (crosses). On the other hand, in the vicinity of SP2, the segments CC21 and CC23 contained in IS2 now include well-classified points.
Similarly, the quadrant CC24 becomes well classified, unlike segments aligned on him, but outside of IS2.
Conversely, the CC25 and CC26 square segments become misclassified, unlike the segments aligned on them, but outside IS2. In the test step 2033 of FIG. 4, certain points of the set S remain poorly classified.
Thus, steps 2031 to 2033 of FIG. 4 are repeated by inserting a new Steiner point SP3, as illustrated in FIG. 7.5.
We then redo the classification calculation, and the error ε, for all the points of the set S, and for the points SP1, SP2 and SP3 added (step 2032 of FIG. 4). This results in an "SP3" version of the f function.
The points where this "SP3" version of the function f is zero define a new isosurface IS3, which includes the points SP1, SP2 and SP3.
As before, we observe that the points that are inside IS3 do not have the same classification as the points located on the same line as them, but outside of IS3. In the test step 2033 of FIG. 4, certain points of the set S remain poorly classified.
Steps 2031 to 2033 of FIG. 4 will be repeated several times, each time inserting a new Steiner point. This gives the figure 7.6, where Steiner's points are big black circles, if their value-label is negative, or big inner circles white, if their value-label is positive. The isosurface obtained approximates the general shape of the volume of tolerance, but there are still badly classified points.
Steps 2031 to 2033 of FIG. 4 will be repeated several times, each time inserting a new Steiner point. This leads to Figure 7.7, where the isosurface is entirely contained in the Tolerance Volume, and there are no more crosses (misclassified points). At the test step 2033 of Figure 4, the end of the refinement has now been reached.
So we go to phase 207 of simplification (or decimation), Figures 2 and 4.
Step 203 of Figures 2 and 4, which is called "refinement", has been described. One of the goals of this refinement is to arrive at a mesh without surface intersection, which corresponds to the topology of the volume of tolerance. As indicated by the word "refinement", one makes evolve the mesh of "coarse-to-end", with the points successively inserted.
The mesh itself can be done using a Delaunay triangulation, whose data structures do not accept intersecting surfaces. Other techniques can be used to construct canonical triangulations that do not intersect. The Applicant currently prefers a triangulation using the Delaunay property, with the proof of termination and the topology guarantee that it allows.
As indicated, the selection of inserted Steiner points can be done according to the error magnitude ε. This can be done on the basis of the mechanism of Figure 6, which will now be described in 3D version. In step 601, for each tetrahedron of the triangulation T, a list of those sample points s of the set S that are contained in this tetrahedron is maintained. Each point is accompanied by its label, and its error ε. The points of the set Sp that are already included in the triangulation are not in this list. In step 603, a dynamic priority queue is maintained for each tetrahedron of the triangulation T, containing the maximum error points in the tetrahedrons, sorted by decreasing error. In step 605, which corresponds to step 2031 of FIG. 4, the maximum tail end error point is added to triangulation T, which can then be deleted from the tail. In step 607, which corresponds to step 2032 of FIG. 4, the error calculations are updated. A test 609, which corresponds to step 2033 of FIG. 4, examines whether the topology is correct, ie if the set S is completely classified. If this is not the case, we return to 601. Otherwise, we can proceed to the next phase of simplification of the mesh.
At the end of refinement, the mesh representation of FIGS. 7.6 and 7.7 is correct, in particular in that it does not include intersections, and that it is isotopic. On the other hand, it is too dense, and contains an excessive number of meshes (or vertices). We will simplify it, as we will see later.
We will first consider Figure 7.8.
At the end of the triangulation mesh that constitutes refinement, we have a set of tetrahedra. The "simple tolerance", denoted by Γ, is the union of the tetrahedra which constitutes a meshed (triangulated) approximation of the tolerance volume Ω. These tetrahedra have vertices with different labels.
The edge of this "simplistic tolerance" is noted ST (in Figure 7.8). In 3D, this edge is composed of triangles which are the free faces of the mesh tetrahedra. It is a triangulated representation of the boundary of the tolerance domain. The mixed line in Figure 7.8 illustrates those edges of this triangulated representation that are in the plane of the figure. From there, the simplification of the mesh representation of FIGS. 7.7 or 7.8 can be done essentially by using a process known as "edge collapse".
The nature of this process will now be described with reference to Figs. 16, which are in 2D.
Figure 16.0 shows the ends A and B of an edge that can be fused (we will see the conditions later). The general merge operator deletes the edge that joins the vertices, at least one of these two vertices, and the faces or tetrahedra adjacent to the removed edge (Figure 16.2). The position of the vertex P resulting from the fusion (target vertex) is a degree of freedom (continuous) of this operator, under condition to preserve the topology and to classify all the points well.
In the case where these two constraints (topology and classification) can be satisfied, there are one or more regions of the space (region of validity) where the target vertex P can be placed. It can be arbitrarily placed in this region, but it is better to choose an optimum point.
For this, one-point error calculation can be used. The error is, for example, the sum of the squares of the distances from this point to the support planes of the facets of the isosurface Z, these facets being selected in a local neighborhood at the considered edge. This local neighborhood may include facets of the isosurface that are located at a distance 2 from the edge in the triangulation graph (so-called "2-ring"). We look for the optimum Q point that minimizes this error.
This error calculation serves as an optimization criterion. Indeed, as the preferred point P, it is then possible to take the point situated in the region of validity, which is as close as possible to the optimum point Q which minimizes the said error.
It should be noted that this mode of error calculation and determination of the preferred point P is particularly relevant for planar surfaces per part; However, we can imagine other solutions depending on the nature of the input surfaces. For example for the curved surfaces by parts, one can imagine to choose either planes but parametric surfaces of the quadric or cubic type, and to take as error the sum of the squares of the distances to these surfaces.
In practice, to increase the speed of the processing, it is interesting to use also, as a variant, a purely combinatorial operator that is called a "half-edge fusion operator": in this less general variant, the operator is forced to merge one vertex of the edge on the other. In FIG. 16.1, the vertex A is thus fused to the vertex B. And the optimization criterion is defined by the distance between the target point (here the point B) and the optimal point Q calculated as above.
This half-edge merge operator is less powerful than the edge merge operator that admits to placing the vertex resulting from the merge at a general position P in space, but it is much faster to simulate, since the target point B is known directly, without having to look for the best point P. The half-edge fusion operator is said to be combinatory in the sense that there exists a finite number of degrees of freedom: 2 E possible fusions, where E represents the number of edges of the triangulation. Then, when no half-edge fusion is possible, one uses the more general operator of fusion of edges.
It is important to understand the difference between the two phases: refinement and simplification.
During refinement, sample points are inserted in a canonical triangulation (whose connectivity is determined by the positions of the points). So, in this phase of refinement, the degrees of freedom are only in terms of choice of points.
During the simplification, we will see that the merge operators act by edges or half-edges, so a priority queue sorts the operators that are valid (which preserve the topology and classification of the points), following a score that depends on a optimization criterion.
The ultimate goal is to simplify as much as possible, and it is observed that certain post-merge point positions are conducive to greater simplification, intuitively by better preparing for future simplifications as more merge operators will be valid thereafter.
We will now specify the constraints (topology and classification) that will make it possible to determine whether a merge operator during simulation is applicable ("valid") or not.
For the preservation constraint of the topology, we can use three notions:
A "link condition", described in [Ref21], for the D-manifold property. In 2D this condition ensures that any neighborhood of a point is homeomorphic (topologically equivalent) to a disk or a half-disk. On the topological plane this condition requires that each edge is adjacent to exactly one or two triangular faces, and that each vertex is adjacent to a single connected component. In 3D this condition ensures that any neighborhood of a point is homeomorphic (topologically equivalent) to a ball or half-ball.
The determination of a polyhedron kernel to verify that the embedding is valid [Ref27], In 3D the nucleus of a polyhedron is the place of the points which see all the edge of the polyhedron. In the general case the nucleus is either empty or a convex polyhedron. The polyhedron considered for the calculation of the nucleus is the polyhedron formed by the union of the tetrahedra adjacent to the two vertices of the edge. When the nucleus is non-empty, we can merge the edge by placing the target vertex in the nucleus: the triangulation remains valid, that is to say without overlapping or inverting tetrahedra. When the kernel is empty you can not merge the edge without creating an invalid triangulation. In our context we use the construction of the nucleus to delimit a zone of search of points which classify well (this is the point below).
The preservation of the classification of the points of the sample, which is done as before, and which will be reviewed below.
A merge operator being simulated will therefore be considered valid if:
The link condition is verified,
The valid embedding condition is verified, the classification of the points of the sample is preserved.
The simplification process may be in accordance with Figure 17.
We consider one by one all the edges existing in different parts of the triangulation, starting with the edge of the simplistic tolerance, as will be seen.
For each edge, step 1701 first simulates the fusion of this edge, to determine if this fusion is possible ("valid"). As already indicated, we will first try a half-edge merge operator, then a general edge merge operator. The simulation is based on the current state of the triangulation.
If the merge operator being simulated is valid, step 1703 stores the definition in a dynamic priority queue. The order of priority is defined by the aforementioned optimization criterion. In step 1705, the first merge operator is applied in the order of the priority queue.
After that, step 1707 updates the priority queue: deletion of operators that are no longer required because they relate to an edge deleted by the merge operator that has just been executed.
Re-simulation of modified operators, which are put back in the queue, with their optimization criteria recalculated. An operator is "modified" when the merge operator that has just been executed has modified the parts of the triangulation that are adjacent to at least one of the two vertices of the edge on which it is carrying (or both vertices ).
Sub-steps 2072 to 2076 of step 207 of FIG. 4 show that the operation is carried out in three stages. At each time, half-edge fusions are first considered, followed by general edge fusions.
Here, a reciprocal triangulation (described in detail later) takes place in step 2074, within the simplification phase. It would be conceivable to perform this reciprocal triangulation just after doing the refinement. In other words, one can imagine simplifying all possible edges after doing all the refinement, including reciprocal triangulation. The proposed process is considered more parsimonious because it allows a lower complexity of the triangulation.
Thus, the Applicant currently believes that it is preferable to simplify the triangulation of the tolerance volume (the simplistic tolerance) before launching the reciprocal triangulation, then the rest of the simplification. The idea is to reduce the size of the triangulation before simplifying it because the number of operators to use depends on this size. Also note the following point: in refinement, the proposed 3D triangulation is that of Delaunay; it is convenient because it is canonical for a set of points, and we know how to prove the termination of refinement. But it is "verbose": for it is at fixed points a triangulation the most isotropic possible- so to speak little parsimonious (in points) in places where the geometry is anisotropic. The idea is to reduce the size of the triangulation before simplifying it because the number of operators to use depends on this size.
The simplification will now be illustrated with reference to Figures 8.0 to 8.11.
Figure 8.0 shows the mesh, in its state of figure 7.7, whose figure 7.8 showed that it was the simplistic tolerance Γ. We know that the isosurface Zset is contained in this volume of "simple tolerance" noted Γ.
The simplification first concerns the edge ST of the "simplistic tolerance" (step 2072 of FIG. 4).
In Figure 8.0, two of the points are connected by an edge SF1, shown in bold, to indicate that they can be merged.
As already indicated, the merger between two adjacent vertices makes disappear the edge which joins them, one of these two vertices, and the faces or tetrahedra adjacent to the removed edge.
When we merge two vertices in 3D, we will also merge (collapse one on the other) two edges located between these two points and a third (which is not in the plane of the figure).
Therefore, we must consider all the primitives (2D triangles or 3D tetrahedra) that are adjacent to the vertices of the removed edge. The points in the sample that are located in these primitives are called here "merge points".
It is then necessary that, in the vicinity of the edges to collapse, the error ε in all the points concerned by the fusion satisfies the aforementioned condition: ε <= (1- a) in other words, all the points involved in the merge are well classified (symbolized by squares) after the merger. This is called preserving the condition of classification of the points of the set S.
As indicated, one determines in advance which fusion operators preserve the classification and the topology by "simulating" them, without applying them. Only the merge operators selected as suitable ("valid") after simulation are stored in the dynamic priority queue of step 1703.
In order to speed up the processing, half-edge collapse is done first, whose operators are much faster to simulate. Then, when no half-edge fusion is possible, we consider the more general operators of edge fusion.
It can also be said that the Delaunay meshes concerned must be homogeneous as regards the good classification of the points. Note that at the level of simplification, it is not verified that the mesh continues to satisfy the Delaunay conditions.
The result after this first fusion of half-edges and / or edges is illustrated in Figure 8.1.
We have redone the classification calculation, and the error ε, for those points of the set S that are concerned by the merger. The isosurface was also recalculated.
In Figure 8.2, two of the points are connected by an edge SF2, shown in bold, to indicate that they can be fused as well.
The result after this other merge is shown in Figure 8.3.
This is repeated with all the points that can be merged. When there are no more edges to merge (points that can be merged) at the edge of the 0 tolérance simplistic tolerance, the result is shown in Figure 8.4.
In summary, so far simplification has involved the following steps: hl. Delimit a volume called "simplistic tolerance", noted Γ. It consists of a mesh union of the Delaunay 3D triangulation, chosen to form a mesh approximation of the tolerance volume. This is illustrated in 2D in Figure 7.8, where the mixed line indicates the 0Γ edge of this simplistic tolerance. h2. Perform edge fusions in 0Γ, checking the preservation of the S classification condition (Figures 8.1 to 8.4).
We continue as follows: h3. Perform a mutual triangulation between the isosurface (Zset) and the so-called "simplistic tolerance" volume, as modified in step h2 (step 2074 of FIG. 4).
This mutual triangulation (sometimes called reciprocal triangulation) adds vertices with the value F (v) = 0 (where v denotes a vertex), edges and meshes in the 3D triangulation, on the isosurface.
By this mutual triangulation operation of step h3, we will somehow integrate the isosurface Z to the general triangulation of the volume of "simplistic tolerance", noted Γ.
In 2D the mutual triangulation between a 2D triangulation T and a polygonal line L (whose vertices coincide with the edges of the triangulation) consists in inserting all the vertices of L in T, all the edges of L in T, then conforming the triangulation adding edges to T to get only triangles.
The operation of the mutual triangulation is illustrated by FIGS. 15, on an object of the same shape as that of FIG. 3:
At the beginning (figure 15.1), we have the existing triangulation (at the point where it is rendered) in hatched lines, and the isosurface Zset in bold lines.
Figure 15.2 illustrates the reciprocal triangulation of the Zset curve and the existing triangulation: new vertices (small black disks) appear on the Zset line, new edges, and new triangles. The Zset curve is now represented as a chain of edges of the triangulation.
Finally, in Figure 15.3, the triangles are classified according to the sign of the interpolated function (white = positive, gray = negative).
For the example of FIG. 8, the result is illustrated in FIG. 8.5. There are edges added to the hatched triangulation, and new vertices (small black disks). h4. Make fusions of edges on this isosurface Z, which takes its final configuration, after these simplifications. (Figures 8.6 to 8.8). h5. Continue to perform edge fusions on all possible edges in the "simplistic tolerance" volume, including checking the preservation of the S-point classification condition of sample points (step 2076 of Figure 4).
The process continues, as long as there are edges to merge, on the inner side of Z. It stops when no edge can be merged without violating the conditions for classifying points and topology.
In the above, the simplification uses edge merge operators as triangulation modification operators. It is conceivable to use other triangulation modification operators, at least in part, for example: continuous operators (vertex displacement), combinatorial operators, which, in addition to the "half-edge" merger, already cited, operators such as 4-4 flips, or edge-removal, as shown in Figure 1 from http://graphics.berkeley.edu/papers/Klingner-ATM-2007-10/Klingner- ATM-2007- 10.pdf and mixed operators whose general edge fusion is an example.
It is also possible to use combinations of operators (for example general edge fusion, followed by a 4-4 flip, then an edge-removal).
The described embodiment avoids excessive requirements in terms of memory and computation complexity. Its final result is shown in Figure 8.10. Figure 8.11 is similar to Figure 8.10, but has been removed from the symbols illustrating the classification of points.
In the final contour of Figure 8.11, the Zset isosurface fits exactly within the tolerance volume.
In the final, the Zset isosurface forms a meshed surface approximation of the tolerance volume. We can consider that Zset and 0Γ are joined during the mutual triangulation.
The mechanism just described (refinement + simplification) works well in the general case. It may have to be arranged in particular situations.
Some factors could compromise the refinement phase of the topology.
First, it is possible that the Zset isosurface passes through δΩ between two samples, for example due to the presence of a flat tetrahedron ("sliver").
This is at least partly avoided by using the above-mentioned parameter in the classification. We saw that a point s is considered as well classified if ε (s) <= (1 - a)
We then consider the heterogeneous tetrahedra, which are those whose vertices have different label values F (s). We also consider a magnitude or "height" h, which is the distance between the maximum dimension triangles, formed by the vertices of the tetrahedron that have the same label value.
In FIG. 9A, the three vertices B, C and D have the same label, and h is the minimum distance between the vertex A and the support plane of the BCD face.
In Figure 9B, the vertices A and B have the same label. Similarly, the vertices C and D have the same label, h is the minimum distance between the support line of AB and the CD support line.
And we constrain these heterogeneous tetrahedra so that h> = 2 / (σα). It is a way of making the interpolation function f satisfy the Lipschitz criterion, according to which the absolute value of the gradient of this function f is bounded.
A proper choice of made as well as the problems of flat tetrahedron ("sliver") are naturally solved.
As other disturbing factors of refinement, one can also encounter problems of orientation (perpendicular or "normal" direction) in complex areas.
They can be solved using the above. Preferably, and optionally, it will also be verified for each tetrahedron that an extension of the piecewise linear function outside the tetrahedron, also classifies points of the sample not only in the tetrahedron, but also outside. We will then say that the interpolation function f classifies the "local geometry".
The value to choose for a depends on the nature of the input data. The value a = 0.2 is suitable, at least as a starting value.
Reference is now made to Fig. 10, which depicts at the top of the picture crude representations of an elephant (from left to right: a cloud of points without noise, a soup of triangles without noise, a cloud of points with noise, and a soup of triangles with noise), and in the lower part the triangulation obtained according to the invention. For each example the raw data is converted to a tolerance volume by calculating a sub-level of the distance function to the data (points or triangles). On the left (Figure 10A), the starting image is a cloud of points that have no noticeable effect on the final triangulated surface. Further to the right (Figure 10B), the starting data forms a soup of unorganized triangles (with intersections, holes) that also have no noticeable effect on the quality of the triangulated final surface. Further to the right (Figure 10 C), the starting data is a cloud of points with a high level of noise (uncertainty in their coordinates) which also has no noticeable effect on the quality of the triangulated final surface . Finally, quite right (Figure 10 D), the starting data form a very irregular and noisy triangles soup that also has no noticeable effect on the quality of the final triangulated surface. It is simply noted that the triangulation is less detailed in Figures 10C and 10D, where the starting data have a high noise level, and for which a larger tolerance volume is chosen.
These examples illustrate the robustness of the technique according to the invention. The invention has been developed using the following computer database:
INTEL Intel 2.4GHz 16 core machine with 128 gigabytes of RAM,
For the triangulation data structures, CGAL library, available from Geometry Factory, 20, Yves Emmanuel Baudoin Avenue, 06130 Grasse, France,
INTEL library "Threading Building Blocks library" for parallelization. It is observed that the "atomic" treatments on the tetrahedrons and the sample points are independent, and can therefore easily be conducted in parallel.
Fig. 11 shows the part of Figs. 1. Fig. 11.0 is the tolerance volume. Figures 11.1 to 11.4 illustrate the final grid obtained, with different processing conditions, with respect to the factor δ, which is the separation distance between the boundaries of the tolerance volume, expressed as a percentage. The following table shows the values of δ, the processing time with the equipment indicated above, the figure with the final mesh, and the number of vertices thereof.
It appears that the calculation time decreases when the tolerance increases. In general, the process is slow, which is a counterpart to its robustness.
The performances obtained by the invention are illustrated in FIG.
It will be observed that a strict comparison with the prior art is not possible since the constraints of the problem posed here are different. The invention can however be compared to the following proposals:
Lindstrom-Turk, which is the method described in [Refl9], which can be implemented using the CGAL library version 4.6, marketed by the aforementioned Geometry Factory, MMGS, which is the method described in [Ref7] ], implemented by MMGS version 2.0a software, directly transmitted by Pascal Frey, second author of [Ref7], MMGS-A, which is a variant of the same MMGS software with the mesh anisotropy option,
Open Flipper, which is the process described in [Ref20], with software available for download at www.openfiipper.org/, version 2.1.
Simplification Envelopes, which is [Ref9], with software version 1.2, transmitted by email by the first author.
The Haussdorf distance measures the dissimilarity between two geometric shapes. The unidirectional distance Haussdorf (A, B) is defined by the maximum of the Euclidean distance between the form A and the form B, for every point of A, and vice versa for Haussdorf (B, A). The symmetrical variant is the maximum of Haussdorf (A, B) and Haussdorf (B, A). The ordinate scale of Figure 12 corresponds to Hausdorff's distance H | o-> i, which is the unidirectional Hausdorff distance between the output and the input. The abscissa scale is the number of vertices at the output.
This figure 12 shows that the invention is better than the other techniques by Haussdorf distances lower, with numbers of peaks in the final lower, in addition to the robustness already shown above.
Figures 12 and 13 have as input a gross surface mesh of the images of Figures 14 (about 14,000 vertices).
Figure 13 shows the processing times. It illustrates the evolution of the mesh complexity as a function of processing and time for different values of the input tolerance δ, indicated in the legend rectangle. On the abscissa, we have the different stages of treatment, namely:
Refinement,
Simplification by half-edge fusions of the ST boundary of the simplest tolerance,
Border merge simplification of the ST boundary of the simplest tolerance, mutual triangulation and zeroSet Z half-edge fusions,
ZeroSet Z edge fusions,
Simplification of all edges. The invention also makes it possible to treat surfaces having holes, for example when they are obtained by laser scanning which tangents concave zones. The holes can be deleted, as long as the tolerance volume includes them. The invention can also be defined as a device.
Figure 18 shows the elements of Figure 4, the steps are performed by operators. In numerical references, the most significant figure is 2 for steps, as opposed to 3 for operators.
Thus, the initialization step 201 of FIG. 4 is performed by the initialization operator 301 of FIG. 18. It starts from the tolerance volume, stored in 310. Inside this initialization, the step 2011 of Figure 4 is performed by the contour sampling operator 3011 of Figure 18.
Figure 19 illustrates a point classification operator, referenced 1900.
For a point to classify, we start from the following data (at least in part, some data being deductible from the others): the coordinates of this point, the label or label of this point, the mesh which surrounds this point, with the coordinates and labels of the vertices of this mesh.
A 1901 operator calculates the interpolation function f, as described above with reference to FIG. 5. It provides a label calculated for this point. The operator 1902 deduces whether the point is well classified or not, as already described.
It will be observed that this figure 19 does not reflect exceptional cases, such as the one where all the vertices of the mesh have the same label value.
This point classification operator, 1900, is called many times, in particular by the operators 3013 and 3032 of FIG. 18, as well as by the simulation operator 1701 of FIG. 17, insofar as the latter must check that the classification of points is preserved.
Appendix 1 - Definitions Isomorphism
In mathematics, an isomorphism between two structured sets is a bijective application that preserves the structure and whose inverse also preserves the structure (For many structures in algebra, this second condition is automatically fulfilled, but this is not the case in topology for example where a bijection can be continuous, without its reciprocal being).
Hom (e) omorphism (in English: "homomorphism")
In topology, a homeomorphism is a continuous bijective application, of a topological space in another, whose reciprocal bijection is also continuous. In view of the above, it is an isomorphism between two topological spaces.
When we say that two topological spaces are homeomorphic, it means that they are "the same", seen differently. This does not always make sense. For example, we show that a cup (with handle) is homeomorphic to a torus, because there is a transformation that moves from one to the other: fill the body of the cup of matter, then deform it gradually, with its handle, so that the whole forms a torus. The reciprocal transformation restores the cup.
isotopy
The notion of isotopy is particularly important in node theory: two nodes are considered identical if they are isotopic, that is to say if one can deform one to obtain the other without the "chord" tears or does not penetrate.
This notion of isotopy should not be confused with isotopy in chemistry, nor with isotropy in physics of materials.
Tolerance volume (in English: "volume tolerance")
This applies to a three-dimensional component. The tolerance volume for a component is the volume between its largest and the smallest allowable outer surface.
In practice, there may be several related components of the tolerance volume. There may also be several related components of its edge surfaces, even though the tolerance volume itself has only one related component.
Appendix 2 - References [Refl], Agarwal, P. K., and Suri, S. 1998. Surface approximation and geometry partitions. Journal of Computing 27, 4, 1016-1035.
[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, TK, 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 Transactions on Graphics 24,1332-1352.
[Ref5], Boissonnat, J.-D., and Cazals, F. 2000. Smooth surface reconstruction via natural neighbor 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. Graphical Models 67, 5, 405-451.
[Ref7], Borouchaki, H., and Frey, P. 2005. Simplification of a 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.
[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.
[ReflO], 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 and Applications 13,1, 61-96.
[Refll], Dey, TK, and Goswami, S. 2003. Tight cocoon: A watertight surface reconstructor. In Proceedings of ACM Symposium on Solid Modeling and Applications, 127-134.
[Refl2], Dey, TK, and Sun, J. 2005. An adaptive set surface for reconstruction with guarantees. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing.
[Refl3], Dey, TK, Li, K., Ramos, EA, and Wenger, R. 2009. Isotopic reconstruction of surfaces with boundaries. Computer Graphics Forum 28, 51371-1382.
[Refl4], Dey, TK 2006. Curve and Surface Reconstruction: Algorithms with Mathematical Analysis [Cambridge Monographs on Applied and Computational Mathematics]. Cambridge University Press.
[Refl5], Gueziec, A. 1996. Surface simplification inside a tolerance volume. Tech. Rep. 20440. IBM Research Report RC 20440.
[Refl6], Hornung, A., and Kobbelt, L. 2006. Robust reconstruction of watertight models from non-uniformly sampled point clouds without normal information. In Proceedings of EUROGRAPHICS Symposium on Geometry Processing, 41-50.
[Refl 7], Ju, T. 2004. Robust repair of polygonal models. ACM Transactions on Graphics 23, 3, 888-895.
[Refl8], Kalvin, AD, and Taylor, RH 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE Computer Graphics and Applications 16, 3.
[Refl9], 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, Springer-Verlag, 488-500.
[Ref21], Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy, Gavin Smith. Edge Contractions and Simplicial Homology. arXiv: 1304.0664.
[Ref22], Aggarwal, A, Booth, H., O'Rourke, J., Suri, S., and Yap, CK 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, HSM 1969. Introduction to geometry (John 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, DT; Preparata, FP [1979], "An Optimal Algorithm for Finding the Kernel of a Polygon", Journal of the ACM 26 [31]: 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.

权利要求:
Claims (12)
[1" id="c-fr-0001]
claims
A method of processing geometric data, comprising the following steps: A. receiving a tolerance volume Ω, relative to raw geometrical data of departure, B. initiating (201) a canonical triangulation in the tolerance volume, starting from a set S of sample points taken at the limits of this tolerance volume, and of points situated outside it, C. refine (203) this canonical triangulation, to classify the points of the sample, which provides a dense mesh of tolerance volume, and D. simplify (207) this dense mesh by triangulation modification operations, preserving the topology and the classification of the points of the sample.
[2" id="c-fr-0002]
2. Method according to claim 1, characterized in that step B comprises the sub-step (2011) of sampling the limits of the tolerance volume according to a selected sampling density σ, which provides the set S of sample points.
[3" id="c-fr-0003]
3. Method according to claim 2, characterized in that step B comprises the marking (2013) of each sample point of the set S by a tag value which represents the index of the edge connected component of this point. , in the tolerance volume, and in that step C comprises the iterative generation of the canonical triangulation, by inserting one point at a time (2031), on at least a part of the set S of points, until that all the points concerned (2033) satisfy a classification condition (2032), based on the value of a function F itself dependent on their index value, and on its interpolation by an interpolation function f applied to each mesh of the 3D triangulation, and the construction of a piecewise linear isosurface Zset, using the points where the interpolation function f has the same selected intermediate value, in particular zero, this Zset isosurface being a closed surface, which forms a surface approximation of the tolerance volume.
[4" id="c-fr-0004]
4. Method according to one of the preceding claims, characterized in that the canonical triangulation is a Delaunay triangulation.
[5" id="c-fr-0005]
5. Method according to one of the preceding claims, characterized in that the initial raw geometric data are 3D data.
[6" id="c-fr-0006]
6. A method of geometric data processing according to one of the preceding claims, characterized in that step D. comprises the following operations: Dl. determine (1701) whether triangulation modification operations are valid, that is, preserve the topology of the mesh and preserve the classification condition of the set S of sample points, and D2. perform (1703-1709) valid triangulation change operations in a specified order.
[7" id="c-fr-0007]
Method according to claim 6, characterized in that the triangulation modification operations comprise edge fusions and / or half-edge fusions.
[8" id="c-fr-0008]
8. Method according to one of claims 6 and 7, characterized in that the order is determined according to an optimization criterion.
[9" id="c-fr-0009]
9. Method according to one of claims 6 and 7, characterized in that step D. is a volume called "simplistic tolerance" approaching the tolerance volume by a mesh of the canonical triangulation, the isosurface Zset being contained in this volume called "simplistic tolerance", and in that the steps Dl and D2 are performed: First (2072) on the edge of the volume called "simplistic tolerance", then on the fruit (2074) of a mutual triangulation between the isosurface (Zset) and the volume called "simplistic tolerance", this mutual triangulation adding vertices, edges and meshes in the triangulation, on the isosurface, Finally (2076), with other edges contained in the so-called "simple tolerance" volume, to cover all possible edges.
[10" id="c-fr-0010]
A device for processing geometric data, comprising: a geometric data memory, for receiving data (310) representing a tolerance volume, an initialization member (301), arranged to perform a first canonical triangulation between the edge of the geometric data, Tolerance volume and points outside thereof, A refinement member (303), arranged to specify said first triangulation to provide a dense mesh of the tolerance volume, which preserves a point classification condition. of the triangulation, a simplification member (307), arranged to simplify said dense mesh, preserving the topology and the classification of its points, and A pilot (300) which actuates successively the initialization member (301), refinement member (303), and the simplification member (307), for changing graphics data from the same tolerance volume.
[11" id="c-fr-0011]
11. Device according to claim 10, characterized in that it comprises: a point classification operator (1900), which receives the designation of a point to be treated, and determines an interpolation function on the basis of the mesh surrounding this point to be processed, and label values relative to the vertices of this mesh, to provide an interpolated label, and compare it to a current label of the point to be treated, which allows to determine a classification condition of the point to treat.
[12" id="c-fr-0012]
A computer program product comprising portions of program code for implementing the method according to one of claims 1 to 9, or the device according to one of claims 10 and 11, when the program is executed on a computer.

类似技术:

---

公开号 | 公开日 | 专利标题

---

FR3039686A1|2017-02-03|TREATMENT OF GEOMETRIC DATA WITH ISOTOPIC APPROXIMATION IN A VOLUME OF TOLERANCE

---

Berger et al.2017|A survey of surface reconstruction from point clouds

---

Tagliasacchi et al.2016|3d skeletons: A state‐of‐the‐art report

---

Borodin et al.2002|Progressive gap closing for meshrepairing

---

Alexe et al.2004|Interactive modelling from sketches using spherical implicit functions

---

WO2001008263A2|2001-02-01|Method and apparatus for generating atomic parts of graphic representation through skeletonization for interactive visualization applications

---

Podobnikar et al.2012|Digital Elevation Model from the Best Results of Different Filtering of a L i DAR Point Cloud

---

Wang2006|Bilateral recovering of sharp edges on feature-insensitive sampled meshes

---

Cuillière et al.2018|Automatic construction of structural CAD models from 3D topology optimization

---

Crane et al.2020|A survey of algorithms for geodesic paths and distances

---

Marinov et al.2006|A robust two‐step procedure for quad‐dominant remeshing

---

US20190362029A1|2019-11-28|Systems and methods for lightweight precise 3d visual format

---

Hamdi‐Cherif et al.2018|Super‐Resolution of Point Set Surfaces Using Local Similarities

---

Sarkar et al.2018|3d shape processing by convolutional denoising autoencoders on local patches

---

Khan et al.2020|Surface remeshing: A systematic literature review of methods and research directions

---

Steiner et al.2002|Cutting 3D freeform objects with genus-n into single boundary surfaces using topological graphs

---

Thayyil et al.2021|Local Delaunay-based high fidelity surface reconstruction from 3D point sets

---

WO2018104183A1|2018-06-14|Method for constructing a 3d digital model from a 2d plan

---

Liu et al.2001|Constrained fairing for meshes

---

Cao et al.2015|Patch layout generation by detecting feature networks

---

Boubekeur et al.2005|Rapid visualization of large point-based surfaces

---

Bukenberger et al.2018|Hierarchical quad meshing of 3d scanned surfaces

---

NL2011811C2|2015-05-19|METHOD AND SYSTEM FOR ANALYZING AND STORING INFORMATION.

---

Udayan2016|An analysis of reconstruction algorithms applied to 3d building modeling

---

US11257290B2|2022-02-22|Decimating a three-dimensional mesh via successive self-parameterization

同族专利:

---

公开号 | 公开日

---

WO2017021644A1|2017-02-09|

---

FR3039685A1|2017-02-03|

---

EP3329465A1|2018-06-06|

---

US20190019331A1|2019-01-17|

---

FR3039686B1|2017-08-04|

引用文献:

---

公开号 | 申请日 | 公开日 | 申请人 | 专利标题

---

US6275233B1|1996-11-01|2001-08-14|International Business Machines Corporation|Surface simplification preserving a solid volume|

---

US11079418B2|2015-03-17|2021-08-03|Zynaptiq Gmbh|Methods for extending frequency transforms to resolve features in the spatio-temporal domain|

---

WO2017040905A1|2015-09-03|2017-03-09|Stc.Unm|Accelerated precomputation of reduced deformable models|

---

US10902625B1|2018-01-23|2021-01-26|Apple Inc.|Planar surface detection|

---

US10580209B2|2018-03-06|2020-03-03|Qualcomm Incorporated|Removal of degenerated sub-primitives in tessellation|

---

US10657675B2|2018-03-06|2020-05-19|Google Llc|Techniques for improved progressive mesh compression|

---

US20200202622A1|2018-12-19|2020-06-25|Nvidia Corporation|Mesh reconstruction using data-driven priors|

法律状态:
2016-08-02| PLFP| Fee payment|Year of fee payment: 2 |

---

2017-02-03| PLSC| Search report ready|Effective date: 20170203 |

---

2017-08-23| PLFP| Fee payment|Year of fee payment: 3 |

---

2018-08-24| PLFP| Fee payment|Year of fee payment: 4 |

---

2019-08-27| PLFP| Fee payment|Year of fee payment: 5 |

---

2020-08-27| PLFP| Fee payment|Year of fee payment: 6 |

---

2021-08-30| PLFP| Fee payment|Year of fee payment: 7 |

优先权:

---

申请号 | 申请日 | 专利标题

---

FR1501664A|FR3039685A1|2015-08-01|2015-08-01|TREATMENT OF GEOMETRIC DATA WITH ISOTOPIC APPROXIMATION IN A VOLUME OF TOLERANCE|US15/749,011| US20190019331A1|2015-08-01|2016-08-01|Processing of geometric data with isotopic approximation within a tolerance volume|

---

EP16758233.7A| EP3329465A1|2015-08-01|2016-08-01|Processing of geometric data with isotopic approximation within a tolerance volume|

---

PCT/FR2016/051997| WO2017021644A1|2015-08-01|2016-08-01|Processing of geometric data with isotopic approximation within a tolerance volume|