Upload
others
View
9
Download
0
Embed Size (px)
Citation preview
1
Infographie
Pipeline graphiqueOpenGL, DirectX etc …
2
Infographie
Pipeline graphique
Approche complémentaire du ray-tracing Beaucoup de versions
Implémentation logicielle, ex. Pixar Renderman But ici : rapidité sans perdre trop en réalisme (flexibilité) Faire le rendu d'un film de 2 heures en 1 an impose 3 minutes
de calcul par image … (mais c'est facilement parallélisable) Implémentation matérielle, e.g. cartes graphiques PC
Temps (presque) réel : plusieurs millions de triangles rendus par seconde
On va se concentrer sur une « abstraction » d'une implémentation matérielle
3
Infographie
Pipeline graphique
On parle de Pipeline graphique
But ici : opérations facilement parallélisables Groupes de processeurs dédiés permettant d'exécuter
de plusieurs dizaines à plusieurs milliers d'opérations en parallèle.
→ performance des GPU ( plusieurs fois celle des CPU à 1/5 de la fréquence d'horloge)
Mémoire dédiée
4
Infographie
Pipeline graphique
Performance des échanges (les données ont qq années - 2010)
Doc
umen
t N
vidi
a
5
Infographie
Pipeline graphique
Organisation particulière d'un GPU
Doc
umen
t N
vidi
a
6
Infographie
Pipeline graphique
Pipeline
Flux de commandes
Géométrie transformée
Fragments ( ~ pixels + données interpolées )
Mémoire de trame (framebuffer)
Application
Opérations sur les sommets (vertex processing)
Rastérisation
Opérations sur les fragments (fragment processing)
Affichage
On est ici
Transformations 3D, ombrage
Composition, mélange, (ombrage)
Ce que l'utilisateur voit
Standards « langage »OpenGL, DirectX etc...
Conversion des primitives en
fragments
7
Infographie
Pipeline graphique
Primitives Points (dans l'espace) Segments de droite
Chaînes de segments connectés Triangles
Chaînes de triangles C'est tout !
Courbes ? Approchées par des chaînes de segments Polygones ? Décomposés en triangles Surfaces courbes ? Approchées par des triangles
La « mode » actuelle est de se restreindre à un minimum de primitives
Simple, uniforme, répétitif → bon pour le parallélisme
8
Infographie
Pipeline graphique
Flux de commandes : dépend de l'implémentation Ex: OpenGL 1, DirectX, autres On retrouve toujours un peu les mêmes choses
Cf Tps pour OpenGL Avantages d'OpenGL :
Multiplateforme, simple, performant, évolutif et non attaché à une compagnie/architecture .
9
Infographie
Pipeline graphique
Pipeline
Flux de commandes
Géométrie transformée
Fragments ( ~ pixels + données interpolées )
Mémoire de trame (framebuffer)
Application
Opérations sur les sommets (vertex processing)
Rastérisation
Opérations sur les fragments (fragment processing)
Affichage
On est ici
Transformations 3D, ombrage
Composition, mélange, ombrage,
Ce que l'utilisateur voit
Conversion des primitives en
fragments
10
Infographie
Pipeline graphique
Pipeline des transformations géométriques
11
Infographie
Pipeline graphique
12
Infographie
Pipeline graphique
Clipping Les opérations de rastérisation supposent que les
triangles (ou les lignes) sont visibles sur l'écran Ceci est effectué dans l'espace 3D canonique, après
l'application de la matrice de projection perspective (cf cours 2 ), mais avant la division perspective.
Tout ce qui n'est pas dans le volume
est « éliminé » Coupure
contre 6 plans
−wxw−w yw−w zw
13
Infographie
Pipeline graphique
Clipping Opération de base : couper un triangle en 3 par un
plan 4 cas :
Tous les points dedanson garde le triangle
Tous à l'extérieuron rejette le triangle
1 sommets dedans; 2 dehors → 1 triangle reste 2 sommets dedans; 1 dehors → 2 triangles restent
14
Infographie
Pipeline graphique
Élimination des faces cachées On a discuté de comment transformer les primitives
vers l'écran (géométriquement parlant) La projection perspective donne un indice de
profondeur L'élimination des faces cachées donne un autre
indice très important. Possibilité de ne dessiner que ce qui est visible
(raison : performance accrue)
15
Infographie
Pipeline graphique
Élimination des faces cachées « backface culling » = occlusion des faces arrières Pour des formes fermées et opaques, on ne voit
pas ce qui est dedans
16
Infographie
Pipeline graphique
Élimination des faces cachées « backface culling » = occlusion des faces arrières Inutile de tracer les faces « à l'arrière »
vn
n
v
17
Infographie
Pipeline graphique
Élimination des faces cachées « backface culling » = occlusion des faces arrières Inutile de tracer les faces « à l'arrière »
vn
n
v
v⋅n≤0
18
Infographie
Pipeline graphique
Élimination des faces cachées « backface culling » = occlusion des faces arrières Dépend de la convention sur la normale
En principe, normale extérieure. Le calcul ne se fait correctement que si les triangles sont
orientés convenablement
s1
n=s1 s2×s1 s3
∥s1 s2×s1 s3∥
s2
s3
19
Infographie
Pipeline graphique
Faces cachées Comment traiter le cas suivant ?
Algorithme du peintre « simple » Arbre de partitionnement binaire Z-buffer
20
Infographie
Pipeline graphique
Algorithme du peintre Idée : tracer toutes les primitives dans le bon ordre On écrase ce qui se trouve en dessous
21
Infographie
Pipeline graphique
Algorithme du peintre Idée : tracer toutes les primitives dans le bon ordre On écrase ce qui se trouve en dessous
22
Infographie
Pipeline graphique
Algorithme du peintre Idée : tracer les primitives dans le bon ordre On écrase ce qui se trouve en dessous
Revient à effectuer un tri topologique Trouver un chemin dans un graphe orienté
AB
C
D
EF
A
B
C
D
E
F
ABCDEFABDCFECAEBDF...
23
Infographie
Pipeline graphique
Algorithme du peintre Impossible en présence de cycles ...
A
B
C
A
B
C
ABC ???
24
Infographie
Pipeline graphique
Algorithme du peintre Impossible en présence de cycles …
Solution : découpage
a
f
o
b,l cd,g
m
k
ej
i,n
h a
o
l
cg
m
k
ei
h
db
n
25
Infographie
Pipeline graphique
Algorithme du peintre Utile lorsqu'un ordre est facile à déterminer Génération de
dessins vectoriels
Fol
ey e
t al.
26
Infographie
Pipeline graphique
Algorithme du peintre L'ordre des opérations de dessin dépend du point
de vue Le classement des primitives est coûteux (en
nlog(n) au mieux ) et doit être refait dès que l'observateur bouge
Les primitives doivent être découpées si elles forment des cycles (comment le détecter ?)
Réponse à ces problèmes : Arbre de partition spatiale binaire (BSP Tree)
27
Infographie
Pipeline graphique
BSP Tree Données d'entrée :
Série de segments en 2D Série de triangles en 3D – raisonnement identique
a b
c
d
e
28
Infographie
Pipeline graphique
Construction du BSP Tree (1)
a b.1
c
d
e
b.2
c+ -
+
-
→ Prendre un des segments et définir un plan coupant le domaine en deux sous domaines signés
→ Classer les autres segments d'un côté ou de l'autre du plan. Si un segment est à cheval, lepartitionner et classer les parties.
→ Dans chaque sous domaine, si il y a plus d'un segment,refaire la même opération récursivement.
29
Infographie
Pipeline graphique
Construction du BSP Tree (2)
a b.1
c
d
e.1
b.2
c
e.2
d
+ -+
-
+- +-
e.1
→ Prendre un des segments et définir un plan coupant le domaine en deux sous domaines
→ Classer les autres segments d'un côté ou de l'autre du plan. Si un segment est à cheval, lepartitionner et classer les parties.
→ Dans chaque sous domaine, si il y a plus d'un segment,refaire la même opération récursivement.
30
Infographie
Pipeline graphique
Construction du BSP Tree (3)
a b.1
c
d
e.1
b.2
e.2
c
d b.1
a
+ -+
-
+-
+-
e.1
→ Prendre un des segments et définir un plan coupant le domaine en deux sous domaines
→ Classer les autres segments d'un côté ou de l'autre du plan. Si un segment est à cheval, lepartitionner et classer les parties.
→ Dans chaque sous domaine, si il y a plus d'un segment,refaire la même opération récursivement.
31
Infographie
Pipeline graphique
Construction du BSP Tree (4)
a b.1
c
d
e.1
b.2
e.2
c
d b.1
a
+ -+
-
+-
+-
e.1+
-
e.2
b.2
→ Prendre un des segments et définir un plan coupant le domaine en deux sous domaines
→ Classer les autres segments d'un côté ou de l'autre du plan. Si un segment est à cheval, lepartitionner et classer les parties.
→ Dans chaque sous domaine, si il y a plus d'un segment,refaire la même opération récursivement.
32
Infographie
Pipeline graphique
Comment choisir le « bon » plan de découpage à chaque étape ?
Un choix aléatoire n'est pas mauvais... Algorithme complet
Soit S un ensemble de segments (ou triangles en 3D)Build(S,BSP){
Si (Card(S) <=1) BSP est un arbre avec un seul noeud, contenant l'éventuel segment de SSinon {
Utiliser un segment aléatoire s de S comme ligne de coupure et découper les autres segmentsS+ = segments appartenant à H+ (demi espace « positif ») (sans s)S- = segments appartenant à H- (demi espace « négatif ») (sans s)Build(S+,BSP+)Build(S-,BSP-)Cree un arbre avec comme racine BSP, enfants BSP+ et BSP-, la racine contient s
}}
33
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
Prenons O c+→ Il est clair que les entités de c- doivent être affichées AVANT les entités sur c, qui doivent être affichées AVANT celles contenues dans c+
c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
34
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
c- c c+La question se repose pour c- (puis c+)O b.1- donc les entités de b.1+ doivent être affichées AVANT les entités sur b.1, qui doivent être affichées AVANT celles contenues dans b.1-
1
23
4
5
c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
35
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
a b.1 (b.1-) c c+La question se repose pour c+O d+ donc les entités de d- doivent être affichées AVANT les entités sur d, qui doivent être affichées AVANT celles contenues dans d+
1
23
4
5
6 c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
36
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
a b.1 (b.1-) c d- d d+
1
23
4
5
6
7
8
9
c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
37
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
a b.1 (b.1-) c e.1 d d+La question se repose pour d+O e.2+ donc les entités de e.2- doivent être affichées AVANT les entités sur e.2, qui doivent être affichées AVANT celles contenues dans e.2+
1
23
4
5
6
7
8
9
10101112
c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
38
Infographie
Pipeline graphique
Utilisation du BSP Tree Comment parcourir l'arbre afin d'obtenir l'ordre
d'affichage correct ?
a
+ -
e.1
b.2
ObservateurO
a b.1 (b.1-) c e.1 d b.2 e.2 (e.2+)
Ordre final : a b.1 c e.1 d b.2 e.2
1
23
4
5
6
7
8
9
10101112
c
d b.1
e.2
a b.1
c
d
e.1
b.2
e.2
+
-
+-
+-
+
-
39
Infographie
Pipeline graphique
Algorithme de parcours récursifDraw(BSP,ViewPoint){
Si BSP est une feuille (pas d'enfants)Dessine les primitives contenues dans BSP
Sinon{
Soit BSP+ et BSP- les enfants de BSPSi ViewPoint est dans H- (demi espace « negatif »){
Draw(BSP+,ViewPoint)Dessine les primitives contenues dans BSPDraw(BSP-,ViewPoint)
}Sinon Si ViewPoint est dans H+ (demi espace « positif »){
Draw(BSP-,ViewPoint)Dessine les primitives contenues dans BSPDraw(BSP+,ViewPoint)
}Sinon (on est juste sur le plan de jonction){
(Dessine les primitives contenues dans BSP) /pas obligatoireDraw(BSP+,ViewPoint)Draw(BSP-,ViewPoint)
}}
}
BSP
BSP-BSP+
40
Infographie
Pipeline graphique
L'arbre BSP n'est généralement pas utilisé directement dans les cartes graphiques.
Construction relativement lente (au mieux en nlogn si l'arbre final est balancé), structure de données complexe
→ Z-buffer : cf plus loin Il peut par contre être utilisé dans certains cas de
façon logicielle pour « faciliter » le travail des cartes graphiques
Ex. Jeux vidéos « FPS » ou les décors sont fixes, mis à part quelques parties animées
« Doom » est un jeu vidéo qui fut précurseur dans cette utilisation
Il peut aussi être utilisé en ray-tracing...
41
Infographie
Pipeline graphique
Pipeline
Flux de commandes
Géométrie transformée
Fragments ( ~ pixels + données interpolées )
Mémoire de trame (framebuffer)
Application
Opérations sur les sommets (vertex processing)
Rastérisation
Opérations sur les fragments (fragment processing)
Affichage
On est ici
Transformations 3D, ombrage
Conversion des primitives en
fragments
Composition, mélange, ombrage,
Ce que l'utilisateur voit
42
Infographie
Pipeline graphique
Rastérisation Première étape : énumérer les pixels couverts par
la primitive « continue » Seconde étape : Interpoler des valeurs connues
aux sommets de la primitive Exemple : la couleur connue aux sommets d'un triangle
doit être « distribuée » sur chaque pixel du triangle. D'autres grandeurs peuvent être interpolées. Par
exemple, les normales si elles sont connues aux sommets
43
Infographie
Pipeline graphique
Rastérisation Transformation des primitives « continues » en
pixels Exemple : tracé d'une droite Point délicat : aliasing
44
Infographie
Pipeline graphique
Algorithme trivial Ligne = rectangle de largeur unité On spécifie les deux points Cas considéré : noir à l'intérieur du rectangle, blanc
à l'extérieur
45
Infographie
Pipeline graphique
Algorithme naïf Ligne = rectangle de largeur unité On spécifie les deux points Cas considéré : noir à l'intérieur du rectangle, blanc
à l'extérieur
46
Infographie
Pipeline graphique
Échantillonnage de points On approche le rectangle en traçant tous les pixels
dont le centre est situé dans le rectangle
47
Infographie
Pipeline graphique
Échantillonnage de points On approche le rectangle en tracant tous les pixels
dont le centre est situé dans le rectangle Problème : parfois, on allume des pixels deux fois
adjacents
48
Infographie
Pipeline graphique
49
Infographie
Pipeline graphique
Algorithme de Bresenham (point milieu) On va définir l'épaisseur de la ligne parallèlement
aux axes...
50
Infographie
Pipeline graphique
Algorithme de Bresenham (point milieu) On va définir l'épaisseur de la ligne parallèlement
aux axes... On allume un
seul pixel par colonne
Les lignes à 45° seront enapparenceplus fines.
51
Infographie
Pipeline graphique
Algorithme de Bresenham (point milieu) On va définir l'épaisseur de la ligne parallèlement
aux axes... On allume un
seul pixel par colonne
Les lignes à 45° seront enapparenceplus fines.
52
Infographie
Pipeline graphique
53
Infographie
Pipeline graphique
Algorithme de tracé de ligne Equation : On évalue l'equation à chaque colonne On allume un
seul pixel par colonne
y=mxb
x0x1
0≤m≤1for x = ceil(x0) to floor(x1) y=b+m*x plot(x,round(y))
0
1
2
4
5
6
7
3
y=0.49x−0.01
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
54
Infographie
Pipeline graphique
Optimisation Multiplications et arrondis sont des opérations
lentes Pour chaque pixel, les seules options sont E et NE
On calcule l'erreur commise d > 0.5 décide
entre E et NE
d=m x1b− y
0
1
2
4
5
6
7
3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
x , y
NE
E
y=mxbmxb− y=0
55
Infographie
Pipeline graphique
Optimisation On doit seulement mettre à jour avec des pas
entiers en x et y Utilisation exclusive de l'addition (pas de
multiplication ni division d > 0.5 décide
entre E et NE On parle d'
« analyseurdigitaldifférentiel »
d=m x1b− y
0
1
2
4
5
6
7
3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
d=dmd=d−1
56
Infographie
Pipeline graphique
Optimisation
0
1
2
4
5
6
7
3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
x=ceil(x0) // arrondi sup.y=round(m*x+b) // arrondid=m*(x+1)+b-yWhile (x<floor(x1)) // arrondi inf.{ If d>0.5 { y=y+1 d=d-1 } x=x+1 d=d+m plot(x,y)}
57
Infographie
Pipeline graphique
En général on dispose des points extrémité
Forme implicite :
y=dydx
⋅x+b x0
y0
x1
y1
dx=x1−x0
dy= y1− y0
G x , y =dy⋅x−dx⋅ydx⋅b
G x , y0
G x , y 0
G x , y =0
≡F x , y=2 dy⋅x−2 dx⋅y2 dx⋅b
58
Infographie
Pipeline graphique
Calcul de la valeur de F au point M
: M est sous la droitechoix NE
: M est au dessuschoix E
d i=F x i1, yi1/2=2 dy⋅x i1−2 dx⋅ y i1 /22 dx⋅b
M
Q
NE?
E?
d i0
d i≤0
x i , y i
59
Infographie
Pipeline graphique
Premier point: que vaut ?
Comme fait partie de la droite,
d 0
d 0=F x01, y01 /2=2 dy⋅ x01−2 dx⋅ y01/22 dx⋅b
=2 dy x0−2 dx⋅y02 dx⋅b2 dy−dx
=F x0, y02 dy−dx
x0, y0 F x0, y0=0
d 0=2dy−dx
60
Infographie
Pipeline graphique
Récurrence : que vaut ? Si alors on est allé à l' E :
Sinon on est allé au NE :
d i1
d i≤0
x i1 , y i1=x i1 , y i
x i1 , y i1=x i1 , y i1
d i1=F x2, y1/2=d i2 dy
d i1=F x2, y3 /2=d i2 dy−2 dx
61
Infographie
Pipeline graphique
Algorithme valable pour un octant
Bresenham( x1, y1, x2, y2 ){
dx = x2 – x1dy = y2 – y1d = 2*dy – dxplot( x1, y1 )while (x1 < x2 ){
if (d <= 0) // ESTd = d + 2*dy
else // NORD-EST{
d = d + 2*(dy-dx)y1 = y1 + 1
}x1 = x1 + 1plot( x1, y1 )
}}
62
Infographie
Pipeline graphique
Que faire si l'on ne se trouve pas dans le bon octant ?
Intervertir x et y Intervertir les points de départ et d'arrivée Remplacer y par -y
63
Infographie
Pipeline graphique
Il existe le même genre d'algorithme pour tracer les cercles (cf littérature)
Qu'en est il de l'aliasing ? Existence d'algorithmes dérivés de celui de Bresenham
permettant de traiter l'aliasing directement
Cf . Algorithme de X. Wu Oversampling → discrétisation sur une grille plus fine,
puis moyenne dans les « gros » pixels.
Bresenham, Jack E. "Algorithm for computer control of a digital plotter", IBM Systems Journal, Vol. 4, No.1, pp. 25–30, 1965
Wu, Xiaolin. "An efficient antialiasing technique". Computer Graphics 25 (4): 143–152, 1991.
64
Infographie
Pipeline graphique
65
Infographie
Pipeline graphique
Interpolation On attribue des valeurs aux sommets (couleur,
normale, etc...) On souhaite disposer d'une valeur représentative le
long de la ligne, pour chaque pixel « allumé » On aimerait une variation progressive d'une valeur
à l'autre le long de la ligne 1D :
2D,3D : est simplement la fraction de distance entre les points de départ et d'arrivée.
f x=1− f 0 f 1
=x−x0/ x1−x0
66
Infographie
Pipeline graphique
Interpolation Les pixels ne sont pas situés exactement sur la
ligne On définit une fonction par projection sur la ligne
C'est linéaire Donc on peut
utiliser lesrésultats pré-cédents pourinterpoler
P0
P1
v
=v x / L=v y / L
=v⋅Q−P0/ L
L=v⋅P1−P0
67
Infographie
Pipeline graphique
Interpolation Les pixels ne sont pas situés exactement sur la
ligne On définit une fonction par projection sur la ligne
C'est linéaire Donc on peut
utiliser lesrésultats pré-cédents pourinterpoler
P0
P1
v
=v x / L=v y / L
=v⋅Q−P0/ L
L=v⋅P1−P0
68
Infographie
Pipeline graphique
Interprétation alternative On met à jour d et de pixel en pixel
d nous dit à quelle distance on se trouve de la ligne nous dit à quelle position on se trouve le long de la
ligne
d et sont des coordonnées par rapport à un repère lié avec la ligne
69
Infographie
Pipeline graphique
Interprétation alternative La boucle signifie la visite des pixels par lesquels
passe la ligne Interpolation de d et pour chaque point Émission d'un fragment si le pixel est dans la bande
L'interpolationdevient l'opé-ration primaire
P0
P1
v
u
70
Infographie
Pipeline graphique
Interprétation alternative
P0
P1
v
u
x=ceil(x0)y=round(m*x+b)d=m*(x+1)+b-y etc...while (x<floor(x1)){
if (d>0.5){
y=y+1d=d-1 etc ...
} else
{x=x+1d=d+m etc...
}If (-0.5 < d <= 0.5)
plot(x,y, … )}
71
Infographie
Pipeline graphique
Rastérisation des triangles Cas le plus commun dans la plupart des
applications Avec un bon antialiasing, cela peut être le seul cas !
Certains systèmes effectuent le rendu d'une ligne avec deux triangles très allongés
Triangle représenté par 3 sommets L'algorithme se présente sous la même forme
que l'algorithme de rasterisation d'une ligne On marche de pixel en pixel Calcul de fonctions linéaires au fur et à mesure Celles ci nous permettent de savoir si on est dedans... ou
dehors
72
Infographie
Pipeline graphique
Rastérisation des triangles En entrée :
Trois points 2D Des valeurs à interpoler à chaque pixel
En sortie : une liste de fragments, avec : Les coordonnées entières des pixels Les valeurs interpolées
x0 , y0 ; x1 , y1; x2 , y2
q00 ,⋯, q0 n ; q10 ,⋯, q1 n ; q20 ,⋯ , q2 n
x , y
q0 ,⋯ , qn
73
Infographie
Pipeline graphique
Rastérisation des triangles Évaluation incrémentale de fonctions linéaires sur
les pixels de la grille Fonctions définies par des valeurs spécifiées aux
les sommets Utilisation de
fonctions spécifiques pour déterminerl'ensemble des fragmentsà renvoyer x0 , y0
q00 ,⋯ , q0n
x1 , y1
q10 ,⋯ , q1n
x2 , y2
q20 ,⋯ , q2n
(x , y)
q0 ,⋯ , qn
sommet
fragment
74
Infographie
Pipeline graphique
Evaluation linéaire incrémentale Une fonction linéaire (affine) sur le plan est :
Il est efficace de l'évaluer sur une grille :q x , y =c x xc y yck
q x1, y=c x x1c y yck=q x , yc x
q x , y1=c x xc y y1ck=q x , y c y
+cx+c
x+c
x
+cy
+cy
.....
.....
75
Infographie
Pipeline graphique
Interpolation des valeurs aux sommets Déterminer qui définissent la fonction
linéaire unique qui donne les valeurs correctes aux sommets
3 paramètres , trois équations :
Matrice singulière si le triangle est dégénéré (trois points alignés)
cx , c y , ck
c x x0c y y0ck=q0
c x x1c y y1ck=q1
cx x2c y y2ck=q2x0 y0 1x1 y1 1x2 y2 1
cx
c y
ck=
q0
q1
q2
76
Infographie
Pipeline graphique
Interpolation des valeurs aux sommets Translation de l'origine des axes vers
Système linéaire 2x2
Solution en utilisant la règle de Cramer
x0 , y0
q x , y=c x x−x0c y y− y0q0
q x1, y1=c x x1−x0c y y1− y0q0=q1
q x2, y2=c x x2−x0c y y2− y0q0=q2
x1−x0 y1− y0
x2−x0 y2− y0cx
c y=q1−q0
q2−q0
c x= q1 y2− q2 y1/ x1 y2− x2 y1
c y= q2 x1− q1 x2/ x1 y2− x2 y1
77
Infographie
Pipeline graphique
Quels sont les fragments à considérer ? Ceux dont ceux dont les coordonnées
barycentriques sont positives … Algébriquement, on a
À l'intérieur si
Pineda, Juan, " A parallel algorithm for polygon rasterization" Computer Graphics 22 (4): 17-20, 1988
a
c
b
, ,
p= a b c=1
0 ;0 ;0
78
Infographie
Pipeline graphique
Les coordonnées barycentriques sont des fonctions interpolées
Chaque coordonnée vaut 1 sur un sommet , 0 sur les autres
Elles sont une représentation implicite des équations des cotés du triangle...
79
Infographie
Pipeline graphique
Rasterisation pixel par pixel (Algorithme de Pineda - 1998)
On visite conservativement un super-ensemble des pixels à afficher
Interpolation des fonctions linéaires Utilisation des
fonctions coordonnéesbarycentriquespour savoirquand émettreun fragment
x0 , y0
q00 ,⋯ , q0n
x1 , y1
q10 ,⋯ , q1n
x2 , y2
q20 ,⋯ , q2 n
80
Infographie
Pipeline graphique
Rasterisation des triangles Attention aux arrondis et décisions arbitraires
On doit visiter ces pixels au moins une fois... (sinon il y a un trou)
Mais pas deux fois ! (ils prendraient alors une couleur arbitraire en fonction de l'ordre du tracé)
Solution élégante :antialiasing...
81
Infographie
Pipeline graphique
Pipeline
Flux de commandes
Géométrie transformée
Fragments ( ~ pixels + données interpolées )
Mémoire de trame (framebuffer)
Application
Opérations sur les sommets (vertex processing)
Rastérisation
Opérations sur les fragments (fragment processing)
Affichage
On est ici
Transformations 3D, ombrage
Composition, mélange, ombrage,
Ce que l'utilisateur voit
Conversion des primitives en
fragments
82
Infographie
Pipeline graphique
Le z-buffer (mémoire de profondeur) Dans beaucoup d'applications, maintenir un
classement en profondeur est trop coûteux Le classement change avec le point de vue.
Il existe l'algorithme de partition binaire de l'espace Indépendant du point de vue; mais :
Structures de données associées relativement complexes (difficile à implémenter directement dans le matériel)
Découpage des primitives Construction et initialisation lente On doit généralement connaître l'ensemble des primitives en
avance
83
Infographie
Pipeline graphique
Solution utilisée habituellement: faire le tracé dans n'importe quel ordre, en gardant trace du plus proche
Utiliser un canal de plus par pixel pour conserver la profondeur la plus faible tracée jusqu'à présent
Quand on trace à nouveau un pixel, on compare la profondeur actuelle avec celle stockée. On ne trace effectivement que si cette dernière est supérieure.
84
Infographie
Pipeline graphique
Le z-buffer
Exemple de technique de « force brute » utilisant beaucoup de mémoire mais qui est devenu un standard
Fol
ey e
t al.
85
Infographie
Pipeline graphique
Le z-buffer De façon évidente, limité aux images bitmap (non
vectorielles) Un peu plus difficile à implémenter pour tenir
compte d'un canal alpha...(transparence)
86
Infographie
Pipeline graphique
Z-buffer et transparence On sépare les objets opaques des autres.
1) Tracer les objets opaques avec mise à jour du z-buffer activée.
2) Ensuite, classer les entités partiellement transparentes dans un arbre BSP
3) Dessiner les entités transparentes dans l'ordre de profondeur décroissante (utiliser le BSP), en tenant compte du z-buffer mais sans mettre celui ci à jour (c'est inutile)
On tient compte du z-buffer car les faces transparentes situées derrière les faces opaques ne sont pas visibles.
87
Infographie
Pipeline graphique
Le z-buffer : précision limitée Le canal supplémentaire est généralement codé
sous forme d'un entier (comme un canal couleur) :
Cause : Implémentation hardware (simple et rapide) Il est possible d'avoir des objets distincts qui sont
confondus (vus à la même distance) si la valeur (un entier = arrondi) dans le z-buffer est la même
La précision est répartie entre n (le plan proche) et f (le plan lointain)
Ceux ci on déjà servi à définir le volume observable, cf cours 2.
0 z*N −1
88
Infographie
Pipeline graphique
z*=0
z*=N −1
Plan n Plan f
Le z-buffer
89
Infographie
Pipeline graphique
Le z-buffer Soit une représentation entière à b bits (8 ou 16...)
Quelle est la précision du z-buffer? Si le z stocké dans le z-buffer est proportionnel à la
distance réelle (cas des projections orthogonales): On dispose de N=2b cases pour une distance de f-n La précision (indépendante de la distance) est donc de
: pour maximiser la précision, il faut minimiser f-n
Si une projection perspective est utilisée, le z stocké dans le z-buffer est proportionnel au résultat obtenu après la division perspective.
La dimension des cases est variable en fonction de la profondeur
z= f −n
2b
90
Infographie
Pipeline graphique
z*=0 z*
=N −1
Plan n Plan f
Cas orthographique
Cas perspectif
Le z-buffer
91
Infographie
Pipeline graphique
Le z-buffer Dans le cours 2, on avait calculé z
c après la
transformation perspective et la division :
x , y , z ,1⋅2∣n∣r−l
0 0 0
02∣n∣t−b
0 0
rlr−l
tbt−b
∣ f ∣∣n∣∣n∣−∣ f ∣
−1
0 02∣ f ∣∣n∣∣n∣−∣ f ∣
0
M proj _ persp _ OpenGL
= X ,Y ,∣ f ∣∣n∣∣n∣−∣ f ∣
⋅z2∣ f ∣∣n∣∣n∣−∣ f ∣
,− z z c=
∣ f ∣∣n∣∣ f ∣−∣n∣
2∣ f ∣∣n∣
z ∣ f ∣−∣n∣
zc=f nf −n
2 f n
z f −n
… en comptant f, n et z positivement et avec f >n
92
Infographie
Pipeline graphique
Le z-buffer L'intervalle pour z
c est 2 (de -1 à 1) et on a toujours
N cases.
On veut connaître la taille des cases dans l'espace réel, on inverse...
La case la plus large est pour z=f :
zc=f nf −n
2 f n
z f −n zc≈
2 z f n
z2 f −n
=2N
z=z2 f −n
N f n
zmax=f f −n
N n
93
Infographie
Pipeline graphique
Le z-buffer Exemple: n est à 1 mètre, f à 100 mètres, le z-buffer
dispose de 8 bits → N=256, quelle est la répartition des case ?
Avec n=10 :
z=z2 f −n
N f n zmax=
f f −n
N n=
100⋅99256⋅1
=39 m 0.15 m avec 16 bits
zmin=n f −n
N f=
1⋅99256⋅100
=0.0039 m
zmax=f f −n
N n=
100⋅90256⋅10
=3.5 m 0.013 m avec 16 bits
zmin=n f −n
N f=
10⋅90256⋅100
=0.035 m
94
Infographie
Pipeline graphique
Le z-buffer Pour un bon fonctionnement du z-buffer, il faut donc
maximiser n et minimiser f. Ne surtout pas poser n=0 → équivalent à
désactiver le z-buffer. En général, le nombre de bits b est imposé par
l'architecture matérielle (habituellement 16, 24 ou 32 bits)
Le plus est le mieux mais cela prend autant de mémoire que l'image (habituellement codée sur 24 bits)
95
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
Projection des extrémités
96
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
Projection du milieu du segment ≠ milieu des projection des points extrémitésInterpolation linéaire dans l'espace de l'écran ≠ de l'interpolation dans l'espace de l'œil.
p1
p2
p1 p2
2
97
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
Projection du milieu du segment ≠ milieu des projection des points extrémitésInterpolation linéaire dans l'espace de l'écran ≠ de l'interpolation dans l'espace de l'œil.
z1 z2
Se projette au milieu...
z1z2/2
98
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
Projection du milieu du segment ≠ milieu des projection des points extrémitésInterpolation linéaire dans l'espace de l'écran ≠ de l'interpolation dans l'espace de l'œil.
répartition équitable sur z (distance)
99
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
Projection du milieu du segment ≠ milieu des projection des points extrémitésInterpolation linéaire dans l'espace de l'écran ≠ de l'interpolation dans l'espace de l'œil.
z c1 z c2
Se projette au milieu...
zc1z c2/2
100
Infographie
Pipeline graphique
Interpolation en projection perspectivePlan de projection
œil
La grandeur reliée à la profondeur que l'on doit interpoler (au niveau pixel) est zc
(profondeur écran) obtenue après la division perspective, et non z, la coordonnée réelle
répartition équitable sur z c (profondeur écran)
101
Infographie
Pipeline graphique
La correction de perspective (utilisation de zc au lieu
de z ) permet d'éviter les problèmes avec les textures appliquées sur des surfaces inclinées
F u=1−u F 0u F 1
F u=
1−uF 0
zc0
uF 1
zc1
1−u1zc0
u1zc1
wik
iped
ia
F0
F1
102
Infographie
Pipeline graphique
Pipeline minimal Etape « sommets » (input : positions 3D / sommet et
couleur / triangle) Transformation de la position (espace objet → espace œil) Transformation de la position (espace œil → espace écran) Passage de la couleur (pas d'interpolation = constante sur le
triangle) Etape « Rasterisation »
Liste de pixels Passage de la couleur
Etape « fragments » (output : couleur) Ecrire directement sur les plans couleur de la mémoire de trame
103
Infographie
Pipeline graphique
104
Infographie
Pipeline graphique
Pipeline minimal avec z-buffer Etape « sommets » (input : positions 3D / sommet et
couleur / triangle) Transformation de la position (espace objet → espace œil) Transformation de la position (espace œil → espace ecran) Passage de la couleur (pas d'interpolation = constante sur le
triangle) Etape « Rasterisation »
Interpolation de zc (z dans l'espace écran)
Passage de la couleur
Etape « fragments » (output : couleur, zc)
(Ecrire sur les plans couleur et mettre à jour le z-buffer) si zc < z
c
courant
105
Infographie
Pipeline graphique
106
Infographie
Pipeline graphique
Ombrage plat Utilisation de la « vraie » normale du triangle Apparence
facettisée Vue la plus
réaliste de la vraie géométrie
Foley et al.
107
Infographie
Pipeline graphique
Pipeline avec z-buffer et ombrage plat Etape « sommets » (input : positions 3D / sommet et
couleur + normale / triangle) Transformation de la position (espace objet → espace œil) Calcul de la couleur (ombrage plat) avec la normale (une couleur
par triangle) Transformation de la position (espace œil → espace écran)
Etape « Rasterisation » Interpolation de z
c (z dans l'espace écran)
Passage de la couleur
Etape « fragments » (output : couleur, zc)
(Ecrire sur les plans couleur et mettre à jour le z-buffer) si zc < z
c
courant
108
Infographie
Pipeline graphique
Ombrage plat
109
Infographie
Pipeline graphique
Observateur et illumination locaux vs. lointains Illumination de Phong requiert de l'info géométrique
Vecteur lumière (fonction de la position) Vecteur observateur (fonction de la position) Normale à la surface (obtenu par calcul)
Les vecteurs observateur et lumière changent Ils doivent être calculés et normalisés pour chaque
facette
observateur
lumière
110
Infographie
Pipeline graphique
Observateur et illumination locaux vs. lointains Cas ou ceux ci sont lointains
Illumination parallèle Projection presque orthographique Dans les deux cas, les vecteur lumière et observateur
changent très peu Une optimisation possible ( et fréquente ) est de les
considérer comme lointains.
111
Infographie
Pipeline graphique
Lumière directionnelle Le vecteur lumière pointe toujours dans la même
direction
Dans beaucoup de cas, cela accélère le traitement (matériel) de l'illumination
observateur
lumière[ x y z 0 ]
112
Infographie
Pipeline graphique
Observateur à l'infini Projection orthographique ?
Projection selon un angle constant – modifie la géométrie On peut faire cela aussi pour la projection
perspective, uniquement pour le calcul de l'illumination
Le vecteur observateur est considéré constant (par exemple c'est la normale au plan image)
Produit des résultats bizarres si camera grand angle Ombrage de Blinn-Phong : vecteur observateur, vecteur
source de lumière et vecteur bisecteur (cf cours 4) tous constants
113
Infographie
Pipeline graphique
Lumière directionnelle + observateur lointain
Seule la normale varie. Cela signifie que la teinte de chaque facette (à normale constante) est constante.
observateur
lumière[ x y z 0 ]
[ xo yo zo 0]
114
Infographie
Pipeline graphique
Interpolation de Gouraud On veut souvent une apparence lisse, sans pour
autant augmenter la résolution de la discrétisation Se souvenir du mapping : sensibilité aux normales plus
importante que la sensibilité aux positions Idée : couleur calculée aux sommets des facettes Interpolation pour avoir la couleur de chaque pixel
lors de la rasterisation
115
Infographie
Pipeline graphique
Interpolation de Gouraud
Foley et al.
116
Infographie
Pipeline graphique
Pipeline avec z-buffer et interpolation de Gouraud
Etape « sommets » (input : positions 3D / sommet et couleur + normale / sommet )
Transformation de la position (espace objet → espace œil) Calcul de la couleur par sommet (peu importe le modèle
d'ombrage...) Transformation de la position (espace œil → espace écran)
Etape « Rasterisation » Interpolation de z
c (z dans l'espace écran), couleur r,g,b
Etape « fragments » (output : couleur, zc)
(Ecrire sur les plans couleur et mettre à jour le z-buffer) si zc < z
c
courant
117
Infographie
Pipeline graphique
Interpolation de gouraud
118
Infographie
Pipeline graphique
Interpolation de Gouraud Normales aux sommets
Mathématiquement indéfinies Si la tessellation (triangulation) est obtenue à partir d'une
surface mathématiquement lisse (sphère, NURBS, etc..), on peut prendre la normale à la vraie surface en ce point
Si on n'y a pas accès, on doit trouver une approximation Schéma simple : moyenner les normales des triangles adjacents
N s=
∑i
N i
∥∑i
N i∥N s
N 1
N 2
N 3N 4
N 5
119
Infographie
Pipeline graphique
Interpolation de Gouraud On peut l'appliquer à n'importe quel modèle
d'illumination Diffuse Blinn-Phong Etc ...
Toutefois, pour les modèles spéculaires cela ne fonctionne pas bien
Variations trop brusques de la luminosité (si le point spéculaire est de taille très inférieure à un triangle)
120
Infographie
Pipeline graphique
Ombrage de Blinn et interpolation de Gouraud
Foley et al.
121
Infographie
Pipeline graphique
Interpolation de Phong Consiste en l'interpolation des normales
Aussi facile que l'interpolation des couleurs Mais on calcule le modèle d'illumination à chaque pixel
plutôt que à chaque sommet (après renormalisation des normales)
Dans le pipeline graphique, cela signifie que l'on déplace le traitement de l'illumination depuis l'étape « traitement des sommets » vers l'étape « traitement des fragments »
122
Infographie
Pipeline graphique
Pipeline
Flux de commandes
Géométrie transformée
Fragments ( ~ pixels + données interpolées )
Mémoire de trame (framebuffer)
Application
Opérations sur les sommets (vertex processing)
Rastérisation
Opérations sur les fragments (fragment processing)
Affichage
On est ici
Transformations 3D, ombrage
Composition, mélange, ombrage,
Ce que l'utilisateur voit
Standards « langage »OpenGL, etc...
Conversion des primitives en
fragments
123
Infographie
Pipeline graphique
Pipeline avec z-buffer et interpolation de Phong Etape « sommets » (input : positions 3D / sommet et
couleur + normale / sommet ) Transformation de la position (espace objet → espace œil) Transformation de la position (espace œil → espace écran) Passage de la couleur
Etape « Rasterisation » Interpolation de z
c (z dans l'espace écran), couleur r,g,b,
normale x,y,z
Etape « fragments » (output : couleur, zc)
Calcul de l'ombrage en utilisant la couleur et la normale interpolées
(Ecrire sur les plans couleur et mettre à jour le z-buffer) si zc < z
c
courant
124
Infographie
Pipeline graphique
Interpolation de Phong
125
Infographie
Pipeline graphique
OpenGL Certains modèles d'ombrage et d'interpolation font
partie du standard (typiquement : Phong, Lambert, Gouraud, Blinn-Phong …), il n'y a rien à faire .
Pour les autres, il existe une API permettant de coder d'autres modèles
soit au niveau du « vertex shader » (traitement au niveau des sommets),
Soit au niveau du « fragment shader » (traitement après la rasterisation, pixel par pixel)
Les cartes graphiques récentes permettent de réellement programmer (en langage pseudo C) le « vertex shader » ou le « fragment shader » (P.ex. Nvidia CUDA , OpenCL)
126
Infographie
Pipeline graphique
Programmable !
Non / peuprogrammable
127
Infographie
GPGPU
GPGPU Utilisation des capacités de calcul des GPU pour
effectuer autre chose que du rendu graphique... Les GPUs récents sont relativement polyvalents
(mais moins que les CPUs) Branchements possibles Accès mémoire aléatoire Mais ils restent faits pour les opérations vectorielles
Existence de standards de fait Open Computing Language (OpenCL, ouvert) Common Unified Device Architecture (CUDA, Nvidia) Direct Compute (Microsoft)
128
Infographie
GPGPU
OpenCL – langage similaire au C Programme hôte en C++ (par exemple) Le code OpenCL est sous forme d'une chaîne de
caractères (char[] ou string ) Le code OpenCL est compilé par le « driver » de la
carte graphique, et chargé sur le GPU par l'appel de fonctions spécifiques
Pour l'utilisation, le programme hôte lui passe des paramètres par tableaux en mémoire principale
Le calcul est effectué sur le GPU Le résultat est rendu au programme hôte,
également en mémoire principale
129
Infographie
GPGPU
Exemple de code OpenCL__kernel void VectorAdd(__global float* c, __global float* a , __global float* b, __constant float *cst{ // Index of the elements to add unsigned int n = get_global_id(0); unsigned int nl = get_local_id(0); unsigned int gsz = get_global_size(0); unsigned int lsz = get_local_size(0); unsigned int gid = get_group_id(0); // do some math from vectors a and b and store in c __private float res; res=0.; int i; for (i=0;i<100;++i) // not a loop over elements of the arrays { res=a[n]+sin(a[n])+b[n]; if (res>5.5) res=a[n]* (*cst) ; } c[n] = res;}
130
Infographie
GPGPU
Dans le programme hôte … initialisationstd::string Src ; // programme source (cf slide precedent)
std::vector<cl::Platform> platforms;cl::Platform::get(&platforms);
cl_context_properties properties[] = { CL_CONTEXT_PLATFORM,(cl_context_properties)(platforms[0])(),
0};
cl::Context context(CL_DEVICE_TYPE_ALL, properties);std::vector<cl::Device> devices =
context.getInfo<CL_CONTEXT_DEVICES>();cl::Program::Sources
source(1,std::make_pair(Src.c_str(),Src.size()));
cl::Program program = cl::Program(context, source);
program.build(devices); // compilation !
131
Infographie
GPGPU
Dans le programme hôte … appelcl::CommandQueue queue(context,devices[0],0,&err);cl::Buffer GPUOutVec(context, CL_MEM_WRITE_ONLY
,sizeof(float)*SIZE, NULL, &err);float cst=1;cl::Buffer GPUVec1(context,CL_MEM_READ_ONLY|CL_MEM_COPY_HOST_PTR
,sizeof(float)*SIZE,HostVec1,&err);cl::Buffer GPUVec2(context,CL_MEM_READ_ONLY|CL_MEM_COPY_HOST_PTR
,sizeof(float)*SIZE,HostVec2,&err);cl::Buffer GPUCst1(context,CL_MEM_READ_ONLY|CL_MEM_COPY_HOST_PTR
,sizeof(float),&cst,&err);cl::Event event1;cl::Kernel kernel(program_, "VectorAdd", &err);kernel.setArg( 0, GPUOutVec);kernel.setArg( 1, GPUVec1);kernel.setArg( 2, GPUVec2);kernel.setArg( 3, GPUCst1);
queue.enqueueNDRangeKernel(kernel,cl::NullRange,cl::NDRange(SIZE_TEST),cl::NullRange,NULL,&event1);
event1.wait();// a ce point, le calcul a ete fait.
132
Infographie
GPGPU
Dans le programme hôte … collecte
Exemple complet disponible sur le site du cours
// a ce point, le calcul a ete fait.
cl::Event event2;queue.enqueueReadBuffer(GPUOutVec,CL_TRUE,0,
SIZE_TEST*sizeof(float),HostOutVec, NULL, &event2);event2.wait();
// on dispose dans HostOutVec du resultat
for (int Rows = 0; Rows < SIZE_TEST/32; Rows++){
for (int c = 0; c <32; c++) std::cout << HostOutVec[Rows * 32 + c] << " " ; std::cout << std::endl;}
133
Infographie
GPGPU
OpenCL est multiplateforme Le programme précédent peut être compilé sut tout
ordinateur (disposant d'un driver GPGPU) Le code peut même être exécuté sur...CPU. (en
l'absence de carte graphique récente) Il existe de « faux » drivers qui compilent et exécutent le
code OpenCL sur le CPU. Performance : facteur 2 à 100 en faveur du GPU pour
des opérations vectorielles (sur de gros tableaux) Core i7 6 cœurs 3,33 Ghz (très performant) vs. Nvidia Quadro
FX 580 (carte assez peu performante) : 110 s. vs 55 s. Sur une carte spécialisée Nvidia Tesla C2075 : 11 s.