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.
|