1. Représentation des formes

Les capacités d'un ordinateur, aussi puissant soit-il, sont limitées en stockage, mémoire et puissance de calcul. Comment représenter des formes complexes avec ces limitations ?

Maillages de surfaces

La première étape consiste à choisir de ne représenter que le bord, la surface des formes à représenter. C'est suffisant pour un grand nombre d'applications, comme la visualisation d'objets opaques. Une seconde étape consiste à décomposer la surface en primitives géométriques simples, des polygones. On appelle maillage cet ensemble de polygones, reliant un ensemble de points, les sommets des polygones. Les maillages composés uniquement de triangles sont courants du fait de leur simplicité. Le nombre de polygones représentable par l'ordinateur étant limité, on ne peut en pratique qu'espérer approcher la surface originale. C'est toutefois exploitable à condition d'utiliser un nombre suffisant de polygones pour l'application visée.

Différents maillages de la statue du David de Michel-Ange, du plus simple au plus détaillé.

Les maillages sont très répandus dans les applications qui exploitent des formes. Il n'est pas rare d'utiliser des maillages comprenant des milliers de polygones pour des jeux en 3 dimensions - une carte graphique moderne peut ainsi afficher 180 millions de triangles par seconde - voire plusieurs millions pour des simulateurs de vols. Les maillages sont aussi devenus un outil clé de l'ingénierie numérique , en permettant la modélisation de formes complexes, leur visualisation et la simulation de phénomènes physiques.

Visualisations pour la médecine, l'histoire de l'art, la topographie, les jeux vidéos, les boutiques virtuelles, la conception, les simulateurs de vol : les applications des maillages sont multiples.

Le développement vertigineux des capacités des ordinateurs autorise la modélisation de maillages de plus en plus précis, et la visualisation de formes de plus en plus complexes. Prenons l'exemple de la statue du David de Michel-Ange. 700 000 triangles suffisent pour reconnaître la statue dans une application multimédia, mais il en faut près de 2 milliards pour retrouver les traces de l'outil utilisé par le sculpteur pour une application en histoire de l'art (Digital Michelangelo ).

Cette évolution, qui offre un gain en fidélité pour la simulation, et en réalisme pour la visualisation par images de synthèse, s'accompagne d'une explosion des tailles des fichiers utilisés pour représenter les maillages (plus de 32 milliards d'octets pour la statue du David en très haute résolution). La compression de maillage devient alors essentielle pour exploiter de telles quantités de données.

Approximation de la statue du David par un maillage comprenant 700 000 triangles et 350 000 sommets. (La statue réelle mesure 5 mètres de haut.)

La compression est motivée par le stockage et les applications en réseau. En effet, le débit d'un réseau est limité, voire variable dans le temps, en fonction de l'encombrement. On cherche en particulier à réduire la latence, le temps d'attente lié au temps de transmission. Il en résulte une meilleure qualité de service, l'objectif prioritaire d'un opérateur de télécommunications.

Représentation d'un maillage

Avant de détailler la compression, voyons comment un maillage de surface peut être représenté simplement dans un ordinateur. Le fichier de description du maillage contient les informations sur les deux composantes principales du maillage, sa géométrie et sa connectivité.

• La géométrie correspond à une liste de points, les sommets des polygones. Cette liste décrit les coordonnées tridimensionnelles (x,y,z) des points :

  x1 y1 z1 (sommet 1)
  x2 y2 z2 (sommet 2)
  x3 y3 z3 (sommet 3)
  ...

• La connectivité décrit comment les points sont reliés entre eux pour assembler les faces. Un triangle relie trois points, un quadrilatère relie 4 points, un pentagone relie 5 points, etc. Chaque face est décrite par la liste de ses sommets, chaque sommet étant représenté par son indice dans la liste de points et non par ses coordonnées. On parle de format indexé. La connectivité est donc une information combinatoire, car elle ne consiste qu'en une information d'identification de sommets dans une liste finie de points.

  1 3 5 (face 1)
  3 4 5 (face 2)
  4 6 5 (face 3)
  ...

Quelle taille de fichier pour un format indexé ?

On peut calculer la taille d'un fichier d'un format indexé en nombre de bits par sommet. Prenons le cas d'un maillage triangulaire. La liste des sommets énumère trois coordonnées (x,y,z) par sommet. Si pour représenter chaque coordonnée, on utilise des nombres flottants stockés sur 32 bits - un format standard pour le calcul en virgule flottante - alors chaque sommet utilisera 3 x 32 = 96 bits. Il y a environ deux fois plus de faces (ou triangles) que de sommets. Si on énumère pour chaque triangle trois indices entiers positifs ou nuls stockés sur 32 bits, il en résulte 2 x 3 x 32 = 192 bits par sommet pour l'information combinatoire. La somme des informations combinatoire et géométrique résulte en 192 + 96 = 288 bits par sommet. Par exemple, la statue du David comprenant 700 000 faces occupe 12.6 Mo dans un format indexé binaire, et davantage pour le format indexé ASCII OBJ , qui nécessite 27 Mo car le fichier comprend des espaces, des caractères de contrôle (v et f) ainsi que des sauts de ligne.

Mentionnons qu'un format de fichier peut également représenter des attributs associés aux primitives du maillage, comme des couleurs par face ou par sommet, des coordonnées de texture, des matériaux qui gouvernent l'interaction entre la lumière et la matière lors du rendu, etc.