Lancer de rayons interactif

Réunion équipe graphique 06/02/2003

Plan

• Rappels sur le lancer de rayons

• vers un lancer de rayons interactif

I Rappels sur le lancer de rayons

• Initialement :– algorithme d ’élimination des parties cachées

• Principe :– pour chaque pixel P

• lancer un rayon d ’origine O et de direction OP dans la scène

• calculer les intersections entre le rayon et les objets

• conserver l ’objet le plus proche

O

P

I1

I2

I1 < I2 P =

Calcul de l ’éclairage• Éclairage local/direct

• Prise en compte de la visibilité de chaque source :– lancer d ’un rayon d ’ombrage depuis le point

d ’intersection vers chaque source• si aucun obstacle :

– la source est visible

– on ajoute sa contribution

• si il existe un obstacle (intersection avec un objet de la scène)

– aucune contribution de la source

=> prise en compte des ombres ...

Illustration

O

Rayons d ’ombrage

Source 1

Source 2P

I(P) = I(Source1) + 0 . I(Source2)

Prise en compte des reflets

O

Source 1

Source 2P

I(P) = I(Source1) + 0 . I(Source2) + I(P’)

P’

Rayon réfléchi

Réflexions spéculaires uniquement

Arbre de rayons

O

P

P’

P’’

S1 Sn….

S1 Sn….

S1 Sn….

Rayon primaire

Rayons réfléchis

Réflexions uniquement

O

P

P’ S1 Sn….

S1 Sn….P’’’P’’

S1 Sn…. S1 Sn

….

Rayons transmis

Réflexions + réfraction

Arrêt du processus

• I(P(n)) < seuil minimal– l ’apport des rayons réfléchis/réfractés suivants

est considéré comme négligeable

• n < profondeur maximale– évite les boucles infinies

• en général, combinaison des deux

Coût de calcul

• Algorithme basé sur le calcul des intersections entre les rayons et les objets composant la scène

• Approche naïve : – calcul de toutes les intersections entre chaque rayon et

tous les objets de la scène

– coût : (N2 x No) x ((Ns+2) x No)P

• N2 : nombre de pixels de l ’image ( = nombre de rayons primaires)

• No

: nombre d ’objets dans la scène

• Ns : nombre de source dans la scène

• P : profondeur maximale de l ’arbre

Réduction du coût

• Simplifier le calcul de chaque intersection– gain limités

• Réduire le nombre d’intersections à calculer– gain importants si Ni << No

– utilisation de structures de données spécialisées

• Distribuer les calculs– efficace sur de petites scènes (duplication de la scène)– plus complexe sur des scènes de grande taille

Structures accélératrices

• Nombreuses et basées sur le regroupement des primitives géométriques partageant un espace commun– volumes englobants– subdivisions spatiales

• régulières

• irrégulières

Les volumes englobants

• Principe :– entourer un objet « complexe » par un objet

plus simple appelé englobant

– 2 étapes pour le calcul d ’intersection• intersection avec l ’englobant

– si intersection, calcul de l ’intersection avec l ’objet interne

– si pas d ’intersection, aucune intersection possible avec l ’objet interne

Pas d ’intersection avec l ’englobant

Intersection avec l ’englobant mais pas avec l ’objet

Intersection avec l ’englobant et avec l ’objet

Hiérarchie de volumes englobants

• Généralisation du principe des englobants à plusieurs niveaux– arborescence de volumes englobants

Subdivision régulière

• Tout le volume englobant la scène est découpé en N x N x N voxels (volume elements)

• Chaque voxel contient la liste des objets qui se trouvent dans l ’espace qu ’il représente

• Il faut calculer le trajet du rayon dans le volume de voxels– Utilisation d ’un algorithme de tracé de droite

3D de type bresenham

Illustration

Avantages / Inconvénients

• Avantages :– découpage fin

• réduction importante du nombre d ’objets à traiter

– suivi incrémental de la trajectoire du rayon• simplicité

• rapidité

• Inconvénients– espace mémoire supplémentaire important

• N3 voxels ; au moins un pointeur par voxel => + de 4N3 octets

– en général beaucoup de voxels sont vides

Subdivisions irrégulières

• Objectif – Réduire le trop grand nombre de voxels vides

• Moyen– Ne pas découper l’espace de manière régulière– Utiliser des voxels de taille différente

• Différentes approches :– Arbres « Octrees »– Arbres « BSP »

Les octrees• Définition :

– Octree = arbre possédant 8 fils

• Principe :– Chaque fils représente un volume parallélépipédique de

l’espace– Ce volume contient

• Soit un nombre maximum d’objets (fixé à l’avance)• Soit rien

• Construction : processus récursif• À chaque étape, on découpe un volume en 8 sous volumes

identiques (division par 2 selon chaque axe)• On teste les conditions de contenu pour chaque sous volume

Illustration

N objets (N<MAX)=

Avantages / inconvénients

• Avantages :– Réduction du nombre de voxels (on regroupe

de nombreux voxels vides au sein d’un seul volume)

• Inconvénients :– Suivi du rayon plus difficile (les volumes

traversés successivement ne sont pas identiques)

Exemple 2D

Les arbres BSP

• BSP = Binary Space Partition• Amélioration des octrees

– On ne découpe pas systématiquement en 8– On découpe en 2, en variant cycliquement le

plan de découpe – Mêmes critères pour le découpage :

• Volume contenant plus de MAX objets : on découpe• Sinon on ne découpe pas

• Avantage : réduction du nombre de voxels• Inconvénient : suivi + difficile des rayons

Illustration 2D1 objet : stop

vide : stop

1 objet : stop

1 objet : stop 1 objet : stop

Cependant ...

• Les performances obtenues restent loin de la notion d ’interactivité– quelques secondes de calcul pour une scène de

très faible complexité– plusieurs minutes à plusieurs heures dès lors

que la scène se complexifie

• Comment obtenir un lancer de rayons interactif, voire … temps réel ???

II. Vers un lancer de rayons interactif

• Références :– « Interactive distributed ray tracing of highly complex models »,

Wald et al, Rendering Techniques 2001

– « Interactive rendering with coherent ray tracing », Wald et al, Eurographics 2001

• Objectifs :– utiliser le LR sur des très grosses scènes

(plusieurs dizaines de millions de triangles)– obtenir une visualisation interactive

(plusieurs images par seconde)

Moyens mis en œuvre

• Distribution des calculs

• Copie « unique » des données

• Optimisation poussée du lancer de rayons

• Pas de pré-calculs coûteux sur la scène, tq– indexation spatiale– niveaux de détail– simplification de la géométrie

Approche distribuée

• Approche relativement classique :– un maître gère la distribution des calculs et

l ’affichage– N esclaves ont en charge les calculs

d ’intersection

• Plus précisément :– chaque esclave calcule une zone image de

taille 32x32 qui lui est affectée dynamiquement par le maître

Le problème des données

• LR : « embarrassingly parallel »– le calcul d’un pixel est indépendant de celui des

autres pixels– même remarque pour une zone 32x32

• Mais – nécessité de disposer a priori de toute la scène pour

les calculs d’un pixel / d’une zone(propagation des arbres de rayons dans la scène)

• Classiquement : mémoire réduite sur esclaves => accroissement des communications

Arbre BSPprincipal

Arbres BSP secondaires

Arbre BSPglobal

Distribution des données (1)

Esclave j

Distribution des données (2)

Absent !

Arbres BSP secondaires

Arbre BSP primaire

Maî

tre

Arbre BSP primaire

Cache pour quelques arbres BSP secondaires

Esclave i

envoyerBSP(x)

x

Distribution des données (suite)

• Gestion du cache : LRU

• Compression des arbres BSP secondaires

• Gestion asynchrone des rayons – mise en attente en cas de données manquantes

• Séparation des données– géométriques : calculs d ’intersection uniquement– photométriques : pour l ’illumination d ’un seul point– réduit les communications – améliore l ’utilisation du cache

Optimisations du lancer de rayons (1)

• Réduction de la complexité du code– objectif = optimiser l ’utilisation du pipeline

matériel du processeur – moyens :

• utiliser un seul type de primitive (triangle)

• choix du BSPTree (code de traversée + simple)

• réduire les conditions au niveau du code

• Gestion des caches– réduire les temps d’accès aux données nécessaires– prefetching (nécessité d ’algos simples ….)

Optimisations du lancer de rayons (2)

• Gestion des cohérences entre rayons – des rayons voisins ont un comportement similaire

lors de leur trajet dans la scène– application aux rayons primaires et d ’ombrage

• Cette forme de cohérence peut être exploitée :– au niveau matériel :

• routines SSE, réduction des accès mémoires aux données communes, amélioration de l ’utilisation du cache

– dans la gestion de la distribution des calculs

Instructions SSE

Registres 64 bits Registres 256 bits

x

y

x+y

x1

y1

x1+y1

x2

y2

x2+y2

x3

y3

x3+y3

x4

y4

x4+y4

+

=

+

=

Application au lancer de rayons

• Calcul simultané de plusieurs intersections– gain de 3.5 à 3.7

• Parcours du BSPTree en parallèle pour 4 rayons– traversée 2 à 3 fois plus coûteuse que le calcul

d ’intersection (sans SSE)

– calculs liés à la traversée « facilement » parallélisables pour le BSP

• Calcul simultané de l ’illumination– réorganisation des calculs en cas de matériaux différents

– lancer des rayons d ’ombrage vers chaque source en SSE

Cohérence et distribution

• Les pixels calculés par un processeur sont corrélés :– zone 32x32 => comportement « similaire » des

rayons• favorise la localité des BSPTrees nécessaires au

calculs d ’intersection

– déplacement (modéré) de la caméra• distribution de chaque zone au processeur l ’ayant

calculée à l ’image précédente (localité des données)

Quelques résultats

• Configuration :– 7 bi-processeurs P3– scène de 50 millions de facettes– images 640 x 480– 1 rayon par pixel– pas de rayons d ’ombrage ni de réflexions

• Performances :– entre 3 et 5 images par seconde (sans SSE)– entre 6 et 12 images par seconde (avec SSE -

estimation)

Commentaires (1)

• Limitations– restriction des réflexions

• la cohérence entre rayons décroît lorsque l ’on descend dans les arbres de rayons

– les résultats présentés sont essentiellement liés aux rayons primaires et d ’ombrage

– les résultats restent convenables si les zones de forte réflexion restent petites sur l ’image

Commentaires (2)

• Intérêts par rapport au tracé de chemin– basé sur le tracé de rayons– doit pouvoir être accéléré par des techniques

similaires• écriture « fine » du code

• distribution des calculs

• Mais nombreux problèmes• essentiellement liés au postulat de cohérence

Lancer de rayons

Tracé de chemins

Commentaires (3)• SSE

– a priori difficulté de trouver des rayons ayant une trajectoire proche

– mais • applicable aux rayons primaires

• applicable aux rayons d ’ombrage de niveau 1 (PTNE)

• envisager une bufferisation des rayons ?

• Distribution– efficacité liée à la cohérence de traversée des arbres

BSP– perdue du fait des réflexions « aléatoires »

• envisager une bufferisation des rayons (bis) ?