IFT3355: Infographie Visibilitéostrom/dift3355/pdf/04_visibilite.pdf2/10/2009 3 1. Algorithmes en espace image - Précision dépend de la résolution de l’image - La visibilité

2/10/2009

1

IFT3355: InfographieVisibilité

© Victor OstromoukhovDé I R ODép. I.R.O.

Université de Montréal

Visibilité

1. Pour créer une image, on doit premièrement effectuer la projection et le clippage

2. Pour une scène constituée d’objets opaques et non-réfléchissants, on doit ensuite déterminer ce qui est à l’avant pour chaque élément de l’image

3. Finalement, on doit afficher l’élément de l’image avec la bonne couleur

2/10/2009

2

Visibilité

• Déterminer les surfaces visibles ou éliminer les surfaces cachées

• Il existe deux classes d’algorithmes pour résoudre le problème de la visibilité:– Algorithmes en espace image

Algorithmes en espace objet– Algorithmes en espace objet

1. Algorithmes en espace image

• Détermine pour chaque élément d’image (de ppixels), l’objet (de n objets) qui est le plus près du centre de projection tout en étant dans le volume de vision

• O(n p)

Ex: 100 x (640x480) = 30,720,000 opérationsEx: 100 x (640x480) 30,720,000 opérations

2/10/2009

3

1. Algorithmes en espace image

- Précision dépend de la résolution de l’image- La visibilité doit être recalculée à chaque q

changement de résolution et/ou de positionnement de la fenêtre

+ Les algorithmes et leurs structures sont habituellement plus simples

Ex: tampon de profondeur, balayage de lignes, subdivision, lancer de rayons

2. Algorithmes en espace objet

• Détermine entre chaque objet lequel est devant l’autre étant donnée la direction de projection

• O( )

Ex: 100 x 100 = 10,000 opérations

2n

2/10/2009

4

2. Algorithmes en espace objet

+ Précision dépend de la résolution des objets+ La visibilité est indépendante de la résolution de p

l’image et peut même être indépendante de la position de la fenêtre

- Les algorithmes et leurs structures sont habituellement assez complexes

Ex: algorithme du peintre, octree, arbres BSP

Cohérences

• Hiérarchies en 3D• Face polygonale (si aucune inter-pénétration)p yg ( p )• Changements seulement aux segments• Faces orientées vers l’arrière (backface culling) • Similarités entre lignes de balayage adjacentes• Similarités entre régions adjacentes de l’espace• Similarités de profondeur pour des parties d’un

même objet• Similarités dans une séquence d’images

2/10/2009

5

Tampon de profondeur (z-buffer)

Initialise tous les pixelsrgb (x,y) = couleur arrière-plang ( ,y) pz (x,y) = distance arrière-plan

Pour chaque objet, scan-conversion dans le tamponPour chaque pixel (x,y) couvert par l’objet

Si distance-objet (x,y) < z (x,y) z (x,y) = distance-objet (x,y)rgb (x,y) = couleur objet


* * * * * * * ** * 5 6 * * * ** 5 6 6 * 3 * *

* * * * * * * ** * * * * * * ** * * * * 3 * *

* * * 3 4 4 4 5

* * 6 7 3 3 4 ** * * 3 3 4 4 ** * * 3 4 4 4 5

* * * * 3 3 4 ** * * 3 3 4 4 *

2/10/2009

6


Scan-conversion: remplissage par balayageProfondeur:

),,()()()()(

1312

1312 CBAPPPPPPPPN =

−×−−×−

=r

111111 0 CzByAxDDCzByAx −−−=⇒=+++BAD

1P

2P3P

consty

CyByxz

CyyBAxDyyxz

constx

CxAyxz

CByxxADyxxz

CByAxDyxz

CB

CA

==Δ

⎭⎬⎫Δ

−=Δ+−−−

=Δ+

==Δ

⎭⎬⎫Δ

−=−Δ+−−

=Δ+

−−−=

1),()(),(

1),()(),(

),(

Interpolation bilinéaire (alternative)

)( 121 zztzza −+=

)( 121 yytyys −+=1z

1yY

)( 121a

12

1

12

1

yyyy

zzzz sa

−−

=−−

)()()(

12

1121 yy

yyzzzz sa −

−−+=

)(

2z

3z

az pzbz

sy

2y

3yX

)()()(

13

1131 yy

yyzzzz sb −

−−+=

)()(

)(ab

apabap xx

xxzzzz

−−

−+=

X

Interpole aussi:couleur, texture, normale, etc.

2/10/2009

7


Avantages/désavantages:

+ simplicité, généralité+ hardware, parallélisme- mémoire additionnelle pour les tampons+ aucune mémoire pour conserver la scène- aliassage (en XY et en Z)

Z-fighting

Δz = f − n( )/2b pour b bits⎡ ⎤ ⎡ ⎤

dérivée de chaque côté

Majeed Hayat

z = n + f −fnzw

Δz ≈fnΔzw

zw2

Δzw

2Δz

n 0 0 00 n 0 00 0 n + f − fn0 0 1 0

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

xw

yw

zw

1

⎡

⎣

⎢ ⎢ ⎢ ⎢

⎤

⎦

⎥ ⎥ ⎥ ⎥

Donc rendre aussipetit que possible correspondà minimiser f et maximiser n

ΔzwmaxDonc rendre aussi

petit que possible correspondà minimiser f et maximiser n

taille des bins en espace mondeΔzw ≈ w

fn

Δzwmax ≈

fΔzn

lorsque z = f

2/10/2009

8

Partition de l’espace

• Dans l’algorithme du peintre, les objets sont ordonnés en fonction de leur distance à la fenêtre, et ils sont affichés du plus éloigné au plus rapprochéEx: celluloïdes, VLSI

• Dans certains cas, cet ordre estDans certains cas, cet ordre estimpossible sans découpageau préalable

Octree• Pour n’importe quel point de vue, on peut énumérer les faces

d’un cube de la plus éloignée à la plus rapprochée.• Cette approche se généralise à l’octree

• En alternant selon X, Y, Z et glissant le plan de subdivision, on obtient un kd-tree

2/10/2009

9

Partition binaire de l’espace (BSP tree)

• L’octree se généralise à son tour à la partition binaire de l’espace en se servant des plans de support des polygones comme éléments de séparation

+ Très utile lorsque la scène est statique mais que le point de vue peut être n’importe où dans la scènep p p

Création d’une partition binaire

BSPTree * BSPMakeTree (liste de polygones) – choisit un polygone comme racinep yg– pour tous les autres polygones p

• si p est devant, ajoute p à la liste de devant• si p est derrière, ajouter p à la liste de derrière• sinon, découpe p en deux par rapport au plan de la

racine et ajoute chaque moitié à sa liste respective

BSPTree = BSPCombineTree ( BSPMakeTree (liste de devant), racine, BSPMakeTree (liste de derrière))

2/10/2009

10

Exemple de construction d’arbre BSP

C1 C2

A

CB

DA

EB

C1 C2

EE

C1

B

D C2

Découpage en 3D

T1 = (a,b,A)( )T2 = (b,B,A)T3 = (A,B,c)

2/10/2009

11

Ordonnancement dans un arbre BSP

• Si l’oeil est d’un côté d’un plan, les objets de l’autre côté ne pourront jamais être devant un objet du même côté du plan que l’oeil

• On peut donc traverser l’arbre de derrière à devant pour tout point de vue en affichant simplement avec un algorithme du peintre

Algorithme d’affichage d’un arbre BSP

AfficheArbre (sousArbre) – si l’oeil est devant la racine

• AfficheArbre (sousArbre->arrière) • AffichePolygone (sousArbre->racine) • AfficheArbre (sousArbre->devant)

– sinon• AfficheArbre (sousArbre->devant)AfficheArbre (sousArbre devant)• AffichePolygone (sousArbre->racine)

• AfficheArbre (sousArbre->arrière) // si aucun backface culling

2/10/2009

12

Avantages et inconvénients du BSP+ Les plans de la pyramide de vue peuvent être

utilisés pour le clippage avec BSP+ Si l’illumination (shading) est coûteuse, on peut

aussi afficher de devant à derrière en n’affichant un pixel que s’il n’a pas déjà été affiché

+ On peut aussi traiter les ombres de sources de lumière ponctuellesObtenir un arbre BSP avec le moins de polygones- Obtenir un arbre BSP avec le moins de polygones coupés est une tâche complexe

- Problèmes de robustesse en créant des polygones étroits

Optimization du BSP

Racine T1: 2 nodesRacine T2: 4 nodesRacine T2: 4 nodes

n objets: n! possibiliés

2/10/2009

13

• Généralement, les techniques précédentes en espace image projettent les objets sur une fenêtre. Il faut alors projetertous les n objets: O(n p)

Lancer de rayons (ray tracing/ray casting)

tous les n objets: O(n p)• Le lancer de rayons (ou ray casting pour ne traiter que la

visibilité) consiste à lancerun rayon au travers de la fenêtrepour identifier la première surfaceentre la fenêtre et la scène 3D:O(n res) pour res pixelsO(n res) pour res pixels

• Traitement pixel par pixel plutôtque objet par objet

• Utilisé aussi pour le picking

• Un rayon est défini parune origine

Lancer de rayons - Le rayon

),,( 000 zyxgune directiondéfinie par un point sur la fenêtre

• Sous forme paramétrique, un rayon s’exprime comme

010 )( PPtPP −+=

)( 000 y),,( zyx ΔΔΔ

),,( 111 zyx

010

010

010

010

)(

zzzztzzyyyytyyxxxxtxx

−=ΔΔ+=

−=ΔΔ+=−=ΔΔ+=

2/10/2009

14

Lancer de rayons - Intersection avec un plan

• L’intersection d’un rayon avec un plan (A,B,C,D) consiste à exprimer le plan en fonction de la formep pparamétrique du rayon

CBADCzByAxt

DztzCytyBxtxADCzByAx

ΔΔΔ+++−

=

=+Δ++Δ++Δ+=+++

)(0)()()(

0

000

000

• Pour l’intersection avec un polygone, il faudra déterminer si le point d’intersection est à l’intérieur du polygone

zCyBxA Δ+Δ+Δ

Lancer de rayons - Intersection avec une sphère

• Similairement pour l’intersection d’un rayon avec une sphère

acbbt

zyxtzzyyxxtzyx

ztzytyxtxzyx

24

0)1()(2)(

1)()()(1

2

20

20

20000

2222

20

20

20

222

−±−=

=−+++Δ+Δ+Δ+Δ+Δ+Δ

=Δ++Δ++Δ+

=++

a2

0, 1 ou 2 intersections réelles

2/10/2009

15

Lancer de rayons - Visibilité au pixel

• Pour identifier la surface visible du pixel, il suffit d’intersecter tous les objets et de ne conserver que l’intersection ayant la plus petite valeur positive de t

1t2t

3t3t

3210 ttt <<<

Lancer de rayons récursif (ray tracing) • Le premier rayon identifie la visibilité à partir de l’oeil• Du point d’intersection, d’autres rayons peuvent être tracés

pour déterminer la visibilité des lumières et calculer leurspour déterminer la visibilité des lumières et calculer leurs contributions

• Du point d’intersection, d’autres rayons peuvent aussi être tracés pour déterminer les contributions de la réflexion et de la transmission/réfraction

• On doit s’assurer de ne pas ré-intersecter l’objet au nouveau point de départ (surface acné)p p ( f )– ajouter une distance epsilon au rayon (trouver la bonne

valeur par rapport aux objets et la scène) – ne pas intersecter la surface elle-même (plus limité:

surface convexe et test par rapport à la normale)

2/10/2009

16

Lancer de rayons récursif (ray tracing)

L2Lr

1Nr

1Rr1L

r

1Tr

3Lr

3Nr

3Rr

3Tr

Lancer de rayons: types de rayons

• Rayons d’ombre:)()(

i

ii PL

PLL−−

=r

• Rayons réfléchis:

)( i

11 )(2 −− −⋅= iiiii VNNVRrrrrr

iNr

iN

iRr

1−iVr

θ θiNr

iRr

1−iVr

2/10/2009

17

Lancer de rayons: types de rayons

• Rayons transmis / réfractés:(la loi de Snell) 1

2

2

1

sinsin

ηη

θθ

=( )

iNr

iNr

−

1−iVr

1θθ

1η 2η

iN iN

iTr2θ

Lancer de rayons: réfraction22 cossin θθ ii NMT

rrr−= 1sinθ

1−iVr

1cosθiNr

iNr

1

11

sin)cos(

θθ −−

= ii VNMrr

r

221

11 cossinsin

)cos( θθθ

θi

iii NVNT

rrr

r−

−= −

2112

1 cos)cos( θθηη

iiii NVNTrrrr

−−= −

1θ

2θ

sinθMr

1i

1

11

sincos

θθ

MVN ii

=− −

rr

2cosθiNr

−

iTr

21η

ηη =

Mr

121 )coscos( −−−= iii VNTrrr

ηθθη

( )122

122

22 cos11sin1sin1 θηθηθ −−=−=−

2sinθMiNr

−

( ) 12

12

1 ))(1(1)( −−− −⋅−−−⋅= iiiiiii VVNVNNTrrrrrrr

ηηη

2η

2/10/2009

18

Intersection en espace objet (instancing)

Mr

MqaM 1−

bM 1−

btMaM 11 −− +

q

r

n

a

btba +

Mq

espace objetespace monde( ) nM T1−

Accélérations du lancer de rayons

Rayon - objet Moins d’intersections par rayon

algorithmes d’intersectionvolumes englobants

subdivisions d’espacetechniques directionnelles

hiérarchies de volumes englobants

Moins de rayons Rayons généralisés

contrôle de profondeurstatistiques

faisceauconiqueparaxial

2/10/2009

19

Volumes englobants

boîte orientée(OBB)

espace objet

( )

boîte alignée sur les axes(AABB)

hiérarchie de boîtes englobantes(BVH)

Grilles

2e test: intersection hors du voxel courant

3e test: intersection valide, dans le voxel, stop

1er test: aucune intersection

2/10/2009

20

Lancer de rayons distribués• Anti-aliassage

– échantillonnage régulieré h ill ifié ( )– échantillonnage stratifié (jitter)

• Pénombres– échantillonner la lumière– échantillonner l’angle solide formé par la lumière

• Profondeur de champ– échantillonner les lentilles (simulées) d’une caméra( )

• Réflexion glossy– échantillonner le cone de réflexion

• Flou de mouvement– échantillonner (le mouvement dans) le temps







2/10/2009

21













2/10/2009

22













2/10/2009

23

Submissions 2007

Weathering

Documents

IFT3355: Infographie Visibilitéostrom/dift3355/pdf/04_visibilite.pdf2/10/2009 3 1. Algorithmes en espace image - Précision dépend de la résolution de l’image - La visibilité