Pipeline graphique OpenGL, DirectX etc · 2 Infographie Pipeline graphique Approche complémentaire...

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.