Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Informatique graphique: Méthodes et modèles (2° Ed.)

De
420 pages
L'informatique graphique est née il y a près de trente-cinq ans maintenant et elle s'est depuis considérablement développée, pénétrant de nombreux domaines industriels comme l'architecture et l'urbanisme, l'audiovisuel, la CAO, la chimie, la médecine, le multimédia, la simulation, la visualisation scientifique, ... Dans ce livre, les auteurs décrivent les méthodes et les algorithmes utilisés pour produire des images de synthèse. Outre des techniques de base comme des éléments de mathématiques et de théorie du signal, les courbes et les surfaces et les algorithmes et structures de données bidimensionnels, ce livre aborde les problèmes de la modélisation géométrique, de la couleur et des modèles d'éclairement et décrit les algorithmes d'élimination des parties cachées, de calculs d'éclairement et texturation. Ce livre présente donc à la fois les fondements de l'informatique graphique et un tour d'horizon des problèmes auxquels celle-ci est confrontée. Il est destiné aux chercheurs dans ce domaine, aux étudiants de 3ème cycle, aux ingénieurs utilisant les images de synthèse et aux étudiants de second cycle ou d'écoles d'ingénieurs suivant des cours d'informatique graphique.
1. Architectures logicielles et matérielles pour la visualisation Le pipeline graphique - Bases générales de l'infographie - Systèmes graphiques 2. Eléments de mathématiques et de théorie du signal Notions géométriques - Echantillonnage régulier, aliassage et antialiassage - Quelques notions d'analyse numérique 3. Courbes et surfaces Introduction - Courbes paramétriques - Surfaces paramétriques - Les surfaces implicites (ou objets mous) 4. Algorithmes et structures de données 2D Affichage de segments de droite - Intersection entre segments - Représentation des polygones - Angles et orientation - Polygones et intersections - Tests d'inclusion dans un polygone - Remplissage - Décomposition des polygones - Les cartes planaires - Carte des trapèzes - Tracés de courbes dans une mémoire d'image - Intersection entre courbes - Quelques difficultés récurrentes - Aliassage et antialiassage 5. Modélisation géométrique Présentation de la modélisation du solide - La représentation par frontières - La représentation constructive - L'énumération spatiale - La partition spatiale - La tétraédrisation - Quelques représentations hybrides - Evaluation des frontières - L'avenir de la modélisation du solide - Critères d'évaluation d'une représentation - Quelques problèmes en modélisation du solide - Les fractales - Les systèmes de particules et la modélisation par masses-ressorts - Les représentations dédiées 6. La couleur La physique de la lumière - La perception des couleurs - La colorimétrie - Problèmes d'affichage sur un moniteur couleurs 7. Modèles d'éclairement Notions sur les ondes électromagnétiques - Notions de radiométrie et de photométrie - L'équation de rendu - Modèles d'éclairement 8. Elimination des parties cachées Le fenêtrage - Le tampon de profondeur - La méthode d'Atherton et celle de Watkins - Une méthode du peintre, utilisant un arbre de partition spatiale - La méthode de Warnock - Le calcul des ombres portées - La représentation des scènes extrêmement complexes 9. Le tracé de rayons Présentation du tracé de rayons - Calculs d'intersections - Algorithmes de rendu - Techniques d'accélération - Antialiassage et lancer de rayons 10. Algorithmes d'éclairement Algorithmes de lissage - Essai de description des méthodes d'éclairement - Méthodes de Monte Carlo - La radiosité classique - Extensions de la radiosité 11. Textures Problématique des textures planes - Textures 3D - Hypertextures - Génération par évolution - Génération par réaction et diffusion Bibliographie - Index
Voir plus Voir moins

collection Informatique
Informatique
graphique
méthodes et modèles
e2 édition revue et augmentée
Bernard Péroche
Djamchid Ghazanfarpour
Dominique Michelucci
Marc Roelens
HERMES Informatique graphique REMERCIEMENT S
A Marie Line Barnéoud, Jean-Michel Dischler, Jean-Michel Moreau, les
thésard s du LISSE (Laboratoire d'Images de Synthèse de Saint-Etienne),
qui nous ont aidés à la réalisation de ce livre.
© Editions HERMES, Paris, 1991, 1998
Edition s HERMES
8, quai du Marché-Neuf
75004 Paris
r eISB N 2-86601-112-0, l édition 1988, 1990
r eTitre original de la l édition : La synthèse d'images
e
ISB N 2-86601-652-1, 2 édition, 1998
ISS N 0993-5037
Catalogage Electre-Bibliographie
Péroche, Bernard*Ghazanfarpour, Djamchid*Michelucci, Dominique*Roelens, Marc
Informatique graphique. - Paris : Hermès, 1998.
ISBN 2-86601-652-1
RAMEAU : infographie : modèles mathématiques
géométrie algorithmique
DEWEY : 006.3 : Méthodes informatiques spéciales.
Infographie et systèmes multimédias
Le Code de la propriété intellectuelle n'autorisant, aux termes de l'article L. 122-5, d'une
part, que les "copies ou reproductions strictement réservées à l'usage privé du copiste et non
destinées à une utilisation collective" et, d'autre part, que les analyses et les courtes citations
dans un but d'exemple et d'illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l'auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4).
Cette représentation ou reproduction, par quelque procédé que ce soit, constituerait donc
une contrefaçon sanctionnée par les articles L. 335-2 et suivants du Code de la propriété
intellectuelle. Informatique
graphique
méthodes et modèles
e2 édition revue et augmentée
Bernard Péroche
Djamchid Ghazanfarpour
Dominique Michelucci
Marc Roelens
HERMES EXTRAIT DU CATALOGUE GÉNÉRAL
eLe multimédia et le droit, off line, on line, Internet, 2 édition revue
et augmentée, Mémento-guide, Alain BENSOUSSAN, 1998 .
Manue l d'optique, Germain CHARTIER, 1997 .
La conception en communication, méthodologie qualité,
Sylvie LELEU-MERVTEL, 1997 .
Le multimédia pour l'entreprise, Patrick MADDALENA, 1997 .
Triangulation de Delaunay et maillage, applications aux éléments finis,
Paul-Louis GEORGE, Houman BOROUCHAKI, 1997 .
eUNIX, utilisation Administration système et réseau, 2 édition revue
et augmentée, Christian PÉLISSIER, 1996.
Technique s de compression des images , Jean-Paul GUILLOIS, 1996 .
Introductio n au traitement du signal, exercices, corrigés et rappels de
cours, Patrick DUVAUT, François MICHAUT, Michel CHUC, 1996 .
eVision par ordinateur, outils fondamentaux, 2 édition revue et augmentée,
Rad u HORAUD, Olivier MONGA, 1995 .
eCompressio n et cryptage des donnéee s multimédias, 2 édition revue
et augmentée, Xavier MARSAULT, 1995 .
La dérivation non entière, théorie, synthèse et applications,
Alain OUSTALOUP, 1995 .
e
Traitemen t du signal, concepts et applications, 2 édition revue
et complétée, Patrick DUVAUT, 1994 .
Géométri e discrète en analyse d'image, Jean-Marc CHASSERY,
Annic k MONTANVERT, 1991 .
Modélisatio n et construction de surfaces pour la CFAO,
Jean-Claud e LÉON, 1991 .
Serveu r web : http://www.editions-hermes.fr Table des matières
Avant-propos '7
Chapitre 1. Architectures logicielles et matérielles pour la visualisation . 19
1.1. Le pipeline graphique 19
1.1.1. Introduction
1.1.2. Les attributs graphiques 21
1.1.3. Less de visualisation2
1.1.3.1. Attributs de prise de vue
1.1.3.2. Attribut d'affichage3
1.1.4. Calculs pour la visualisation4
1.1.4.1. Des calculs géométriques
1.1.4.2. Dess de rendu5
1.1.5. Les processus de base
1.1.6. Diverses approches pour les logiciels graphiques 26
1.1.6.1. Systèmes spécialisés 2
1.1.6.2.s généraux
1.2. Bases générales de l'infographie8
1.2.1. Architecture logique d'un système graphique 2
1.2.1.1. Le module pilote
1.2.1.2. Lee graphique
1.2.1.3. Le module vidéo9
1.2.2. Eléments de technologie 2
1.2.2.1. Les tubes à rayons cathodiques (TRC)
1.2.2.2. Les systèmes à balayage de trame 30
1.2.2.3. Systèmes graphiques couleur1
1.2.2.4. Les mémoires d'image
1.2.2.5. Les tables de couleurs6 Informatique graphique
1.3. Systèmes graphiques 32
1.3.1. Un modèle pour les stations graphiques 33
1.3.2. Architecture des stationss
1.3.3. Performances graphiques4
1.3.4. Un exemple d'architecture : celle de Silicon Graphics 36
1.3.4.1. Le sous-système géométrique7
1.3.4.2. Le sous-système de discrétisation9
1.3.4.3. Sous-système d'affichage 40
Chapitre 2. Eléments de mathématiques et de théorie du signal 41
2.1. Introduction 4
2.2. Notions géométriques
2.2.1. Les repères de la synthèse d'images1
2.2.2. Géométrie vectorielle2
2.2.2.1. Introduction
2.2.2.2. Opérations3
2.2.2.2.1. Définitions
2.2.2.2.2. Propriétés4
2.2.2.3. Combinaisons linéaires 45
2.2.2.4. Produits scalaire, vectoriel et mixte6
2.2.2.5. Notions de base et de coordonnées7
2.2.2.6. Transformations affines9
2.2.2.6.1. Définition
2.2.2.6.2. Coordonnées homogènes et matrices 4
2.2.2.6.3. Transformations affines classiques 51
2.2.2.7. Changements de repère 54
2.2.2.7.1. Formule de changement de repère
2.2.2.7.2. Usage des changements de repère6
2.2.3. Projections7
2.2.3.1. Les projections parallèles
2.2.3.2. Less perspectives
2.2.4. Conclusion 59
2.3. Echantillonnage régulier, aliassage et antialiassage 60
2.3.1. Introduction 6
2.3.2. Fondements théoriques de l'aliassage et liens avec les images
de synthèse
2.3.2.1. Echantillonnage régulier monodimensionnel et aliassage . 6
2.3.2.1.1. Premier cas : f > 2f2 e ma x
2.3.2.1.2. Deuxième cas : f < 2f 63 e ma x
2.3.2.2. Antialiassage et reconstitution
2.3.2.2.1. Augmentation de la fréquence d'échantillonnage .. . 6Table des matières 7
2.3.2.2.2. Limitation du spectre fréquentiel du signal analogique 63
2.3.2.3. Echantillonnage régulier bidimensionnel et reconstitution . 64
2.3.2.3.1.el sans aliassage ... . 65
2.3.2.3.2. Echantillonnagel avece ... .
2.3.2.4. Antialiassage bidimensionnel dans le cas d'un échantillonnage
régulier 66
2.3.2.5. Méthodes générales d'antialiassage en informatique
graphique7
2.3.2.5.1. Augmentation des fréquences d'échantillonnage et
contraintes technologiques
2.3.2.5.2. Limitation du spectre fréquentiel de l'image 68
2.3.3. Echantillonnage stochastique
2.3.4. Filtrage bidimensionnel dans le domaine spatial 71
2.3.5. Aspects psychovisuels 72
2.3.5.1. La réponse quasilogarithmique
2.3.5.2. Sensibilité aux zones de transition3
2.3.5.3. Distribution de Poisson4
2.4. Quelques notions d'analyse numérique
2.4.1. Résolution d'une équation algébrique à une inconnue : f(x) = 0 . 7
2.4.1.1. Formule explicite
2.4.1.2. Algèbre linéaire 75
2.4.1.3. Le théorème de Sturm [KNU 81]
2.4.1.3.1. Rappels sur le théorème de Sturm
2.4.1.3.2.s sur les bornes des zéros d'un polynôme ... 7
2.4.1.4. L'analyse par intervalles (cf. 2.4.3) 76
2.4.1.5. Par continuité
2.4.1.6. Par subdivision dans la base de Bemstein
2.4.2. La méthode de Newton-Raphson8
2.4.3. L'arithmétique d'intervalles et l'analyse par intervalles 79
2.4.4. Notion de résultants 83
2.4.4.1. L'implicitisation [SED 95]4
2.4.4.2. Le calcul des points d'intersection 8
2.4.4.3. L'inversion [MAN 93]5
Chapitre 3. Courbes et surfaces7
3.1. Introduction 8
3.2. Courbes paramétriques8
3.2.1. Interpolation polynômiale
3.2.1.1. Utilisation de la base canonique 8
3.2.1.2.n de la base de Lagrange
3.2.1.3. Utilisation de la base de Newton9 8 Informatique graphique
3.2.2. Interpolation polynômiale par morceaux 91
3.2.3. Lissage 92
3.2.3.1. Courbes de Bézier
3.2.3.1.1. Définition
3.2.3.1.2. Forme polynômiale 94
3.2.3.1.3. Fonctions de Bernstein5
3.2.3.1.4. Propriétés des courbes de Bézier6
3.2.3.2. B-splines debase8
3.2.3.3.s 100
3.2.3.4. B-splines1
3.2.3.5. Formes rationnelles (NURBS) 103
3.3. Surfaces paramétriques4
3.3.1. Carreaux de surface d'interpolation
3.3.2. Produit tensoriel
3.3.2.1. Surfaces de Bézier5
3.3.2.2.s B-splines 106
3.4. Les surfaces implicites (ou objets mous)
3.4.1. Définition7
3.4.2. Les fonctions de potentiel
3.4.3. Less de distance9
3.4.4. Difficultés
Chapitre 4. Algorithmes et structures de données 2 D 111
4.1. Introduction 11
4.2. Affichage de segments de droite
4.3. Intersection entre segments4
4.3.1. Quelques méthodes naïves
4.3.1.1. Algorithme naïf
4.3.1.2.e par partition 115
4.3.2. Technique de balayage
4.4. Représentation des polygones7
4.4.1. Représentation par contours8
4.4.2.n par arêtes orientées9
4.4.3. Triangulation et convexification
4.4.4. Cartes planaires 11
4.4.5.s des trapèzes
4.4.6. Conversion entre les diverses représentations des polygones . . 120
4.5. Angles et orientation 120
4.5.1. Mesure d'un angle
4.5.2. Virage à gauche, virage à droite1
4.5.3. Orientation d'un contourTable des matières 9
4.6. Polygones et intersections 122
4.6.1. Coupe d'un polygone par une droite
4.6.2. Coupe d'une représenté par des contours 123
4.6.3. Fenêtrage d'un polygone4
4.6.4. Intersection, réunion, différence de deux polygones
quelconques
4.7. Tests d'inclusion dans un polygone
4.7.1. Inclusion d'un point dans un polygone non auto-intersectant... 124
4.7.2. Intérieur d'un polygone auto-intersectant 125
4.7.3. Inclusion dans un polygone convexe6
4.7.4. Boîte englobante 12
4.7.5. Localisation d'un point7
4.8. Remplissage8
4.8.1. Coloriage de taches
4.8.2. Affichage d'un polygone quelconque
4.8.3. Cas particuliers de coloriage9
4.8.3.1. Coloriage d'un polygone non auto-intersectant 12
4.8.3.2.e d'un contour convexe 12
4.8.3.3. Coloriage d'unr monotone 130
4.9. Décomposition des polygones
4.9.1. Définitions et propriétés1
4.9.2. Triangulation 132
4.9.3. Décomposition en trapèzes ou en monotones
4.9.4.n d'un polygone monotone3
4.9.5.n en convexes5
4.9.6. Convexifications naïves
4.10. Les cartes planaires6
4.10.1. Carte planaire locale7
4.10.2. Cartee globale8
4.11. Carte des trapèzes 140
4.12. Tracés de courbes dans une mémoire d'image 143
4.12.1. Courbes algébriques
4.12.2. Tracé de courbes paramétriques
4.12.3. Tracé des algébriques implicites4
4.12.3.1. Par suivi
4.12.3.1.1. Suivi de courbe par prédiction-correction 14
4.12.3.1.2. Suivi dee dans un réseau 145
4.12.3.2. Par exclusion, ou arithmétique d'intervalles7
4.12.3.3. Par subdivision adaptative9
4.13. Intersection entre courbes 151
4.14. Quelques difficultés récurrentes
4.14.1. Le traitement des cas particuliers10 Informatique graphique
4.14.2. Les imprécisions numériques 152
4.15. Aliassage et antialiassage3
4.15.1. Présentation des problèmes4
4.15.1.1. Effet de marches d'escalier irréguliers
4.15.1.2. Petits objets5
4.15.2. Techniques d'antialiassage de base6
4.15.2.1. Sur-échantillonnage et filtrage numérique 157
4.15.2.2. Filtrage analytique ; méthodes géométriques et
incrémentales 158
Chapitre 5. Modélisation géométrique 16
5.1. Présentation de la modélisation du solide5
5.1.1. Historique
5.1.2. Définition des solides7
5.1.3. Opérations booléennes et régularisation
5.1.4. Les représentations classiques des solides9
5.2. La représentation par frontières
5.3. Lan constructive 172
5.3.1. Le principe
5.3.2. Extensions3
5.3.2.1. Les déformations géométriques élémentaires 173
5.3.2.2. Lesss libres4
5.3.2.3. Les sommes de Minkowski
5.3.2.4. Les surfaces implicites5
5.3.3. Quelques notions utiles 17
5.3.3.1. Arbres de construction et formules logiques 17
5.3.3.2. Les boîtes de Cameron
5.3.3.3. Les zones actives6
5.4. L'énumération spatiale7
5.5. La partition spatiale9
5.6. La tétraédrisation 181
5.7. Quelques représentations hybrides 182
5.8. Evaluation des frontières
5.8.1. Les méthodes récursives3
5.8.2. Less indirectes
5.8.3. Les méthodes de facettisation par suivi4
5.9. L'avenir de la modélisation du solide5
5.9.1. La modélisation hétérotrope
5.9.2. Lan par caractéristiques 187
5.9.3. La représentation par contraintes géométriques
5.9.3.1. Les méthodes de décomposition et propagation 188 Table des matières 11
5.9.3.2. Les méthodes symboliques 188
5.9.3.3. Less numériques
5.9.4. La représentation paramétrique, ou fonctionnelle9
5.9.5. Lan multiéchelles
5.9.5.1. La représentation constructive multiéchelles 190
5.9.5.2. Les triangulations dynamiques 19
5.9.5.3. Les représentations par frontières multiéchelles1
5.10. Critères d'évaluation d'une représentation
5.11. Quelques problèmes en modélisation du solide3
5.11.1. Le problème du nommage [CHE 95, KRI95]
5.11.1.1. La robustesse (robustness problem)4
5.11.1.2. Les problèmes de reconnaissance des formes 19
5.11.1.3. L'ingénierie inverse, ou reconstruction
5.11.1.4. Les échanges de données entre modeleurs différents, et la
standardisation des données 19
5.11.1.5. Problèmes de conversion entre représentations
différentes5
5.12. Les fractales
5.12.1. Présentation
5.12.2. Utilisation en synthèse d'images7
5.12.3. Les itérations de fonctions, ou IFs 198
5.12.4. Les graftales 200
5.12.5. Mise en perspective2
5.13. Les systèmes de particules et la modélisation par masses-ressorts . . 20
5.14. Les représentations dédiées4
5.15. Conclusion
Chapitre 6. La couleur5
6.1. Introduction
6.2. La physique de la lumière 20
6.2.1. Le système visuel humain6
6.2.1.1. L'œil
6.2.1.2. Le mécanisme visuel8
6.2.2. Attributs psychophysiologiques
6.3. La perception des couleurs9
6.4. La colorimétrie 213
6.4.1. Le système XYZ de la CIE
6.4.2. Les modèles de représentation des couleurs 21
6.4.2.1. Le modèle RVB (Rouge, Vert, Bleu)
6.4.2.2. Lee CMJ (Cyan, Magenta. Jaune)
6.4.2.3. Le modèle CIELUV 220 12 Informatique graphique
6.4.2.4. Le modèle YIQ 221
6.4.2.5. Lee TSL (Teinte, Saturation, Luminance) 22
6.4.2.6. Le modèle TSI,, Intensité)3
6.5. Problèmes d'affichage sur un moniteur couleurs5
Chapitre 7. Modèles d'éclairement7
7.1. Introduction 22
7.2. Notions sur les ondes électromagnétiques 228
7.2.1. Introduction
7.2.2. Propagation des ondes dans un milieu homogène
7.2.2.1. Onde plane monochromatique dans le vide9
7.2.2.2. Polarisation 231
7.2.2.3. Énergie électromagnétique
7.2.2.4. Spectre2
7.2.2.5. Propagation de la lumière dans la matière 23
7.2.2.6. Absorption, dispersion4
7.2.3. Réflexion et réfraction
7.2.4.n macroscopique des matériaux8
7.2.4.1. Réflexion sur une surface plane 23
7.2.4.1.1. Le second milieu est diélectrique homogène et
isotrope 23
7.2.4.1.2. Le second milieu est conducteur et isotrope (métal) . 239
7.2.4.1.3. Led milieu est diélectrique hétérogène 240
7.2.4.2. Réflexion sur une surface rugueuse 241
7.3. Notions de radiometric et de photométrie2
7.3.1. Introduction 24
7.3.2. Radiometric
7.3.3. Photométrie7
7.3.4. Perception visuelle8
7.4. L'équation de rendu
7.4.1. Introduction
7.4.2. Modèles locaux9
7.4.3.s globaux
7.4.3.1. Approche basée sur la luminance 250
7.4.3.2.e basée sur les flux1
7.5. Modèles d'éclairement 253
7.5.1. Introduction
7.5.2. Modélisation des surfaces
7.5.2.1. Modèles de distribution des altitudes
7.5.2.2.s den des pentes 254
7.5.3. Les différents modèles d'éclairement5 Table des matières 13
7.5.3.1. Modèle de Lambert 255
7.5.3.2.e du miroir
7.5.3.3. Modèle de Phong6
7.5.3.3.1. Définition du modèle
7.5.3.3.2. Compatibilité du modèle avec la physique 257
7.5.3.4. Modèle de Cook-Torrance8
7.5.3.4.1. Présentation du modèle9
7.5.3.4.2. Etude de la composante diffuse 260
7.5.3.4.3. Etude de lae spéculaire
7.5.3.4.4. Calcul du facteur d'atténuation2
7.5.3.4.5. Compatibilité avec les lois de la physique 265
7.6. Conclusion 266
Chapitre 8. Elimination des parties cachées 267
8.1. Introduction
8.2. Le fenêtrage8
8.3. Le tampon de profondeur
8.4. La méthode d'Atherton et celle de Watkins 275
8.5. Unee du peintre, utilisant un arbre de partition spatiale ... . 279
8.6. La méthode de Warnock 281
8.7. Le calcul des ombres portées
8.7.1. Méthode de la double image2
8.7.2.e de lae passe
8.7.3. Les volumes d'ombre et les algorithmes à balayage 283
8.7.4. Volumes d'ombre et arbre de partition spatiale
8.8. La représentation des scènes extrêmement complexes5
Chapitre 9. Le tracé de rayons 287
9.1. Présentation du tracé de rayons
9.1.1. Historique
9.1.2. Principe de l'algorithme8
9.1.3. Premiers constats 290
9.2. Calculs d'intersections1
9.2.1. Définition d'un rayon
9.2.2. Intersection avec une tranche d'espace 292
9.2.3.n avec un cube3
9.2.4. Intersection avec un polyèdre convexe
9.2.5.n avec un objet implicite
9.2.5.1. Intersection avec une quadrique4
9.2.5.2.n avec un tore 295 14 Informatique graphique
9.2.5.3. Intersection avec un blob 295
9.2.6. Intersection avec une représentation par frontières6
9.2.7.n avec un arbre octal7
9.2.8. Intersection avec un objet transformé
9.2.9.n avec un objet du type arbre de construction 29
9.2.9.1. Principe général
9.2.9.2. Propriétés des objets8
9.3. Algorithmes de rendu 29
9.3.1. Principe général
9.3.2. Modèle de Whitted9
9.3.3. Modèles spectraux 300
9.3.4. Effets optiques1
9.3.5. Tracé de rayons distribué
9.4. Techniques d'accélération2
9.4.1. Le sous-échantillonnage
9.4.2. Les méthodes de partition3
9.4.2.1. Partition plane
9.4.2.2.n volumique
59.4.2.3. Partition de R4
9.4.3. Les méthodes à englobants 30
9.5. Antialiassage et lancer de rayons6
9.6. Conclusion 308
Chapitre 10. Algorithmes d'éclairement 311
10.1. Introduction 31
10.2. Algorithmes de lissage2
10.2.1. Le lissage de Gouraud
10.2.2. Lee de Phong3
10.3. Essai de description des méthodes d'éclairement 314
10.3.1. Grammaire de description des chemins lumineux
10.3.2. Classification des types de chemins lumineux5
10.3.3. Formalisation des algorithmes d'éclairement6
10.3.3.1. Méthodes de résolution par l'image
10.3.3.2.s den par la scène 317
10.3.3.3. Méthodes mixtes 31
10.4. Méthodes de Monte Carlo8
10.4.1. Méthode d'intégration par Monte Carlo
10.4.2. Echantillonnage stratifié 320
10.4.3.e d'importance1
10.4.4. Méthodes de Monte Carlo pour résoudre des équations
intégrales 32Table des matières 15
10.4.5. Méthode de la roulette russe 322
10.4.6. Application des méthodes de Monte Carlo à l'équation
de rendu 324
10.4.6.1. Tracé de chemins (Path tracing)
10.4.6.2. Tracé de photons (light)5
10.4.6.3. Tracé de rayons bidirectionnel6
10.5. La radiosité classique
10.5.1. Le principe
10.5.2. La résolution du système linéaire KB =E 329
10.5.2.1. Itération de Jacobi 32
10.5.2.2.n de Gauss-Seidel 330
10.5.2.3. Itération de Southwell1
10.5.2.4. Radiosité progressive2
10.5.2.5.é par Monte Carlo3
10.5.3. Le calcul des facteurs de forme
10.5.3.1. Formules analytiques
10.5.3.2. Analogie de Nusselt4
10.5.3.3. La méthode de l'hémicube 335
10.5.3.4. Lae de Monte Carlo6
10.5.3.5. Les intégrales de contour7
10.5.4. Le maillage (meshing en anglais)
10.5.4.1. Le maillage régulier
10.5.4.2. La radiosité hiérarchique
10.5.4.3. Le maillage de discontinuité (discontinuity meshing) . . . 340
10.5.4.4. Radiosité hiérarchique et maillage de discontinuité ... . 343
10.5.4.5. Reconstruction de la fonction de radiosité 343
10.6. Extensions de la radiosité 34
10.6.1. Extension aux surfaces non diffuses4
10.6.2.n aux milieux semi-sphériques
10.6.3. Extension à la radiosité non constante sur chaque surfel 34
10.6.4.n à des objets mobiles5
Chapitre 11. Textures7
11.1. Introduction 34
11.2. Problématique des textures planes8
11.2.1. Génération dess planes 34
11.2.1.1. Méthode fractale9
11.2.1.2. Méthode spectrale
11.2.1.3.e syntaxique
11.2.1.4. Méthodes structurelles
11.2.1.5.s stochastiques16 Informatique graphique
11.2.2. Mise en perspective des textures planes 350
11.2.2.1. Transformation perspective des textures planes
11.2.2.2. Notion de taux de compression4
11.2.2.3. Méthodes de traitement6
11.2.2.3.1. Méthodes de filtrage simultané
11.2.2.3.2.s de filtrage a priori 358
11.3. Textures 3D 36
11.3.1. Génération de textures 3D
11.3.1.1. Approche périodique de Gardner 365
11.3.1.2. Fonctions aléatoires et génération de textures 3D 36
11.3.1.3. Méthodes analytiques etn automatique de
textures 3D8
11.3.1.4. Perturbation de la normale en 3D9
11.3.2. Antialiassage
11.4. Hypertextures 370
11.4.1. Visualisation1
11.4.2. Génération2
11.4.3. La notion de texels3
11.4.4. Méthode à base géométrique 37
11.5. Génération par évolution4
11.6.n par réaction et diffusion5
11.7. Conclusion 378
Bibliographie 38
Index 407 Avant-propos
En 1988, les Editions Hermès publiaient un ouvrage intitulé La synthèse
d'images, qui présentait un état de l'art de ce domaine de l'informatique, vingt cinq
ans environ après l'introduction du logiciel SKETCHPAD par I. Sutherland.
Or. en dix ans, la synthèse d'images a évolué, tant sur le plan scientifique que sur
les plans industriel et commercial. De nouveaux domaines d'application, comme la
médecine, ont été conquis. De nouveaux champs se sont ouverts, notamment la
réalité virtuelle et la visualisation scientifique, qui utilisent les techniques de base de
la synthèse d'images. Enfin, la recherche scientifique a réalisé de nombreuses
avancées, par exemple dans le domaine de la simulation des effets lumineux
(éclairagisme).
C'est pourquoi il nous a paru nécessaire de mettre à jour cet ouvrage. Mais pour
prendre en compte les modifications intervenues en dix ans. il nous a semblé qu'une
simple remise en forme ne suffisait pas. Nous avons donc renouvelé complètement
l'édition de 1988. la synthèse d'images étant devenue l'informatique graphique.
Notre expérience d'enseignant nous a conduits à étoffer les notions de base utilisées
en informatique graphique, notamment en ajoutant des éléments de géométrie et
d'analyse numérique et en développant considérablement les chapitres sur les
courbes et surfaces, les algorithmes 2D et la couleur.
L'évolution scientifique de notre discipline nous a contraints à remanier
entièrement le chapitre sur la modélisation et à insister sur tout un pan de la
recherche en pleine expansion depuis dix ans et qui a trait à la simulation des
phénomènes lumineux, avec par exemple l'introduction d'un chapitre sur les
modèles d'éclairement. De la même manière, nous avons insisté sur de nouveaux
algorithmes d'éclairement (méthodes de Monte Carlo, radiosité) et sur de nouvelles
notions liées aux textures. 18 Informatique graphique
L'objectif de ce livre est de présenter les bases de l'informatique graphique,
notamment en ce qui concerne les méthodes, les modèles et les algorithmes. Son
contenu a été testé à l'occasion d'un cours d'informatique graphique dispensé dans le
cadre du DEA d'informatique "Images", cohabilité par l'Université Jean Monnet et
l'Ecole des Mines de Saint-Etienne.
Les quatre premiers chapitres présentent les notions de base indispensables pour
lire avec profit les chapitres qui suivent et qui constituent le cœur de l'informatique
graphique. Le chapitre 1 décrit le pipeline graphique, c'est-à-dire le processus
logique qui permet de construire une image de synthèse ou une séquence de ces
images. Il fournit également un certain nombre d'éléments concernant les aspects
matériels de l'informatique graphique. Dans le chapitre 2 sont abordés des éléments
de mathématiques et de traitement du signal propres à l'informatique graphique. Les
notions de courbes et de surfaces paramétriques et implicites sont développées dans
le chapitre 3, alors que le chapitre 4 est consacré aux principaux algorithmes 2D
utilisés, avec les structures de données associées. Le chapitre 5 porte sur la
modélisation géométrique, et plus particulièrement sur la modélisation du solide (ou
volumique). Le chapitre 6 est consacré à la couleur et le chapitre 7 aux modèles
d'éclairement, c'est-à-dire aux concepts qui permettent de simuler le comportement
de la lumière. Dans le chapitre 8, nous décrivons les principaux algorithmes
d'élimination des parties cachées, en réservant toutefois l'algorithme du tracé de
rayons au chapitre 9. Les algorithmes d'éclairement sont exposés dans le chapitre 10
et les textures dans le chapitre 11.
En décrivant les modèles et les méthodes de base en informatique graphique,
nous avons cependant dû effectuer des choix, car nous ne pouvions tout traiter. Ces
choix ont essentiellement été justifiés par les thèmes de recherche actuels des
auteurs de ce livre.
Bernard PÉROCHE Chapitre 1
Architectures logicielles et matérielles
pour la visualisation
1.1. Le pipeline graphique
1.1.1. Introduction
Une image analogique diffère d'une image numérique en ce que cette dernière
code les informations concernées sous formee et non sous forme continue.
Pour l'image numérique, on peut distinguer l'image-vecteurs (où l'image est
constituée d'un ensemble de segments joignant des points de l'écran) de l'image-
pixels (où l'image est constituée d'un tableau de pixels, chaque pixel étant la quantité
élémentaire d'information codée sous forme de n bits).
Le domaine de l'image numérique s'est beaucoup développé depuis quelques
dizaines d'années. Il peut être représenté par le schéma de la figure 1.1 qui fait
apparaître deux niveaux distincts : un niveau physique, où une image est un signal
bidimensionnel, et un niveau conceptuel qui comprend les structures et/ou les
modèles qui permettront de construire les images du niveau physique.
La synthèse d'images est donc un domaine de l'image numérique, celui qui. à
partir de structures et/ou de modèles, permet d'obtenir des signaux numériques
pouvant être visualisés sur un écran graphique par exemple.
Dans ce premier chapitre, nous allons décrire le processus permettant de générer
une image à partir de modèles. En fait, ce processus peut être représenté par la 20 Informatique graphique
figure 1.2, le logiciel graphique jouant un rôle d'intermédiaire entre l'opérateur
humain et le programme d'application. Il s'agit d'un pipeline dans lequel on construit
d'abord un modèle objet avant de visualiser celui-ci.
Transformation
(calcul scientifique)
Programmes/Données Dispositif d'interactivité
(souris, tablette, clavier, etc.)
Visualisation scientifique
Vision par ordinateur À Synthèse d'images
Capteurs
Affichage/Enregistrement (caméra, etc.)
Transformation
(traitement d'images)
Figure 1.1. Le domaine de l'image numérique
Pour préciser la terminologie utilisée ici (et qui n'est certainement pas standard),
on peut penser à l'exemple de la conception d'une voiture. Le programme
d'application est un logiciel de CAO capable, par exemple, d'effectuer des calculs
de structure sur les éléments rentrés dans la mémoire de l'ordinateur. Le logiciel
graphique peut permettre, lui, de visualiser la carosserie de la voiture en fonction de
la peinture choisie et dans des conditions d'éclairement données.
La séparation entre le programme d'application et le logiciel graphique n'est pas
toujours très nette. Le logiciel graphique peut se réduire à un simple ensemble
matériel géré par l'application ou, au contraire, proposer une interface de plus haut
niveau et un ensemble d'outils spécifiques.
Nous allons donc successivement étudier les paramètres, appelés attributs
graphiques, qui permettent de constituer le modèle objet dans le paragraphe 1.1.2
puis, dans le paragraphe 1.1.3, les attributs de visualisation qui régissent le
processus d'affichage. Nous évoquerons, dans le paragraphe 1.1.4, les problèmes qui
doivent être résolus pour produire effectivement une image à partir d'un modèle Architectures logicielles et matérielles 21
avant de définir, dans le paragraphe 1.1.5. les processus de base utilisés dans tout
logiciel graphique. Nous conclurons cette partie en présentant les deux grandes
approches utilisées pour la réalisation de logiciels graphiques : l'approche
spécialisée puis l'approche générale.
Dispositifs de visualisation
Programme d'application
Logiciel graphique
Opérateur
Système informatique
Dispositifs d'interaction
Figure 1.2. Le processus de visualisation scientifique
1.1.2. Les attributs graphiques
En informatique graphique, le programme d'application contient en général un
modèle des entités manipulées, sous forme de structures de données ou de
procédures.
Parmi ces données, certaines sont propres à l'application (la masse, la résistance
des matériaux, par exemple). D'autres sont liées à la représentation graphique. Ce
sont celles qui vont nous intéresser ; nous les appellerons les attributs graphiques
[MAR 84]. Dans ses travaux, F. Martinez a mis en évidence cinq attributs qui sont
les suivants :
- la morphologie, qui permet de définir la forme intrinsèque des objets (par
exemple, un cube, une sphère, une surface gauche, etc.) ;
- la géométrie, qui permet de positionner les objets les uns par rapport aux
autres ;
- l'aspect, qui permet de définir l'apparence d'un objet (sa couleur, sa texture, sa
brillance, son mode de réflexion de la lumière, etc.).
Ces trois attributs sont purement graphiques ; les deux qui suivent sont surtout
utilisés pour la gestion des données :
- l'identité, qui permet la nomination, la désignation d'objets ou de groupes
d'objets ; 22 Informatique graphique
- la structure, qui exprime les relations liant certains objets (l'appartenance,
l'inclusion, le contact, la proximité, etc.).
Ces cinq attributs graphiques permettent de définir les éléments pouvant
conduire à un modèle des objets. L'élaboration de ce modèle se fait, en général, en
deux étapes :
- la description du modèle, qui permet de définir les éléments constitutifs du
modèle et les liens relationnels entre eux ;
- la construction du modèle, qui fournit une réalisation effective du modèle.
Un exemple illustrant la distinction établie ci-dessus est celui d'un objet de
révolution. Un tel objet est décrit par un contour plan et un axe de révolution et la
construction peut fournir une approximation de l'objet à l'aide de facettes
polygonales.
1.1.3. Les attributs de visualisation
Le processus de visualisation en synthèse d'images est. le plus souvent, identique
au processus photographique. Les paramètres régissant la visualisation peuvent donc
se classer en deux catégories, less de prise de vue qui précisent comment
la scène est observée et ceux d'affichage, qui définissent la manière suivant laquelle
l'image sera affichée sur l'écran de visualisation.
1.1.3.1. Attributs de prise de vue
Deux attributs sont utilisés :
- la géométrie de prise de vue (Gv). Cet attribut peut être plus ou moins
complexe selon le logiciel mis en œuvre. Les paramètres les plus classiques sont les
suivants :
- le point de visée,
- le point de vue,
- le plan de près,
- le plan de loin,
- les caractéristiques de l'appareil de prise de vue (distance focale, ouverture,
roulis, format de prise de vue, etc.) ;
-l'éclairage. Là-aussi, les paramètres peuvent être très différents selon le
réalisme que l'on désire obtenir. Voici quelques exemples d'éléments pouvant être
pris en compte :
- la forme, la position, la couleur, la direction des sources lumineuses,
- le modèle d'éclairement utilisé, Architectures logicielles et matérielles 23
- le modèle de lissage utilisé,
- effet de bleu atmosphérique,
- effet de brouillard.
1.1.3.2. Attribut d'affichage
Le seul attribut concerné s'appelle la géométrie d'affichage (Ga). Cet attribut
permet de situer une vue sur l'écran d'affichage (multifenêtrage) et agit sur la
présentation de la vue.
Le processus de visualisation peut finalement être représenté par le schéma de la
figure 1.3. Il faut noter que les différents attributs définis précédemment ne jouent
pas le même rôle par rapport au pipeline graphique. Si les paramètres I, M, A, G et S
sont nécessaires dès la description du modèle, les trois autres n'interviennent qu'au
niveau de la visualisation. Il est important de tenir compte de cette remarque lors de
la réalisation d'un logiciel, pour éviter de relancer tout le processus si on change
simplement le point de vue par exemple, ou l'emplacement sur l'écran de la fenêtre
d'affichage.
1 M A G S E Gv Ga
Description
du modèle
!
Construction
du modèle
Base de
^données^
Prise de vue
!
Affichage
Figure 13. Le pipeline graphique 24 Informatique graphique
1.1.4. Calculs pour la visualisation
Nous avons présenté, sur la figure 1.3, le pipeline du processus graphique qui est
décomposé en deux grandes parties : la construction du modèle, puis le calcul et
l'affichage de l'image.
Dans ce paragraphe, nous allons compléter ce pipeline en expliquant ce qui se
passe entre la construction du modèle et l'affichage proprement dit de l'image. En
fait, le pipeline graphique peut être représenté par la figure 1.4.
Comme on le voit, le passage du modèle objet à l'image comporte deux étapes
principales.
1.1.4.1. Des calculs géométriques
Ces calculs, qui nécessitent la connaissance des attributs de prise de vue,
comprennent notamment :
- le positionnement des objets, de l'observateur, des sources lumineuses, etc. ;
- la coupe (clipping) par rapport à la pyramide de vision et. éventuellement, les
plans de près et de loin ;
- la transformation perspective, qui permet de projeter la scène définie dans un
espace 3D sur un écran bidimensionnel ;
- l'élimination des parties cachées.
Gestion contenu scène
Base de données graphique
Calculs géométriques
Rendu
Mémoire d'image
Affichage
Figure 1.4. Le pipeline graphique revisité Architectures logicielles et matérielles 25
1.1.4.2. Des calculs de rendu
Ces calculs sont plus ou moins complexes suivant le degré de réalisme souhaité
pour I'(ou les) image(s) à créer. Ils se font, en général, dans l'espace image. Le calcul
de rendu peut se décomposer en une liste de sous-calculs, qui ne sont pas toujours
complètement indépendants :
- calculs d'éclairement, qui consistent à simuler le comportement des objets
vis-à-vis de la lumière ;
- calcul des ombres portées ;
- ajout de textures, qui permettent de simuler l'aspect de certains matériaux, sans
que cet aspect soit décrit géométriquement, ce qui serait trop complexe (on peut
penser, par exemple, à la peau d'une orange ou à un mur en briques ) ;
- calculs d'antialiassage, permettant d'atténuer certains défauts dus au fait qu'une
image numérique est obtenue par échantillonnage discret de phénomènes continus.
REMARQUE. - Le fait de mettre l'élimination des parties cachées dans la partie
calculs géométriques peut prêter à discussion. Tous les autres calculs géométriques
sont réalisés dans l'espace objet ; or, selon l'algorithme d'élimination des parties
cachées choisi, les calculs se font dans l'espace objet (tracé de rayons, algorithme du
peintre, etc.) ou dans l'espace image (z-buffer, algorithme par balayage de ligne,
etc.), comme les autres calculs de rendu (cf. chapitre 8) .
1.1.5. Les processus de base
Les attributs (graphiques ou de visualisation) peuvent être échangés par les
acteurs du processus de visualisation (l'opérateur, le programme d'application) au
moyen de ce que l'on appelle les processus de base. Ceux-ci sont définis ainsi
(cf. figure 1.5) :
'Visualisation Attribution
Logiciel
Graphique
Consultation Description
Figure 1.5. Les processus de base
Programme
u application
Opcnilcur 26 Informatique graphique
- le processus d'attribution permet d'affecter les structures de données du logiciel
graphique à l'aide d'attributs calculés par le programme d'application ;
- le processus de description permet l'affectation interactive, par l'opérateur,
d'attributs au logiciel graphique ;
- le processus de consultation permet au programme d'application de récupérer
des attributs (rentrés interactivemeni par exemple) ;
- le processus de visualisation, de loin le plus complexe, met en jeu quatre types
d'opérateurs :
- un opérateur de synthèse, qui permet la composition de deux attributs. Ainsi on
peut appliquer une information géométrique à une information morphologique, ou
on peut moduler l'aspect d'un objet en fonction de l'éclairage.
- un opérateur de construction, qui transforme une information d'un type donné
dans un autre type. Ainsi, un cercle défini par son centre et son rayon peut être
transformé en l'ensemble discret des points de son contour que l'on pourra afficher.
- un opérateur de composition, qui concerne un attribut de plusieurs objets
simultanément. Par exemple, certains algorithmes d'élimination des parties cachées
nécessitent un tri suivant leur éloignement à l'œil de toutes les faces de la scène,
- un opérateur de mémorisation, qui permet de stocker les informations sous une
forme intermédiaire. C'est le cas d'une mémoire d'images qui se situe entre le
processeur graphique et le processeur d'affichage (cf. paragraphe 1.1.2).
1.1.6. Diverses approches pour les logiciels graphiques
On peut, grosso modo, distinguer deux grandes approches pour les logiciels
graphiques : les systèmes spécialisés et les systèmes généraux.
1.1.6.1. Systèmes spécialisés
Ces systèmes dépendent à la fois de l'application et du matériel utilisé (par
exemple, clavier, souris ou tablette, tube à balayage cavalier, à balayage de trame ou
table traçante, etc.). Ils ont l'avantage d'être performants, car adaptés et à
l'application et au matériel. Ils ont cependant l'inconvénient de ne pas être
réutilisables facilement, en particulier lorsque le matériel évolue.
1.1.6.2. Systèmes généraux
Ces systèmes se veulent indépendants du contexte d'utilisation (applications
concernées, matériel graphique, environnement informatique). Ils ont bien entendu
l'avantage de la portabilité (des programmes d'application, de l'affichage, de Architectures logicielles et matérielles 27
l'information graphique, apprentissage plus aisé, etc.) et, en contre-partie, présentent
une baisse des performances.
De tels logiciels sont conçus selon le principe des couches (cf. figure 1.6) : il
existe une couche indépendante du matériel et une seconde qui, elle, dépend du
poste de travail. Entre l'application, le matériel et les deux couches du logiciel, on
doit donc définir trois interfaces :
Logiciel graphique
Niveau Niveau
Dispositif f f Application indépendant poste
physiquphysiquphysique e e du matériel de travail
API VDI
Figure 1.6. Les couches d'un logiciel graphique
- une interface avec le matériel (driver), qui permet d'utiliser effectivement le
matériel d'un constructeur donné ;
- une interface " terminal virtuel " (VDI) ; deux types de solutions opposées sont
envisageables pour définir cette interface. Une première place cette interface à un
niveau très bas. constitué par l'intersection des possibilités des divers matériels. Une
seconde solution définit l'interface comme l'union des possibilités des matériels ;
dans ce cas, l'interface est rapprochée du programme d'application :
- une interface avec le programme d'application (API). Une idée importante est
mise en œuvre dans ces interfaces : la séparation entre la visualisation et la
modélisation. Grosso modo, il existe trois stratégies possibles d'implémentation
d'une API :
- l'utilisation d'un langage graphique (par exemple, LOGO ou POSTSCRIPT).
- l'extension d'un langage de programmation existant (par exemple. MIRA-2D ou
MIRA-3D [MAG 83], qui sont des extensions de Pascal, TURBO-PASCAL),
- les bibliothèques de sous-programmes, solution la plus répandue actuellement
(par exemple Xlib, PEXlib, etc.).
Signalons enfin, pour conclure, les efforts de normalisation accomplis pour
rendre plus efficace les systèmes graphiques généraux. On peut citer GKS (Graphie
Kernel System) [HOP 83] ou PHIGS (Programmer's Hierarchical Interactive
Graphics [PHI 88] comme normes pour les interfaces avec l'application et
CGM (Computer Graphie Metafile) [ARN 88] pour less terminal virtuel. 28 Informatique graphique
1.2. Bases générales de l'infographie
Cette partie se veut un pont entre la partie 1.1 dévolue à une présentation
générale des logiciels graphiques et la partie 1.3 où seront présentés des exemples
d'architectures de stations graphiques.
Nous présenterons d'abord, dans le paragraphe 1.2.1, les différents modules
constituant l'architecture logique d'un système graphique. Dans le paragraphe 1.2.2,
nous décrirons les constituants de base des systèmes de visualisation (mémoires
d'images, tubes à rayons cathodiques à balayage de trame, tables de couleur, etc.).
1.2.1. Architecture logique d'un système graphique
Suivant [MAR 84], l'architecture d'un système graphique est constituée
logiquement de trois modules et d'une mémoire d'images, comme indiqué sur la
figure 1.7.
Moniteur
Module Mémoire Module Module
pilote d'image vidéo graphique
Figure 1.7. Architecture logique d'un système graphique
Nous allons décrire les principales fonctionnalités des trois modules de la
figure 1.7 tout en remarquant que ces derniers n'existent pas physiquement sur
toutes les machines graphiques.
1.2.1.1. Le module pilote
Il gère les structures de données, effectue les calculs géométriques, la projection
perspective, la coupe des objets, les calculs de normales, etc.
1.2.1.2. Le module graphique
Il génère les objets graphiques (droites, cercles, caractères, etc.). effectue le
remplissage des polygones, gère l'accès aux ressources (mémoire d'image, tables de
couleur, etc.) et exécute certains algorithmes de base (le tampon de profondeur, le
lissage de Gouraud. etc.).
Bus système Architectures logicielles et matérielles 29
1.2.1.3. Le module vidéo
Il effectue la conversion numérique-analogique, génère les signaux de
synchronisation, réalise les effets de zoom, le fenêtrage et les translations d'images,
modifie le contenu des tables de couleur, etc., sans modification de la mémoire
d'image.
1.2.2. Eléments de technologie
Dans ce paragraphe, nous allons décrire les principes des tubes cathodiques qui
sont, à l'heure actuelle, les plus utilisés sur les écrans ou moniteurs des ordinateurs,
puis les mémoires de trame et les tables de couleurs.
1.2.2.1. Les tubes à rayons cathodiques (TRC)
Un écran TRC classique est composé (cf. figure 1.8) d'un écran de luminophores,
d'un canon à électrons et de deux systèmes de déviation verticale et horizontale des
électrons. Les luminophores sont excités par les faisceaux d'électrons, pour former
un spot.
Grille de Amplificateur de
contrôle déviation horizontale
Anode
Canon à Amplificateur de
Ecran
électrons déviation verticale
Système de Paroi métallique
focalisation (haute tension positif)
Figure 1.8. Coupe d'un tube à rayons cathodiques
Une cathode chauffée par un filament émet des électrons qui sont accélérés par
les parois d'un tube à vide. Une grille de contrôle régule le nombre d'électrons émis
par le canon (ce qui permet de régler la luminosité du spot). Un dispositif de
focalisation permet d'obtenir un faisceau très fin. Quand un faisceau heurte l'écran,
les luminophores émettent de la lumière ; l'intensité de cette lumière décroît en
fonction du temps. Si on veut qu'un point reste allumé continuellement, il faut le
rafraîchir à une vitesse dépendant de la rémanence du luminophore (c'est le temps
entre l'excitation et le moment où l'émission a perdu 10 9c de son intensité). Les 30 Informatique graphique
systèmes les plus utilisés à l'heure actuelle sont ceux à balayage de trame qui vont
être définis dans le paragraphe suivant.
1.2.2.2. Les systèmes à balayage de trame
Ces systèmes disposent d'une mémoire d'images rangée comme un tableau à
deux indices. Chaque élément de lae correspond à un point (i. j) de l'image
numérique et s'appelle pixel (picture element). Chaque coordonnée (i, j) est
convertie en deux tensions électriques qui sont appliquées aux systèmes de déviation
horizontale et verticale du faisceau d'électrons.
Si le nombre de pixels de la mémoire d'image est supérieur à celui de l'écran
d'affichage, la mémoire d'image n'est que partiellement affichée. On appelle
mémoire de trame la partie affichée de la mémoire d'image.
Dans les systèmes à balayage de trame, l'écran est parcouru ligne par ligne de
façon continue et il y a réaffichage de tous les pixels de l'écran (cf. figure 1.9). La
fréquence de rafraîchissement est le nombre de balayages de l'écran effectués par
seconde. Cette fréquence est définie de façon à minimiser l'effet de scintillement.
Retour ligne
Balayage ligne
Retour trame
Figure 1.9. Système à balayage de trame
Il existe deux types de balayage de trame : simple et entrelacé. Pour le balayage
simple, toutes les lignes de l'écran sont balayées par le faisceau, de gauche à droite
et de haut en bas, avec une fréquence F. Pour le balayage entrelacé, un premier
balayage est effectué pour les lignes impaires suivi d'un second balayage pour les
lignes paires. Le balayage entrelacé est utilisé pour diminuer l'effet de scintillement. Architectures logicielles et matérielles 31
1.2.2.3. Systèmes graphiques couleur
Les tubes couleurs fonctionnent selon le principe de la synthèse additive des
couleurs. L'écran est composé de trois types de phosphores correspondant aux trois
couleurs primaires (rouge, vert, bleu). Un écran TRC couleur dispose donc de trois
canons à électrons (un par couleur primaire) et d'un masque qui évite qu'un faisceau
d'une couleur n'aille heurter un phosphore d'une autre couleur.
1.2.2.4. Les mémoires d'image
Comme indiqué dans le paragraphe 1.2.2.2, les systèmes à balayage de trame
utilisent une mémoire d'image dans laquelle sont stockées les informations
numériques permettant d'afficher les images. Cette mémoire d'image est organisée
sous forme de plans, un plan correspondant à un bit de codage du pixel à afficher.
Pour un système graphique avec niveaux de gris, on peut disposer d'une mémoire
d'image avec huit plans, ce qui permet d'obtenir des images avec 256 niveaux de
gris.
Pour les systèmes couleur, chaque couleur primaire est codée sur n bits. Pour les
systèmes les plus simples, on a n = 1, ce qui permet d'afficher 8 couleurs. Les s perfectionnés disposent de 3 x 8 plans, ce qui autorise l'affichage de plus
de 16 millions de couleurs différentes.
Il faut noter que la mémoire d'image doit être à double accès : les 3n bits
correspondant aux pixels doivent être fournis au module vidéo au rythme du
balayage vidéo. Inversement, le module graphique effectue de très nombreux accès
à cette mémoire (c'est le cas par exemple du tampon de profondeur).
Les composants mémoire les plus classiques aujourd'hui en informatique, sont
les DRAM {Dynamic Random Access Memory). Cependant, ces circuits permettent
difficilement la gestion des doubles accès à la mémoire. C'est la raison pour laquelle
sont apparues les mémoires vidéo VRAM qui, en intégrant un registre à décalage de
la taille d'une ligne connecté à un port série, permettent ce double accès [CHA 92].
1.2.2.5. Les tables de couleurs
Quand un système dispose d'un nombre restreint de plans mémoire pour les
couleurs, il est possible d'améliorer la qualité des couleurs obtenues en utilisant une
table de couleurs (Look Up Table, LUT). On ne mémorise pas directement les
valeurs R, V et B à afficher, mais une adresse dans un tableau où sont stockées ces
valeurs. 32 Informatique graphique
Convertisseurs
numérique-analogique
Adresse
Point (x,y)
Table de couleurs Mémoires de trame
Figure 1.10. Principe des tables de couleur
Ainsi, si un système graphique dispose de 12 plans couleurs (cf. figure 1.10), on
utilisera une table de couleurs à 4 096 entrées adressables par les 12 bits. Chaque
mot de la table des peut contenir 3 octets initialises par programme pour
représenter une couleur. On peut ainsi afficher simultanément 4 096 couleurs
choisies parmi plus de 16 millions.
1.3. Systèmes graphiques
Unité(s)
centrale(s)
Mémoire
Mémoire
cache
BUS INTERNE
Sous-système Sous-système Disques
graphique d'entrées/sorties
Cartouche Ethernet
Moniteur Clavier, souris
Figure 1.11. Architecture d'une station graphique Architectures logicielles et matérielles 33
Dans cette partie, nous allons nous intéresser à l'architecture matérielle des
machines graphiques récentes. L'architecture standard dune telle machine peut être
schématisée par la figure 1.11. Il faut noter que la plupart des stations graphiques
utilisent le lissage de Gouraud (cf. chapitre 10) et le tampon de profondeur (cf.
chapitre 6). Elles supposent la plupart du temps que la scène soit décomposée en
facettes polygonales planes, le plus souvent triangulaires. Les calculs de profondeur
et d'éclairement sont donc réalisés aux sommets des polygones et les valeurs aux
autres pixels sont déterminées par interpolation.
1.3.1. Un modèle pour les stations graphiques
Dans [AKE 89], Akeley a proposé un modèle pour les systèmes graphiques basé
sur cinq tâches qui constituent un pipeline (cf paragraphe 1.1). Les tâches sont les
suivantes :
1. La Génération (G). Les données graphiques sont générées et structurées.
2. Le Parcours (P). Les structures de données graphiques sont parcourues pour
fournir des données au(x) processeur(s) approprié(s).
3. La Transformation (T). Dans cette tâche, les données graphiques sont
transformées de l'espace du monde à celui de l'oeil. Les coordonnées sont alors
coupées et les coordonnées obtenues sont projetées dans l'espace écran.
4. La Discrétisation par balayage (D). Les objets de l'espace écran (points, lignes
et polygones) sont discrétisés et inscrits dans la mémoire image après que les calculs
d'éclairement prenant place dans l'espace écran ont été réalisés.
5. Affichage (A). Les pixels de la mémoire image sont envoyés sur un moniteur
d'affichage à l'aide d'un balayage.
1.3.2. Architecture des stations graphiques
Comme nous l'avons vu. les systèmes graphiques réalisent cinq tâches
fondamentales. Nous allons étudier maintenant comment peuvent se répartir ces
tâches entre des processeurs à usage général et des processeurs spécialisés. Nous
adopterons des conventions d'écriture assez proches de celles proposées par Akeley
[AKE 89] : nous utiliserons les lettres G, P, T, D et A pour les tâches et le symbole
— pour indiquer la séparation entre les tâches exécutées sur un processeur à usage
général et celles exécutées sur un processeur spécialisé. Ainsi la notation GPTD—A
signifie que seule la tâche d'affichage est exécutée sur un processeur spécialisé.
On peut d'abord remarquer que la tâche d'affichage est toujours réalisée sur un
processeur spécialisé. En effet, pour éviter les effets de scintillement, les moniteurs 34 Informatique graphique
à balayage de trame doivent afficher des images à une fréquence d*au moins 60 Hz.
Ainsi un moniteur couleur de résolution 1 280 x 1 024 doit recevoir des données à
un débit d'au moins 236 Mo par seconde. Ce débit est très difficile à atteindre pour
un processeur à usage général alors qu'il est réalisé aisément par un processeur
spécialisé (module vidéo).
Les tâches de génération sont en général d'une grande complexité algorithmique,
dépendent de l'application et sont donc très variées. Elles sont toujours exécutées
sur un processeur à usage général.
Nous allons voir maintenant que les trois autres tâches (Parcours,
Transformation, Discrétisation) ont toutes été réalisées soit sur un processeur à
usage général, soit sur un processeur spécialisé par les divers constructeurs au cours
des quinze dernières années :
- architecture GPTD—A : ce type d'architecture a bien existé, mais uniquement
sur les premières générations de stations de travail avec mémoire de trame. C'était le
cas dess stations SUN ou de la machine Alto de chez Xerox [THA 82],
- architecture GPT—DA : les " super stations de travail " comme Apollo,
Ardent ou Stellar ont toutes utilisé des variantes de ce type d'architecture,
- architecture GP—TDA : toutes les stations Silicon Graphics sont basées sur
unee de ce type.
1.3.3. Performances graphiques
Nous allons évaluer les performances (en nombre d'opérations flottantes ou en
remplissage de pixels) nécessaires pour traiter 100 000 polygones par seconde sur
une machine graphique ayant une architecture standard.
Nous supposerons que les polygones ont 3 ou 4 côtés, qu'ils ont une orientation
quelconque, qu'ils ont chacun une couleur codée en RVB. qu'ils ont une taille
d'environ 10 x 10 pixels et qu'ils sont visualisés après calculs d'éclairement (de
type Phong) et lissage de Gouraud, que l'élimination des parties cachées se fait avec
le tampon de profondeur, qu'ils subissent la coupe par une pyramide de vision et
qu'ils sont projetés et affichés dans une fenêtre (parmi plusieurs se recouvrant
éventuellement).
Pour évaluer les performances nécessaires pour afficher 100 000 polygones par
seconde, nous allons décomposer le pipeline de tâches en sept composantes. Architectures logicielles et matérielles 35
1. Transfert des données de la mémoire au sous-système graphique
Cette opération nécessite que 400 000 spécifications de sommets soient
transférées par seconde. Une spécification de sommet comprend six valeurs
flottantes : trois pour spécifier la position dut et trois pour spécifier la
direction de la normale en ce sommet. Le débit moyen demandé par cette
composante est donc de :
400 000 x 6 x 4 = 6,4 Mo/s
2. Transformation des coordonnées des sommets
Les sommets 3 D sont définis à laide de quatre coordonnées homogènes et les
transformations géométriques sont effectuées à l'aide de matrices 4 x 4. La
puissance de calcul nécessaire est donc de :
400 000 x (16+ 12)= 11 Mflops
3. Transformation des normales aux sommets
Les normales aux sommets ont trois composantes. Comme les normales sont
unitaires et ne dépendent pas de la position des sommets, les composantes
translation et homothétie de la transformation géométrique sont inutiles. La
transformation géométrique peut donc être effectuée par une matrice 3 x 3, ce qui
fournit la puissance de calcul :
400 000 x (9 + 6) = 6 Mflops
Mais, après transformation, les normales doivent être unitaires. Une somme de
carrés nécessite trois multiplications flottantes et deux additions flottantes. Si on
estime le coût de l'inverse d'une racine carrée à huit opérations, la
puissance de calcul demandée par la normalisation est de :
400 000 x (3 + 2 + 16 + 3) s 9,5 Mflops
4. Calculs d'éclairement
Comme un lissage de Gouraud est effectué, les calculs d'éclairement doivent être
réalisés uniquement aux sommets des polygones. Pour effectuer les calculs, nous
supposerons que le modèle d'éclairement utilisé vérifie les contraintes suivantes :
- une seule source de lumière située à l'infini,
- l'observateur est placé à finfini.
- utilisation du modèle de Phong :
n
Cobjel = Cambieni + Cdiffus Csouice N.L + C&pec Csource (N.H)36 Informatique graphique
Cette équation est appliquée trois fois (une fois pour chaque composante rouge,
verte, bleue) et les produits scalaires sont évalués une seule fois. Dans ces
conditions, chaque calcul d'éclairement demande douze multiplications flottantes,
dix additions flottantes, cinq comparaisons flottantes et un accès à une table de
couleurs. La puissance de calcul totale est donc de :
400 000 x (12 + 10 + 5 + 1) = 11 Mflops
5. Coupe
Les polygones sont coupés à l'aide de l'algorithme de Sutherland-Hodgman
[SUT 74]. Cet algorithme nécessite une comparaison flottante par plan de coupe,
c'est-à-dire six comparaisons par sommet. Dans le cas où il faut effectivement
couper le polygone, c'est-à-dire assez rarement, des opérations flottantes
supplémentaires sont nécessaires ; elles ne seront pas prises en compte ici. La coupe
demande donc une puissance de :
400 000 x 6 = 2,5 Mflops
6. Projection
Chaque sommet en coordonnées homogènes est projeté en calculant d'abord un
terme l/co puis en multipliant chaque coordonnée x, y et z par ce terme. La
projection perpective nécessite donc une puissance de :
400 000 x (8 + 3) = 4,5 Mflops
7. Transformation des coordonnées des sommets en coordonnées écran
Les sommets projetés sont transformés en coordonnées écran par un simple
calcul affine. Chacune des trois composantes d'un sommet subit une affinité (avec
un facteur indépendant pour chaque) et un déport (avec un paramètre
indépendant pour chaque composante) puis est recalée sur un entier. La puissance de
calcul correspondante est donc de :
400 000 x (3 + 3 + 3) s 3,5 Mflops
Finalement, la puissance de calcul flottante nécessaire pour convertir des
sommets de l'espace du monde en coordonnées écrans et en couleurs est de l'ordre
de 46,5 Mflops pour un affichage de 100 000 polygones par seconde.
1.3.4. Un exemple d'architecture : celle de Silicon Graphics
Toutes les stations de chez Silicon Graphics ont une architecture assez similaire
depuis plusieurs années. Cette architecture, de type GP-TDA, va être présentée Architectures logicielles et matérielles 37
rapidement maintenant. La figure 1.12 reproduit le diagramme du sous-système
graphique de l'Extrême.
Le sous-système graphique est une composante d'une station de travail dont le
processus hôte comporte plusieurs CPU de type RISC. Les CPU et le sous-système
graphique partagent un bus synchrone rapide à 32 ou 64 bits.
Le système graphique est découpé en trois sous-systèmes disposés en pipeline.
1.3.4.1. Le sous-système géométrique
Ce sous-système comprend un module FIFO, une puce " Command Engine " et
plusieurs processeurs " Geometry Engine " disposés suivant une architecture
parallèle de type SIMD.
Les commandes d'affichage ainsi que les coordonnées géométriques dans le
monde sont transférées à travers le bus système et écrites dans le module d'entrée
FIFO. Le " Command Engine " contrôle la sortie du module FIFO et transfère le flot
de commandes et de données du programme d'application au sous-système
géométrique.
Le cœur du sous-système géométrique est constitué de processeurs " Geometry
Engine ". Chacun de ces processeurs exécute les tâches suivantes :
-transformations matricielles des sommets et des normales ; normalisation des
vecteurs normaux,
-calculs d'éclairement (il peut y avoir jusqu'à huit sources ponctuelles ou de
type projecteur),
- coupe par une boîte englobante à six plans,
- mise en perspective,
- décomposition des polygones en triangles indépendants et détermination des
paramètres qui seront utilisés dans l'étape suivante. 38 Informatique graphique
Indigo GI032/G1064 System Bus
Figure 1.12. Sous-système graphique de l'Extrême (d'après [SIL 92])
Pre- Host
Geometry Subsystem
•rame Buffer
Display Subsyslcrr Raster Engine
processor CPU Architectures logicielles et matérielles 39
1.3.4.2. Le sous-système de discrétisation
Ce sous-système réalise les opérations nécessaires pour remplacer un vecteur ou
un triangle par les pixels qui seront écrits dans une mémoire de trame ou un tampon
de profondeur. Ces opérations, qui utilisent des algorithmes du type DDA (Digital
Differential Analyser), sont schématisés sur la figure 1.13.
Ljg Réseau de triangles Polygones
n e
Figure 1.13. Algorithmes de discrétisation sur station Silicon Graphics
(d'après [SIL 92])
Ce sous-système réalise également des opérations au niveau des pixels, ce qui
permet les traitements d'antialiassage, les effet de brume, etc.
Enfin, les opérations permettant la coupe par rapport à une fenêtre d'affichage
rectangulaire, les comparaisons de profondeur, etc. sont aussi réalisées par ce sous-
système. 40 Informatique graphique
Pour chaque pixel de l'écran, une valeur de sortie est stockée dans une mémoire
de trame qui peut comporter jusqu'à 56 bits par pixel (incluant 24 bits pour le
tampon en profondeur).
1.3.4.3. Sous-système d'affichage
Ce sous-système reçoit les informations sur les pixels provenant de la mémoire
de trame, les aiguille vers le mode d'affichage approprié puis les envoie vers des
convertisseurs numérique-analogique pour affichage. Il faut noter qu'à ce niveau,
cinq processeurs graphiques travaillent en parallèle pour alimenter les
convertisseurs.