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, ...)
- ...
|
||||||||
| 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,
- ...
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.
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.
|
Deux facettes à afficher au moyen d’un Z-Buffer |
|
|
Résultat obtenu pour le calcul
| Z-Buffer sur deux facettes |
|
|
|
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 |
|
|
|
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 |
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 |
|
|
|
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 |
|
|
|
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 |
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.
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.