Le Z-Buffer

 

INTRODUCTION

PRINCIPE

IMPLANTATION

ALGORITHME

EXEMPLE

IMPLANTATION PRATIQUE

PERFORMANCES

CONCLUSION

 

Version
texte long

RETOUR

 

 

 

Introduction

L'algorithme du Z-Buffer est un algorithme d'élimination des parties cachées.
-> Lors de la visualisation d'une scène, cet algorithme calcule l'image de manière que l'affichage de tout objet ou morceau d'objet masqué par un autre objet ou par lui même soit supprimé.

Algorithme conçu au milieu des années 70.

Autres algorithmes d'élimination des parties cachées:

  • Algorithme du peintre
  • Algorithmes de la ligne de balayage (scanline)
  • Algorithmes par subdivision de l'image (Warnock, ...)
  • ...

Sans Z-Buffer
Facette verte
puis facette rose

Sans Z-Buffer
Facette rose
puis facette verte

 
Avec Z-Buffer
Facette rose puis verte, facette verte puis rose

Programme GLUt

Exécutable GLUt

Espace pour switcher entre les affichages

Principe du Z-Buffer

Le calcul de l’image est effectué séquentiellement en traitant les objets extraits de la scène (classiquement des facettes triangulaires) les uns à la suite des autres pour en extraire l'intégralité des pixels qui les représentent.
Au cours du processus de traitement d'un objet, la "profondeur" écran (de -¥, le plus profond possible, à +¥, le moins profond possible) de chaque pixel calculé est comparée à celle déjà calculée en cette position image.
En fonction du résultat de cette comparaison, la couleur du pixel est:
  - soit inchangée si la profondeur calculée établit que l'objet en cours de traitement est derrière,
  - soit affectée avec la couleur de l'objet en cours de traitement, s'il est devant.
On gère ainsi, pour chaque pixel de l'écran, une recherche de maximum dans le but d'afficher finalement l'objet le moins profond présent en cette position (vis à vis de l'observateur).
  -> Il n'y a pas de tri des objets et donc pas de problème de non-linéarité intrinséque du temps d'exécution.

Ne pas réaliser la séquentialisation principale sur les pixels mais sur les objets a beaucoup d'intérêts:

  • optimisation des calculs,
  • algorithme en temps linéaire du nombre de facettes,
  • possibilité de commencer le calcul de l'image sans connaître l'intégralité de la scène,
  • ...

Implantation

On définit deux zones mémoire de résolutions identiques à la résolution de l'image que l'on souhaite calculer:

  • Un tampon couleur destiné à contenir la couleur de chacun des pixels de l'image (initialisé à la couleur de fond souhaitée)

  • Un tampon profondeur destiné à contenir la profondeur écran maximum de chacun des pixels de l'image (initialisée à -¥, utilisée comme valeur courante de comparaison en cours d'exécution du Z-Buffer)

La scène a été pré-traitée et est donc disponible en coordonnées écran.

On décompose (rasterise) chaque objet o à afficher en l'ensemble des pixels de coordonnées (x,y) qui le composeraient s'il était intégralement affiché seul.

Au cours de la décomposition, on calcule la profondeur écran z de chaque pixel de o de coordonnées image (x,y).

Si cette coordonnée z est plus grande que celle déjà présente dans le tampon profondeur aux coordonnées (x,y), la nouvelle profondeur en (x,y) devient z et la couleur du pixel (x,y) du tampon couleur est réaffectée avec une valeur calculée en fonction de x, de y, des caractéristiques de l'objet o, de sources lumineuses, ...

Quand tous les objets ont été traités, l'image est disponible dans le tampon couleur pour être affichée à l'écran.

Algorithme

Initialiser le tableau PROF à -¥
Initialiser le tableau COUL
            à la couleur de fond
Pour chaque objet o de la scène à représenter
  Pour chaque pixel p=(x,y) de o
    Calculer la profondeur z de p=(x,y) ;
    Si z > PROF(x,y) alors
      PROF(x,y) = z ;
      COUL(x,y) = couleur(o,x,y) ;
    Finsi
  Finpour
Finpour

Les objets sont très fréquemment des facettes planes triangulaires car ce sont des surfaces simples à rastériser au moyen de variantes de l'algorithme de Bresenham.
Pour ce type d'objet, le calcul de la profondeur écran nécessaire à la rastérisation se marie bien avec l'opération de remplissage et entraîne donc un surcoût de calcul peu important.

Exemple

 

Deux facettes à afficher au moyen d’un Z-Buffer


Les deux facettes avec les coordonnées de leurs sommets
facette (1) en rose, facette (2) en vert


Rasterisation de la facette (1)
avec calcul des z de ses pixels


Rasterisation de la facette (2)
avec calcul des z de ses pixels

Résultat obtenu pour le calcul
des z maximum en chaque pixel
en fonction de l'ordre de traitement des facettes
A gauche : facette (1) puis facette (2)
A droite : facette (2) puis facette (1)

Programme GLUt

Exécutable GLUt

 

Z-Buffer sur deux facettes


Les deux facettes


Résultat du ZBuffer avec des "gros" pixels

Programme GLUt

Exécutable GLUt

Enter pour switcher entre les différents affichages
Espace pour switcher entre les modes d'affichage
fil de fer et plein
b pour switcher entre les affichages
sans et avec les triangles réels matérialisés par leurs cotés
c pour activer/désactiver l'élimination des parties cachées
Touches de curseur et souris pour manipuler la scène
Z-Buffer sur deux facettes
avec différentes tailles de pixel virtuel


Les deux facettes

 

 

 

Programme GLUt

Exécutable GLUt

Enter pour switcher entre les différents affichages
+/ pour augmenter/diminuer la taille des pixels
Espace pour switcher entre les modes d'affichage
fil de fer et plein
b pour switcher entre les affichages
sans et avec les triangles réels matérialisés
par leurs cotés
c pour activer/désactiver l'élimination des parties cachées
Touches de curseur et souris pour manipuler la scène

Implantation pratique

On dispose de facettes triangulaires dont les sommets sont connus en coordonnées écran.

Problèmes:

  • Établir quels sont les pixels recouvrant chacune des facettes : Remplissage 2D.
  • Calculer l'altitude de chacun de ces pixels.

Solution au premier problème: Trouver les pixels sur les cotés droit et gauche de la facette traitée. Tracer la trame horizontale entre le couple de pixels de chaque ligne de pixels sur laquelle la facette apparaît.

Solution au second problème: Travailler le remplissage 2D en gérant z en paramètre supplémentaire (pour optimiser les calculs, mariage de la gestion de z avec l'algorithme de remplissage 2D).

Problème (1) : Remplissage d'une facette 2D
Remplissage classique de type "FillPoly"


Facette à remplir

Extraction des bords

Remplissage trame horizontale
après trame horizontale

Remplissage final

Comparaison entre le triangle initial
matérialisé par ses cotés
et les pixels rastérisés dessinés en fil de fer

Programme GLUt

Exécutable GLUt

Enter pour switcher entre les différents affichages
Espace pour switcher entre les modes d'affichage
fil de fer et plein
b pour switcher entre les affichages
sans et avec les triangles réels matérialisés par leurs cotés
c pour activer/désactiver l'élimination des parties cachées
t pour afficher une facette 2D ou une facette 3D
Touches de curseur et souris pour manipuler la scène

 


Même triangle que ci-dessus vu d'un autre
point de vue qu'en projection selon l'axe -z
de projection écran normale

Affichage en fil de fer des pixels obtenus
par rasterisation des cotés
Dessin de ces pixels en tant que carrés
dessinés dans le plan xy

Remplissage progressif trame après trame

Résultat final avec matérialisation du triangle initial

Programme GLUt

Exécutable GLUt

Enter pour switcher entre les différents affichages
Espace pour switcher entre les modes d'affichage
fil de fer et plein
b pour switcher entre les affichages
sans et avec les triangles réels matérialisés par leurs cotés
c pour activer/désactiver l'élimination des parties cachées
t pour afficher une facette 2D ou une facette 3D
Touches de curseur et souris pour manipuler la scène

Performances

Différentes unités de mesure de performance avec élimination des parties cachées:

  • Taux de génération de pixels (pixels/seconde)
  • Segments/seconde
  • Polygones/seconde
  • ...

Sur PC, de quelques centaines de millions à plusieurs centaines de milliards de pixels par seconde, de quelques centaines de milliers à plusieurs centaines de millions de polygones par seconde (de quelques dizaines d'€ à plusieurs milliers d'€).

En constante évolution.

Conclusion

Intérêt

  • Algorithme facilement implantable. Quelques centaines de lignes de code.

  • Algorithme pouvant être optimisé (utilisation exclusive d'entiers et d'opérations élémentaires, utilisation de variantes de l'algorithme de Bresenham pour le tracé de segments).

  • Algorithme "facilement" implantable hard.

  • Algorithme "facilement" parallélisable.

  • Compatible de manière simple avec le calcul d'illumination de Gouraud et le plaçage de texture.

  • Gestion implicite des recoupements entre objets.

  • Exécution en un temps en o(n) du nombre de facettes -> bonne scalabilité.

Inconvénients

  • Les deux zones tampon peuvent avoir des tailles très importantes (plusieurs dizaines de Mo dans le cas d'écrans haute résolution). Actuellement, ce n'est plus véritablement un problème.

  • La décomposition de chaque surface élémentaire en pixels nécessite une puissance de calcul importante (de l'ordre de la centaine de Mips pour 100000 facettes/s pour des facettes de 100 pixels de surface moyenne) et une vitesse d'accès mémoire très élevée (mémoire spécifique -> plus chère).

  • Pas de gestion intrinsèque des phénomènes relatifs à l'éclairage des objets par des lumières.
     - Première possibilité : Un prétraitement est réalisé visant à attribuer une couleur à chaque sommet de chaque facette en fonction des lumières présentes dans la scène. Un dégradé de couleur (Gouraud) est opéré pour les pixels de rasterisation (OpenGL 1.0).
     - Seconde possibilité : La couleur de chaque pixel de rasterisation est calculée en fonction des lumières présentes dans la scène (OpenGL 2.0 via l'écriture d'un shader).

  • Pas de gestion implicite des ombres portées.

-> Algorithme standard pour l'obtention en temps réel d'images de qualité moyenne pour des scènes complexes.

-> Application à la conception et fabrication assistée par ordinateur (station de travail graphique), à la réalité virtuelle, à la réalité augmentée et au jeu.

-> Pas d'application à la génération d'images photo-réalistes car méthode de rendu trop limitée fonctionnellement.