Le travaille sur lequel je suis intervenu aux E.U. "Progressiv Forest Flip Compression" devrait être intégré dans M.P.E.G. 4. Cela dit, il y a d'autres technologies qui ont été développées en parallèle et par la suite, et l'une des meilleures aujourd'hui est à mon avis celle qui va paraître au Siggraph 2001. L'article correspondant à cette technologie s'appelle "Progressive Compression for Lossless Transmission of Triangle Meshes" présenté par Pierre Alliez et Mathieu Desbrun . Cette technique intègre à la fois la compression et la multi-échelle. Un format qui contient un objet à plusieurs niveau de résolution et le tout compressé. Sachant que l'on peut au fur et à mesure de la transmission reconstruire l'objet à des résolutions différentes, avant d'avoir reçu le fichier en entier.

Dans le cas de "Progressiv Forest Flip Compression", l'idée est d'enlever des bandes de triangles sur l'objet et ensuite de refermer les trous laissés par ces bandes jusqu'à obtenir un maillage relativement simplifié lequel est codé à l'aide de deux arbres : un arbre couvrant sur les sommets et un autre sur les faces. Et ensuite lorsque l'on veut reconstruire la surface (la complexifier à partir du modèle le plus simple) on va découper selon certains arbres sur la surface, puis ouvrir et recoudre ces ouvertures à l'aide de bandes de triangles.

Dans l'autre méthode (Lossless Transmission of 3D Meshes), on parcourt la surface et lorsque l'on rencontre un sommet, on code son degré et on marque toutes les arrêtes incidentes. Et à chaque fois que l'on rencontre un sommet on compte les arrêtes qui n'ont pas encore été visitées. Au bout du compte, on va obtenir une suite de nombres qui représentent des degrés de sommets. Pour intégrer l'aspect multi-échelle, il va y avoir une succession de simplifications en ôtant un à un des sommets du maillage (maillage triangulaire) qui vont laisser des trous et ces trous sont retriangulés de manière implicite. Lorsque l'on veut faire l'opération inverse, il va falloir remplacer certains petits groupes de triangles par un sommet rejoignant les bords du trou laissé par ces triangles.
En ce qui concerne les chiffres : après l'étape de quantification (les coordonnées des sommets ne sont plus définis sur 64 bits, mais sur 10/12 bits), 15/20 bits par sommet suffisent (dont 4 bits/sommet pour la topologie ou connectivité du maillage).

Il y d'autres technologies, ce ne sont pas les seules. Certaines orientés vers le rendu, il s'agit d'envoyer assez vite les triangles au processeur graphique et de ne pas répéter plusieurs fois l'information des sommets. Le principe étant d'optimiser l'utilisation de la mémoire tampon du processeur graphique. Pour se faire les triangles que l'on va afficher seront formés en priorité à partir de sommets présents dans la mémoire tampon. Il y avait une méthode efficace qui a donné lieu à un chip hardware. Les taux de compression ne sont pas aussi impressionnants dans ce cas, l'objectif étant différant : parce que ce n'est pas tant de compresser mais de bien préparer les données pour le processeur graphique.

Oui sur certains maillages : on a rarement sur ce type de résultats des théorèmes ! On peut dire que sur la plupart des maillages que l'on rencontre que cela se passe bien et l'on obtient souvent plus de 80%. Dans un fichier Ascii il faut en effet compter environ 15 octets par sommet (pour chacune des 3 coordonnées des points avec 5 chiffres significatifs) puis un indice est affecté à chaque point. Cet indice va intervenir 6 fois puisqu'en moyenne un sommet appartient à 6 faces. La taille de l'indice dépend du nombre total de triangles (pour un objet de 10000 sommets on utilisera en moyenne 4 octets par indice). Cela fait 15 octets plus 6*4 = 24 octets, il va donc falloir en moyenne 40 octets par sommets (320 bits).
Ce chiffre est à raporter aux 17 bits de la méthode Lossless transmission of 3D meshes. On dépasse donc largement les 80%, c'est plutôt de l'ordre de 90% voir un peu plus. Sachant que pour des maillages très réguliers (formes lisses et sommets du même degré 6 on peut atteindre 99,..%.

Tout au début, alors que c'était la course aux formats de compression pour le VRML, il y avait une autre solution de compression lancé par Deering . Il s'agissait de former des bandes de triangles. L'idée était de ne coder qu'un seul indice par triangle. Mais l'on n'obtient par cette méthode pas les mêmes taux de compression.

Une des réponses les plus simples est sans doute le rendu. Il s'agit d'une représentation que l'on affiche le plus simplement. Dans le cas d'objets implicites les algorithmes de rendu sont plus complexes. Pour ces objets d'ailleurs, une étape de polygonisation est souvent nécessaire pour l'affichage. Une autre raison pour l'utilisation de maillage est l'acquisition par capteurs qui génère des fichiers de points qui sont facilement convertis en maillages traditionnels.