Brevet FR3035990A1 — publié le 20161111

PROCEDE DE SIMPLIFICATION DE MODÈLE DE GÉOMÉTRIE La présente invention concerne le domaine de la modélisation d'objet et notamment le domaine de la simplification de modèles de géométrie (maillage ou 5 nuages de points, par exemple) pour des objets modélisés en trois dimensions. Lors de la modélisation d'objet en trois dimensions à partir d'objets réels, les modèles de points obtenus ou les modèles de mailles (ex. faces triangulaires) peuvent être présents en très grand nombre (ex. plusieurs millions de mailles / de 10 triangles) pour représenter finement la géométrie de l'objet. La modélisation en trois dimensions (i.e. 3D) de ces objets réels peut notamment être effectuée à l'aide de techniques utilisant des scanners tridimensionnels. Un scanner tridimensionnel est un appareil qui analyse les objets ou leur environnement proche pour recueillir des informations précises sur la forme et éventuellement sur 15 l'apparence (couleur, texture...) de ceux-ci. Ces scanneurs tridimensionnels peuvent utiliser diverses technologies comme la lumière (ex. laser, lumière structurée, lumière modulée), les ultrasons ou encore les rayons X. Un exemple de scanner tridimensionnel visant le grand public est la tablette Google Tango ou encore le produit Microsoft Kinect. N'importe quel capteur photo est aussi un scanner 3D 20 potentiel, à partir du moment où lui adjoint un programme de stéréovision, reconstruisant une forme 3D à partir d'un série de photos. Qu'ils soient numérisés ou créés virtuellement, les objets 3D numérique peuvent être de différentes natures et usages, notamment : - des données urbaines et architecturales (ex. bâtiments), 25 - des données culturelles (scans de sites archéologiques, scans d'ceuvres d'art), - données massives issues de simulation, - données extraites d'images médicales, 3035990 2 - données capturées pour des médias visuels comme la prévisualisation en effets spéciaux, - création de contenus pour les jeux vidéo, - etc. Néanmoins, les modèles 3D issus de ces outils de modélisations sont le plus souvent très complexes et donc très lourds. Dès lors, il peut être compliqué de manipuler / de visualiser ces modèles sur des équipements informatiques de faible puissance de calcul (ex. smartphone). En outre, les capacités réseau limitées (ex. réseaux WiFi de faibles qualités, réseaux mobiles) peuvent empêcher de télécharger ces modèles lourds de manière instantanée et commode. Pour adapter ces modèles à de tels contextes contraints, les méthodes existantes de simplifications géométriques reposent principalement sur deux grandes catégories de techniques : - des algorithmes de simplification itérative : regroupement de sommets de mailles ou contraction d'arêtes (Hoppe et al. « Mesh optimization » 1993 ou Garland et al. « Surface simplification using quadrics error metrics » 1997) ; - des algorithmes de partitionnement : partitionnement des mailles en régions (ex. Lindstrom et al. « Out-of-core simplification of large polygonal models » 2000 ou Cohen-Streiner et al. « Variational Shape approximation » 2004). Ces algorithmes sont relativement lents et peuvent nécessiter une grande consommation de mémoire. Dès lors, leur application sur de grands modèles peut être difficile. De plus, pour certains algorithmes de partitionnement, la convergence des algorithmes peut ne pas être garantie. Il existe ainsi un besoin pour simplifier de manière efficace et réaliste les modèles 25 lourds et complexes que peuvent produire des outils de modélisation 3D. En outre, il existe également un besoin pour effectuer cette simplification de manière très rapide afin d'être en capacité de simplifier les modèles en quasi temps réel (ex. besoin de réactivité forte en cas de demande de simplification, transmission d'un modèle en mouvement). 3035990 3 Bien entendu, si cette simplification doit être rapide, cette simplification doit également éviter, au maximum, de dégrader la qualité des modèles simplifiés, préservant au mieux la forme d'origine. La présente invention vient améliorer la situation. 5 À cet effet, la présente invention propose un procédé de simplification de modèle de géométrie efficace et optimisé pour les calculs parallèles. La présente invention vise alors un procédé de simplification d'un modèle de géométrie, le procédé comprend : /a/ réception dudit modèle de géométrie comprenant une pluralité de points, 10 chaque point de la pluralité étant associé à une mesure d'erreur ; /b/ pour chaque point courant dudit modèle de géométrie, - détermination d'un code de Morton associé au point courant en fonction de coordonnées dudit point courant ; - détermination d'une mesure d'erreur intégrale définie comme étant 15 fonction d'une somme des mesures d'erreur associées aux points de la pluralité ayant un code de Morton associé inférieur au code de Morton associé au point courant ; /c/ détermination si un ensemble donné de points de la pluralité peut être simplifié par un nouveau et un unique point, les points de l'ensemble donné 20 étant tous les points de la pluralité ayant un code de Morton associé avec un même préfixe de longueur donné, en fonction au moins d'une différence entre : - la mesure d'erreur intégrale déterminée pour le point de l'ensemble donné ayant le code de Morton le plus grand ; et - la mesure d'erreur intégrale déterminée pour le point de la pluralité ayant un code de Morton immédiatement inférieur au code de Morton le plus petit parmi les codes de Morton associés aux points de l'ensemble. Un « modèle de géométrie » peut être par exemple un maillage ou un nuage de 3035990 4 point. Par soucis de simplicité, par la suite, le terme de « maillage » est utilisé à la place de « modèle de géométrie ». Le plus souvent, les « mesures d'erreur » sont représentées à l'aide d'une fonction, d'une matrice (ex. 4x4) représentant une quadrique. À partir d'une mesure 5 d'erreur donnée, il est possible de calculer une valeur d'erreur (e). Bien entendu, les termes « inférieur », « le plus grand », « le plus petit » sont à interpréter en fonction d'une relation d'ordre donnée (au sens mathématique). Dès lors, la terminologie « inférieur » au sens de cette relation d'ordre peut très bien signifier « supérieur » au sens de la relation d'ordre dit « naturelle » (i.e. celle à 10 laquelle nous sommes habitués, ex. 1 110101). Comme il le sera expliqué ci-dessous, il est possible d'effectuer la détermination de l'étape Ici en identifiant le noeud parent commun à l'ensemble de points dans un 15 arbre k-d. En outre, la mesure d'erreur associée à un point courant de la pluralité peut être fonction d'une quadrique représentative de mailles du modèle dont au moins un des sommets est ledit point courant ou est à une distance inférieure à une distance 20 prédéterminée dudit point courant. La distance prédéterminée peut être choisie inférieure à une dimension des mailles (ex. 30% de la dimension la plus petite parmi les mailles du modèle ou parmi des mailles proches dans le modèle). 25 Dans un mode de réalisation particulier, la mesure d'erreur associée à un point courant de la pluralité peut être fonction de couleur de mailles du modèle dont au moins un des sommets est ledit point courant. Cette prise en compte de la couleur dans la détermination de la mesure d'erreur peut permettre d'éviter des simplifications trop importantes dans des zones du 3035990 5 maillage ayant des changements de couleur importants. En complément ou en variante, la mesure d'erreur associée à un point courant de la pluralité peut être fonction d'une quadrique représentative d'un vecteur normal 5 associé audit point courant. Cette prise en compte de vecteurs normaux dans la détermination de la mesure d'erreur peut permettre d'éviter des simplifications trop importantes dans des zones du maillage ayant des motifs géométriques importants, mais de faibles amplitudes (ex. zone comportant des cheveux, ou une zone comportant des structures en fibres, 10 etc.). En outre, le procédé peut comprendre: - si un premier point de la pluralité est associé à un code de Morton identique à un deuxième point de la pluralité, suppression de la pluralité de points ledit 15 deuxième point. Ainsi, il est possible de dédupliquer des points du maillage très proches. En effet, le code de Morton associé peut avoir une précision plus faible que la précision des coordonnées de l'espace (i.e. le nombre de bits utilisés pour le code de Morton est inférieur à trois fois le nombre de bits utilisés pour chacune des coordonnées). Dès 20 lors, deux points différents du modèle peuvent avoir un même code de Morton. Dans un mode de réalisation, ledit nouveau point peut être fonction des points de l'ensemble. Par exemple, ce nouveau point peut être un barycentre (éventuellement pondéré) des points de cet ensemble. 25 En complément ou en variante, ledit nouveau point peut être déterminé par une minimisation d'une valeur fonction de ladite différence. Par exemple, si la différence est une quadrique Q et si le nouveau point est noté p, il est possible de minimiser 3035990 6 (p,1)TQ(p,1). Cette minimisation peut être itérative (i.e. modification de la valeur de p de nombreuses fois pour tendre vers une valeur minimale), formelle (i.e. résolution d'une équation de minimisation) ou même semi-formelle (résolution d'une équation donnant un résultat proche de la minimisation). 5 Par ailleurs, le procédé peut comprendre en outre : - détermination d'un arbre k-d sur la base d'un codage de Morton, ledit arbre ayant comme feuilles ladite pluralité de points. La détermination d'un tel arbre permet de simplifier la mise en oeuvre informatique du 10 procédé décrit ci-dessus et de faciliter une implémentation en calcul parallèle. Dès lors, le procédé peut être décrit par des parcours d'arbres, parcours qu'il est possible d'optimiser pour favoriser les allocations statiques de mémoire (ex. ne conserver en mémoire que les index initiaux (mi) et finaux (las) des noeuds feuilles à regrouper plutôt que la liste des noeuds à regrouper, etc.). 15 Ainsi, ledit arbre k-d possédant des noeuds internes, chaque noeud interne peut être associé à un point. La détermination de l'étape /c/ peut être également fonction dudit point et d'une transposée dudit point. 20 Dans un mode de réalisation, la mesure d'erreur intégrale pour chaque point courant peut être calculée comme étant fonction d'une somme : - de la mesure d'erreur intégrale d'un point ayant un code de Morton immédiatement plus petit que le code de Morton du point courant ; - de la mesure d'erreur dudit point courant. 25 Ainsi, le nombre d'opérations nécessaire pour le calcul de chaque mesure d'erreur intégrale est limité à une seule opération mathématique. Si aucun point ayant un code de Morton immédiatement plus petit que le code de Morton du point courant n'existe (i.e. le point courant a un code de Morton le plus 3035990 7 petit), alors la mesure d'erreur intégrale est simplement la mesure d'erreur dudit point courant. Cela revient à considérer que « la mesure d'erreur intégrale d'un point ayant un code de Morton immédiatement plus petit que le code de Morton du point courant » est égale à l'élément nul (noté « 0 », mais correspondant éventuellement à 5 une quadrique/matrice nulle). La présente invention vise également un dispositif destiné à simplifier de manière efficace un de modèle de géométrie. Le dispositif comprend : /a/ une interface pour une réception dudit modèle de géométrie comprenant 10 une pluralité de points, chaque point de la pluralité étant associé à une mesure d'erreur ; /b/ un circuit adapté pour, pour chaque point courant dudit modèle de géométrie : - une détermination d'un code de Morton associé au point courant en 15 fonction de coordonnées dudit point courant ; - une détermination d'une mesure d'erreur intégrale définie comme étant fonction d'une somme des mesures d'erreur associées aux points de la pluralité ayant un code de Morton associé inférieur au code de Morton associé au point courant ; 20 /c/ un circuit adapté pour une détermination si un ensemble donné de points de la pluralité peut être simplifié par un nouveau point, les points de l'ensemble donné étant tous les points de la pluralité ayant un code de Morton associé avec un même préfixe de longueur donné, en fonction au moins d'une différence entre : 25 - la mesure d'erreur intégrale déterminée pour le point de l'ensemble donné ayant le code de Morton le plus grand ; et - la mesure d'erreur intégrale déterminée pour le point de la pluralité ayant un code de Morton immédiatement inférieur au code de Morton le plus petit parmi les codes de Morton associés aux points de l'ensemble. 3035990 8 Un programme informatique, mettant en oeuvre tout ou partie du procédé décrit ci- avant, installé sur un équipement préexistant, est en lui-même avantageux, dès lors qu'il permet une simplification efficace de modèle de géométrie. Ainsi, la présente invention vise également un programme informatique 5 comportant des instructions pour la mise en oeuvre du procédé précédemment décrit, lorsque ce programme est exécuté par un ou plusieurs processeurs. Ce programme peut utiliser n'importe quel langage de programmation (par exemple, un langage orienté objet ou autre), et être sous la forme d'un code source interprétable, d'un code partiellement compilé ou d'un code totalement compilé. 10 Les figures 6a, 6b et 6c décrites en détail ci-après, peuvent former l'organigramme de l'algorithme général d'un tel programme informatique. D'autres caractéristiques et avantages de l'invention apparaîtront encore à la lecture de la description qui va suivre. Celle-ci est purement illustrative et doit être 15 lue en regard des dessins annexés sur lesquels : - la figure la illustre un exemple de codage des coordonnées d'un point selon un codage de Morton ; - la figure lb illustre un exemple de troncation d'un codage de Morton ; - la figure 2 présente un exemple d'arbre k-d représentatif de différents points 20 d'un modèle selon un codage de Morton ; - la figure 3 représente le calcul de quadriques dans un modèle 2D permettant le calcul d'erreurs géométriques dans ce modèle ; - la figure 4 représente le calcul de quadriques dans un modèle 3D permettant le calcul d'erreurs géométriques dans ce modèle ; 25 - la figure 5 représente le calcul d'intégrales de quadriques pour le calcul de quadriques pour des noeuds internes de l'arbre k-d ; - la figure 6a présente un exemple d'ordinogramme pour la création de l'arbre k-d ; 3035990 9 - la figure 6b présente un exemple d'ordinogramme pour le calcul de quadriques pour des noeuds internes de l'arbre k-d ; - la figure 6c est un exemple d'ordinogramme pour l'identification des noeuds à conserver pour le modèle simplifié ; 5 - la figure 7 est un exemple d'arbre k-d dans lequel certains noeuds ont été sélectionnés pour être conservés dans le modèle simplifié ; - la figure 8a et la figure 8b sont des exemples de modèles simplifiés obtenus à l'aide de différents algorithmes ; - la figure 9 représente un exemple de dispositif de simplification de maillage 10 dans un mode de réalisation de l'invention. La figure la illustre un exemple de codage d'une coordonnée d'un point selon un codage de Morton. Le codage de Morton est un codage permettant de représenter avec un unique 15 entier un ensemble de coordonnées. À titre d'illustration, si un point p est associé à un ensemble de trois coordonnées (x,y,z) dans un espace E, il est possible de représenter ces coordonnées à l'aide d'un entier pm représentatif d'un code de Morton (pm est appelé « code de Morton » de p). 20 Il est supposé ici que la valeur de x s'exprime en binaire sous la forme de trois bits x1 x2 x3 (avec x1 la valeur du premier bit de x, x2 la valeur du deuxième bit de x, et x3 la valeur du troisième bit de x). De même, il est supposé que la valeur de y s'exprime en binaire sous la forme de trois bits Yi y2 y3 (avec Yi la valeur du premier bit de y, y2 la valeur du deuxième bit de y, et y3 la valeur du troisième bit de y). Enfin, il est 25 supposé que la valeur de z s'exprime en binaire sous la forme de trois bits z1 z2 z3 (avec z1 la valeur du premier bit de z, z2 la valeur du deuxième bit de z, et z3 la valeur du troisième bit de z). Dès lors, le code de Morton des coordonnées de p peut être calculé (étape 100) 3035990 10 en concaténant successivement le premier bit de x, puis le premier bit de y, le premier bit de z. La concaténation est poursuivie en prenant les deuxièmes bits de chaque coordonnée et ainsi de suite. Dans l'exemple de la figure 1 a, la valeur de pm pourra s'écrire en binaire comme étant : x1 Yi z1 x2 y2 z2 x3 y3 z3 5 Ainsi, si deux points ont un code de Morton proche (notamment sur les premiers bits), ces points seront en général proches dans l'espace E. La réciproque n'est pas nécessairement vraie. La figure lb illustre un exemple de troncations d'un codage de Morton. 10 On appelle « code de Morton tronqué d'ordre 1 » la valeur d'un code de Morton pm dont le dernier bit est supprimé / ignoré. On note cette valeur Pm-1 On appelle « code de Morton tronqué d'ordre N » (avec N un entier naturel) la valeur d'un code de Morton pm dont les N derniers bits sont supprimés / ignorés. On note cette valeur pm-N 15 Ainsi, si le code de Morton pm est xi yi z1 x2 y2 z2 x3 y3 z3 en binaire, alors Pm-1 est - Yi z1 X2 Y2 Z2 X3 y3 et Pm-2 est x1 Yi z1 X2 y2 Z2 X3 La figure 2 présente un exemple d'arbre k-d représentatif de différents points d'un modèle selon un codage de Morton. 20 Un arbre k-d (ou « kd-tree » en anglais pour « k-dimensional tree ») est arbre binaire dans lesquels chaque noeud contient un point en dimension k. Chaque noeud « non terminal » (ou encore « non-feuille » ou « interne ») divise l'espace en deux demi-espaces. Dans l'exemple de la figure 2, les noeuds « feuilles » sont les noeuds 201 à 206. 25 Ces noeuds sont associés chacun à un point du modèle dans l'espace E et à un code de Morton de ce point comme décrit précédemment. Par exemple, le point 201 possède le code de Morton « 0000 » et le noeud 204 possède le code de Morton « 0111 ». 3035990 11 Afin de faciliter le processus décrit ci-dessous, les noeuds « feuilles » sont classés par ordre croissant de gauche à droite selon leur code de Morton. Il est tout à fait possible de classer ces noeuds selon un autre ordre (ex. décroissant). Bien entendu, la précision du code de Morton peut être plus faible que la précision 5 des coordonnées du modèle. Dès lors, il est possible que deux noeuds « feuilles » soient associés au même code de Morton : dans cette hypothèse, il suffit de parcourir les noeuds « feuilles » classés et si un doublon est détecté, ces deux noeuds (consécutifs puisque les noeuds feuilles sont classés) sont alors combinés en un seul noeud. 10 On appelle « noeud parent » / « internes » un noeud de l'arbre n'étant pas un noeud feuille. Tous les noeuds parents sont internes. Par exemple, le noeud 209 est le noeud parent des deux noeuds feuilles 205 et 206 et le noeud 211 est le noeud parent du noeud parent 209. On appelle « noeud descendant d'un noeud donné » un noeud associé à un code 15 de Morton ayant comme préfixe le code de Morton du noeud donné. Ainsi, le noeud 205 est un noeud descendant du noeud 209 ou encore du noeud 211. On appelle « noeud fils d'un noeud donné » un noeud descendant dudit noeud donné et directement connecté dans l'arbre k-d. Ainsi, le noeud 205 est un noeud fils du noeud 209, mais n'est pas un noeud fils du noeud 211. 20 On appelle « noeud feuille descendant d'un noeud donné » un noeud descendant du noeud donné, ce noeud descendant étant de plus un noeud « feuille ». Un noeud « feuille » n'a pas de fils. Les noeuds parents correspondent à un code de Morton tronqué : ce code de Morton est le plus long préfixe commun aux noeuds « descendants». Ainsi, le noeud 25 « parent » 207 possède deux « descendants» 201 et 202 et correspond au code de Morton « 000 » (i.e. le code de Morton tronqué d'ordre 1 du code de Morton associé au noeud 201 ou au noeud 202). De la même manière, le noeud parent 208 possède deux descendants 203 et 204 et correspond au code de Morton « 01 » (i.e. le code de Morton tronqué d'ordre 2 du code de Morton associé au noeud 203 ou au noeud 30 204, le code de Morton tronqué d'ordre 1 du code de Morton associé au noeud 203 et 3035990 12 au noeud 204 étant différent). Le noeud « racine » 212 n'est associé à aucun code de Morton, mais représente la terminaison de l'arbre associant les deux noeuds de l'arbre n'ayant pas de parents. Afin de permettre à un algorithme de parcourir efficacement l'arbre k-d, il est 5 possible de définir pour chaque noeud de l'arbre (hors noeuds « feuilles »), les noeuds « descendants» (divisant l'espace en deux au maximum). En outre, il est possible de définir pour chaque noeud feuille i une quadrique Qi permettant de quantifier une erreur géométrique associée à ce noeud i. Pour les noeuds « feuilles », cette quadrique Qi peut être déterminée en s'inspirant de 10 l'algorithme présenté par Michael Garland et al. (1997, Surface Simplification Using Quadric Error Metrics, section 5) et de la manière décrite en relation avec la Figure 3 et 4. Essentiellement, cette quadrique donne, en tout point de l'espace, le carré de la distance à un plan (ex : plan de support d'un triangle, ou plan défini par un point et sa normale). 15 La figure 3 représente le calcul de quadriques dans un modèle 2D permettant le calcul d'erreurs géométriques dans ce modèle. Pour chaque noeud feuille i, il est possible de déterminer une quadrique Qi sous la forme d'une matrice symétrique de dimensions 4x4. 20 Par exemple, pour calculer la quadrique associée au noeud 302, on calcule les quadriques des faces du maillage ayant parmi leurs sommets le point associé au noeud 302 : dans le cas de la figure 3 (le modèle étant 2D) la quadrique de la face plane 311 (i.e. Q311) et la quadrique de la face plane 312 (i.e. Q312) sont calculées. Si une face plane est décrite par l'équation ax + by + cz + cl = 0 ou par le vecteur 25 [a,b,c,cl]T , alors la quadrique associée à cette face sera de la forme : Q = [a2 ab b2 bc cd ac ad bd cd d2 ab ac ad bc c2 cd 3035990 13 Par ailleurs, pour un point y donné de l'espace, le carré de la distance de ce point à la quadrique (ou au plan dans le cadre d'un plan) est donné par la formule : (y, 1)TQ(V, 1) = (y, 1)T [q11 q12 q13 q14 (y, 1) ,q12 q22 q32 q42 q32 q24 ,, 1/13 q33 ut 34 q14 q34 q44 (y, 1) est un vecteur de taille 4 comprenant les trois coordonnées du point y suivi du chiffre 1. Cette notation permet d'écrire le point y dans des coordonnées 5 homogènes. En outre, la somme de quadriques étant une quadrique, il est possible d'associer au noeud 302 la quadrique Q302 définie comme étant la somme des quadriques des faces du maillage ayant comme sommet au moins le point associé au noeud 302, c'est-à-dire dans cet exemple Q302 = 10 représenter par la courbe 352. Q311 ± Q312. La quadrique Q302 peut se De la même manière, il est possible d'associer au noeud 303 la quadrique Q303 définie comme étant la somme des quadriques des faces du maillage ayant comme sommet au moins le point associé au noeud 303, c'est-à-dire dans cet exemple Q303 = Q312 ± Q313. La quadrique Q303 peut se représenter par la courbe 351. 15 À supposer que les deux points 302 et 303 représentent deux points de l'arbre k-d ayant un même parent, il peut être souhaitable de calculer la quadrique associée à ce parent (i.e. -parent)- serait envisageable de calculer cette quadrique Qparent comme étant la somme des quadriques des faces ayant comme sommet un point associé à un noeud « feuille » descendant i.e. associé au noeud 302 ou au noeud 20 303, i.e. : - Qparent = Q311 ± Q312+ Q313 (si chaque quadrique est comptabilisée une seule fois dans la somme) ou - Qparent = Q311 ± 2.Q312 ± Q313 (si chaque quadrique est comptabilisée autant de fois dans la somme que le nombre de noeuds « feuilles » sommet de la 25 face associée à cette quadrique). La quadrique Qparent peut être représentée par la courbe 353. 3035990 14 Par ailleurs, pour les noeuds internes (i.e. les noeuds non « feuilles »), il est possible d'associer un point dit « représentatif » y. Ce point « représentatif » peut être, pour un noeud parent donné : - un point y de l'espace minimisant la quadrique associé (i.e. minimisant 5 (y, 1)TQ(12, 1) , Q étant la quadrique associée au noeud parent). Cela est possible en q14 q24 résolvant (y, 1) = q11 q12 q22 q32 0 q13 q14 1 0 si [q11 q12 q13 q34 est inversible [C112 (la q32 q24 O Q' = q12 q22 q32 1 q13 q33 q34 1 q13 q32 q33 0 0 1 0 0 0 matrice [q11 q12 q22 q32 0 q13 q14 étant donc fonction de la quadrique Q , les trois q12 q32 q24 q13 q33 q34 0 0 1 premières lignes étant identiques) ; 10 - si la matrice précédente n'est pas inversible, un point y de l'espace 0 0 satisfaisant (y, 1)= 0 ,pseuclo 0 avec Qpseudo une matrice carrée 4x4 pseudo- 1 inverse de la matrice Q' calculée, par exemple, à l'aide d'une décomposition en valeurs singulières ou en valeurs propres. - si la matrice Q' n'est pas inversible et/ou si un mode de réalisation le prévoit, 15 un point y de l'espace choisi comme étant une fonction des points associés aux noeuds « feuilles » descendant de ce noeud parent donné (ex. un barycentre éventuellement pondéré des points 302 et 303). En outre ce point y peut être également fonction de points voisins des points associés aux noeuds feuilles descendants de ce noeud parent donné (ex. un barycentre 20 éventuellement pondéré des points 302, 303, 301 et 304, le point 301 partageant une face avec le point 302 et le point 304 partageant une face avec le point 304). À titre d'illustration, le point « représentatif » associé au noeud parent des deux 3035990 15 noeuds descendants 302 et 303 peut être le point 321. Néanmoins, cette heuristique nécessite, pour chaque noeud parent de l'arbre k-d, de parcourir l'arbre jusqu'aux noeuds « feuilles » descendants de ce noeud parent, d'identifier les faces du maillage ayant comme sommet au moins un de ces noeuds 5 feuilles, de déterminer les quadriques associées, de calculer n sommes (n entier, n pouvant être important en fonction du nombre de quadriques déterminées), etc. Ainsi, cette heuristique peut être très complexe ( 2nbit(11. 1) opérations unitaires, nbit étant ici le nombre de bit du code de Morton le plus long) et fortement itératif dans le cas de maillage important (i.e. d'arbre k-d important). 10 De plus, pour réaliser cette heuristique, il peut être utile, pour une implémentation informatique, d'allouer dynamiquement des blocs mémoires pour la sauvegarde de chacune des quadriques des noeuds feuilles descendants avant la réalisation de la somme. L'allocation dynamique de mémoire n'est pas efficace d'un point de vue algorithmique dans un contexte parallèle. Il n'est pas possible d'allouer de manière 15 statique de la mémoire ici, car le nombre de quadriques à considérer pour le calcul de la quadrique du noeud parent n'est pas connu en avance et il n'est pas envisageable d'allouer de manière statique une mémoire correspondant au plus grand nombre de noeuds feuilles descendants possibles sous peine de saturer la mémoire. 20 Cette heuristique n'est donc pas adaptée à un calcul parallèle performant. Une heuristique améliorée est présentée en relation avec les figures 5 et 6. La figure 4 représente le calcul de quadriques dans un modèle 3D permettant le calcul d'erreurs géométriques dans ce modèle. 25 Dans le cas d'un maillage 3D 400, la description faite en relation avec la Figure 3 peut être généralisée sans difficulté. En particulier, pour un noeud 401 du maillage, il est possible de prendre en compte les quadriques associées aux faces adjacentes de ce point 401 (i.e. les faces t1, t2 et t6) : ainsi la quadrique associée au point 401 peut être Qt1+Qt2+Qt6. Pour un 3035990 16 noeud 402 du maillage, il est possible de prendre en compte les quadriques associées aux faces adjacentes de ce point 402 (i.e. les faces t1, t2, t3, t4 et t5) : ainsi la quadrique associée au point 402 peut être Qti+ Qt2±Qt3±Qt4±Qt5. Pour le noeud parent des deux noeuds 401 et 402 (à supposer que ces deux 5 noeuds feuilles aient le même parent), la quadrique Q associée peut être Qti+ Qt2±Qt3±Qt4±Qt5±Qt6ou encore 2Qti+ 2Qt2±Qt3±Qt4±Qt5±Qt6. Par ailleurs, le point « représentatif » à ce noeud parent peut être, comme précédemment, un point minimisant la quadrique Q (via une inversion ou une pseudo-inversion d'une matrice fonction de la matrice Q) ou un point fonction des 10 points 401 et 402 (ou encore fonction des points 401 à 406). La figure 5 représente le calcul d' « intégrales » de quadriques pour le calcul de quadriques pour des noeuds internes de l'arbre k-d. Comme indiqué ci-dessus, il peut être complexe et lourd de déterminer les 15 quadriques des noeuds internes à l'arbre k-d. Pour simplifier le processus de calcul de ces quadriques, une fois que les noeuds « feuilles » ont été triés selon leur code de Morton (voir Figure 2, les noeuds ayant un index i reflétant cet ordre), il est possible de suivre l'algorithme suivant : - initialiser la valeur de Qès., à 0; 20 - pour chaque noeud i pris dans l'ordre croissant ou décroissant selon le code de Morton, calculer la valeur Qis. associée à ce noeud i, Qis. étant égale à + Q. (Qi étant la quadrique associée à ce noeud, voir Figure 2). On appelle Qi9 la « quadrique intégrale » associée au noeud i. Si Qi9 1 n'est pas définie, on peut considérer que sa valeur est nulle. 25 Ces quadriques intégrales permettent de calculer de manière très simple n'importe quelle quadrique associée à un noeud interne par la simple connaissance de son noeud feuille descendant ayant le code de Morton le plus petit parmi les noeuds feuille descendant (d'index imin) et de de son noeud feuille descendant ayant le code 3035990 17 de Morton le plus grand parmi les noeuds feuille descendant (d'index imax) : en effet, la valeur de la quadrique de ce noeud interne peut être calculée comme la différence de Qismaxet de Q1. Ainsi, la valeur de la quadrique du noeud 207 est Qe _ Qès.' la valeur de la quadrique du noeud 208 est Qs4. - Qe, la valeur de la quadrique du noeud 5 211 est Q - Qs4., la valeur de la quadrique du noeud 210 est Qs4. - Qès.' etc. Cette heuristique permet de ne réaliser qu'une seule opération mathématique (i.e. différence de matrices 4x4) pour chacun des noeuds internes. Dès lors, seulement 2nbit+i _ 1 opérations mathématiques unitaires sont nécessaires au maximum (nbit étant ici le nombre de bit du code de Morton le plus long) pour calculer l'ensemble 10 des quadriques des noeuds internes. De plus, pour chaque noeud, il n'est nécessaire de n'accéder en mémoire qu'à deux noeuds descendants feuilles (i.e. celui d'index i max et celui d'index imin). Dès lors, aucune allocation dynamique de mémoire n'est nécessaire ce qui renforce l'efficacité de l'algorithme. De plus, le calcul de la quadrique associée à un noeud ne nécessite pas le calcul préalable des quadriques 15 associées à tous ses descendants : seuls les noeuds descendants feuilles dépendant de ce noeud doivent avoir leur quadrique initialisée (i.e. calculée). La figure 6a présente un exemple d'ordinogramme pour la création de l'arbre k-d. Lors de la réception des N points {p1,p2, ...,pN} du maillage (601) décrivant le 20 modèle, il est possible de convertir les coordonnées de ces points en code de Morton comme décrit en relation avec la Figure la (étape 602). Une fois un code de Morton associé à chacun de ces points, il est possible d'ordonner ces points (ou noeuds feuilles) en fonction de ce code de Morton associé comme décrit en relation avec la Figure 2 (étape 603). 25 Si deux noeuds feuilles possèdent deux codes de Morton identiques (du fait de la résolution finie utilisée pour le code de Morton), il est possible de dédupliquer ces noeuds en les combinant en un seul noeud feuille (étape 604). Ensuite, il est possible de créer un arbre k-d (606) sur la base des noeuds feuilles ordonnés comme cela est décrit en relation avec la Figure 2 (étape 605). Il est tout à 3035990 18 fait possible de remplacer l'arbre k-d par un arbre de type « octree » (un arbre pouvant avoir jusqu'à 8 fils). La figure 6b présente un exemple d'ordinogramme pour le calcul de quadriques 5 pour des noeuds internes de l'arbre k-d. Une fois l'arbre k-d déterminé, il est possible d'associer (étape 607) à chaque noeud feuille i de l'arbre (i étant un indice du noeud feuille dans l'ordre de Morton) : - p: les coordonnées des points correspondant au code de Morton associé ; - Q: une quadrique Qi calculée comme décrit en relation avec la figure 3 ou 4; 10 - Q5: une quadrique intégrale Qis calculée comme décrit en relation avec la figure 5 (i.e. Q = Q. + Pour des raisons d'efficacité algorithmique, il est possible de stocker les valeurs de la quadratique intégrale dans un tableau pour lequel chaque valeur de Qis est accessible grâce à l'index i. En effet, les valeurs de la quadratique intégrale peuvent 15 être régulièrement accédées (voir ci-dessous). En outre, il est possible d'associer (étape 608) à chaque noeud interne j de l'arbre 606: - ini : un index d'un noeud feuille descendant ayant le plus petit index. Cette valeur peut être simplement calculée comme étant la valeur minimale entre 20 les valeurs mi des noeuds fils du noeud interne courant si ces noeuds fils sont également des noeuds internes ; - las : un index d'un noeud feuille descendant ayant le plus grand index. Cette valeur peut être simplement calculée comme étant la valeur maximale entre les valeurs las des noeuds fils du noeud interne courant si ces noeuds fils 25 sont également des noeuds internes ; - Q: une quadrique Qi calculée comme une fonction de la différence : - entre la quadrique intégrale Qism_1, 3035990 19 - et la quadrique intégrale 0 : ?as - p : les coordonnées d'un point minimisant ladite quadrique Qi (si le calcul est possible) ; - w: le nombre de noeuds feuilles descendants dépendant du noeud interne 5 courant. On appelle également ce nombre « poids ». Cette valeur peut être simplement calculée comme étant la somme des valeurs w des noeuds fils du noeud interne courant si ces noeuds fils sont également des noeuds internes ou comme las - mi + 1 ; - : les coordonnées d'un point « moyen » représentant un barycentre des 10 points p des noeuds feuilles descendants dépendant de ce noeud interne. Il est possible de calculer efficacement ce point moyen en calculant un barycentre des points « moyens » p pondérés par des nombres w pour les noeuds fils du noeud interne courant (ex. en référence à la figure 5, 15 210 = W207 _L W208 P207 m 1:5208). Si les noeuds fils du noeud interne courant W207 +w208 "207 W208 15 sont des noeuds feuilles, leur nombre w peut être considéré comme étant 1 et leur point moyen associé peut être considéré comme étant le point p (ex. en référence à la figure 5, P208 = P203 + -2 P204 ). Les noeuds de l'arbre k-d 609 sont ainsi enrichis d'informations complémentaires. 20 La figure 6c est un exemple d'ordinogramme pour l'identification des noeuds à conserver pour le modèle simplifié. Si une valeur d'erreur e (610) est indiquée, il est possible d'initialiser (étape 611) l'algorithme d'identification des noeuds à conserver pour le modèle simplifié. Pour ce faire, il est possible de lancer N processus de calculs en parallèle (N étant 25 le nombre de noeuds feuilles de l'arbre k-d), chaque processus i de calculs en parallèle étant associé à un noeud feuille pi (6121, ... 612, ..., 612N). Ces processus de calculs en parallèle vont parcourir l'arbre du noeud racine jusqu'au noeud associé {pi} à moins d'être « terminés » avant d'y arriver (voir ci- 3035990 20 dessous). Par exemple, si un processus est associé au noeud 202 de la Figure 2, ce processus parcourra les noeuds 212, 210, 207, et 202. Si un processus est associé au noeud 204 de la Figure 2, ce processus parcourra les noeuds 212, 210, 208, et 204. 5 Bien entendu, dans ce mode de réalisation, certains processus parcourront les mêmes noeuds, mais il a été constaté que d'essayer de limiter ce multiple parcours peut être défavorable, dans de multiples situations, pour l'efficacité algorithmique du processus global. Pour chaque processus de calculs en parallèle, le processus est positionné sur le 10 noeud racine de l'arbre k-d 609 (il est rappelé que ce noeud n'est pas associé à un code de Morton), puis remonte d'un noeud en direction du noeud feuille associé au processus. Le noeud sur lequel le processus est positionné est appelé « noeud courant du processus ». Pour le noeud courant du processus, il est déterminé une valeur d'erreure' (étape 15 613). Cette valeur d'erreur e' est calculée comme étant e' = 1)Q(p, 1)T si un point p est défini pour ce noeud (voir ci-dessous la description en relation avec la figure 6b) ou comme étant e' = (15, 1)Q(15, 1)T si le point p n'est pas défini pour ce noeud (ex. la résolution permettant de calculer p n'est pas possible) ou si un mode de réalisation le prévoit. Bien entendu, le calcul de e' peut avoir été effectué en amont lors du 20 processus décrit en relation avec la figure 6b. Si la valeur d'erreur déterminée e' est supérieure à la valeur d'erreur indiquée e (test 614, sortie OK), cela signifie que le point p ou /5 n'est pas acceptable pour effectuer une simplification du maillage : dès lors, le processus se déplace d'un noeud en direction du noeud feuille associé à l'processus (étape 615). 25 Sinon (test 614, sortie KO), le noeud est sélectionné / marqué comme étant acceptable pour effectuer une simplification du maillage et le processus est « terminé » (étape 616). Si le processus arrive jusqu'à un noeud feuille, il n'est pas nécessaire de calculer E' puisque, sous cette hypothèse, ce noeud feuille est alors sélectionné / marqué 30 comme étant acceptable pour effectuer une simplification du maillage. 3035990 21 La figure 7 est un exemple d'arbre k-d dans lequel certains noeuds ont été sélectionnés pour être conservés dans le modèle simplifié. Dans cet exemple, et après l'exécution du processus décrit en figure 6, les noeuds 5 207, 203, 204 et 211 ont été sélectionnés / marqués comme étant acceptables pour effectuer une simplification du maillage. Si une maille du modèle initial était décrite par les points associés (p) aux noeuds 202, 203 et 204, la nouvelle maille est alors décrite par les points associés (13 ou 15 ou p) aux noeuds 207, 203 et 204. De manière générale, la nouvelle maille est décrite 10 par les noeuds parents sélectionnés qui ont au moins un noeud feuille descendant décrivant la maille initiale. Si une maille du modèle initial était décrite par les points associés (p) aux noeuds 201, 202 et 203, on dit que la maille est dégénérée : n'étant plus décrite que par deux points (i.e. associés aux noeuds 207 et 203), cette maille est supprimée du 15 modèle. Cela peut arriver lorsque deux (ou plus) noeuds feuilles décrivant une même maille sont les noeuds feuilles descendants d'un même noeud parent sélectionné / marqué. Il peut arriver de plus que certaines mailles se « retournent » lors de la simplification. Dès lors, il est possible de vérifier ce retournement en comparant la 20 moyenne des vecteurs normaux des mailles initiales (i.e. celles qui seront remplacées) au vecteur normal de la nouvelle maille : si la direction du vecteur normal change notablement, il est possible d' « inverser » la maille finale pour assurer la cohérence du modèle. 25 La figure 8a et la figure 8b sont des exemples de modèles simplifiés obtenus à l'aide de différents algorithmes. À titre d'illustration, il a été testé différents algorithmes sur le modèle maillé 801 comportant 28 millions de mailles afin d'obtenir un modèle maillé simplifié possédant environ 116 milles mailles. 3035990 22 Le maillage 802 est un exemple de simplification effectuée avec un algorithme basé sur un partitionnement uniforme (grille) selon la méthode proposée par Decoro et Tatarchuk (Real-time mesh simplification using the gpu, 2007) en 121 ms. Le maillage 803 est un exemple de simplification effectuée avec l'algorithme 5 présenté ci-dessus en 222 ms. Le maillage 804 est un exemple de simplification effectuée avec un algorithme basé sur la méthode proposée par Michael Garland et al. (1997, Surface Simplification Using Quadric Error Metrics) en 234985 ms. On constate que la qualité de la simplification proposée par Garland est meilleure, 10 mais que celle-ci n'est pas adaptée aux contraintes temps réels (simplification plus de 1000 fois plus lente que la simplification proposée ci-dessus). Si la simplification proposée par Decoro et Tatarchuk est plus rapide, la qualité de la simplification est également plus basse. 15 Il a également été testé différents algorithmes sur le modèle maillé 811 comportant 770 mille mailles afin d'obtenir un modèle maillé simplifié possédant environ 18 mille mailles. Le maillage 812 est un exemple de simplification effectuée avec un algorithme basé sur un partitionnement uniforme (en grille) selon la méthode proposée par 20 Decoro et Tatarchuk en 8 ms. Le maillage 813 est un exemple de simplification effectuée avec l'algorithme présenté ci-dessus en 18 ms. Le maillage 814 est un exemple de simplification effectuée avec un algorithme basé sur la méthode proposée par Michael Garland et al. (1997, Surface 25 Simplification Using Quadric Error Metrics) en 7544 ms. La figure 9 représente un exemple de dispositif de simplification de maillage dans un mode de réalisation de l'invention. 3035990 23 Dans ce mode de réalisation, le dispositif comporte un ordinateur 900, comprenant une mémoire 905 pour stocker des instructions permettant la mise en oeuvre du procédé, les données de mesures reçues, et des données temporaires pour réaliser les différentes étapes du procédé tel que décrit précédemment. 5 L'ordinateur comporte en outre un circuit 904. Ce circuit peut être, par exemple : - un ou plusieurs processeurs apte à interpréter des instructions sous la forme de programme informatique, ou - une carte électronique dont les étapes du procédé de l'invention sont décrites dans le silicium, ou encore 10 - une puce électronique programmable comme une puce FPGA (pour « Field- Programmable Gate Array » en anglais). Cet ordinateur comporte une interface d'entrée 903 pour la réception des points du maillage, et une interface de sortie 906 pour la fourniture du maillage simplifié à un ordinateur distant par exemple 907. Enfin, l'ordinateur peut comporter, pour 15 permettre une interaction aisée avec un utilisateur, un écran 901 et un clavier 902. Bien entendu, le clavier est facultatif, notamment dans le cadre d'un ordinateur ayant la forme d'une tablette tactile, par exemple. Par ailleurs, le schéma fonctionnel présenté sur la figure 6 est un exemple typique 20 d'un programme dont certaines instructions peuvent être réalisées auprès de dispositif décrit. À ce titre, la figure 6 peut correspondre à l'organigramme de l'algorithme général d'un programme informatique au sens de l'invention. Bien entendu, la présente invention ne se limite pas aux formes de réalisation 25 décrites ci-avant à titre d'exemple ; elle s'étend à d'autres variantes. D'autres réalisations sont possibles. Par exemple, il est possible, pour le calcul de l'erreur e' basé sur la quadrique associée au noeud, de prendre en compte également : 3035990 24 - une couleur associée au noeud et/ou - la valeur d'une normale associée au noeud. Pour ce faire, lors du processus décris en Figure 6b (étape 607), il est possible de déterminer, pour chaque noeud feuille i, la couleur moyenne Col, des couleurs des 5 mailles adjacentes au point associé à ce noeud feuille, cette couleur moyenne étant déterminée en pondérant les couleurs des mailles par la surface de ces mailles. Il est également possible de calculer des couleurs moyennes intégrales Col de la même manière que sont calculées les quadriques intégrales en relation avec la Figure 5. 10 La somme des surfaces des mailles adjacentes au point associé à ce noeud feuille est notée A. Il est également possible de calculer des surfaces intégrales A,s, de la même manière que sont calculées les quadriques intégrales en relation avec la Figure 5. Les valeurs de Colt et de Ais. sont associées au noeud feuille i. 15 Par ailleurs, pour chaque noeud interne j de l'arbre k-d, il est possible de déterminer une valeur de couleur Coli comme étant : Coli -- As las ri1 Lors du calcul de l'erreur e' de l'étape 613 de la Figure 6c, cette erreur peut être également fonction de 8Ci = Col - Ci avec Ci la couleur moyenne des couleurs des mailles adjacentes au point associé à ce noeud dans le maillage simplifié pondéré 20 par la somme des surfaces de ces mailles adjacentes. Il est également possible de /Sias 2 S 2 calculer 8Ci comme étant 8Ci = °L s La valeur de e' peut être une ALs-Aini-1 - somme pondérée de l'erreur géométrique (présentée ci-dessus) et de la valeur de 8Ci. La prise en compte de 8Ci permet une meilleure prise en compte de la couleur et ainsi d'éviter de supprimer des mailles dans des zones possédant une forte variation 25 de couleurs. C o isas - Col iSn _ 3035990 25 Pour la prise en compte d'une normale (vecteur indiquant l'orientation du plan tangent à la surface au point, qui peut être issu d'un processus de capture/calcul/modélisation différent de celui ayant abouti à la position du point, et donner une information plus précise sur la géométrie), il est également possible 5 d'associer à chaque noeud feuille une deuxième quadrique représentative d'une normale au point associé à ce noeud feuille. Dès lors, différents calculs sont effectués dans le processus proposé en Figure 6 de manière similaire à la quadrique évoquée précédemment et représentant les surfaces. La valeur de e' peut être une somme pondérée de l'erreur géométrique (présentée ci-dessus) et/ou de la valeur de 10 8Ci et/ou de l'erreur sur la normale (calculée avec la deuxième quadrique représentative de la normale). La prise en compte des normales permet une meilleure préservation des détails du modèle et ainsi d'éviter de supprimer des mailles dans des zones possédant de forts détails (ex. une chevelure) mais de faibles amplitudes géométriques. 15 Un arbre k-d n'est qu'une représentation simple des points du maillage (accès simplifié en fonction des codes de Morton associé, parcours optimisé, facilité d'implémentation informatique, etc.). Dès lors, il est tout à fait possible de ne pas utiliser d'arbre de ce type pour la réalisation de l'invention : une approche plus globale est possible comme cela est décrit ci-dessus. 20 REVENDICATIONS1. Procédé de simplification d'un modèle de géométrie, le procédé comprend : /a/ réception dudit modèle de géométrie (601) comprenant une pluralité de points (p,), chaque point de la pluralité étant associé à une mesure d'erreur (Q); /b/ pour chaque point courant (pi) dudit modèle de géométrie, - détermination (602) d'un code de Morton associé au point courant (pi) en fonction de coordonnées (Q,) dudit point courant ; - détermination (607) d'une mesure d'erreur intégrale ( Qi9) définie comme étant fonction d'une somme des mesures d'erreur associées aux points de la pluralité ayant un code de Morton associé inférieur au code de Morton associé au point courant ; /c/ détermination (614) si un ensemble donné de points de la pluralité peut être simplifié par un nouveau point, les points de l'ensemble donné étant tous les points de la pluralité ayant un code de Morton associé avec un même préfixe de longueur donné, en fonction au moins d'une différence entre : - la mesure d'erreur intégrale ( eas ) déterminée pour le point de l'ensemble donné ayant le code de Morton le plus grand (las); et - la mesure d'erreur intégrale (Q,_1) déterminée pour le point de la pluralité ayant un code de Morton immédiatement inférieur (mi-1) au code de Morton le plus petit parmi les codes de Morton associés aux points de l'ensemble. 2. Procédé selon la revendication 1, dans lequel la mesure d'erreur (Q,) associée à un point courant (pi) de la pluralité est fonction d'une quadrique représentative de mailles du modèle dont au moins un des sommets est ledit point courant ou est à une distance inférieure à une distance prédéterminée dudit point courant. 3035990 27 3. Procédé selon l'une des revendications précédentes, dans lequel la mesure d'erreur (Q,) associée à un point courant (pi) de la pluralité est fonction de couleur de 5 mailles du modèle dont au moins un des sommets est ledit point courant. 4. Procédé selon l'une des revendications précédentes, dans lequel la mesure d'erreur (Q,) associée à un point courant (pi) de la pluralité est fonction d'une quadrique représentative d'un vecteur normal associé audit point courant. 10 5. Procédé selon l'une des revendications précédentes, dans lequel le procédé comprend en outre : - si un premier point de la pluralité est associé à un code de Morton identique à un deuxième point de la pluralité, suppression (604) de la pluralité de 15 points ledit deuxième point. 6. Procédé selon l'une des revendications précédentes, dans lequel ledit nouveau point est fonction (15) des points de l'ensemble. 20 7. Procédé selon l'une des revendications précédentes, dans lequel ledit nouveau point est déterminé (p) par une minimisation d'une valeur fonction de ladite différence. 8. Procédé selon l'une des revendications précédentes, dans lequel le procédé 25 comprend en outre : - détermination (605) d'un arbre k-d sur la base d'un codage de Morton, ledit arbre ayant comme feuilles (201, 202, 203, 204, 205, 206) ladite pluralité de 3035990 28 points. 9. Procédé selon la revendication 8, dans lequel, ledit arbre k-d possédant des noeuds internes (207, 208, 209, 210, 211), chaque noeud interne (207, 208, 209, 210, 5 211)est associé à un point (p), et dans lequel la détermination de l'étape /c/ est également fonction dudit point et d'une transposée dudit point. 10. Procédé selon l'une des revendications précédentes, dans lequel la mesure 10 d'erreur intégrale (Qi9) pour chaque point courant est calculée comme étant fonction d'une somme : - de la mesure d'erreur intégrale (Qi91) d'un point ayant un code de Morton immédiatement plus petit que le code de Morton du point courant ; - de la mesure d'erreur dudit point courant (Q,). 15 11. Dispositif de simplification d'un modèle de géométrie, le dispositif comprend : /a/ une interface (903) pour une réception dudit modèle de géométrie comprenant une pluralité de points, chaque point de la pluralité étant associé à une mesure d'erreur ; 20 /b/ un circuit (904) adapté pour, pour chaque point courant dudit modèle de géométrie : - une détermination d'un code de Morton associé au point courant en fonction de coordonnées dudit point courant ; - une détermination d'une mesure d'erreur intégrale définie comme 25 étant fonction d'une somme des mesures d'erreur associées aux points de la pluralité ayant un code de Morton associé inférieur au code de Morton associé au point courant ; 3035990 29 Ici un circuit (904) adapté pour une détermination si un ensemble donné de points de la pluralité peut être simplifié par un nouveau point, les points de l'ensemble donné étant tous les points de la pluralité ayant un code de Morton associé avec un même préfixe de longueur donné, en fonction au 5 moins d'une différence entre : - la mesure d'erreur intégrale déterminée pour le point de l'ensemble donné ayant le code de Morton le plus grand ; et - la mesure d'erreur intégrale déterminée pour le point de la pluralité ayant un code de Morton immédiatement inférieur au code de Morton 10 le plus petit parmi les codes de Morton associés aux points de l'ensemble. 12. Produit programme informatique comportant des instructions pour la mise en oeuvre du procédé selon l'une des revendications 1 à 10, lorsque ce programme est 15 exécuté par un ou plusieurs processeurs.