DONNÉES

[ooi] L'invention concerne un procédé de compression de données représentatives d'un objet tridimensionnel. L'invention concerne en outre un ensemble de données représentatives d'un objet tridimensionnel compressées obtenu au moyen de ce procédé de compression, ainsi qu'un support d'enregistrement d'informations contenant cet ensemble de données. L'invention concerne également un procédé de décompression de telles données qui ont été compressées à l'aide de ce procédé. L'invention concerne enfin un support d'enregistrement d'information et un calculateur pour mettre en œuvre ces procédés.

[002] Typiquement, dans le domaine de la vision par ordinateur et de l'infographie tridimensionnelle (« computer graphies » ou « computer vision » en langue anglaise), un objet tridimensionnel est représenté numériquement sous la forme d'un maillage (« polygonal mesh » en langue anglaise). Ce maillage est formé d'une pluralité de polygones planaires contigus les uns par rapport aux autres. Chaque polygone comporte une pluralité de sommets reliés entre eux par des arêtes qui délimitent une face du polygone.

[003] Des procédés de compression dits « progressifs » (« progressive compression » en langue anglaise) sont connus. Ces procédés facilitent notamment la transmission d'un objet tridimensionnel depuis un serveur de contenu multimédia vers un terminal d'un client sur lequel l'objet doit être affiché. Dans ces procédés, le maillage est graduellement simplifié par des opérations de suppression sélective (opérations aussi nommées « décimation ») des sommets, pour en réduire la taille. Le maillage simplifié est transmis vers le terminal, où il est affiché. Puis il est graduellement reconstruit sur ce terminal à partir de données incrémentielles transmises par la suite, jusqu'à retrouver l'objet tridimensionnel tel qu'il était initialement avant la compression.

[004] Un exemple de ce procédé est décrit dans le document : « Rate-distortion optimization for progressive compression of 3D mesh with color attributes », Ho Lee et al, The Visual Computer, vol. 28, p. 137-153, Springer-Verlag, mai 2011, DOI : 10.1007/s00371-011-0602-y.

[005] Lors de l'affichage progressif de l'objet tridimensionnel en cours de décompression, ces procédés ont pour inconvénient de générer des artefacts graphiques lorsqu'ils sont utilisés avec des objets tridimensionnels texturés. Par objet texturé, on entend un objet tridimensionnel dans lequel les polygones du maillage ont leur surface recouverte par une image numérique, dite « texture » ( « texture mapping » en langue anglaise). [006] De l'état de la technique est également connnu de :

- HOPPE H : « Progressive Meshes », Computer Graphics Proceedings, Siggraph'96, ACM, New York, US, 1/1/1996,

- HOPPE et Al : « Efficient implementation of progressive meshes », Computers and graphies, Elsevier, GB, vol. 22, n°l, 25/02/1998, pages 27-39,

- Lili Wang et Al : « Simplification for texture mapping models with mesh segmentation », Virtual Systems and Multimedia (VSMM), 2010 16th International Conférence on, IEEE, Piscataway, NJ, USA, 20/10/2010, pages 197-203,

- CUI XIE XIUWEN LIU : « Feature-Preserving Simplification of Texture-Mapped Models », International Conférence on Computer Graphics, Imaging and visualisation

(CGIV'06), 1/1/2006, pages 390-395,

- US2004/164982A1.

[007] Il existe donc un besoin pour un procédé de compression progressive d'un objet tridimensionnel qui limite l'apparition de tels artefacts graphiques sur l'objet lorsque celui-ci comporte des textures.

[008] L'invention concerne donc un procédé de compression de données représentatives d'un objet tridimensionnel numérique conforme à la revendication 1.

[009] Les inventeurs ont identifié qu'un problème se pose lorsque l'objet tridimensionnel comporte des polygones adjacents l'un à l'autre et dont les textures sont différentes. Le problème se pose particulièrement au niveau de frontières entre des portions de l'objet qui possèdent des textures très différentes l'une de l'autre. Typiquement, les procédés connus de compression progressive sélectionnent les sommets à supprimer en fonction de propriétés géométriques du maillage, sans tenir compte des informations de texture des polygones. Ainsi, l'arête commune qui sépare ces polygones adjacents peut être supprimée du fait de la simplification. L'information concernant le fait que, avant simplification du maillage, il existait des textures différentes de chaque côté de l'arête supprimée est ainsi absente dans le maillage simplifié obtenu. Dès lors, lors de la décompression, quand ce maillage simplifié est affiché, un artefact graphique apparaît. Cela dégrade la qualité visuelle de l'objet tridimensionnel perçu lors de sa décompression.

[ooio] Dans le procédé ci-dessus, la recherche des premier et second polygones permet d'identifier les polygones où un artefact serait susceptible d'apparaître si la simplification était directement mise en œuvre. Le remplacement, dans le second polygone, des premier et second sommets en commun par les troisième et quatrième sommets distincts et la création des arêtes permettent de séparer les premier et second polygones. Ils ne sont alors plus adjacents l'un à l'autre. Ainsi, par exemple, la suppression du premier ou du second sommet n'a pas pour conséquence la disparition à la fois des premier et second polygones. Lors de la compression, l'information sur la différence de texture est donc préservée au moins tant que les premier, second, les troisième et quatrième sommets n'ont pas été supprimés du maillage simplifié. Cette information est donc conservée plus longtemps pendant le processus de compression. Dès lors, à l'inverse, lors de la décompression, cette information réapparaît beaucoup plus tôt dans le maillage simplifié affiché sur l'écran. On minimise ainsi le temps pendant lequel un tel artefact est visible ce qui améliore la qualité visuelle de l'objet affiché en cours de décompression.

[ooii] Enfin, comme les troisième et quatrième sommets occupent la même position que les premier et second sommets et que la longueur des arêtes est nulle, l'aspect extérieur de l'objet n'est pas modifié par cette création de sommets supplémentaires.

[ooi2] Selon un autre aspect, l'invention concerne également un ensemble de données représentatives d'un objet tridimensionnel numérique compressé conforme à la revendication 3.

[ooi3] Selon un autre aspect, l'invention concerne également un support d'enregistrement d'informations, comportant l'ensemble de données représentatives d'un objet tridimensionnel numérique compressé conforme à l'invention.

[ooi4] Selon un autre aspect, l'invention concerne également un procédé de décompression de données représentatives d'un objet tridimensionnel numérique compressé conforme à la revendication 5.

[ooi5] Selon un autre aspect, l'invention concerne également un procédé de transmission de données représentatives d'un objet tridimensionnel numérique entre un émetteur et un récepteur, ce procédé comportant :

- la compression des données acquises, au moyen d'un procédé de compression conforme à l'invention ;

- la décompression, par le récepteur, des données compressées transférées, au moyen d'un procédé de décompression conforme à l'invention.

[ooi6] Les modes de réalisation de l'invention peuvent présenter une ou plusieurs des caractéristiques des revendications dépendantes.

[ooi7] Selon un autre aspect, l'invention concerne également un support d'enregistrement d'informations, comportant des instructions pour l'exécution d'un procédé conforme à l'invention lorsque ces instructions sont exécutées par un calculateur électronique.

[ooi8] Selon un autre aspect, l'invention concerne enfin un calculateur électronique pour la mise en œuvre de l'invention.

[ooi9] L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple non limitatif et faite en se référant aux dessins sur lesquels :

- la figure 1 est une illustration schématique d'un objet numérique tridimensionnel ;

- la figure 2 est une illustration schématique d'un ensemble de données représentatives d'une portion de l'objet de la figure 1 ; - la figure 3 est une illustration d'un dispositif pour transmettre les données de la figure 2 ;

- la figure 4 est un ordinogramme d'un procédé de compression des données de la figure 2 ;

- la figure 5 est une illustration schématique de la portion de l'objet de la figure 2 telle que modifiée à l'issue d'une étape du procédé de la figure 4 ;

- les figures 6A à 6C sont des illustrations schématiques de portions du maillage de l'objet de la figure 1 telles que modifiées lors de l'exécution d'une étape du procédé de la figure 4 ;

- les figures 7A et 7B sont des illustrations schématiques de l'objet de la figure 1 après application du procédé de compression de la figure 4 ;

- les figures 8A et 8B sont des illustrations schématiques de l'objet de la figure 1 après application du procédé de compression de la figure 4 lorsqu'une étape de duplication de sommets est omise de ce procédé ;

- la figure 9 est une illustration schématique d'un support d'enregistrement d'informations qui comporte un ensemble de données représentatives de l'objet numérique tridimensionnel compressé à l'issue du procédé de la figure 4 ;

- la figure 10 est un ordinogramme d'un procédé de décompression des objets des figures 7A à 8B pour reconstruire l'objet de la figure 1 ;

- la figure 11 est une illustration schématique d'un autre mode de réalisation d'une étape du procédé de la figure 4.

[0020] Dans ces figures, les mêmes références sont utilisées pour désigner les mêmes éléments.

[0021] Dans la suite de cette description, les caractéristiques et fonctions bien connues de l'homme du métier ne sont pas décrites en détails.

[0022] La figure 1 représente un objet 2 numérique tridimensionnel sur lequel est appliquée une texture en forme de damier. Cet objet 2 comporte un maillage 4 et un atlas 6 de textures.

[0023] Le maillage 4 (« polygonal mesh » en langue anglaise) est formé d'une pluralité de polygones planaires contigus les uns aux autres. Chaque polygone comporte :

- des sommets (« vertex » en langue anglaise),

- des arêtes qui relient les sommets du polygone deux à deux,

- une face, délimitée par les arêtes.

[0024] Le maillage 4 ne comporte ici aucun trou.

[0025] L'atlas 6 comporte une pluralité de textures individuelles, qui recouvre chacune une face d'un polygone du maillage 4. Chaque texture est une image bidimensionnelle, par exemple une image matricielle. Cette technique est connue sous le nom de « texture mapping » en langue anglaise. [0026] Les polygones sont ici de forme triangulaire. En effet, la plupart des processeurs graphiques (« graphical processing unit » en langue anglaise) sont optimisés pour le traitement de polygones triangulaires. Aussi, dans ce qui suit, on pourra utiliser le terme de triangle pour désigner ces polygones.

[0027] Dans cet exemple, l'objet 2 représente schématiquement une grenouille. L'atlas 6 présente un motif en damiers de couleur noire et blanche, qui recouvre la totalité de la surface extérieure du maillage 4.

[0028] La figure 2 représente un ensemble 10 de données numériques utilisées pour représenter l'objet 2. Pour simplifier, ces données sont décrites pour uniquement deux triangles 12 et 14 du maillage 4. Ces deux triangles 12, 14 sont aussi représentés en version agrandie dans la figure 2. Dans ce qui suit, le terme d'objet 2 est utilisé pour désigner des données 10 représentatives de l'objet 2. On parlera d'acquisition de l'objet 2 pour désigner l'acquisition des données 10.

[0029] L'ensemble 10 comporte :

- l'atlas 6 de textures ;

- une liste 22 des sommets des polygones du maillage 4;

- une liste 24 des polygones du maillage 4;

- une liste 26 de coordonnées de texture des polygones du maillage 4.

[0030] L'atlas 6 contient toutes les textures nécessaires pour remplir chaque face de chaque polygone du maillage 4. Chaque texture d'une face d'un polygone est indexée au sein de l'atlas 6 par un jeu de trois coordonnées (U _a ,V _a ), (U _b , V _b ) et (U _c , V _c ) (« UV mapping » en langue anglaise). Par exemple, l'atlas 6 contient une image matricielle 27 à deux dimensions. Les coordonnées (U _a ,V _a ), (U _b , V _b ) et (U _c , V _c ) codent la position de trois points dans un repère orthonormé de cette image 27. Ces trois points délimitent un morceau de l'image 27 également appelé « morceau de texture ». C'est ce morceau de texture qui est utilisé pour remplir la face d'un polygone. Dans ce qui suit, ces coordonnées seront désignées sous le nom de « coordonnées UV ». Plus précisément, ici, chaque morceau de texture présente la même forme que le polygone auquel elle correspond. Ainsi, chaque morceau de texture a une forme triangulaire qui a exactement les mêmes dimensions que la face du polygone à remplir avec ce morceau de texture. Cependant, les sommets des morceaux de texture ne sont pas des sommets du maillage 4. Pour éviter toute confusion, on parlera de « point » pour désigner les sommets des morceaux de texture. Les morceaux de texture correspondant aux polygones 12 et 14 portent respectivement les références 28 et 29 dans l'image 27. On note leurs coordonnées de texture respectives (Ui _a ,Vi _a ), (Ui _b , V _ib ) et (Ui _c , V _ic ) pour le morceau 28 et (U _2a ,V _2a ), (U _2b , V _2b ) et (U _2c , V _2c ) pour le morceau 29.

[0031] Typiquement, l'atlas 6 est organisé de telle sorte que les textures qui présentent des propriétés graphiques différentes sont placées à des emplacements distincts de l'image 27. Par propriétés graphiques, on désigne par exemple des valeurs représentatives des intensités de pixel.

[0032] La liste 22 comporte, pour chaque sommet, les coordonnées de ce sommet exprimées dans un repère de l'espace. Dans l'exemple de la figure 2, on note A, B et C les sommets du polygone 12. Le polygone 14 comporte ici les sommets B, C et D car, dans cet exemple, les polygones 12 et 14 sont adjacents et les sommets B et C sont communs aux polygones 12 et 14.

[0033] La liste 24 comporte, pour chaque polygone, une entrée énumérant les sommets de la liste 22 contenus dans ce polygone. Par exemple, l'entrée du polygone 12 dans la liste 24, notée « PI », comporte les sommets « ABC ».

[0034] La liste 26 comporte, pour chaque polygone de la liste 24, un jeu de coordonnées UV qui définit le morceau de texture associé à ce polygone. Par exemple, l'entrée « PI » associée au polygone 12 comporte les coordonnées, notées (ul, vl), des trois points qui délimitent le morceau de texture 28 dans l'atlas 6. Il en va de même pour l'entrée, notée P2, correspondant au polygone 14. L'entrée P2 est associée, par la liste 26, aux coordonnées (u2, v2) des trois points qui délimitent le morceau de texture 29.

[0035] Par exemple, les données 10 sont compatibles avec le standard « OpenGL » (pour « open graphies library » en langue anglaise) bien connu de l'homme du métier. [0036] La figure 3 représente un exemple de dispositif pour transmettre l'objet 2 depuis un émetteur 40 vers un récepteur 42. L'émetteur 40 et le récepteur 42 sont aptes à échanger des données entre eux au moyen d'une liaison 44 d'échange de données. Généralement, l'émetteur 40 et le récepteur 42 sont séparés l'un de l'autre par plusieurs mètres ou plusieurs kilomètres. La liaison 44 est typiquement une liaison établie par l'intermédiaire d'un réseau grande distance de transmission d'information comme le réseau internet (« World Wide Web »).

[0037] L'émetteur 40 comporte une unité de calcul 46 qui inclut :

- un support 48 d'enregistrement d'informations ;

- un calculateur 50 électronique programmable ;

- une interface 52 d'échange de données.

[0038] Le support 48 comporte les instructions nécessaires pour exécuter le procédé de compression de la figure 4. Le calculateur 50 lit et exécute les instructions enregistrées sur le support 48. L'interface 52 permet l'échange et le transfert des données 10 sur la liaison 44.

[0039] L'émetteur 40 est par exemple un serveur de distribution d'un contenu multimédia. Le récepteur 42 est ici un terminal client tel qu'un ordinateur ou un dispositif de communication mobile. Le récepteur 42 est notamment apte à afficher l'objet 2 (« rendering » en langue anglaise). Il comporte ici pour cela un processeur graphique 48 et une unité de calcul 47, par exemple identique à l'unité 46. [0040] L'émetteur 40 est apte à compresser les données 10 puis à les transmettre vers le récepteur 42 pour que ce dernier les décompresse et affiche l'objet 2 sur un écran 49.

[oo4i] Un exemple de compression des données 10 va d'abord être décrit, en référence à l'ordinogramme de la figure 4 et à l'aide des figures 1 à 7C. Ce procédé est un procédé de compression progressif du maillage (« progressive compression » en langue anglaise).

[0042] D'abord, lors d'une étape 60, les données 10 sont acquises par l'unité 46.

[0043] Ensuite, lors d'une étape 62, le maillage 4 est mis en forme en vue des étapes subséquentes du procédé de compression. Ces étapes, et notamment de simplification seront décrites plus en détail dans ce qui suit.

[0044] Cette étape comporte d'abord une opération 64 de recherche, parmi les polygones du maillage 4, de premier et second polygones adjacents qui présentent des textures différentes.

[0045] Deux polygones sont dits être adjacents s'ils présentent entre eux un premier et un second sommets en commun et sont reliés entre eux par une arête commune.

[0046] Ici, deux textures sont dites être différentes si l'intersection des morceaux de textures correspondants dans l'atlas 6 est un ensemble nul, c'est-à-dire que les morceaux de texture sont complètement disjoints dans l'atlas 6. Par exemple, les morceaux 28 et 29 de texture sont disjoints car la plus petite distance qui les sépare est non nulle.

[0047] Ici, les polygones 12 et 14 sont adjacents et ont en commun les sommets B et C. De plus, leurs morceaux de texture respectifs 28 et 29 sont différents. Aussi, dans ce qui suit, on utilisera les références 12 et 14 pour désigner de façon générique de tels polygones. De même, on utilisera les références B et C pour désigner les sommets en commun aux polygones 12 et 14.

[0048] Par exemple, les polygones 12 et 14 sont identifiés en recherchant automatiquement, à l'aide des listes 24 et 26, des polygones qui sont à la fois adjacents entre eux et qui sont associés par la liste 26 à des morceaux de texture disjoints.

[0049] Si des polygones 12, 14 ont été identifiés, alors, l'étape 62 comporte, pour chaque paire de polygones identifiés, la séparation de ces polygones suivant ce qui suit.

[0050] Lors d'une opération 66, les sommets B et C sont remplacés dans le polygone 14 par des sommets B' et C, dits sommets dédoublés. Les sommets B' et C occupent respectivement les mêmes positions dans l'espace que les sommets B et C. Ils ont donc les mêmes coordonnées que ces derniers.

[0051] Par exemple, les sommets B' et C sont créés dans la liste 22 et la définition BCD du polynôme 14 dans la liste 24 est remplacée par la définition B'C'D. Ainsi, dans les données 10 une nouvelle arête B'C est créée et les arêtes BD et CD du polygone 14 sont remplacées par des arêtes, respectivement, B'D et CD. Par la suite, le polygone 14 ainsi modifié porte la référence 14' (figure 5). Dans cette description, une arête qui relie directement deux sommets X et Y dans un polygone porte la référence « XY ».

[0052] Lors d'une opération 68, au moins deux arêtes de longueur nulle sont créées entre, d'une part, les sommets B et B' et, d'autre part, les sommets C et C, de façon à créer au moins un polygone intermédiaire interposé entre les polygones 12 et 14'. Ces arêtes BB' et CC raccordent entre eux les polygones 12, 14'. Ce raccord est nécessaire pour éviter l'apparition d'artefact supplémentaire à la jonction des polygones 12, 14' comme, par exemple, l'apparition d'un trou. La face de ce polygone intermédiaire a une superficie nulle de sorte qu'il n'est pas visible sur un écran et ne crée aucun artefact visible. Ici, comme les polygones du maillage 4 sont nécessairement des triangles, ce sont deux polygones triangulaires intermédiaires 67, 69 (figure 5), interposés entre les polygones 12 et 14', qui sont créés. Par exemple, une arête supplémentaire B'C est créée pour former ces polygones 67 et 69. Ici, le polygone 67 est délimité par les arêtes BC, CB' et BB' et le polygone 69 est délimité par les arêtes B'C, CC et CB'. Les nouvelles arêtes BB', CC et CB' sont créées en ajoutant dans la liste 24 la définition de ces nouveaux polygones 67, 69. Par exemple, les polygones 67 et 69 présentent une texture de valeur nulle et ne sont donc associés à aucun morceau de texture par la liste 26.

[0053] Pour faciliter la lecture de la figure 5, les triangles 67 et 69 y sont dessinés avec une face de superficie non nulle alors que, comme expliqué ci-dessus, ils ont une surface nulle. De même, sur cette figure, les arêtes BB', CC sont représentées avec une longueur non nulle alors que ce n'est pas le cas. Le fait qu'un polygone présente une face de superficie nulle ne signifie pas pour autant qu'il n'existe pas dans le maillage 4, puisque tout polygone y est défini en fonction de ses sommets, notamment dans la liste 24. Il en va de même pour les arêtes.

[0054] Ces opérations 66 et 68 se traduisent par une modification correspondante des listes 22, 24 et 26 des données 10 pour refléter les modifications du maillage 4. [0055] La duplication des sommets B et C, en les remplaçant dans le polygone 14 par les sommets B' et C, permet de séparer les polygones 12 et 14 l'un de l'autre. Cela évite que l'information selon laquelle il existe une différence de texture entre ces deux polygones soit perdue dès que l'on supprime l'un des sommets B et C. De plus, le fait que les sommets B' et C soient reliés aux sommets B et C par des arêtes évite que les polygones 12 et 14' ne se déplacent l'un par rapport à l'autre au cours de la suite du procédé. Un tel déplacement engendrerait des trous dans le maillage 4, ce qui dégraderait la qualité graphique de l'objet 2. La valeur nulle des longueurs des arêtes et de la superficie de la face des polygones 67 et 69 font que cette duplication des sommets B et C ne se traduit pas par une modification de l'aspect graphique extérieur du maillage 4 et donc de l'objet 2. Ces arêtes permettent de modifier localement la connectivité du maillage 4, de sorte que des opérations de simplification ultérieures, qui se basent sur des informations de connectivité, n'aboutissent pas à une disparition trop rapide de ces polygones.

[0056] Lorsque plus aucune paire de polygones adjacents et de texture différente n'est trouvée dans les données 10 modifiées, alors l'étape 62 se termine.

[0057] A l'issue de l'étape 62, le maillage 4 ne comporte pas de polygones adjacents qui ont des textures différentes.

[0058] Ensuite, lors d'une étape 70, le maillage 4 est simplifié. Cette simplification comporte la suppression de sommets, et donc de polygones, du maillage 4. Cette simplification a pour but de créer de nouveaux polygones qui présentent une face plus étendue que les polygones supprimés. Ces nouveaux polygones viennent remplacer les polygones supprimés. On obtient ainsi une image simplifiée qui occupe moins de place en mémoire.

[0059] L'étape 70 comporte à cet effet :

- une opération 72 d'identification, en fonction d'un critère prédéterminé, de sommets à supprimer ;

- une opération 74 de suppression des sommets identifiés et des arêtes qui relient ces sommets entre eux et aux autres sommets du maillage 4 ;

- une opération 76 de création :

· de nouvelles arêtes pour relier les sommets qui n'ont pas été supprimés, créant ainsi les nouveaux polygones et,

• de nouvelles textures pour recouvrir les faces des nouveaux polygones, à partir des textures respectives des polygones supprimés.

[0060] L'identification lors de l'opération 72 est par exemple réalisée en sélectionnant les sommets de la liste 22 sur la base de critères de connectivité, tels que le nombre de leurs plus proches voisins.

[0061] L'opération 74 a pour conséquence la suppression d'une partie des polygones du maillage 4.

[0062] Dans cet exemple, l'étape 70 est réalisée au moyen de l'algorithme décrit dans les documents suivants :

- « Rate-distortion optimization for progressive compression of 3D mesh with color attributes », Ho Lee et al, The Visual Computer, vol. 28, p. 137-153, Springer-Verlag, mai 2011, DOI : 10.1007/s00371-011-0602-y.

- P. Alliez et al. « Progressive compression for lossless transmission of triangle meshes », ACM Proceedings of SIGGRAPH, p. 195-202, 2001.

[0063] Les figures 6A à 6C illustrent le fonctionnement de cet algorithme sur une portion 80 du maillage 4.

[0064] Cet algorithme fonctionne en deux temps. D'abord, les opérations 72 à 74 sont réalisées lors d'une phase dite de « conquête ». Les sommets du maillage 4 sont parcourus automatiquement de proche en proche, en se déplaçant le long des arêtes du maillage 4, à la manière d'un graphe. L'ordre dans lequel les sommets sont parcourus est défini par un parcours de graphe (« graph traversai » en langue anglaise) prédéfini. Pour chaque sommet, on détermine quelle est la valence de ce sommet, c'est-à-dire le nombre de voisins immédiats S' de ce sommet auxquels il est directement connecté par des arêtes. Si ce sommet S présente une valence inférieure à un seuil prédéterminé, alors il est supprimé. Les arêtes qui reliaient ce sommet S à ses voisins immédiats sont alors supprimées. Ces arêtes portent les références SS' sur la figure 6A. Les nouvelles arêtes 80, 81, 82 (figure 6B) sont créées pour remplacer les arêtes SS'.

[0065] Dans une seconde phase, dite de nettoyage, l'algorithme supprime avantageusement certains sommets 83 excédentaires ainsi que les arêtes reliant ces sommets et crée de nouvelles arêtes en remplacement, de manière à obtenir des nouveaux polygones 84 présentant une forme régulière. L'opération 76 est ici en partie réalisée lors de cette phase, puisque des arêtes y sont créées.

[0066] Ces opérations 72, 74 et 76 se traduisent ici par des modifications correspondantes des listes 22, 24 et 26 et de l'atlas 6 pour refléter les modifications apportées au maillage 4.

[0067] Avantageusement, lors d'une opération 89, sont enregistrées des données dites incrémentielles ou de raffinement. Ces données indiquent quels ont été les sommets et les arêtes supprimées ainsi que ceux créés lors de l'étape 70. Par exemple, ces données comportent une liste des sommets supprimés lors de l'étape 70, ainsi que d'une liste donnant, pour chacun de ces sommets supprimés, l'ensemble des sommets voisins auxquels ce sommet supprimé était directement connecté par une arête. Les données incrémentielles permettent, lorsqu'elles sont utilisées dans un procédé de décompression, de réaliser les opérations inverses de celles de l'étape 70. Cela permet de reconstruire le maillage tel qu'il était avant application de l'étape 70 à partir du maillage simplifié obtenu à l'issue de cette étape 70 et de ces données incrémentielles. Avantageusement, ces données comportent également des informations permettant de retrouver le morceau de texture associé à chaque polygone reconstruit sans perte d'information.

[0068] La figure 7A représente une version simplifiée de l'objet 2, dite aussi objet simplifié 94, dont on dispose à l'issue de l'étape 70 après la simplification de l'objet 2. L'objet 94 possède moins de sommets et de polygones que l'objet 2. Du fait de cette moindre résolution, les données représentatives de cet objet 94 présentent une taille moindre que les données 10. La transmission de l'objet 94 en est ainsi facilitée.

[0069] Dans cet exemple, la simplification est répétée plusieurs fois pour obtenir un taux de compression plus élevé. Dans ce cas, le procédé comporte en outre, à l'issue de l'étape 70, une étape additionnelle 91 de simplification. L'étape 91 est par exemple identique à l'étape 70, sauf qu'elle est exécutée sur l'objet 94 de façon à simplifier cet objet 94. Typiquement, lors de chaque nouvelle itération de l'étape 91, les critères de sélection des sommets à supprimer sont élargis pour supprimer de nouveaux sommets.

[0070] On obtient ainsi, à l'issue de l'étape 91, une version finale de l'objet 2, dite objet final 96, comme illustré à la figure 7B. L'objet 96 comporte moins de sommets et de polygones que l'objet 94. Il correspond à une version de l'objet 2 plus simplifié que ne l'est l'objet 94. Les données incrémentielles générées lors de cette exécution de l'étape 91 sont également enregistrées.

[0071] Enfin, lors d'une étape 92, l'objet 96 est transmis sur l'interface 50.

[0072] Le présent procédé est particulièrement avantageux pour réduire l'apparition d'artefacts graphiques sur les objets 94, 96 à l'issue de leur compression. En effet, les procédés de compression progressive classiquement utilisés ne tiennent pas compte des différences de texture entre polygones adjacents. Dans un tel procédé classique, les sommets B et C des polygones 12 et 14 peuvent rapidement être supprimés lors de l'opération 74. Les polygones 12 et 14 sont alors supprimés et remplacés par des nouveaux polygones. Alors, la texture des polygones est remplacée par une nouvelle texture déterminée à partir des points des morceaux de texture 28 et 29. Par exemple, il arrive fréquemment qu'un de ces nouveaux polygones soit associé à un nouveau morceau de texture défini par deux points du morceaux 29 et un point du morceau 28. Ce nouveau morceau comprend une portion de l'image 27 située entre les morceaux 28 et 29. Or cette portion est souvent complètement différente des morceaux 28 et 29. Cela fait donc apparaître à l'emplacement des polygones 12 et 14, dans l'objet simplifié, un morceau de texture très différent et donc particulièrement visible. Cela donne lieu à des artefacts graphiques particulièrement visibles du fait de la différence de texture entre les polygones 12 et 14.

[0073] Les figures 8A et 8B illustrent, respectivement, des objets 94' et 96'.

[0074] L'objet 94' est un objet simplifié obtenu à l'issue d'un procédé de compression appliqué à l'objet 2 et identique au procédé de la figure 4 (sans l'étape 91), mais dans laquelle l'étape 62 n'a pas été exécutée.

[0075] De même, l'objet 96' est un objet final obtenu après exécution du procédé de compression sur l'objet 2 au cours duquel les étapes 70 et 91 ont été appliquées, mais dans laquelle l'étape 62 n'a pas été exécutée.

[0076] L'objet 94' est identique à l'objet 94, sauf qu'il comporte un artefact graphique 100. De même, l'objet 96' est identique à l'objet 96, sauf qu'il comporte un artefact graphique 102. Ces artefacts 100 et 102 correspondent à des polygones dont l'information de texture a été perdue en partie ou en totalité lors de l'étape 70 ou 91. Cette perte d'information résulte de la suppression de polygones adjacents qui présentaient des textures différentes. Puisque ces polygones n'ont pas fait l'objet d'une séparation au cours de l'étape 62 préalablement à l'étape de simplification, ils ont été supprimés lors de l'opération 74. [0077] A l'inverse, quand le procédé de la figure 4 est appliqué, l'information selon laquelle les polygones adjacents 12 et 14 ont des textures différents n'est pas perdue tant que tous les sommets B, B', C et C n'ont pas été supprimés. Cette perte d'information ne peut donc se produire qu'après un nombre bien plus important d'itérations des étapes 70 et 91. Ainsi, soit les artefacts visuels n'apparaissent pas, soit ils apparaissent à un stade de compression bien plus avancé. Or, comme on le comprendra à la lecture de ce qui suit, plus l'artefact visuel apparaît à un stade avancé de la compression, plus vite il disparaît lors de la décompression. Avec le procédé de la figure 4, lors de la décompression, les artefacts sont donc supprimés ou beaucoup plus éphémères.

[0078] La figure 9 représente un support 104 d'informations contenant un ensemble 106 de données représentatives de l'objet 96'.

[0079] L'objet simplifié est par la suite transmis par l'émetteur 40 vers le récepteur 42, pour y être affiché. De même, les données incrémentielles respectivement associées à chaque exécution de l'étape 70 ou 91 sont elles aussi transmises depuis l'émetteur 40 vers l'émetteur 42. Cette transmission est par exemple réalisée séquentiellement.

[0080] La figure 10 illustre le procédé de décompression pour reconstruire l'objet 2. Ce procédé est par exemple celui décrit dans la demande de brevet FR2998685. [0081] Lors d'une étape 110, les données représentatives de l'objet 96 sont acquises en premier par le récepteur 42, suite à leur transmission depuis l'émetteur 40. Le récepteur 42 affiche alors immédiatement l'objet 96 reçu.

[0082] Puis, lors d'une étape 112, le récepteur 42 reconstruit automatiquement l'objet 94 à partir de l'objet 96 et à l'aide des données incrémentielles qui ont été générées lors de l'étape 91, en effectuant des opérations inverses de celles réalisées lors de cette étape 91.

[0083] Ces données incrémentielles sont typiquement acquises par le récepteur 42 après la réception des données représentatives de l'objet 96 et, souvent, après l'affichage de l'objet 96 sur l'écran 49. Puis, à partir de ces données, le récepteur 42 modifie l'objet 96 pour rajouter les sommets du maillage qui ont été supprimés lors de l'étape 91. Cela conduit à la suppression de certains polygones du maillage de l'objet 96 pour les remplacer par des polygones de remplacement, qui sont plus nombreux et qui présentent une superficie plus réduite.

[0084] Ainsi, dans l'objet 96, le récepteur 42 :

- rajoute les sommets supprimés lors de la simplification de l'étape 91,

- remplace les arêtes du maillage qui avaient été créées lors de l'étape 91, par des arêtes supplémentaires qui relient les sommets rajoutés aux sommets existants de l'objet 96, de façon à créer les polygones supplémentaires ; - crée des morceaux de textures supplémentaires, pour ces polygones supplémentaires, à partir des textures respectives des polygones remplacés et des données incrémentielles.

[0085] A l'issue de l'étape 112, le récepteur 42 a reconstruit l'objet 94. L'objet 94 est alors affiché à la place de l'objet 96 sur l'écran 49.

[0086] Ensuite, lors d'une étape 114, le récepteur 42 reconstruit l'objet 2 à partir de l'objet 94 reconstruit et à l'aide des données incrémentielles qui ont été générées lors de l'étape 70. Cette étape 114 est par exemple identique à l'étape 112, sauf qu'elle s'applique sur l'objet 94 plutôt que sur l'objet 96.

[0087] Ainsi, l'objet 2 est progressivement reconstruit, par raffinements successifs à partir des données incrémentielles, avec une précision croissante, au fur et à mesure de leur réception, jusqu'à retrouver un niveau de détail identique ou proche à celui qu'il présentait avant la compression. Les objets simplifiés intermédiaires, comme l'objet 94, sont affichés dès qu'ils sont reconstruits. Le récepteur 42 affiche ainsi, au fur et à mesure qu'il reçoit les données incrémentielles et qu'il met en œuvre les étapes de reconstruction, des objets dont la précision va en augmentant. Ce procédé est utile lorsque le débit de la liaison 44 est limité ou est sujet à des variations importantes. Cela évite que l'affichage de l'objet sur le récepteur 42 ne soit perturbé par un phénomène de retard (« lag » en langue anglaise). Cela limite également le temps d'attente pour que l'objet soit affiché (même dans une version simplifiée) par le récepteur 42, par rapport au cas où il faudrait attendre que tout l'objet 2 compressé soit transmis au récepteur 42 avant de pouvoir commencer la décompression puis son affichage.

[0088] Puisque, lors de la décompression, les objets simplifiés sont affichés dans l'ordre inverse de leur création par la compression, plus l'artefact visuel apparaît tardivement lors de la compression, plus vite il disparaît lors de la décompression et donc de l'affichage progressif de l'objet décompressé.

[0089] Avantageusement, lors d'une étape 116, le maillage de l'objet 2 reconstruit est mis en forme pour supprimer les sommets et arêtes créés lors de l'étape 62. Cette étape comporte ici :

- le remplacement des sommets B' et C par, respectivement, les sommets B et C et,

- la suppression des arêtes BB', CC et B'C.

[0090] Ainsi, les polygones 67, 69 sont supprimés et les polygones 12, 14 retrouvent la configuration qu'ils avaient initialement dans l'objet 2.

[0091] De nombreux autres modes de réalisation sont possibles.

[0092] L'objet 4 peut être différent. Il peut s'agir de n'importe quel objet apte à être représenté sous la forme d'un maillage. De même, l'atlas 6 peut être choisi différemment.

[0093] Les polygones peuvent présenter une forme autre qu'un triangle. Par exemple, les polygones ont une forme de parallélépipède. [0094] Les données 10 peuvent être enregistrées dans un format compatible avec un autre standard graphique, tel que Direct3D.

[0095] L'émetteur 40 peut être différent. Par exemple, l'unité 46 peut être distincte de l'émetteur 40. La compression de l'objet 2 n'est donc pas réalisée par l'émetteur 40, ce dernier n'ayant alors pour rôle que de transférer les données vers le récepteur 42.

[0096] Le récepteur 42 peut être différent. Il peut par exemple s'agir d'une tablette, d'un téléphone mobile, d'un téléviseur. L'affichage de l'objet 2 peut également être réalisé indépendamment de la réception. Le terme de « récepteur » 42 englobe alors deux dispositifs distincts, l'un recevant l'objet 2 et l'autre affichant cet objet 2.

[0097] L'étape 62 peut être réalisée autrement.

[0098] En particulier, l'opération 64 peut être réalisée différemment pour identifier des polygones adjacents. Par exemple, la figure 11 illustre une autre méthode pour identifier les polygones 12, 14 dans une portion du maillage 4. Selon cette méthode, on parcourt automatiquement les arêtes du maillage en sélectionnant les sommets du maillage les uns après les autres selon un ordre prédéterminé. Pour chaque sommet 150 sélectionné, on parcourt tous les sommets immédiatement voisins 152, 153 de ce sommet 150, en tournant autour du sommet 150 selon un sens prédéfini, sens ici identifié par la flèche 154. Ces sommets voisins sont définis comme les sommets directement raccordés au sommet 150 par une arête. Pour simplifier, seuls les sommets 152 et 153 portent une référence numérique. On détermine ensuite, s'ils existent, des sommets 152 et 153 possédant un autre sommet commun immédiatement voisin 156 autres que le sommet 150. Si tel est le cas, cela indique que les sommets 152, 153 sont communs à plusieurs polygones. Dans cet exemple, on identifie des polygones adjacents 158 et 160. Le polygone 158 comporte les sommets 150, 152 et 153. Le polygone 160 comporte les sommets 152, 153 et 156. Ensuite, on vérifie si les morceaux de textures associés aux polygones 158 et 160 sont différents.

[0099] En variante, ce sont les sommets B et C du polygone 12 qui sont remplacés par les sommets B' et C.

[ooioo] L'étape 91 peut être omise. Dans ce cas, l'objet 94 est l'objet final et c'est lui qui est transmis. L'étape 112 est alors omise du procédé de décompression,

[ooioi] Selon d'autres variantes, l'étape 91 est répétée plusieurs fois, de façon à augmenter le taux de compression de l'objet 2 avant sa transmission. Le procédé de décompression comporte alors un nombre d'étapes identiques à l'étape 112 égal au nombre de fois où l'étape 91 a été répétée.

[ooio2] Dans une autre variante, lorsque l'étape 91 est exécutée au moins une fois, alors l'étape 62 est répétée, par exemple avant chaque exécution de l'étape 91. Si les polygones 67 et 69 ont été supprimés lors d'une exécution de l'étape 91, ils peuvent ainsi être recréés avant d'exécuter à nouveau l'étape 91. Cela limite le risque que les polygones 12 et 14 soient supprimés lors de cette étape 91. Dans ce cas, l'étape 116 peut être répétée plusieurs fois. Par exemple, l'étape 116 est appliquée lors de la décompression après chaque étape 112 ou 114..

[ooio3] L'étape 70 peut être réalisée différemment. Par exemple, on utilise l'algorithme décrit dans le document suivant : Maglo, A., Courbet, C, Alliez, P. . « Progressive compression of manifold polygon meshes », Computers and Graphics, 2012, DOI : 10.1016/j.cag.2012.03.023.

[ooio4] L'étape 116 peut être omise. Cette étape peut aussi être appliquée après l'étape 112 pour nettoyer le maillage de l'objet 94 reconstruit, avant que ne soit appliquée l'étape 114.

[ooio5] Dans un autre mode de réalisation, lors de l'étape 62, les sommets B' et C, de même que les sommets B et C, font l'objet d'un marquage au cours d'une opération 180 (figure 4), indiquant ainsi qu'ils ne devront de préférence pas être supprimés lors de l'étape 70. Ce marquage consiste par exemple en une valeur prédéfinie d'un bit de données supplémentaire ajouté dans la liste 22 pour chaque sommet. Ainsi, lors de l'étape 70, on vérifie lors de l'opération 72 si le sommet présente un tel marquage. Par exemple, on réalise un premier parcours de tous les sommets du maillage. Si un sommet non marqué est rencontré et qu'il satisfait les critères pour être supprimé, alors il est supprimé. Par contre, s'il est marqué, alors on ne le supprime pas d'emblée et on indique dans une liste spécifique qui ne sera consultée que lors d'un second parcours des sommets du maillage. Si l'étape 70 peut se terminer sans qu'il ne soit nécessaire de le supprimer, alors on ne supprime pas ce sommet. S'il est impossible de ne pas supprimer ce sommet (par exemple parce que sa suppression est imposée pour préserver certaines propriétés de régularité du maillage) alors ce sommet est supprimé. Autrement dit, on retarde sa suppression jusqu'à ce qu'il ne soit pas possible de faire autrement. Le marquage peut être réinitialisé après chaque application de l'étape 70 et 91, pour tenir compte des modifications du maillage induites par la simplification. Dans un cas extrême, la suppression d'un sommet ainsi marqué est interdite, ce qui garantit qu'aucun artefact visuel n'apparaîtra.

[00106] Enfin, d'autres méthodes sont possibles pour identifier des morceaux de textures différents. Par exemple, dans une version simplifiée, des morceaux de texture sont différents dès qu'ils n'ont aucun point en commun dans l'image 27. Dans une autre variante, des morceaux de textures sont différents seulement si la distance minimale d qui sépare ces deux morceaux est strictement supérieure à un seuil prédéterminé. Ce seuil prédéterminé peut être égal à zéro ou strictement supérieur à zéro.

[ooio7] Il est aussi possible de comparer des caractéristiques représentatives de la texture pour décider si des morceaux de texture sont différents ou non. Par exemple, pour chaque morceau de texture, cette caractéristique est calculée puis si l'écart entre la valeur de cette caractéristique pour un premier morceau et un second morceau est supérieur à un seuil prédéterminé, alors ces morceaux de texture sont dits être différents. La caractéristique peut être la valeur médiane ou le maximum ou le minimum d'un histogramme des couleurs contenues dans le morceau. La caractéristique peut être une grandeur représentative du motif graphique figurant sur la texture, comme une dimension fractale ou un exposant de Hurst. Cette dernière façon de procéder basée sur des caractéristiques représentatives n'utilise pas les positions des points délimitant les morceaux de texture dans l'image 27.