Le point 3D comme primitive de rendu

Figure 1.5: Objet 3D représenté sous forme d'un nuage de points (sous échantillonné pour les mettre en évidence)
\includegraphics[%
width=1.0\columnwidth,
height=4cm,
keepaspectratio]{eps/ea-points-cloud-tore.eps}

Partant de ces constatations, Levoy et Whitted en 1985 [LW85] ont été les premiers à proposer d'utiliser des points comme unique primitive de rendu. Leur méthode permet de modéliser et d'afficher avec des points une surface 3D continue texturée.

Tout d'abord la scène définie par un maillage de polygones est transformée en un ensemble de points. Cet ensemble de points est généré par discrétisation régulière de la surface à l'aide des coordonnées de texture : il est donc défini comme une grille 2D de points de coordonnées $ (u,v)$ dans l'espace de la texture. Chaque point de cette grille stocke la position 3D de la surface $ (x,y,z)$ ainsi que la couleur $ (r,v,b)$ du point . Ce mode de représentation permet d'appliquer des déformations à l'objet, comme le déplacement de points1.6 (displacement mapping) exemple typique de modélisation de surface très coûteux à afficher.

Cet ensemble de points déplacés est ensuite transformé et projeté à l'écran. La contribution de chaque point projeté à la couleur d'un pixel donné de l'écran est fonction de sa distance avec le centre de ce pixel, maximum au centre et décroissante en fonction de l'éloignement. Pour calculer cette contribution, la distance point/pixel est pondérée par une fonction d'atténuation, représentée par un filtre Gaussien. Un point projeté contribue donc à plusieurs pixels de l'image, et est appelé Splat [Wes90]. Dans leur méthode, ceci permet d'éviter les trous dus aux zones sous échantillonnées1.7, d'antialiasser les bordures de l'objet et de gérer la visibilité des points (avec l'utilisation d'un A-buffer [Car84] modifié). Les points peuvent être dessinés dans n'importe quel ordre, l'image se construisant au fur et à mesure qu'ils sont projetés. Ainsi Levoy et Whitted proposent dans leur conclusion d'utiliser leur méthode pour afficher la scène de façon graduelle : l'utilisateur visualiserait d'abord une version vectorielle (ou ''fil de fer'' ) de l'objet pour choisir son point de vue, puis quand il a choisi, les points seraient progressivement affichés de façon à donner une première version grossière de la scène. Ce principe permettant une visualisation en temps réel du modèle sera utilisé de façon étendue dans les QSplat [RL00].

Les avantages de cette méthode sont d'une part une haute qualité de rendu (bordures et surfaces antialiassées quelle que soit la finesse de la géométrie originelle) et d'autre part la rapidité d'affichage. De plus, comme les points 3D projetés ne sont pas connectés, un traitement en parallèle est possible. Néanmoins, l'image peut paraître floue quand le sous-échantillonnage est trop important ou que le noyau Gaussien utilisé est trop grand.

Grossman [Gro98] étend le principe de l'utilisation de points comme primitive de rendu et modélisant un objet sous la forme d'un ensemble dense de points. Les points sont acquis automatiquement à partir de la projection orthogonale d'un modèle géométrique conventionnel selon différents angles, jusqu'à obtenir un échantillonnage suffisant. Puis les points sont affichés et les trous comblés en utilisant la technique du push-pull1.8[GGSC96] sur une hiérarchie de tampons de profondeurs.

Le rendu à base de points est devenu plus récemment d'actualité avec l'apparition des scanners LASER qui numérisent une surface 3D sous forme de trames de points. Avec le projet Italien ''The Digital Michaelangelo Project : 3D scanning of large statues'' [LPC+00], des modèles composés de centaines de millions de points sont devenus courants et leur affichage nécessitait une technique adaptée. L'utilisation d'un maillage polygonal standard basé sur un tel nuage de points est tellement coûteuse en temps de rendu qu'il est en pratique impossible de l'afficher en temps réel, sans parler de la taille en mémoire d'une telle structure. Avec les progrés récents des cartes graphiques, il est devenu possible d'effectuer le rendu de millions de points par seconde.

Rusinkiewicz et Levoy [RL00] ont développé un système de rendu à base de points appelé QSplat permettant d'afficher en temps réel de telles structures numérisées. Dans cette méthode, les points sont répartis dans une structure hiérarchique de sphères englobantes permettant d'effectuer les tests de visibilité et de gérer des niveaux de détails pour le rendu. Chaque noeud de l'arbre contient le centre de la sphère, son rayon, un cône de visibilité1.9 et éventuellement une couleur1.10. Lors du rendu, l'arbre est parcouru jusqu'aux feuilles, représentant un point isolé, ou jusqu'à ce que l'aire de la sphère d'un noeud, projetée sur l'écran, soit inférieure à un certain seuil. Le seuil permet de contrôler le niveau de détail que l'on souhaite : plus le seuil est grand, plus on affiche les noeuds de faible profondeur, c'est à dire que l'on affiche une version approximative du modèle. Chaque sphère (noeud ou feuille) est donc projetée sur l'écran avec une taille basée sur son diamètre apparent. Le calcul de la couleur de la sphère projetée est basé sur le modèle d'éclairement de Phong et utilise les informations stockées dans le noeud (normale et couleur). La taille d'une sphère englobante de la hiérarchie est choisie de façon à ce qu'elle chevauche légèrement les sphères du niveau inférieur afin d'éviter les trous. Le rendu est effectué en utilisant le tampon de profondeur pour résoudre les problèmes de visibilité.

Trois différentes primitives sont utilisées pour l'affichage des points : le point OpenGL (un carré), le cercle (un polygone avec une texture représentant un disque) et un ''point flou'' (un billboard, cf. section 1.4.2.1) dont l'opacité baisse radialement selon une Gaussienne. Des ellipses orientées en fonction de la direction d'observation1.11 peuvent être utilisées pour améliorer le rendu des bordures, mais elles générerent des trous et ralentissent les performances.

Au final, cet algorithme peut afficher de 1,5 à 2,5 millions de points par secondes sur des machines de milieu de gamme (Processeur de 1Ghz). Il permet également un affichage adaptif : l'utilisateur navigue autour de l'objet avec un affichage rapide et approximatif puis l'affichage se raffine automatiquement quand il arrête de se déplacer.

Les données (points, sphères et hiérarchies) sont toutes quantifiées et représentées sur un nombre optimal de bits de façon à réduire au maximum l'espace nécessaire en mémoire. Notamment, les positions des points contenus dans une sphère sont relatives à la sphère de niveau supérieur.

Porquet Damien 2005-03-02