1Daniel Meneveaux IRCOM-SIC, Poitiers Le 17.02.2000 Simulation déclairage dans des environnements architecturaux complexes : approches séquentielle et

1 Daniel Meneveaux IRCOM-SIC, Poitiers Le 17.02.2000

Simulation d’éclairage dans des

environnements architecturaux complexes :

approches séquentielle et parallèle

Daniel Meneveaux

Kadi Bouatouch


PlanPlanPlanPlan

Introduction

Problématique

Structuration

Modélisation

Regroupement de surfaces

Radiosité séquentielle

Conclusion et perspectives


IntroductionIntroductionIntroductionIntroduction

Simuler les transferts d’énergie lumineuse entre les surfaces d’un environnement

Architectes, éclairagistes (placement de luminaires)

Évaluer différents paramètres de confort visuel :

niveau d ’éclairement éblouissement

Acquisition des propriétés photométriques des matériaux (spectrophotomètres)

Utilisation d ’un modèle mathématique exprimant les interreflexions lumineuses


dxLxkxLxL e cos,,,,2

IntroductionIntroductionmodèle d’éclairementmodèle d’éclairementIntroductionIntroduction

modèle d’éclairementmodèle d’éclairement

Équation de luminance :

k : réflectance bidirectionnelle

Le : luminance auto-émise

: angle du rayon incident


IntroductionIntroductionéquation de radiositééquation de radiositéIntroductionIntroductionéquation de radiositééquation de radiosité

Hypothèse : Surfaces diffuses

Bi : radiosité du carreau i i : réflectivité du carreau i Ei : radiosité auto-émise par le carreau i Fij : facteur de forme entre les carreaux i et j

Résolution de ce système à l ’aide de méthodes itératives (Jacobi / Gauss-Seidel / Southwell)

j

N

jijiii BFxExB

1


IntroductionIntroductionRadiosité hiérarchiqueRadiosité hiérarchiqueIntroductionIntroduction

Radiosité hiérarchiqueRadiosité hiérarchique

Surface A Surface B

Liens d ’interaction

Mailles

Maillage hiérarchique des surfaces afin de réduire le nombre de mailles

Création de liens entre les mailles afin d ’accélérer les calculs


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


ProblématiqueProblématiqueProblématiqueProblématique


ProblématiqueProblématiqueProblématiqueProblématique

20 000 surfaces :

200 000 mailles

1 million de liens

1 Go de mémoire

Comment faire avec plusieurs millions de surfaces ?

Calcul de radiosité Visualisation (interactive)


ProblématiqueProblématiqueSolutionsSolutions

ProblématiqueProblématiqueSolutionsSolutions

Découper l’environnement en plusieurs sous-parties appelées cellules

Précalculer les relations de visibilité entre ces cellules

Effectuer les calculs de radiosité seulement sur un sous-ensemble de cellules à la fois


ProblématiqueProblématiquesolution : architecturesolution : architecture

ProblématiqueProblématiquesolution : architecturesolution : architecture

Cellules 3D

Modeleur

Structuration

géométrie

Clusters

Regroupementde surfaces

SIM_SEQ

SIM_PAR

BDD RAD

VISU


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


StructurationStructurationStructurationStructuration

Objectif «diviser pour mieux régner» :

Découper l’environnement en plusieurs régions appelées «cellules»

1 cellule = 1 pièce, 1 couloir, etc. Calculer les relations de visibilité inter-cellules

Résultat :

1 liste de cellules 1 graphe de visibilité


StructurationStructurationl’existantl’existant

StructurationStructurationl’existantl’existant

Découpage binaire de l’espace BSP [Fuchs80]:

Utilisé par J.M. Airey en 1990 (environnements axiaux) Repris par Teller en 1992 Découpage binaire récursif de l’environnement Chaque partie est découpée à l’aide d’un seul plan Déterminé selon des heuristiques empiriques (polygone le plus

occlusif, découpant le moins de surfaces possibles, etc..)

Résultats :

De trop nombreuses cellules Ne respectant pas la topologie de l’environnement Ne fonctionne que pour certains bâtiments : axiaux


StructurationStructurationnotre approchenotre approche

StructurationStructurationnotre approchenotre approche

Déterminer des «plans de découpage» verticaux :

associés à plusieurs polygones verticaux quasi-alignés à l’aide d ’un espace dual

Extraire des cellules :

selon une méthode basée modèle base de règles fonctionne pour tout type de bâtiment

Déterminer les ouvertures de chaque cellule :

situées sur les plans de découpage

Construire un graphe de visibilité


StructurationStructurationplans de découpageplans de découpageStructurationStructurationplans de découpageplans de découpage

Espace dual , :

représente l ’angle entre la normale du polygone et l ’axe Ox du repère de la scène

correspond à la distance orthogonale entre le plan du polygone et l’origine du repère global de la scène

Normale

Polygone vertical

z

x

y

Aire



Classification :

Regrouper les points de l’espace dual proches les uns des autres <=> regrouper des polygones verticaux quasi-alignés

Méthode de classification de type BSP :

» Découpage selon l’axe

» Puis selon l’axe

P4

P3P2

P1

P2 P3

P4

P1



1 plan de découpage associé à chaque groupe de polygones verticaux représentés dans l’espace dual

Déterminé par s et s :

s tel que : le demi-espace défini par Ns.Ps + s >= 0 contienne tous les polygones associés aux points appartenant au cluster

clusterii

clusteriii

aire

aires




StructurationStructurationBase de règlesBase de règles

StructurationStructurationBase de règlesBase de règles

Cellules rectangulaires contraintes

Cellules rectangulaires non contraintes

Couloirs avec deux murs parallèles

Pièces convexes quelconques : suivi de contours

1

2

34


StructurationStructurationcréation des ouverturescréation des ouverturesStructurationStructuration

création des ouverturescréation des ouvertures

Ouvertures situées sur les plans de découpage

Chambranle (de porte)

Plan de découpage


StructurationStructurationcréation du graphe de visibilitécréation du graphe de visibilité

StructurationStructurationcréation du graphe de visibilitécréation du graphe de visibilité

Création d’un graphe d’adjacence

1 nœud = 1 cellule 1 arc = 1 ouverture commune

Création du graphe de visibilité

Parcours du graphe d’adjacence en profondeur Échantillonnage des ouvertures Calculs de visibilité à l’aide de lancé de rayon


StructurationStructurationdécoupage semi-interactifdécoupage semi-interactif


Sélection d’une zone 3D




Extraction de la cellule 1




















Zone bleue = cellules extraites




Extraction d’une cellule quelconque (suivi de contour)




Extraction d’une cellule quelconque (suivi de contour)




Après extraction de toutes les cellules

Fenêtre de visualisation


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


ModélisationModélisationModélisationModélisation

Pourquoi structurer l’environnement après sa modélisation ?

Plus simple d’utiliser les connaissances de l’utilisateur pour effectuer une structuration efficace

Solution :

Outil interactif permettant de modéliser rapidement des environnements très complexes

Guider la structuration par une modélisation modulaire


ModélisationModélisationmodule piècemodule pièce

ModélisationModélisationmodule piècemodule pièce


ModélisationModélisationcréation d’ouverturecréation d’ouvertureModélisationModélisationcréation d’ouverturecréation d’ouverture

Description d’une ouverture


ModélisationModélisationmodule bâtimentmodule bâtiment

ModélisationModélisationmodule bâtimentmodule bâtiment


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


Regroupement de surfacesRegroupement de surfacesproblématiqueproblématique

Regroupement de surfacesRegroupement de surfacesproblématiqueproblématique

A partir d’une cellule => de nombreuses surfaces sont visibles

Calculs de radiosité pour 1 seule cellule => taille mémoire importante


Regroupement de surfacesRegroupement de surfacessolutionsolution

Regroupement de surfacesRegroupement de surfacessolutionsolution

Comment affiner encore les relations de visibilité ?

Construire des groupes de surfaces proches les unes des autres : le «clustering»

Évaluer les relations de visibilité inter-«cluster»


Regroupement de surfacesRegroupement de surfacestravaux existantstravaux existants

Regroupement de surfacesRegroupement de surfacestravaux existantstravaux existants

Subdivision spatiale : grilles 3D régulières, arbres BSP, arbres quaternaires, octrees, etc.

Techniques nécessitant la création d’une hiérarchie de volumes, approche descendante

Critères empiriques et peu intuitifs


Regroupement de surfacesRegroupement de surfacesnotre approchenotre approche

Regroupement de surfacesRegroupement de surfacesnotre approchenotre approche

Pas de gestion de hiérarchie, méthode ascendante

Technique de classification de type k-means : les nuées dynamiques :

Barycentres mobiles usuellement utilisée en 2D


Regroupement de surfacesRegroupement de surfacesles nuées dynamiques en 3Dles nuées dynamiques en 3D

Regroupement de surfacesRegroupement de surfacesles nuées dynamiques en 3Dles nuées dynamiques en 3D

Nombre de groupes = nb_total / nb_moyen

nb_total = nombre total de polygones nb_moyen = nombre moyen de polygones par groupe, fixé

par l’utilisateur

Choix des barycentres : de manière aléatoire

parmi les sommets des polygones

Distance entre un barycentre et une surface = distance au barycentre du polygone

Barycentre d’un groupe de polygones = barycentre des barycentres


Regroupement de surfacesRegroupement de surfacesapplication aux environnements complexesapplication aux environnements complexesRegroupement de surfacesRegroupement de surfacesapplication aux environnements complexesapplication aux environnements complexes

Utilisation de la structuration de l’environnement

Regroupement effectué pour chaque cellule

accélération des calculs

réduction des données en mémoire


Regroupement de surfacesRegroupement de surfacescalculs de visibilitécalculs de visibilité

Regroupement de surfacesRegroupement de surfacescalculs de visibilitécalculs de visibilité

Boîte englobante associée à chaque cluster

Zone visible d’un cluster C à travers une ouverture

pyramide à l’intérieur d’une cellule déterminée par l ’ouverture et la boîte englobante de C

Zone visible de C(pyramide)

CelluleCluster C

Ouverture


Regroupement de surfacesRegroupement de surfacespropagation de la visibilitépropagation de la visibilité

Regroupement de surfacesRegroupement de surfacespropagation de la visibilitépropagation de la visibilité

Si une ouverture est contenue dans la pyramide, alors les objets situés de l ’autre côtés de l ’ouverture peuvent être visibles

Cluster C

Nouvelle pyramide


Regroupement de surfacesRegroupement de surfacesinterface graphiqueinterface graphique


Visualisation des relations de visibilité




Visualisation des relations de visibilité


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


Radiosité séquentielleRadiosité séquentielletravaux antérieurstravaux antérieurs

Radiosité séquentielleRadiosité séquentielletravaux antérieurstravaux antérieurs

Une seule approche : [Teller94]

Objectif : maintenir une bonne localité des données en mémoire

4 heuristiques :

choix aléatoire du cluster (étalon) choix du cluster = ordre de modélisation source : choisir le cluster ayant servi comme émetteur le

plus souvent choix BSP : ordre obtenu par le découpage


Radiosité séquentielleRadiosité séquentiellenotre contributionnotre contribution

Radiosité séquentielleRadiosité séquentiellenotre contributionnotre contribution

Proposer de nouvelles heuristiques

Prenant effectivement en compte les accès-disque

Objectif : prédire les coûts des échanges disque/mémoire

à court terme

à moyen terme

à long terme


Radiosité séquentielleRadiosité séquentiellestratégies « glouton » S et Cstratégies « glouton » S et C

Radiosité séquentielleRadiosité séquentiellestratégies « glouton » S et Cstratégies « glouton » S et C

Choix d’une cellule à un instant donné :

Sans se préoccuper des coûts à long terme l’ordre global n’est pas optimal (en terme d’E/S)

Glouton S :

Coûts évalués en terme de polygones donnés par le modeleur

cellules contenant beaucoup de polygones choisies en fin d’itération

Glouton C :

Coûts évalués en terme de cellules (ou clusters) Afin de favoriser la réutilisation des cellules (ou clusters)

déjà en mémoire


Radiosité séquentielleRadiosité séquentiellestratégies « retour-arrière » S et Cstratégies « retour-arrière » S et C

Radiosité séquentielleRadiosité séquentiellestratégies « retour-arrière » S et Cstratégies « retour-arrière » S et C

Prévision de coûts à moyen terme

Création d’un arbre de recherche de profondeur N

Choix du chemin optimal (de longueur N) dans cet arbre

Ci


Radiosité séquentielleRadiosité séquentiellestratégie du « voyageur de commerce »stratégie du « voyageur de commerce »Radiosité séquentielleRadiosité séquentielle

stratégie du « voyageur de commerce »stratégie du « voyageur de commerce »

Pour prévoir à long terme les coûts d ’E/S

Problème équivalent au voyageur de commerce (VC) NP-complet

Utilisation d’un algorithme classique de résolution VC

Orientation et valuation du graphe de visibilité (=> GVC) Recherche d’un cycle passant par tous les nœuds de GVC Effectuer les calculs de radiosité en suivant ce chemin

Inconvénients :

Coûts d’écriture impossibles à prévoir Pour un graphe trop important, temps de calcul prohibitif


Radiosité séquentielleRadiosité séquentiellearchitecture logiciellearchitecture logicielle

Radiosité séquentielleRadiosité séquentiellearchitecture logiciellearchitecture logicielle

Graphe de visibilité

Module d’ordonnancement

Module deRadiosité

Mémoire principale (RAM)

Disque dur

Tableau de clusters (ou cellules)

EnMémoire[ ]


Radiosité séquentielleRadiosité séquentiellestratégie « voyageur de commerce »stratégie « voyageur de commerce »Radiosité séquentielleRadiosité séquentiellestratégie « voyageur de commerce »stratégie « voyageur de commerce »


Radiosité séquentielleRadiosité séquentiellerésultatsrésultats

Radiosité séquentielleRadiosité séquentiellerésultatsrésultats

Stratégie aléatoire

Maxénergie

GloutonS

GloutonC

Ret-ArrS

VoyComm

Ret-ArrC

229 mn 975 mn 130 mn280 mn 161 mn 140 mn 1378 mn

152 mn 186 mn 107 mn 93 mn 918 mn 650 mnPlusieurs

jours

Cellules

Clusters

Scène 615 cellules, 57786 surfaces et 12942 clusters, 360000 mailles, 1.5 Millions de liens (maillage grossier)

Taille mémoire minimale avec les cellules : 150 Mo avec les clusters : 60 Mo

Temps dus aux accès-disque = env. 1/10 du temps total


Introduction

Problématique

Structuration

Modélisation




PlanPlanPlanPlan


Conclusion et perspectivesConclusion et perspectivesconclusionconclusion

Conclusion et perspectivesConclusion et perspectivesconclusionconclusion

Calculs de radiosité pour des environnements complexes :

temps de calculs prohibitifs, problèmes de stockage mémoire

Prétraitement : découpage de l ’environnement en cellules

regroupement de surfaces (clusters)

Simulation d’éclairage : réduction des accès-disque (stratégies d ’ordonnancement)

calcul parallèle

Visualisation interactive : Avant, pendant, après les calculs de radiosité


Conclusion et perspectivesConclusion et perspectivesperspectivesperspectives

Conclusion et perspectivesConclusion et perspectivesperspectivesperspectives

Adaptation au découpage à des environnements complexes d’extérieur (urbains ou ruraux)

Adaptation / ajout de nouvelles règles

Modélisation :

A compléter et rendre plus opérationnelle (Y. Bertrand)

Rendu-basé-image

Réalisme des images résultantes Réduction de certains traitements


Documents

1Daniel Meneveaux IRCOM-SIC, Poitiers Le 17.02.2000 Simulation déclairage dans des environnements architecturaux complexes : approches séquentielle et