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 supprime l'affichage de tout
objet ou morceau d'objet masqué par un autre objet ou par lui même.
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, ...),
- ...
Principe du Z-Buffer
Le calcul de limage 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, chaque pixel calculé voit sa
"profondeur" comparée à celle déjà calculée en cette position image pour
pouvoir afficher finalement la facette la moins "profonde" présente en cette
position (vis à vis de l'observateur).
-> Il n'y a pas de tri des objets, mais un calcul de maximum, pour
chaque pixel de l'image, vis à vis de l'ensemble des objets présents en ce pixel.
Ne pas réaliser la séquentialisation 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 tailles identiques à la taille 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 est disponible en coordonnées image (coordonnées écran).
On décompose (rasterise) chaque surface s à afficher en l'ensemble des
pixels de coordonnées (x,y) qui la composeraient si elle était intégralement affichée
seule.
Au cours de la décomposition, on calcule la profondeur écran z de chaque
pixel de s de coordonnées image (x,y).
Si cette coordonnée 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 la surface s, de sources lumineuses, ...
Quand toutes les surfaces ont été traitées, l'image est disponible dans
le tampon couleur pour être affichée à l'écran.
Algorithme
Initialiser le
tableau PROF à -¥
Initialiser de 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 simple à
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
2 facettes à afficher
au moyen dun Z-Buffer
Rasterisation de chacune de ces facettes
Calcul daltitude pour chacun des pixels
de chacune des deux facettes
Affichage des pixels visibles
par comparaison des altitudes
(deux affichages possibles suivant
l'ordre de parcours des facettes)
|
Le programme GLUt |
Exécutable GLUt |
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).
Performances
Différentes unités de mesure de performance:
- taux de génération de pixels (pixels/seconde),
- segments/seconde,
- polygones/seconde.
Sur PC, de quelques dizaines de millions à plusieurs milliards de pixels
par seconde, de quelques dizaines de milliers à plusieurs dizaines de millions de
polygones par seconde (de quelques dizaines d' à plusieurs milliers d').
En constante évolution.
Conclusion
Intérêt
Algorithme facilement implantable.
Algorithme pouvant être optimisé (utilisation exclusive d'entiers,
utilisation de variantes de l'algorithme de Bresenham pour le tracé de segments).
Algorithme facilement implantable hard.
Algorithme facilement pipelinable et parallélisable.
Compatible de manière simple avec le calcul d'illumination de Gouraud
et le placage 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 Mo dans le cas de grands écrans). 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 50 Mips pour 100000 facettes/s) et une
vitesse d'accès mémoire très élevée (mémoire spécifique -> plus chère).
Des techniques incrémentales (Bresenham) permettent toutefois d'optimiser les
performances par l'utilisation de variables entières et d'opérations simples (additions
et comparaisons).
Pas de gestion intrinsèque simple des phénomènes de réflexion
spéculaire et de transmission.
Pas de gestion implicite des ombres portées.
-> Difficultés pour implanter la modélisation de phénomènes optiques complexes.
-> Algorithme standard pour l'obtention en temps réel d'images de
qualité moyenne.
-> Application à la conception et fabrication assistée par ordinateur
(station de travail graphique), à la réalité virtuelle et au jeu. |