FR 2806194 A1 20010914 FR 0002914 A 20000307 Traitement de données pour une construction perfectionnée d'images multidimensionnelles L'invention concerne un traitement de données pour une construction d'images multidimensionnelles. La modélisation géométrique consiste élaborer un traitement d'un ou plusieurs objets tridimensionnels mesurés par un capteur télémêtrique, tel qu'un palpeur, un télémètre laser, ou encore des systèmes d'imagerie tridimensionnelle. Les données initiales se présentent sous la forme d'un ensemble de points sans structure particulière mesurés sur la surface des objets. Un tel problème se rencontre notamment en conception assistée par ordinateur (CAO), en infographie, en imagerie médicale, en chimie moléculaire ou en géologie. A partir du nuage de points qui constitue ces données initiales, on veut pouvoir effectuer tout ou partie des opérations suivantes, indépendamment ou en combinaison - construire une surface représentative de ce nuage, appelée surface sous-jacente, - calculer des informations sur la surface sous-jacente, telles que les normales ou les courbures à la surface, - calculer une approximation polyédrique (encore appelée maillage) de la surface, - visualiser cette surface à différents niveaux de résolution, notamment agrandir l'image d'un échantillon de surface à observer ("zoomer" certaines parties de la surface), - modifier la position relative des points de mesure par rapport à la surface sous-jacente pour lisser ou déformer la surface, - simplifier le nuage de points en retirant du nuage des points qui ne satisfont pas une condition choisie. Le traitement par modélisation géométrique, construction et/ou reconstruction de surface, nécessite l'élaboration préalable d'un modèle informatique. Ce modèle doit être optimisé pour limiter les temps de traitement à des durées acceptables. En terme de gestion des flux de données, il est recherché en outre une transmission progressive du nuage de points. On veut pouvoir visualiser et mettre à jour, notamment affiner, une approximation de l'objet au fur et à mesure que les données sont transmises. Avec le développement des techniques de construc- tion/reconstruction de surfaces, différents procédés ont vu le jour. En particulier, un procédé connu, basé sur la considération des plus proches voisins (en nombres choisis) d'un point courant, a donné des résultats satisfaisants pour la construction/reconstruction de surfaces. Des détails sur le principe de ce procédé sont donnés notamment dans [HDD+92] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorgani- zed points. Comput. Graphics, 26(2 ) :71-78. Proc. SIGGRAPH492. Cependant, l'application de ce procédé suppose la vérification préalable d'une condition la répartition des points échantillonnés doit être uniforme sur la surface. De tels procédés, quoique prometteurs, ont montré leur limite, notamment à cause du caractère non structuré que présente généralement un nuage de points, ou encore à cause des temps de traitement souvent rédhibitoires qu'ils nécessitent. La présente invention vient apporter des solutions permettant de résoudre les problèmes posés par la mise en oeuvre de tout ou partie des opérations ci-avant. Selon une approche différente, l'invention utilise une interpolation de données spatiales, de type "interpolation naturelle", appliquée à la modélisation géométrique. on connaît le principe d'une interpolation naturelle notamment par [Sib81] R. Sibson. A brief description of natural neighbour interpolation. In Barnet, editor, Interpreting Multivariate Data, pages 21-36. John Wiley & Sons, Chichester, 1981. Sans entrer davantage dans détails, une interpolation naturelle consiste globalement à définir tout point comme le barycentre d'un sous-ensemble de points du nuage, ces points étant alors définis comme voisins naturels de ce barycentre. Les coefficients de pondération du barycentre, associés chacun à un voisin naturel, sont appelés coordonnées naturelles. La présente invention propose un procédé de traitement de données, notamment pour la construction/reconstruction d'images multidimensionnelles. I1 peut s'agir aussi bien d'images bidimensionnelles, ou encore tridimensionnelles. Comme on le verra en détail plus loin, ce procédé s'applique à une dimension quelconque, supérieure ou égale à deux. Le procédé de traitement comprend donc les étapes suivantes a) obtenir tout d'abord un nuage de points de coordonnées connues, et b) définir, par une interpolation naturelle de ce nuage de point, les voisins naturels d'un point courant du nuage et évaluer les coordonnées naturelles du point courant, chacune en correspondance avec un voisin naturel. Selon une première caractéristique importante de l'invention, le procédé comprend en outre les étapes suivantes c) calculer, à partir des voisins naturels d'un point courant de ses coordonnées naturelles, une fonction implicite représentative d'une distance entre ce point courant et un elément de surface comprenant sensiblement les voisins naturels de l'élément courant, répéter les étapes b) et c) avec au moins une partie des points du nuage pris successivement comme points courants, et construire une surface comprenant une pluralité de points pris â l'étape d) comme points courants et dont la fonction implicite vérifie une condition choisie, telle que dans une forme de réalisation, la fonction implicite est nulle. Selon une seconde caractéristique importante de l'invention, le procédé comprend en outre les étapes suivantes c11) estimer une orientation d'un premier élément surface choisi, préférentiellement pour le point de plus grande abscisse en tant que point courant, et c12) déduire les uns des autres et à partir de l'orientation du premier élément, les orientations respectives tous les éléments de surface, ce qui permet d'obtenir l'orientation des vecteurs unitaires perpendiculaires chacun à un elément de surface. Selon une troisième caractéristique importante de l'invention, l'étape e) du procédé comprend une opération consistant â ignorer les points du nuage dont la distance à la surface à construire est inférieure à une valeur seuil, en vue d'effec tuer une simplification du nuage de points, ce qui permet de construire une surface totale à partir du nuage de points et/ou de lisser cette surface, de préférence en fonction d'une tolérance choisie, et/ou de déformer localement cette surface. Selon une autre caractéristique importante de l'invention, 1 étape b) du procédé comprend les opérations préalables suivantes appliquer une triangulation de Delaunay au nuage de points, b2) construire des cellules de Voronoï et en déduire les centres des cellules, b3) ajouter à chaque cellule deux pôles correspondant sensiblement à des points les plus éloignés du centre de la cellule, préférentiellement situés de part et d'autre de surface, et dont les coordonnées naturelles associées sont préférentiellement considérées comme nulles, et b4 évaluer les coordonnées naturelles dans chaque cellule ainsi augmentée. Ainsi, au lieu de calculer les coordonnées naturelles sur diagramme de Voronoï du nuage de points initial, pour chaque point courant, on calcule ces coordonnées sur le diagramme Voronoï du nuage augmenté des pôles. Une interpolation ainsi exécutée présente les avantages suivants - les résultats obtenus par cette interpolation sont proches de ceux obtenus par une interpolation rigoureuse sur tout nuage de points, et - les temps de traitement associés sont considérablement diminués, au moins d'un facteur dix. Le procédé selon l'invention peut être mis en oeuvre par un dispositif comprenant notamment - moins une mémoire pour ranger les coordonnées de chaque point du nuage, - processeur apte à coopérer avec la mémoire pour effectuer tout ou partie des opérations du procédé, - interface graphique agencée pour coopérer avec le processeur, et - écran relié à l'interface graphique pour afficher au moins la surface construite. A ce titre, la présente invention vise aussi un tel disposi tif. D'autres caractéristiques et avantages de l'invention apparal- tront à l'examen de la description détaillée ci-après, et des dessins annexés sur lesquels - la figure 1 représente schématiquement un dispositif pour la mise en ouvre du procédé selon l'invention, - la figure 2 illustre la construction d'une cellule de Voronoï dans un espace bidimensionnel, - la figure 3 illustre le principe d'une insertion d'un point x dans une triangulation de Delaunay bidimensionnelle, - la f figure 4 est une représentation schématique d' une surface avec ses normales, dans un plan comprenant l'axe abscis ses - figure 5 représente les pôles S et S' d'une cellule de Voronoï dont le point Ai est le centre, et - figure 6 est un organigramme représentant les etapes d'un procédé pour l'orientation des vecteurs unitaires perpendicu laires (vecteurs normaux). L'annexe I comprend des équations auxquelles texte de description ci-après se réfère et l'annexe II retranscrit sous forme d'un pseudo-code un traitement informatique pour l'insertion d'un point dans une triangulation de Delaunay tridimensionnelle. Les dessins contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la description, mais aussi contribuer à la définition de l'invention, le cas échéant. En se référant à la figure 1, le dispositif se présente sous la forme d'un ordinateur comprenant une unité centrale UC munie d'un microprocesseur uP qui coopère avec une carte-mère CM. Cette carte-mère est reliée à divers équipements, tels qu'une interface de communication COM (de type Modem ou autre), une mémoire morte ROM et une mémoire de travail RAM (mémoire vive). La carte-mère CM est reliée en outre à une interface graphique IG, laquelle pilote l'affichage de données sur un écran ECR que comporte le dispositif. I1 est prévu en outre des moyens de saisie, tels qu'un clavier CLA et/ou un organe de saisie dit "souris" SOU, reliés à l'unité centrale UC et permettant à un utilisateur une interactivité avec le dispositif. Dans l'exemple représenté sur la figure 1, une partie gauche de l'écran représente un nuage de points dont les coordonnées sont connues et préalablement enregistrées, par exemple en mémoire morte ROM du dispositif. Sur la partie droite de l'écran est représentée une surface reconstruite, par exemple dans un espace à trois dimensions, par un traitement selon le procédé de l'invention et effectué par le microprocesseur en coopération avec les différentes mémoires de l'unité centrale. Les moyens de saisie CLA, SOU permettent à un utilisateur d'entrer par exemple une tolérance de lissage de la surface reconstruite, ou encore d'affiner cette surface. Dans une autre réalisation, le dispositif peut recevoir progressivement des points du nuage dans un ordre choisi, par son interface de communication COM, puis construire une surface brute, tandis que la mémoire ROM comporte un module avec lequel le microprocesseur peut coopérer pour affiner la surface brute en y insérant des points de coordonnées choisies, comme on le verra plus loin. Le procédé selon l'invention applique à la modélisation géométrique une interpolation de données spatiales dont le principe est décrit dans [Sib81] et appelée "interpolation naturelle". En se référant la figure 2, l'interpolation naturelle permet, étant donné un ensemble de points A = @A1,...An} d'un espace E, d'exprimer tout point X de E comme le barycentre d'un sous-ensemble de points de A qu'on appelle les voisins naturels du point X. Dans l'équation 1 en annexe les coefficients \i sont appelés les coordonnées naturelles de X sont chacune en correspondance avec un voisin naturel Ai. Pour définir précisément les coefficients ai, il faut considérer le diagramme de Voronoï de A ou la triangulation Delaunay duale. Dans l'exemple représenté sur la figure 2, le polygone représenté en traits pointillés forme la cellule Voronoï dont le point X est le centre. Dans l'espace tridimensionnel, cette cellule est délimitée par un polyèdre. définitions et les propriétés de ces structures géométri ques sont décrites dans des livres de géométrie algorithmique, exemple dans BY98] Jean-Daniel Boissonnat and Mariette Yvinec. Algo- rithmic Geometry. Cambridge University Press, UK, 1998. Traduit par Hervé Brdnnimann. Le calcul de la triangulation de Delaunay est possible en toutes dimensions. Un algorithme particulièrement efficace dans un espace à deux ou trois dimensions peut être issu du principe décrit dans Dev98] Olivier Devillers. Improved incremental randomized Delaunay triangulation. In Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 106-115, 1998. Dans ce qui suit, on appelle V(Ai) la cellule du diagramme de Voronoï de l'ensemble A et qui est associée au point .. On note V (X) la cellule d'un point X dans le diagramme de Voronoï l'ensemble A augmenté du point X. Ai est un voisin naturel de X, alors V(Ai) et V(X) une intersection non vide V(Ai,X). La coordonnée naturelle 1,i(X) le rapport du volume de V(Ai,X) sur le volume de V(X). calcul des coordonnées naturelles dans un espace bidimen sionnel est décrit notamment dans [Wat92] David F. Watson. Contouring . A guide to the Analysis and Display of Spatial Data. Pergamon, 1992. Dans un espace tridimensionnel, une évaluation des coordonnées naturelles par le calcul explicite de l'intersection entre la cellule de Voronoï de X et celles de ses voisins est decrite dans la thèse de S.J.Owen [Owe92] S.J. Owen. An implementation of natural neighbor interpolation in three dimensions. Master's thesis, Brigham Young University, 1992. Cependant, cette évaluation, quoique satisfaisante dans le principe, a montré sur un plan pratique quelques limites dont notamment le fait que l'algorithme associé à cette évaluation est pas efficace. est décrit ci-après un procédé d'évaluation efficace. traitement proposé s'appuie d'abord sur un algorithme d'insertion d'un point X dans une triangulation de Delaunay tridimensionnelle. A titre indicatif, la figure 3 illustre dans l'espace bidimensionnel le principe d'insertion d'un point X dans une triangulation de Delaunay. Tous les triangles dont le cercle circonscrit entoure le point X doivent être supprimés. Ces triangles sont dits en conflit avec X. Le trou ainsi créé polygone pl à p6 sur la figure 3) est ensuite retriangulé en reliant X aux arêtes du bord du trou, comme indiqué en pointillé sur la figure 3. considère, dans l'exemple représenté, un ensemble de points p1 à p6. Chaque point est joint à son voisin par l'arrête d'un triangle. Un point x est inséré s'il est contenu dans tous les disques délimités par des cercles dans lesquels sont circons crits les triangles, un à un. Dans l'espace tridimensionnel, les tétraèdres en conflit avec le point X sont repérés dans un premier temps. est rappelé qu on appelle "tétraèdre en conflit" un tétraèdre dont la sphère circonscrite contient le point X. L'union de ces tétraèdres forme un polyèdre appelé "cavité" dans ce qui suit. Les arêtes des tétraèdres en conflit sont situées soit sur la frontière de cette cavité, soit dans son intérieur. On les appelle respectivement arêtes externes et internes à la cavité. Ensuite, les nouveaux tétraèdres remplissant cavité sont creés. Ils s'appuient sur les faces de la cavité et ont pour sommet commun le point X. La création et la mise à jour des relations d'adjacence entre ces tétraèdres sont préférentiel lement effectuées en tournant autour des arêtes externes de la cavité. L'algorithme de calcul des coordonnées naturelles consiste à décrire une triangulation de la frontière des régions subtilisées par le point X à ses voisins. Les volumes des V(Ai,X) sont calculés à partir des triangulations, par exemple selon le principe décrit dans [Ber87] M. Berger, Geometry II, section 12.2, Springer, 1987. Les coordonnées naturelles Ai sont ensuite déduits de ces volumes par normalisation. Ainsi, les tétraèdres en conflit sont d'abord trouvés. Ensuite, à l'occasion des rotations autour des arêtes internes et externes, les faces duales de ces arêtes sont reportées. Chaque face de ce type est commune à deux régions naturelles, et ses sommets sont les centres de Voronoï des tétraèdres traversés. La séquence de ces sommets est alors la triangula- tion utilisée pour calculer le volume. On pourra se référer au traitement retranscrit à l'annexe II et préféré ici, pour 'insertion de point dans une triangulation de Delaunay tridimensionnelle. Selon l'invention, une fonction implicite est calculée à partir d'informations locales sur une surface à reconstruire. Cette fonction implicite interpole ces informations de la manière suivante. appelle A un nuage de points A = {A1,...An} 'un espace E (E est en général le plan ou l'espace tridimensionnel usuels mais le procédé s'applique en toutes dimensions mesurés sur une surface orientable S. Dans un premier temps, on considère en chaque point Ai, le vecteur normal ni à surface en point est connu. On évalue une approximation de la distance signée d'un point X de E à la surface par la fonction implicite h(X) donnée par la formule correspondant à l'équation 2 en annexe. Ainsi, l'évaluation de la fonction implicite h(X) peut s'effectuer en procédant aux étapes suivantes - déterminer, pour chaque voisin naturel Ai du point courant X, un vecteur XAi entre le point courant et ce voisin naturel, calculer le produit scalaire entre le vecteur XAi et le vecteur unitaire ni perpendiculaire à l'élément de surface comprenant ce voisin naturel Ai, pondérer le produit scalaire par la coordonnée naturelle Ai (préalablement calculée) du point courant et associée au voisin naturel Ai, et - estimer la somme des produits scalaires ainsi pondérés sur tous les voisins naturels du point courant X. L'utilisation de cette fonction implicite présente de nombreux avantages. En effet, la fonction h est continuement différen- tiable. De plus, l'ensemble SA des points X pour lesquels la fonction h(X) est nulle, est une surface qui passe par les Ai et dont la normale en Ai est le vecteur ni. I1 est alors proposé ici une approximation de la surface S par surface SA. principe consistant à calculer une fonction implicite à partir des Ai et des vecteurs ni a été décrit notamment dans [HDD+92] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Surface reconstruction from unorgani- zed points. Comput. Graphics, 26(2):71-78. Proc. SIGGRAPH492. Cependant, dans leurs travaux, les auteurs n'utilisent les voisins naturels mais les k plus proches voisins. Ainsi le procédé décrit dans [HDD+92] est inutilisable si la surface n'est pas uniformément échantillonnée. Outre le fait qu'elle permette de traiter correctement cas de surfaces échantillonnées de manière non uniforme, l'utilisation du procédé selon l'invention fournit une surface SA lisse et donne de bons résultats même si les données sont rares, avec peu de points dans le nuage. L'estimation des vecteurs normaux ni est décrite ci-apres. Dans ce qui suit, on appelle maintenant "voisins naturels" d'un point Ai d'un ensemble A, les voisins naturels de Ai que l'on obtiendrait si l'on retirait le point Ai de l'ensemble A. On peut alors calculer les voisins et les coordonnées naturels de Ai dans le nouvel ensemble A\@Ai}. Pour estimer la direction ôi du vecteur normal ni, une première approche consiste à calculer le plan moyen (au sens des moindres carrés) passant par les voisins naturels de Ai pondérés par les coordonnées naturelles associées. Une autre approche, préférée ici, est basée sur l'insertion, parmi les voisins naturels Ai, des pôles de la cellule de Voronoï dont le point Aj le centre. Ces pôles seront décrits en détail plus loin La direction du vecteur ni étant connue, il reste à orienter le vecteur ni, c'est-à-dire à choisir une orientation parmi les deux orientations possibles. On cherche en particulier à effectuer ces orientations de manière cohérente pour tous les points Ai. On se réfère à la figure 6 pour le détail des étapes du procédé d'orientation des vecteurs normaux ni. Après une instruction de début 10, on choisit tout d'abord (étape 12), pour le point de plus grande abscisse Ax, l'orientation du vecteur ni, telle que ce vecteur ni, forme un angle aigu (figure 4) avec le vecteur unitaire porté par le premier axe de coordonnées (axe des abscisses). Un premier point Ail a maintenant un vecteur normal ni,. Considérons alors une étape générale du procédé d'attribution des orientations, où un certain nombre de points de A ont déjà un vecteur normal (mais pas tous). On effectue d'abord un test (etape 16) pour savoir si un point Aj a ou non un vecteur normal avec j allant de 1 à N où N est le nombre total de vecteurs normaux à orienter (étape 14). Pour chaque point Aj qui n'a pas encore de vecteur normal, on estime son vecteur normal mj par la formule donnée par l'équa tion 3 en annexe. Dans cette equation 3, le vecteur ni (Aj) est considéré comme nul si le point Aj n'a pas encore de vecteur normal. A chaque point Aj on associe (étape 18) la valeur vj de la projection du vecteur sur la direction ô j. Si la valeur absolue de vj la plus grande parmi celles calculées précédemment (test 20), alors on lui attribue la direction 6 j (étapes 24 et 25). Son orientation est déterminée en fonction du signe de vj (test 22). Les valeurs des projections vk associées aux voisins naturels de . sont mises à jour (étape 26) et on maintient ensuite la liste des Aj triée par valeurs décroissantes des vj (étape 28 Ces étapes sont réitérées par récurrence (étape 30) jusqu a épuisement de la liste (test 32 et instruction de fin en ). Ainsi, on affecte un vecteur normal ni, au premier élément de la liste (le point Ail) et on met progressivement cette liste ' jour, par exemple en utilisant en pratique structure de données de type "queue de priorité". Toutes les normales ont alors été orientées. procédé d'orientation des normales est particulièrement avantageux par rapport aux autres procédés connus, par exemple procédé basé sur le principe décrit dans [HDD+92] et qui suppose une répartition uniforme des points sur la surface S. autre détermination des vecteurs normaux est basée sur un principe décrit dans [ABK98] N. Amenta, M. Bern, and M. Kamvysselis. A new voronoi-based surface reconstruction algorithm. In Proc. SIGGRAPH'98, Computer Graphics Proceedings, Annual Conference Series, pages 415- , July 1998. Cependant, seule la direction des normales est fournie ici, non leur orientation. procédé particulièrement avantageux pour évaluer les coordonnées naturelles avec une durée réduite temps de traitement est décrit ci-après. Pour chaque cellule de Voronoï V(Ai) on recherche son sommet le plus éloigné S et le sommet S' le plus éloigné dans la direction du vecteur SAi (figure 5). Ces points sont appelés les pôles. On note A+ l'ensemble formé des points de A et des pôles rajoutés. L'évaluation des coordonnées naturelles est faite en considérant le diagramme de Voronoï de A' mais en posant que la coordonnée naturelle associée à un point rajouté est nulle. Le nombre de volumes à calculer est alors propor tionnel au nombre de voisins naturels du point qui sont des points l'échantillon voisins de X sur la surface (et non plus dans tout l'espace). Ce procédé permet diviser les temps calcul par un facteur d'environ vingt I1 est décrit ci-après un procédé de simplification du nuage de points initial. Souvent les données sont redondantes et il souhaitable d'extraire du nuage de points A un sous-ensemble aussi petit que possible qui représente à une tolérance e prés la surface S. Pour cela, on considère un petit sous-ensemble A' de A et on évalue pour tous les points de A\A' leur distance à SA, en utilisant la fonction implicite décrite ci-avant. Si la distance d'un point Ai excède en valeur absolue e, on ajoute Ai à A' On réévalue ensuite les distances des points de A\A' dont le point Ai est devenu un voisin naturel. On réitère le processus jusqu'à ce que tous les points de A\A' soit à une distance plus petite en valeur absolue que e de SA,. Ce procédé diffère des procédés habituels qui consistent par exemple à construire un maillage initial à partir des points de données puis, dans un deuxième temps, à simplifier ce maillage. Ainsi, le procédé de simplification décrit ci-avant est particulièrement avantageux dans le cas de très gros ensembles de données pour lesquels il n'est pas envisageable de construire un maillage. Cette situation est souvent rencontrée dans les applications de modélisation à partir de mesures. Ce procédé permet en outre de représenter la surface à différents niveaux de résolution. Typiquement, si l'on trie les points de l'ensemble A suivant l'ordre d'insertion décrit plus haut, il est possible de faire varier la résolution de la reconstruction en ne retenant par exemple qu'un nombre choisi premiers points. Le proce 'trouve une application particulièrement avantageuse à la transmission des données par une liaison du type utilisant une interface de communication COM (figure 1). les points sont transférés dans l'ordre d'insertion précité le modèle reconstruit peut être progressivement raffiné au et à mesure que les points sont transmis. Une application à une utilisation en ligne (type "internet") permet ainsi voir s'afficher progressivement un objet tridimensionnel complexe sans avoir à attendre le chargement complet données I1 est decrit ci-après un procédé pour l'affichage à l'écran ECR de surface construite S. Pour visualiser la surface S avec les cartes graphiques (ou interfaces graphiques IG) habituelles, il faut mailler surface S, c'est-à-dire construire un polyèdre qui approche S à une certaine tolérance il prédéterminée. Un procedé connu consiste à utiliser un algorithme de type "marching cubes" issu du principe décrit par exemple dans référence [HDD+92]. Cependant, ce procédé présente plusieurs inconvénients, notamment le fait que la résolution dépende la taille de la grille et non des propriétés locales de la surface et, d'autre part, le fait que les points Ai ne sont pas, de manière générale, des points du maillage. Le procedé utilisé ici débute par une triangulation grossière de la surface S, suivie éventuellement d'une pluralité d'étapes consistant globalement à raffiner cette triangula- tion. A chaque triangle de la triangulation courante, on associe un point sur la surface, équidistant des sommets du triangle. On appelle ce point le centre du triangle. Ce point est éventuel lement ajouté comme nouveau sommet du maillage. Cependant, dans le cas de données ponctuelles, on ne connaît pas de maillage initial. Néanmoins, le diagramme de Voronoï et la triangulation de Delaunay de l'ensemble A ont été calculés pour évaluer les coordonnées naturelles, et sont donc disponibles. On détermine les facettes d'un maillage "initial" comme suit. Dans un premier temps, on recherche des arêtes dites "bipolai res" et qui correspondent à des arêtes de Voronoï dont la fonction distance (évaluée selon l'équation 2 de l'annexe ) est positive à une de leurs extrémités et négative à l'autre (en d'autres termes, ces arêtes coupent S). Les facettes du maillage initial sont alors les facettes la triangulation de Delaunay dont l'arête duale est bipolaire Ce maillage peut être ensuite raffiné par insertion centres des facettes du maillage et par mise à jour progres sive de 1 ensemble des faces du maillage. Ainsi, centre est inséré si sa distance au triangle correspondant est supérieure à un seuil il prédéterminé. Pour plus de détails sur le principe mathématique dont ce procédé avantageusement adapté, on pourra se référer à [Che97] Chew. Guaranteed quality Delaunay meshing in 3d. Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 391-393, 1997. Le maillage obtenu a comme sommets les points Ai et centres rajoutés. On peut obtenir ainsi des surfaces lisses même avec très peu de points de données. Ce procédé trouve donc une application particulièrement intéressante à la transmission de données (par exemple en ligne) et à la compression de modèles géométriques. I1 suffit en effet de transmettre les points Ai et, à la réception, d'utiliser le procédé de maillage décrit ci-avant. autre application intéressante se trouve dans la création interactive d'objets à partir de points. A partir d un petit echantillon, il est alors possible de construire une première surface qui peut ensuite être modifiée. De telles modifications peuvent s'effectuer en déformant la surface construite. procédé pouvant être utilisé consiste à choisir pour un point courant, un jeu de paramètres ai à ajouter ou sous traire chacun à l'un des produits scalaires de l'équation 3, vue de déformer la surface construite en ce point courant. Ainsi, en remplaçant, pour un jeu de paramètres choisis ai, l'équation 3 par l'équation 4 dans l'annexe I, ou encore en modifiant un ou plusieurs vecteurs normaux ni, peut de manière simple déformer localement la surface SA. I1 est alors possible d'éditer par exemple un modèle à partir de points, comme décrit ci-avant. Bien entendu, l'invention n'est pas limitée à la forme de réalisation décrite précédemment à titre d'exemple ; elle peut s'étendre à d'autres variantes néanmoins définies dans le cadre des revendications ci-après. ANNEXE I ANNEXE II void delaunay::create(tetrahedron *n, Index i) {tetrahedron *son, *nn; //create the tetrahedron leaning on the i-th face of n //and update adjacencies (1) son n->son[i] = new tetrahedron(insertedPoint, n, i); (2) son->Neighbor[0] = n->Neighbor[i] ; (3) n->Neighbor[i]-> Neighbor[n->Neighbor[i]->n->findNeighborIndex(n)] son; //recursively create the sons neighbors (4) for(j = 1 ; j 4 ; j++ ) (5) rotate around the edge opposite to [i,j] until the next cavity face. let nn be the corresponding tetra and k be this face //create the sons neighbor and link it (6) if ( ! nn->son[k] ) create(nn,k); (7) son->Neighbor[j] = nn->son[k] ; Revendications 1. Procédé de traitement de données pour une construction d'images multidimensionnelles, comprenant les étapes suivantes a) obtenir un nuage de points (E) de coordonnées connues, b) définir, par une interpolation naturelle de ce nuage de point, les voisins naturels (A\(Ai}) d'un point courant (Ai) du nuage (E) et évaluer les coordonnées naturelles (Xj) du point courant (Ai), chacune en correspondance avec un voisin naturel (Aj), caractérisé en ce qu'il comprend en outre les étapes suivantes c) calculer, à partir des voisins naturels d'un point courant (Ai) et des coordonnées naturelles, une fonction implicite représentative d'une distance (h(Ai)) entre ce point courant et un élément de surface (SAi) comprenant sensiblement les voisins naturels (Aj) de l'élément courant (Ai), d) répéter les étapes b) et c) avec au moins une partie des points du nuage pris successivement comme points courants, et e) construire une surface (SA) comprenant une pluralité de points pris à l'étape d) comme points courants et dont la fonction implicite vérifie une condition choisie. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape e) comprend les opérations suivantes el) déterminer les points courants dont la fonction implicite est nulle, et e2) insérer ces points courants dans la surface à construire. 3. Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'étape c) comprend les opérations suivantes cl) déterminer, pour chaque voisin naturel (Ai) du point courant (X), un vecteur (XAi) entre le point courant et ce voisin naturel, c2) calculer un produit scalaire entre le vecteur (RAi) déterminé à l'étape cl) et un vecteur unitaire (ni) perpendi culaire à l'élément de surface comprenant ce voisin naturel, c3) pondérer le produit scalaire par la coordonnée naturelle du point courant (ki) qui est en correspondance avec voisin naturel ), et c4) estimer la somme des produits scalaires ainsi ponderés sur tous les voisins naturels du point courant. 4. Procedé selon l'une des revendications précédentes, caractérisé en ce qu'il comprend en outre étapes suivantes c11) estimer une orientation (ni,) d'un premier elément de surface choisi, et c12) déduire les uns des autres et à partir de l'orientation du premier élément, les orientations respectives ( # de tous les éléments de surface, ce qui permet d'obtenir l'orientation des vecteurs unitaires perpendiculaires chacun à un élément de surface. 5. Procédé selon la revendication 4, caractérisé ce que l'orientation (ni,) du premier élément de surface est estimée pour le point de plus grande abscisse (Ail) en tant point courant. 6. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape e) comprend une operation consistant à ignorer les points du nuage dont la distance à la surface à construire est inférieure à une valeur seuil (s), en vue effectuer une simplification du nuage de points. 7. Procedé selon la revendication 6, caractérisé en ce que la valeur seuil () est choisie en fonction d'une tolérance de lissage de la surface à construire. 8. Procédé selon l'une des revendications 3 à 7, caractérisé en ce qu' il comporte une opération consistant à choisir un jeu de paramètres (ai) à ajouter ou soustraire chacun à l'un des produits scalaires, en vue de déformer la surface construite en ce point courant. 9. Procédé selon l'une des revendications 4 à 8, caractérisé en ce qu'il comporte une opération consistant à modifier les coordonnées d'au moins un vecteur (ni) normal à un élément surface, en vue de déformer la surface construite en élément de surface. 10. Procédé selon l'une des revendications précédentes caractérisé en ce que l'étape b) comprend les opérations préalables suivantes b1) appliquer une triangulation de Delaunay au nuage points, b2) construire des cellules de Voronoï et en déduire centres (X) des cellules, b3) ajouter à chaque cellule deux pôles (S, S') correspondant sensiblement à des points les plus éloignés du centre de la cellule, et b4 évaluer lesdites coordonnées naturelles dans chaque cellule ainsi augmentée. 11 Procédé selon la revendication 10, caractérisé en ce que à 'étape b4), les coordonnées naturelles associées aux pôles ajoutés (S, S') sont considérées comme nulles. 12 Procédé selon l'une des revendications 10 et 11, caracté risé en ce qu'il comprend en outre les étapes suivantes hl) déterminer, à partir de la triangulation de Delaunay à l'étape b1), au moins une facette, ainsi qu'un centre de cette facette, h2 estimer, en calculant la fonction implicite du centre de la facette, la distance entre la facette et son centre, et h3 insérer ce centre dans la surface construite si la distance estimée est supérieure à un seuil prédéterminé (il), ce qui permet d'affiner la surface construite. 13 Dispositif pour la mise en oeuvre du procédé selon l'une revendications précédentes, caractérisé en ce qu'il comprend - au moins une mémoire (ROM) pour ranger les coordonnées de chaque point du nuage, - un processeur (pP) apte coopérer avec la mémoire pour effectuer tout ou partie des opérations du procédé, - une interface graphique (IG) agencée pour coopérer avec le processeur, et - un écran (ECR) relié à l'interface graphique pour afficher au moins la surface construite.