Lien de la note Hackmd

Le rendu

Rendu temps reel vs Rendu photorealiste

Rendu photorealiste:
- Objectif:
  - Generation d’images realistes
  - Contrainte de temps faible
- Strategies
  - Object-based rendering algorithms
    - Illumination globale calculee independamment du point de vue
  - Image-based rendering algorithms
    - Illumination calculee partiellement, en fonction du point de vue
  - Deterministic rendering algorithms
  - Monte Carlo rendering algorithms
Rendu temps reel
- Objectif:
  - Generation rapide d’images

Le rendu temps reel

Principe general

Modelisation des objets dans un repere local
Modelisation de la scene dans un repere global
Projection de la scene sur le plan image
- passage repere global au repere camera
- projection sur le plan image (+dessin 2D)

Pour faire le rendu:

camera qui possede son propre repere
les objets sont exprimes dans le repere lies a la scene
- on les change de repere et on les exprimes dans le repere lie a la camera
- on peut maintenant les projeter sur le plan image.

Algorithmes 3D fondamentaux

Projection des objets sur le plan image:

Comment projeter un objet sur le plan image ? Plusieurs objets ?

Il faut identifier les problemes!

Comment determiner les sommets/face non visibles ?
Comment determiner les objets caches (ou partiellement caches ?)
Comment determiner les objets qui sont hors champ (ou partiellement hors champ/derrrier le plan image) ?
Comment determiner les objets qui sont derriere le plan image ou partiellement visible ?

Afin de les resoudre et:

avoir une projection correcte
etre efficace

Clipping

Comment determiner les objets qui sont hors champ (ou partiellement hors champ/derrrier le plan image) ?
Comment determiner les objets qui sont derriere le plan image ou partiellement visible ?

Estimation de la positiopn d’une face par rapport aux plans
Elimination des faces a l’exterieur
Decoupage des polygones a cheval (equations parametriques)

Backface culling

Comment determiner les faces non visibles ?

Enumerer les sommets toujours dans le meme sens
Determiner l’orientation de la face par rapport a l’axe optique:
- Calculer le vecteur normal a la surface (produit vectoriel)
- Determiner l’angle entre le vecteur normal a la surface et le vecteur directeur de l’axe optique (produit scalaire)

Comment determiner les objets caches ou partiellement caches ?

Trier les objets et les dessiner dans l’ordre
Comment determiner cet ordre ?
- Utiliser le centre de gravite
- Ne fonctionne pas dans tous les cas !

Si on dessine du plus pres au plus loin au lieu de par-dessus, on peut etre plus rapide.

Utilisation d’un arbre B.S.P. (Binary Space Partitionning Tree)

Chaque noeud represente un hyperplan (deduit d’une face F)
Le 1$^{er}$ fils contient les faces du demi-espace derriere F et le second fils contient les faces du demi-espaces devant F
Lorsque l’hyperplan intersecte une face, la face est coupee en 2
On peut deduire un ordre de parcours des polygones pour les dessiner du plus eloigne au plus proche
idem, du plus proche au plus eloigne

Efficacite:

Compromis entre arbre equilibre et nombre de polygones (fragmentation des polygones)

Z-buffer

Comment determiner les objets caches ou partiellement caches ? Utilisation du Z-buffer

Sauvegarde de la profondeur pour chaque pixel dessine

Avantages	Inconvenients
Simple	Oblige a projeter l’ensemble des polygones
	Probleme de resolution lors de l’encodage du Z

Projection

Une fois que l’on a elimine les elements hors champ de la camera, les elements qui ne sont pas de face

On projette les sommets et on dessine (et rempli) le polygone en tenant compte de la profondeur

\[\begin{aligned} &p_i=\frac{fp}{z} &(1) \end{aligned}\]

Algorithmes 2D fondamentaux

Remplissage de polygones

Suivant la projection des polygones, il faut dessiner/remplir le polygone
- Determiner si une partie n’est pas visibile
- Determiner la couleur et l’eclairage
  - Eventuellement plaquer une texture
- …
Les donnees sont la liste des sommets

Depend de plusieurs choses:

Triangle de polygone
- Triangle ?
- Convexe ?
- Quelconque…?
Donnees:
- Liste de sommet
Approches:
- Triangulation
- Remplissage direct
- Inondation

Algorithme:

Parcourir toutes les arretes de haut en bas et remplir horizontalement

Algorithme

Trier les sommets pour definir les section
- Ordre de remplissage
Determiner les arretes actives (dans la section)
- A chaque transition, il faut remettre a jour la liste des arretes actives
  - On arrive a une frontiere de section
  - On regarde le sommet suivant
  - Il faut desactiver l’arrete actuelle et activer la suivante
A chaque niveau il faut tracer des segments horizontaux
- On obtient des points d’intersection avec chaque arrete
- On les trie horizontalement pas ordre croissant

Il faut etre prudent car en arrivant a un niveau une arrete peut etre ignoree.

Simplification pour les polygones convexes (ou meme dans le cas du triangle)
- Se restreindre a des cas plus simples

Trace de segments

Trace rapide de segments
- Affichage de segments
- Suivi des arretes activer
Comment faire ?

Algorithme naif:

Repose sur l’utilisation des nombres a virgule flottante (un peu lent)

  
for (x = 1; ...;) {
    y = ax + b
    plot(x,y)
}

Critiquons ce bout de code: c’est pas ouf

Si on parcourt les x et qu’on veut dessiner les y
- Matrice de pixel
- Si coeff faible (ex: 1), on avance lentement
- Si on a a = 4, pente tellement forte qu’on a des discontinuite dans le trace du segment

Est-ce qu mon algo est bien ?

a est un ratio donc float
multiplication $\rightarrow$ beaucoup de calculs
Le resultat est un float avec une multiplication et addition

Autre solution: Bresenham (65?)

Uniquement avec des additions d’entiers

Critere:

$y=mx+p$ avec $m=\frac{d_y}{d_x}$
$D=d1-d2=(m(x_p+1)+p+y_p)-(y_p+1-m(x_p+1)+p)$
$D=d1-d2=2d_y(x_p+1)-2d_xy_p-d_x+2d_xp$
$D\lt0\Rightarrow(x_{p+1}, y_p)$ inc: $2d_y$
$D\gt0\Rightarrow(x_{p+1},y_{p+1})$ inc: $2d_y-2d_x$

Probleme d’aliasing.

Trace de cercle

Algorithme naif

Repose sur l’utilisation des nombres a virgule flottante float (un peu lent)
Utilisation des symetries
Precalcule des fonctions trigos

Algorithme de Bresenham

Meme esprit que pour les segments

Critere:

$D(P) = x^2 + y^2 - r^2$
$D(A) = (x+1)^2 + y^2-r^2$
$D(B) = (x+1)^2+(y-1)^2-r^2$
$S=D(A)+D(B)$
$S\ge0\Rightarrow B$
$S\lt0\Rightarrow A$
Calcul de S incremental

Clipping

Une fois qu’on a projete le polygone, on l’a clipe mais on peut aussi le projeter et le fenetrer.

Meme s’il est possible de fenetrer les polygones dans l’espace, on peut aussi le faire dans le plan (apres projection)

Fenetrage rectangulaire de segments:
- Cohen-sutherland
Fenetrage d’un polygone a partir des segments:
- Weiler-Atherton

Fenetrage rectangulaire de segments

Cohen-sutherland

Pour fenetrer il faut des criteres simples et rapides
Fenetre de vue: 4 frontieres dans le plan
Code associe a la position relative du point dans le plan
Attribue a chaque sommet un code a 4bits
- Chaque bit representant la position relative du point par rapport a la frontiere

Les points a l’interieur de l’image on tous leurs bits a 0
Les points a l’exterieur ont au moins un bit a 1

Pour savoir si une arrete est completement visible, on fait un ou logique entre le code du premier et deuxieme sommet
- Si le resultat = 0, l’arrete est entierement visible

Pour savoir si une arrete est visible quand ses sommets sont hors de l’image, on fait un et logique
- Si resultat = 0, l’arrete est potentiellement visible
- Sinon, probablement hors de l’image

Weiler-Artherton

Polygone projete sur l’image:

Partie a l’interieur
Partie a l’exterieur

On prend notre polygone et fenetre de vue et on y insere tous nos points d’intersection:

Ex: AB1, 1 sommet supplementaire, on l’insere
Obtient 2 nouveaux polygones

Comment trouver le polygone resultat de la fenetre de vue ?

Partir d’un point dun polygone depuis la fenetre de vue
Parcours les arretes
A point d’intersection, change de polygone (polygone $\leftrightarrow$ quadrilatere)

Toujours partir d’un point in l’interieur de la fenetre sinon on tourne en rond. S’il n’y a pas de point du polygone a l’interieur de l’image, commencer par une intersection
Avoir parcouru tous les points du polygone dans la fenetre

Cyrus-Beck

Fenetrage entre 2 polygones

Cyrus-Beck (Pour deux polygones convexes)

Connaitre la position d’un point $Q$ par rapport a un cote de la fenetre ?

\[\begin{align} &I(Q) = (Q-P).n \begin{cases} &= 0\\ &\lt0\\ &\gt0 \end{cases} &(2) \end{align}\]

Fenetrage d’un segment ?

$L(t)=A+(B-A)t$
$I(Q)=(Q-P).n$
$I(L(T)) = (L(T)-P).n$
Intersection
- $(L(t)-P).n = 0\Leftrightarrow t = \frac{(A-P).n}{A-B.n}$
$D=(B-A)$
- Cas 1: $D.N\lt0\Rightarrow t=t_{\text{sup}}$
- Cas 2: $D.N=0$
- Cas 3: $D.N\gt0\Rightarrow t=t_{inf}$
On recommence pour tout les segments de la fenetre
- puis si $t_{\text{inf}}\gt t_{\text{sup}}$ segment non visible
- sinon segment compris entre $[t_{\text{inf}}..t_{\text{sup}}]$

Polygones non convexe

Decoupage en polygones convexes
Triangulation de Delaunay

Retour sur le clipping

Application de Cohen-Sutherland sur la pyramide 3D

Peut appliquer l’algo en 3D
- Au lieu de 4 codes on en a 6

Determination de la couleur des pixels durant le remplissage

Remplissage en fonction de:

La couleur de la face ?
L’eclairage ?

Eclairage

Determination de la couleur

Modele de Lambert
- $I_d = k\times \frac{N.L}{\Vert N\Vert.\Vert L\Vert}$
- Meme niveau d’eclairement pour un polygone donne
  - Un peu moche d’avoir des polygones uniformes
  - Impression polygones plats

Modele de Gourand
- Essayer de lisser le polygone
- On calcule l’illumination a chaque extremite du polygone
- Interpoler l’illumination
- Repeter l’interpolation pour tous les points de la surface
- Utile quand on a beaucoup de points sur la surface

Anecdote: Sur les verisons ancienne de OpenGL, c’etait soit Lambert soit Gourand. Fabrizio voulait avoir une lampe torche pour son 1$^{er}$ projet OpenGL, des qu’un spot illumine un angle ca eclaire beaucoup plus que si on eclaire plus le centre

Modele de Phong
- On interpole la normale en tous les points du polygone suivant les arretes
- Beaucoup plus de calcul
- Marche mieux

Attention au calcul des normales

Echnatilloner suffisemment la surface ou bien placer la normale

On approxime une surface ronde par des polygones. Si on calcule Lambert, on espere que l’interpolation represente la normale reelle a la surface. L’aclairage donne l’impression de volume. Pour chaque sommet du maillage, on stoque la normale.

Resultats

La difference entre Phong et Gouraud se creuse lorsque le modele est pauvre

lightmap

Eclairages plus evolues

On peut afficher des eclairages pre-calcules (du moment qu’il n’y a pas trop d’illumination) Permet de donner pas mal de realisme en temps reel

Conclusion

Beaucoup d’algorithmes
Implementes dans les moteurs
- A connaitre pour inter-agir avec ces moteurs
De nouvelles technologies emergent (RTX…)

ISIM: Rendu temps reel

Le rendu

Le rendu temps reel

Principe general

Algorithmes 3D fondamentaux

Clipping

Backface culling

Comment determiner les objets caches ou partiellement caches ?

Z-buffer

Projection

Algorithmes 2D fondamentaux

Remplissage de polygones

Algorithme

Trace de segments

Autre solution: Bresenham (65?)

Trace de cercle

Clipping

Fenetrage rectangulaire de segments

Weiler-Artherton

Cyrus-Beck

Retour sur le clipping

Determination de la couleur des pixels durant le remplissage

Eclairage

Resultats

lightmap

Conclusion

Further Reading

ISIM: La modelisation

ISIM: Rappels

ISIM: Rendu photorealiste