Dossier Techniques de modélisation avancée : La compression des données

La compression de modèles 3D est cruciale pour toutes les visualisation temps réel : Internet, jeux vidéo, réalité virtuelle, etc. Le défi technique est d'autant plus grand que les techniques de saisies de données réelles génèrent des bases de données gigantesques. Exemple extrême mais représentatif, dans le cadre du projet Michelangelo, un nuage de deux milliards de points et 7000 photographies ont été générées par la numérisation du David. Les techniques de compression se révèlent aussi très utiles pour optimiser certains calculs. Ainsi le lancer de rayons se fait sur des objets simplifiés et non sur les objets d'origine, qui feraient exploser les calculs. Les applications de la compression de données 3D sont diversifiées mais toutes aussi exigeantes.

Le principe de base pour simplifier des modèles polygonaux consiste à fusionner les polygones les plus coplanaires tout en conservant au maximum les trous, les arêtes et les pointes, caractéristiques de la topologie et de la silhouette de l'objet. Par exemple, dans les simulateurs de vol, les polygones seront très dégradés à l'horizon alors que la ligne d'horizon sera maintenue la plus précise et la plus cohérente possible lors de l'animation. Le cas d'un grand objet comme ici le terrain, à la fois très proche et très éloigné de l'utilisateur, est d'ailleurs un cas spécifiquement compliqué. L'objet est découpé. Mais les différentes parties qui sont simplifiées avec des degrés différents de compression doivent rester parfaitement raccords.

Les contraintes de simplification peuvent varier suivant l'application. Dans certains domaines industriels qui font usage des éléments finis ou pour certaines applications médicales, il peut s'avérer nécessaire de garder constant le volume de l'objet lors de la compression. La mesure de l'erreur du modèle simplifié par rapport au modèle d'origine - distance par rapport à la surface d'origine ou variation par rapport au volume d'origine - est caractéristique de la qualité de la compression.

Gérer les niveaux de détails

En pratique un seul niveau de simplification est rarement suffisant. Pour la visualisation temps réel - jeu ou réalité virtuelle - le niveau de détails doit être modifié adaptativement en fonction du point de vue caméra et de la précision désirée. La solution la plus simple consiste à générer plusieurs versions du même objet avec des définitions différentes. Le moteur de rendering est alors capable de remplacer automatiquement une version par une autre en fonction du déplacement de la caméra. Ce principe existe aussi dans la plupart des logiciels 3D pour accélérer le rendering. Mais si la substitution est trop abrupte, on va constater une saute en animation. Pour corriger ce défaut, le rendering peut effectuer des fondus ou des morphs. Encore mieux, des techniques comme les "progressive meshs" ou la compression par ondelettes permettent de subdiviser de manière continue les objets à partir d'un seul modèle de référence. La très efficace technologie Viewpoint Experience Technology (VET) (ex-MetaStream), développée à l'origine par Metacreations et Intel, utilise une combinaison de compression par ondelettes pour les textures et d'une technique propriétaire de multi-résolution à la demande.

Hugues Hoppe, du centre de recherche de Microsoft, a présenté en 1996 au Siggraph la technique des "Progressive meshs". L'idée révolutionnaire était de garder les relations entre les différents niveaux de décimation afin de pouvoir gérer les niveaux de détails de manière progressive. Le modèle polygonale étant simplifié par étapes, l'astuce consiste à garder les informations sur les positions des vecteurs supprimés. Il devient possible de transmettre un modèle géométrique en deux étapes. On envoie d'abord le modèle simplifié puis à la demande les informations complémentaires permettant de le resubdiviser pour revenir à la forme d'origine. L'autre qualité de cet algorithme est de prendre en compte les discontinuités de couleurs, de textures et de tangentes afin d'optimiser la compression. Un outil comme Virtools, dédié au temps réel interactif, a adopté cette technique après avoir essayé avec moins de succès la triangulation adaptative de patchs. Et ce n'est pas le seul.

Hugues Hoppe

Les ondelettes

Issu du traitement du signal, la compression de modèles 3D par ondelettes s'est elle aussi imposée par son efficacité. La décomposition classique en fréquences – la transformée de Fourier – souffrait d'être globale sur l'ensemble de l'objet étudié. Même pour reconstituer les détails d'une petite portion de l'objet compressé, l'ensemble du spectre devait être transmis. L'algorithme des ondelettes permet en revanche une décompression locale. Le modèle simplifié - équivalent aux basses fréquences - est transmis dans un premier temps. Ne sont transmises ensuite à la demande que les hautes fréquences nécessaires à une reconstitution locale. Ce qui explique son succès.

Les algorithmes de compression, comme celui des ondelettes, sont très efficaces et permettent un contrôle local en temps réel précis et optimisé. Mais d'après Guillaume Thibault, ingénieur de recherche à EDF R&D, "si les techniques de compression ont fortement progressées, il faut se demander dans quel but. L'étude de la perception humaine apporte de nouvelles contraintes et de nouvelles idées (perception based algorithm). Par exemple, pour la compression de visages, il est important de sauvegarder le contour des yeux et de la bouche. La compréhension des éléments saillants d'une scène est devenue aussi nécessaire que la performance technologique."

Guillaume Thibault

Patrick Gioia Ingénieur de recherche, France Telecom R&D, Rennes Pourquoi développer Wavier ? Le logiciel Wavier, développé par mon équipe et commercialisé depuis peu, permet de visualiser en temps réel sur Internet de grandes bases de données géographiques fournies par IGN. L'idée était d'utiliser la technologie émergente à base d'ondelettes géométriques (ondelettes de deuxième génération) qui permet de transmettre des données 3D par réseau. La grande puissance de cet algorithme est son adaptativité. L'utilisateur, qui doit quand même avoir une liaison ADSL, peut choisir son point de vue et son degré de précision. Dans le cas présent, la technologie est appliquée aux bases de données IGN qui sont particulièrement lourdes et comportent des millions de polygones. Mais la technologie peut s'appliquer à n'importe quels autres objets 3D. Le but à terme de notre projet réalisé avec la société IVT est de pouvoir se déplacer en 3D et en temps réel sur Internet dans la France entière avec 50 cm de précisions. La technologie le permet, il reste à IGN à fournir l'ensemble des données. Comment choisit-on un algorithme de compression ? Parmi les algorithmes avec perte de topologies - mais pas forcément avec perte en visualisation – la compression par ondelettes est le meilleur algorithme que l'on puisse trouver. Découvert et utilisé assez récemment, il vient du codage d'images et permet de jouer sur l'espace et les fréquences. Les détails peuvent être isolés ainsi que les niveaux de subdivision qui correspondent en 3D aux bandes de fréquences. Comment sont gérés les niveaux de détails ? Nous avons déposé plusieurs brevets sur ce sujet. A partir d'un seul maillage, on peut mettre à jour localement (ajouter ou retirer du détail) à la volée, avec une fréquence de rafraîchissement paramétrable. Le serveur décide de ce qui est transmis, et le client met à jour son modèle de référence. Il n'est pas obligé de tout traiter. La visualisation est adaptative en fonction du poste, et le client décide s'il privilégie la fréquence de rafraîchissement ou la performance visuelle. De plus, avec la gestion du cache il peut réutiliser ce qu'il a déjà télécharger. Et tout ceci sur une station client équipée d'un P500Mhz avec carte graphique Geforce. Va-t-on voir un jour l'avénement d'un standard ? Nous sommes en discussion pour que notre algorihme soit inclus dans le standard MPEG-4 dont une nouvelle version doit sortir en Octobre prochain. Ce format inclut les surfaces géométriques (NURBS, splines, etc) et les modes de compression de type ondelettes. Le MPEG-4 va certainement émerger, c'est plus un problème de communication que de qualité. De nouvelles applications doivent se développer pour faire sa promotion. Technologiquement nous ne sommes pas loin des limites des algorithmes de compression. L'effort va plus porter maintenant sur l'exploitation de ces nouvelles techniques que sur la recherche.

Pour plus d'informations :

Viewpoint : www.viewpoint.com
Virtools : www.virtools.com
Opticore : www.opticore.com

© mars 2002 François Ploye et Pixel SA