Procédé et système de simplification d'un maillage d'une scène en trois dimensions

La présente invention concerne le domaine de la modélisation d'un objet à trois dimensions ou d'une scène comprenant une pluralité d'objets en un modèle graphique dont la représentation peut être mise en œuvre par un programme d'ordinateur.

Plus particulièrement la présente invention a pour objet un procédé de simplification d'un maillage d'une scène en trois dimensions comprenant une pluralité d'objets.

Un modèle graphique est une représentation structurée d'un objet ou d'une scène par une pluralité de polygones définis par des vertex/sommets reliés par des arêtes de façon à constituer un maillage.

Afin de fournir un niveau de réalisme graphique satisfaisant pour un utilisateur lors du rendu de la scène, il est souhaitable de pouvoir manipuler des modèles complexes présentant un grand nombre de polygones pouvant dans certaines applications atteindre plusieurs centaines ou milliers de millions.

Cependant, le temps de calcul de rendu nécessaire et le besoin en ressources machines, et en particulier en mémoire limitent la complexité d'un modèle pouvant être pris en charge par un système informatique de configuration donnée.

Il est ainsi souhaitable dans certaines applications de simplifier le modèle de manière à limiter le temps de calcul de rendu et à économiser les ressources machines, en particulier la mémoire vive.

A cet effet, il est connu d'utiliser un procédé de simplification par effondrement d'arêtes. Ce procédé consiste en un ensemble d'étapes élémentaires visant à supprimer une arête du maillage en remplaçant deux ve rtex/som m ets d i sposés a ux extré m ités d e l ' a rête pa r u n u n ique vertex/sommet positionné de façon à limiter un coefficient d'erreur.

En particulier, le coefficient d'erreur peut être une mesured'erreur quadratique (Quadric Distance Error) basée sur le calcul d'une distanceentre la position du nouveau vertex/sommet et les plans des polygones auxquels participaient les vertex/sommets de l'arête supprimée. Ce procédé est satisfaisant en ce qu'il produit rapidement une approximation de haute qualité de l'ensemble des objets d'une scène en trois dimensions.

Cependant, ce procédé est prohibé pour des maillages complexes de plusieurs millions de polygones car il nécessite un espace de stockage trop important pour les coefficients d'erreur et pour les données géométriques associées au maillage modifié.

Une première solution à ce problème à été donnée par H. Hoppe dans sa publication intitulée « New quadric metric for simplifying meshes with appearance attributes ».

Cette solution consiste à ne pas stocker les coefficients d'erreur mais à les calculer au vol à chaque étape.

Cependant, cette solution augmente considérablement le temps de traitement pour définir le nouveau maillage simplifié de l'ensemble des objets de la scène. Par ailleurs, il est nécessaire lors de la mise en œuvre de procédé par ordinateur, de charger l'intégralité de la scène en mémoire. Ceci rend cette technique difficilement exploitable dans le cas de très grandes scènes.

La présente invention a pour but de résoudre tout ou partie des inconvénients mentionnés ci-dessus.

A cet effet, la présente invention a pour objet un procédé de simplification d'un maillage d'une scène en trois dimensions comprenant une pluralité d'objets en fonction d'un critère de simplification global à appliquer, chaque objet étant modélisé par un premier ensemble de polygones formés par des arêtes, ledit procédé comportant les étapes suivantes :

a) sélectionner un objet parmi la pluralité d'objets de la scène, b) réaliser un premier ensemble d'étapes de simplification sur le premier ensemble de polygones correspondant à l'objet sélectionné, les étapes de simplification étant des étapes de mod ifications géométriques dont l'ordonnancement est déduit d'une métrique d'erreur définissant un degré d'erreur,

c) stocker à chaque étape de simplification des données de simplification comprenant :

- une valeur de degré d'erreur associée à cette étape,

- un nombre de polygones supprimés lors de cette étape, d) réitérer les étapes a) à c) pour l'ensemble des objets de la scène, e) réal iser u n reg rou pement des don nées de simplification correspondant à l'ensemble des objets de la scène,

f) réaliser une sélection de données de simplification dans le regroupement des données de simplification, ladite sélection étant réalisée par valeur de degré d'erreur croissant jusqu'à respecter le critère de simplification global à appliquer,

g) définir pour chaque objet un critère de simplification spécifique en fonction d'une sous-sélection de données de simplification correspondant à l'objet considéré parmi la sélection de données de simplification,

h) sélectionner un objet parmi la pluralité d'objets de la scène, i) réaliser un deuxième ensemble d'étapes de simplification sur le premier ensemble de polygones correspondant à l'objet sélectionné jusqu'à respecter le critère de simplification spécifique de l'objet considéré, de façon à obtenir un second ensemble de polygones.

j) réitérer les étapes h) à i) pour l'ensemble des objets de la scène.

Grâce aux dispositions selon l'invention, dans le premier ensemble d'étapes a à d, des données de simplification sont collectées, puis analysées dans les étapes e et f de façon à appliquer une simplification adaptée à chaque objet dans les étapes g à i.

II est par exemple possible de simplifier de façon plus importante un petit objet plutôt qu'un objet plus grand pour un nombre de polygones sensiblement identique entre les deux objets, le degré d'erreur étant faible dans le cas de petits objets et étant grand dans le cas de grands objets.

Ainsi, à titre d'exemple, la simplification à 10% d'une scène composée de 2 objets ayant le même nombre de polygones peut donner lieu à une simplification à 15% de l'objet A et une simplification à 5% de l'objet B ; soit une simplification globale de 10% tel que demandé au départ. Cette liberté dans le choix du ratio de simplification de chaque objet permet d'obtenir des maillages de qualité supérieure à ce qui pourrait être obtenu par un processus de simplification trivial au cours duquel chaque objet serait simplifié à un ratio fixe de 10%.

L a s i m p l if i cat i o n d u m a i l l a g e d e l a s cène est réalisée individuellement pour chaque objet aux étapes a à d et g et i, ce qui permet de limiter les besoins en ressource mémoire du procédé car un seul objet doit être chargé en mémoire. Ainsi, un fonctionnement hors cœur (« out-of-core ») est permis, dans lequel les données sont partiellement chargées en mémoire vive. Il est à noter que les données de simplification qui sont stockées pour l'ensemble de la scène représentent une très faible taille mémoire.

I l est à noter q ue par obj et on peut égal ement entendre un regroupement de plusieurs objets élémentaires.

Selon une mise en œuvre du procédé, le degré d'erreur est mis à jour à l'issu de chaque étape de simplification du premier ensemble d'étapes de simplification pour les étapes restantes, de sorte que l'accomplissement de l'ensemble des étapes s'effectue selon un ordre croissant du degré d'erreur.

Selon une mise en œuvre du procédé, le critère de simplification global correspond à une valeur du nombre total de polygones à conserver ou à supprimer par le procédé de simplification du maillage de la scène en trois dimensions.

Selon une autre m ise en œuvre d u procédé, le critère de simplification global correspond à une valeur maximale d'erreur correspondant à une somme des erreurs des étapes de simplification sur la scène.

Selon une autre mise en œuvre du procédé, un critère d'espace disque à occuper peut être utilisé.

Selon une mise en œuvre du procédé, le critère de simplification spécifique correspond à une valeur du nombre total de polygones à conserver ou à supprimer par objet.

Selon une mise en œuvre du procédé, l'étape e) de réalisation d'un regroupement comprend une sous-étape consistant à réaliser un arrangement des étapes de simplification d'arêtes par valeur de degré d'erreur croissant.

Selon une mise en œuvre du procédé, l'arrangement des étapes de simplification par valeur de degré d'erreur croissant est également réalisé de man ière à ordon ner par valeur décroissante le nombre de polygones supprimés lors d'une étape de simplification lorsqu'une même valeur de degré d'erreur est associée à deux étapes de simplification différentes.

Selon une première possibilité de mise en œuvre du procédé, les étapes de simplifications réalisées sont des étapes d'effondrement d'arêtesdes polygones du premier ensemble de polygones formant les objets.

La technique d'effondrement d'arêtes est une technique performante de simplification itérative de la géométrie d'un objet.

Selon une mise en œuvre du procédé, la position d'un nouveau vertex/sommet d'un polygone du deuxième ensemble de polygones issu de l'effondrement d'une arête reliant deux vertex du premier ensemble de polygones est déterminé en minimisant la valeur de degré d'erreur.

Selon une m ise en œuvre d u procédé, la position du nouveau vertex/sommet est choisie de manière à minimiser la distance entre le nouveau vertex/sommet et des plans passant par chacun des deux vertex/sommets reliés par l'arrête supprimée au cours d'une étape d'effondrement d'arête.

Selon une autre possibilité de mise en œuvre, les étapes de simplification sont des étapes d'effondrement de sommets, qui consistent à supprimer itérativement un sommet du maillage et tous les triangles qui l'entourent, puis à boucher le trou ainsi formé avec de nouveaux triangles.

Selon d'autres possibilités, d'autres types d'étapes de simplification peuvent être utilisés, c'est-à-dire des étapes de modifications géométriques dont l'ordonnancement est déduit d'une métrique d'erreur définissant un degré d'erreur, cette métrique d'erreur donnant le même résultat d'ordonnancement des modifications géométriques sur un objet si cet objet est considéré seul ou au sein d'une pluralité d'objets.

La p résen te i nve nt io n a ég a l e m e n t pou r o bj et u n produit programme d'ordinateur destiné à mettre en œuvre un procède de simplification tel que décrit précédemment.

La présente i nvention a également pou r obj et u n support de données comprenant les instructions dudit produit programme d'ordinateur.

La présente invention a également pour objet un tel produit programme d'ordinateur instal lé sur des moyens d 'acq u isitions et/ou de traitement d'une scène en trois dimensions.

De toute façon, l'invention sera bien comprise à l'aide de la description qui suit, en référence au dessin schématique annexé représentant, à titre d'exemple non limitatif, les étapes d'un procédé selon l'invention.

La figure 1 illustre les étapes d'un procédé selon l'invention.

La figure 2 illustre une étape du procédé selon l'invention. La figure 3 illustre une autre étape du procédé selon l'invention.

La figu re 4 il lustre encore une autre étape du procédé selon l'invention.

La figure 5 représente une scène comprenant trois objets. La figure 6 est une première représentation d'un objet avant simplification. La figure 7 est une deuxième représentation de l'objet de la figure 6 après simplification.

Comme illustré à la figure 1 , le procédé de simplification selon l'invention comporte une succession d'étapes.

Ces étapes sont m ises en œuvre par u n produ it programme d'ordinateur faisant également l'objet de la présente invention.

La présente invention a également pour objet un tel produit programme d'ordinateur installé sur des moyens d'acquisitions et/ou de traitement d'une scène S en trois dimensions.

Le procédé a pour objet la simpl ification d'un maillage d'une scène S en trois dimensions comprenant une pluralité d'objets Ci, i Θ [0..n].

Cette simplification est réalisée en fonction d'un critère de simplification global CR à appliquer, par exemple en fonction d'une information fournie par un utilisateur, ou par un calcul sur l'espace mémoire que l'on souhaite allouer au stockage de la géométrie.

A titre d'exemple, ce critère de simplification global CR correspond à un nombre total de triangles à conserver ou à supprimer dans le maillage de la scène S en trois dimensions. De toute façon, que ce soit un nombre total de triangles à conserver ou à supprimer, le critère de simplification choisi permet facilement de déterminer une valeur pour l'autre critère.

Selon une variante, il est possible d'envisager un critère de simplification global CR correspondant à un seuil de degré d'erreur décrit ci- après.

Da n s l ' exe m p l e p rése n té , l es éta pes d e s i m p l ifi cat i on correspondent à des étapes d'effondrement EFF d'une arête e.

La figure 5 montre une représentation de ces objets Ci en deux dimensions de manière à simplifier la compréhension de l'invention.

Comme représenté sur cette figure 5, chaque objet Ci de la scène S est respectivement modél isé par un premier ensemble E1 Ci de polygones p, par exemple des triangles, présentant chacun un ensemble de vertex/sommets V reliés par des arêtes e.

Initialement, chaque vertex/sommet V commun à plusieurs polygones p est contenu à l'intérieur des plans des polygones p entourant ce vertex V dans un espace à trois dimensions.

Les différentes étapes du procédé vont maintenant être explicitées en référence à la figure 1 . Dans une première étape a) du procédé, on choisit tout d'abord un objet Ci parmi la pluralité d'objets de la scène S.

Dans une deuxième étape b) du procédé, on réalise pour l'objet Ci sélectionné, une simpl ification complète en réalisant successivement une pluralité d'étapes d'effondrement EFF des arêtes e appartenant à l'objet Ci.

Ainsi cette étape b) conduit à réaliser un premier ensemble EFFI Ci d'étapes d'effondrement EFF des arêtes e sur le premier ensemble E1 Ci de polygones p correspondant à l'objet Ci.

Le résultat d'une étape de simpl ification par effondrement EFF d'une arrête e est illustrée à titre d'exemple par les figures 6 et 7 pour un objet à deux dimensions.

Chaque étape d'effondrement EFF d'arête e correspond à la suppression d'une arête e sélectionnée en fusionnant les vertex/sommets V0, V1 définissant ladite arête e en un unique vertex/sommet V1 '. La définition de la position d'un nouveau vertex/sommet V1 'lors d'un effondrement EFF d'une arête e est réalisée de la façon suivante.

On exprime la d istance d'un point x à u n plan comprenant u n polygone p par la formule :

d _p (x) = x ^T . r + o _p

où le vecteur r désigne le vecteur normal au plan contenant le polygone p et :

Op = —V . n _p

où V est l'un des sommets du polygone p.

Selon un mode de mise en œuvre du procédé, une erreur quadratique associée à un vertex V de l'objet C\K _v (x) est définie pour tout point x par :

K _v (x) Da ns l 'éq uation ci-dessu s, N (V) représente l 'ensem bl e des polygones de l'objet Ci partageant le vertex/sommet V. Les ë\ëmenis(A _v , B _v , CV)sont les coefficients d'erreur associés au sommet V:

- ^est une matrice de dimension (3, 3),

-B^est un vecteurde dimension 3, et

-C _v est un scalaire. Le nouveau vertex/sommet Vf d'une arête e est déterminé comme étant le point x _op t associé au degré d'erreur K _e minimal défini par:

K _E = min K _V (x) + K _V (x)

X ^{u 1} Plus cette valeur K _e sera élevée et plus le/les triangle(s) supprimé(s) à l'étape d'effondrement EFF d'arête e a/ont de l'importance pour le rendu visuel de l'image.

A contrario, plus cette valeur sera faible et plus le/les triangle(s) supprimé(s) à l'étape d'effondrement EFF d'arête e est/sont insignifiant pour le rendu visuel de l'image.

Il conviendra donc comme cela est expliqué ci-après d'appliquer une étape d'effondrement EFF à l'arête e dont la valeur de degré d'erreur K _e est minimale.

Ainsi, la réalisation d'un effondrement complet du maillage d'un l'objet consiste à réaliser des effondrements successifs de l'ensemble des arêtes dudit objet jusqu'à suppression de l'intégralité de ses polygones.

On calcule initialement la valeur du degré d'erreur K _e correspondant pour chaque arête e de l'objet.

Puis, on réalise les itérations ou étapes individuelles EFF suivante : i -on sélectionne une arête e dont l'effondrement et le repositionnement par un nouveau vertex correspond au plus faible degré d'erreur Ke ;

ii - on procède à l'effondrement de l'arête e sélectionnée ; iii - suite à cet effondrement, la géométrie du modèle est mise à jour, ainsi que les valeurs de degré d'erreur Ke pour les arêtes restantes du modèle modifié. En particulier, après avoir effondré une arête e, il est nécessaire de mettre à jour les coefficients d'erreur associés au nouveau vertex x _op t avec:

(^ _opt ' ^B x _op t> ^c x _op t) ⁼ ( ^A v ₀ > ^B v ₀ > ^c v ₀ ) + (A _VL , B _VI , C _V

Ces itérations sont arrêtées lorsque l'ensemble des arêtes e de l'objet Ci ont été effondrées ou lorsqu'un nombre minimal prédéfini d'effondrements a été atteint.

Lors d'une troisième étape c) du procédé, on stocke au cours de chaque étape d'effondrement EFF, d'arête e, des données de simplification Ti.

Ces données d'effondrement Ti comprennent : - la valeur du degré d'erreur K _e de la position du nouveau vertex/sommet Vrpour l'arête e sélectionnée de l'objet Ci considéré, et

- un nombre N de polygones p supprimés lors de l'effondrement de l'arête e sélectionnée de l'objet Ci considéré.

La présente invention a également pour objet une telle structure de données Ti.

Dans l'exemple présenté aux figures 6 et 7, l'objet comprend notamment les polygones p1 , ... , p8 avant simplification et ne comprend plus que les polygones p1 , p2, p4, p5, p6 et p8 après simplification, les polygones p3 et p7 ayant été supprimés lors de cette simplification par effondrement EFF de l'arête e joignant les vertex sommet/sommets V ₀ et Vi .

Pour cet exemple, le nombre N de polygones supprimés lors d'une étape d'effondrement est donc égal à 2.

Dans une quatrième étape d) du procédé, les étapes a), b) et c) précédentes du procédé sont réitérées jusqu'à ce que l'ensemble des objets Ci de la scène S ait été sélectionné à la première étape a).

Dans une cinqu ième étape e) du procédé, les données de simplification Ti contenant les d'étapes d'effondrement EFF relatives aux premiers ensembles E1 Ci de polygones correspondant à chacun des objets Ci de la scène S sont regroupées dans un regroupement REFF.

Selon une variante, ce regroupement REFF peut consister en un arrangement A de l'ensemble des étapes d'effondrement EFF d'arêtes e sur la base des données d'effondrement Ti pour l'ensemble des objets Ci de la scène S de manière à ordonner par valeur croissante la valeur du degré d'erreur K _e définie pour chacune des étapes d'effondrement EFF d'arêtes e sur l'ensemble du maillage de la scène S.

Dans une sixième étape f), une sélection PSEL de données de simplification dans le regroupement REFF des données de simplification est effectuée par valeur croissante de degré d'erreur K _e jusqu'à respecter le critère de simplification global CR à appliquer.

Dans le cas où le critère de simplification global CR correspond à un nombre de polygones à supprimer, la sélection PSEL peut consister à sélectionner dans l'arrangement A, en partant de l'étape d'effondrement EFF de l'arête e qui correspond au degré d'erreur Ke le plus faible, les étapes d'effondrement EFF d'arêtes e dont la somme du nombre de polygones supprimés N satisfait au critère de simplification globale CR. Dans une septième étape g), on définit pour chaque objet Ci, un critère de simplification spécifique CRCi.

Chacun de ces critères de simplification spécifique CRCi est défini en fonction d'une sous-sélection SSEL de données de simplification parmi la sélection PSEL de données de simplification en choisissant les données de simplification correspondant à l'objet considéré Ci.

La formation des sous-sélections SSEL consiste ainsi à regrouper par objet Ci les étapes sélectionnées lors de la première sélection PSEL.

Les critères de simplification spécifiques CRCi de chaque objet Ci sont alors déterminés en réal isant la somme du nombre de polygones supprimés N de chacune des étapes de simplification par effondrement EFF d'arête e de l'objet Ci considéré.

La somme des nombres de polygones à supprimer pour chaque objet Ci est égale au nombre total des polygones à supprimer NT pour la scène.

Dans une huitième étape h) du procédé, on sélectionne un objet Ci parmi la pluralité d'objets de la scène S.

Puis dans une neuvième étape i) du procédé, on réalise un deuxième ensemble EFF2Ci d'étapes d'effondrement EFF des arêtes e sur le premier ensemble E1 Ci de polygones p correspondant à l'objet Ci sélectionné jusqu'à respecter le critère de simpl ification spécifique CRCi de l'objet considéré, de façon à obtenir un second ensemble de polygones E2Ci.

Enfin, dans une dixième étape j), on réitère les étapes g) à i) pour l'ensemble des objets Ci.

On a ainsi simplifié le maillage de l'ensemble des objets Ci de la scène en modélisant chacun des objets Ci respectivement par un deuxième ensemble de polygones E2Ci qui par rapport au prem ier ensem ble de polygones E1 Ci, ne comprend plus les polygones qui influaient le moins sur le rendu de l'image des objets Ci de la scène S, ces polygones peu significatifs ayant été supprimés et les sommets des autres polygones environnant ces polygones supprimés ayant été repositionnés en conséquence.

Etant donné que l'ordre des étapes d'effondrement dans un objet donné Ci est déterminé par l'ordre de la valeur des degrés d'erreurs K _e , il suffit de conserver pour chaque objet Ci le nombre de polygones à supprimer correspondant aux critères de simplification spécifique CRCi, puis de réaliser l'effondrement successif des arêtes de l'objet donné dans l'ordre prédéterminé jusqu'à satisfaire le critère de simplification spécifique CRCi relatif à l'objet considéré.

U n exemple simple d 'appl ication du procédé tel q ue décrit ci- dessus est illustré sur les figures 2 à 4.

Dans l'exemple présenté aux figures 2 à 4, le maillage comprend dix sept triangles répartis sur trois objets C0, C1 , C2 d'une scène S en trois dimensions pour former le prem ier ensemble E1 C0 , E 1 C 1 , E 1 C2 de polygones p.

Comme illustré à la figure 2, la troisième étape c)consiste à stocker à chaque étape d'effondrement EFF d'arête e des données d'effondrement T0, T1 , T2 comprenant :

- une valeur de degré d'erreur (K _e ) associée à cette étape,

- un nombre de polygones supprimés (N) lors de cette étape.

Les données d'effondrement T0, T1 , T2 sont réun ies dans une structure de données TAB prenant la forme d'un tableau pour chaque objet C0, C1 , C2.

Dans chaq ue tableau TABO, TAB1 , TAB2, chaque colonne correspond à une étape d'effondrement EFF d'arête e d ' u n triangle p composant l'objet C0, C1 , C2.

Dans chaque tableau TABO, TAB 1 , TAB2, il est inscrit sur une prem ière l igne la valeur de degré d 'erreu r K _e de la position d u nouveau vertex/sommet Vr, pour l'étape d'effondrement EFF considéré et il est inscrit sur une deuxième ligne le nombre N de triangles supprimés au cours de cette étape d'effondrement EFF d'arête e considérée.

La valeur du nombre des triangles supprimés N au cours de cette étape d'effondrement d'arête e est généralement égale à 1 ou 2.

Sur ces tableaux TABO, TAB1 , TAB2, on remarque que la somme du nombre des triangles supprimés N des trois tableaux TABO, TAB1 , TAB2 est égale au nombre total de triangles du maillage, soit dix sept.

On remarque également que la valeur de degré d'erreur K _e associée aux étapes d'effondrement EFF d'arête e d'un même objet C0, C1 , C2 peut considérablement différer d'une étape d'effondrement E F F à une autre.

C'est a insi q ue dans l 'exemple présenté, une première étape d'effondrement EFF d'arête e du premier objet C0 induit une valeur de degré d'erreur égale à 0,1 tandis qu'une quatrième étape d'effondrement EFF d'arête e induit une valeur de degré d'erreur égale à 9,1 .

Cette va l e u r d e degré d'erreur K _e révèle pour l'util isateur l'importance du ou des polygones supprimés pour le rendu de la représentation graphique de l'objet C0, C1 , C2 considéré.

Comme ill ustré à la figu re 3, la cinquième étape e) consiste à réal iser un regroupement REFF des données d'effondrement TO, T1 , T2 correspondant à l'ensemble des objets C0, C1 , C2 de la scène S.

Cette étape revient à regrouper en un seul tableau TABS, l'ensemble des tableaux TABO, TAB1 , TAB2 comprenant les données d'effondrement T0, T1 , T2.

Cependant, ce regroupement n'est pas une simple concaténation de chacu n des tabl eaux TABO, TAB 1 , TAB2 com prenant les données d'effondrement T0, T1 , T2 afférentes à chacun des objets C0, C1 , C2 mais prend en compte individuellement chacune des étapes d'effondrement EFF d'une arête e.

En effet, chacune des étapes d'effondrement EFF d'une arête e ou colonne des tableaux TABO, TAB1 , TAB2 est arrangée de manière à ordonner par valeur croissante la valeur du degré d'erreur K _e associé à une étape d'effondrement EFF d'arête e.

C'est a i n s i q u e les colonnes correspondant à des étapes d'effondrement E F F de mêmes objetsCO, C 1 , C2 ne sont pas forcément adjacentes.

En outre, ce tableau TABS présente une troisième ligne comprenant un identifiant ID pour chaque objetCO, C1 , C2.

Comme illustré à la figure 4, la sixième étape consiste à définir pour chaque objet C0, C1 , C2 un critère de simpl ification spécifique CRC0, CRC1 , CRC2 en fonction :

- d'une première sélection PSEL de données d'effondrement dans le regroupement REFF des données d'effondrement, ladite sélection étant réalisée par valeur de degré d'erreur K _e croissant jusqu'à respecter le critère de simplification global CR à appliquer, et

- d'une seconde sélection SSEL de données d'effondrement parmi la première sélection PSEL de données d'effondrement en choisissant les données d'effondrement correspondant à l'objet considéré C0, C1 , C2. C'est ainsi qu'avec un critère de simplification global CR correspondant à un nombre total de triangles à supprimer NT égal à neuf, la première sélection PSEL va permettre de sélectionner cinq étapes d'effondrement EFF d'arêtes e dans l'arrangement A formé dans le regroupement REFF, en réalisant la somme du nombre de triangle N supprimé par étape d'effondrement EFF jusqu'à atteindre un nombre total de triangles à supprimer NT égal à neuf.

Après avoir sélectionné ces étapes d'effondrement, il est possible de déterminer le nombre de triangles à supprimer N par objet C0, C1 , C2 correspondant respectivement au critère de simpl ification spécifique CRCO, CRC1 , CRC2.

C'est ainsi que dans l'exemple présenté, quatre triangles peuvent être supprimés de l'objet C0, deux triangles peuvent être supprimés de l'objet C1 et trois triangles peuvent être supprimés de l'objet C2 sans que le rendu de l'image ne soit significativement affecté.

Dans une huitième étape h), le procédé de simplification du maillage va modéliser un objet C0, C1 , C2 de la scène S par un deuxième ensemble E2C0, E2C 1 , E2C2 de polygones p définis uniquement en appliquant au premier ensemble E1 C0, E1 C1 , E1 C2 de polygones p les étapes d'effondrement EFF d'arêtes e sélectionnées pour ledit objet jusqu'à respecter le critère de sim pl ification spécifiq ue CRCO , C RC 1 , C RC2 de l'objet considéréCO, C1 , C2.

Ch a c u n d e s o bj et s C 0 , C 1 , C 2 d e l a s c è n e S est ainsi successivement modélisé.

C ' est a i n s i q u e dans l'exemple présenté, le procédé de simplification du maillage réalisera l'effondrement de deux arêtes e de l'objet C0, d'une arête e de l'objet C1 , et de deux arêtes e de l'objet C2.

De ces divers effondrements, il résultera la suppression de quatre triangles pour l'objet C0, de deux triangles pour l'objet C1 et de trois triangles pour l'objet C2.

Bien que l'invention ait été décrite en liaison avec des exemples particuliers de réalisation, il est bien évident qu'elle n'y est nullement limitée et qu'elle comprend tous les équ ivalents techn iques des moyens ou étapes décrits ainsi que leurs combinaisons.

C'est ainsi que d'autres types d'étapes de simplification pourraient être utilisées, comme par exemple des étapes d'effondrement de sommets, qui consistent à supprimer itérativement un sommet du maillage et tous les triangles qui l'entourent, puis à boucher le trou ainsi formé avec de nouveaux triangles.