1 Pré-traitement de Grosses bases de données pour la Visualisation interactive Xavier Décoret iMAGIS-GRAVIR / IMAG i MAGIS est un projet commun CNRS -

1

Pré-traitement de Grosses bases de données

pour la Visualisation interactive

Pré-traitement de Grosses bases de données

pour la Visualisation interactive

Xavier Décoret

iMAGIS-GRAVIR / IMAG

iMAGIS est un projet commun CNRS - INPG - INRIA - UJF

2

Plan de la présentationPlan de la présentation

• Problématique• Calcul de visibilité

– Travaux précédents– Contributions

• Niveaux de détails– Travaux précédents– Nuages de Billboards

• Conclusion

3





• Conclusion

4

ProblématiqueProblématique

• Environnements virtuels– Jeu, tourisme virtuel, simulateurs

• L’utilisateur se promène librement

• L’ordinateur affiche ce que « voit » l’utilisateur

Mise à jour rapide de l’affichage (25 fois par sec)

5

Sentiment d’immersion:Sentiment d’immersion:

• Environnements complexes– Étendue spatiale grande– Détails nombreux

• Effets réalistes– Ombres– Effets d’éclairages (reflets)– Apparence

Temps de calcul élevé

6

Actionsutilisateur

Actionsutilisateur

ProblématiqueProblématique

Systèmede

rendu

Systèmede

renduBase de donnéesBase de données imagesimages

Complexité du modèle Temps de calcul limité

Pré-calcul pour accélérer•Réutiliser certains résultats

•Optimiser les représentations

7

Élimination des faces cachéesÉlimination des faces cachées

• Projections des sommets

• Remplissage des faces

Pyramide de vue

8




Image

9




ImagePixel

10




Image

11




Image

12




Image

13




Image

14




Image

Pixel =couleurprofondeur

profondeur

15



• Remplissage des faces• Z-buffer [Cat74]

Image

Profondeur > profondeur

16

ConséquencesConséquences

• Modèle 3D complexe ) calculs nombreux

• Redondances de calculs

• Calculs inadaptés

17





Image

18





Image

19





Image

20





Image

21





Image

22





Image

23





Image

24





Image

25

Solutions possiblesSolutions possibles

• Calcul de visibilité– Déterminer ce qui est caché– Éviter de le dessiner inutilement

• Niveaux de détails– Plusieurs niveaux de précision– Utiliser le niveau adapté à la distance

• Rendu alternatifs

26





• Conclusion

27

Calcul de visibilitéCalcul de visibilité

• Éliminer le plus tôt possible

ce qui n’apparaîtra pas dans l’image

• Deux approches possibles– Calcul à la volée ) pour le point de vue courant

– Pré-calcul ) pour une région de l’espace

• Difficulté: fusion des ombres et de pénombres

28

Fusion des ombresFusion des ombres

Point de vue

Cône d’ombre

Bâtiments (vue de dessus)

29



Point de vue

Cône d’ombre

30



Point de vue

Cône d’ombre

31



Point de vue

32

Fusion des pénombresFusion des pénombres

Cellule


33

Fusion des pénombresFusion des pénombres

Cellule


34

VisibilitéVisibilité• Nombreux travaux [Dur99]• Classification [SPS74]

Espace ImageEspace Objet

•Hierarchical Frustum Culling [GBW90]

•Shaft culling [HW91]

•Shadow volumes [CT97]

•Bloqueurs convexes [CZ98]

•Convex Vertical Prisms [DM01]

•Volumetric visibility [SDSD00]

•Portals [ST91]

•Hierarchical Z-buffer [GKM93]

•Hierarchical Occlusion Map [ZMH97]

•2D1/2 Occlusion maps [WS99]

•Extended projections [DDTP00]

•Line Space subdivision [BWW01]

•Portals [LG95]

35

Problème complexeProblème complexe

• Pas de solution exacte ) être conservatif

• Réalise plus ou moins bien les fusions

• Espace objet ) visibilité étendue

• Espace image ) fusion (implicite)

Mélanger les approches

36





• Conclusion

37

DifficultéDifficulté

• Objets visibles d’un point facile– Z-buffer

• Objets visibles d’une région difficile

Se ramener à un problème ponctuel

38

Réduction de bloqueursRéduction de bloqueurs

• Proposé par [WWS00]

Cellule

Objet

Bloqueurs

39



Objet

Bloqueurs réduits

Centre de lacellule

40



O

41



O { P tel que Br(P) O }

r-réduction

42



O

V

M

• Généralisation à des cellules convexes

• Réduction des objets testés

V’

43

Réduction bloqueurs/bloquésRéduction bloqueurs/bloqués

Cellule

Objet

Bloqueurs

44

Réduction bloqueurs/bloquésRéduction bloqueurs/bloqués

Bloqueurs réduits

Centre de lacellule

Objet réduit

Image prise du centre de la cellule

avec les objets réduits

•Traitement similaire bloqueurs/bloqués•Calcul en une seule passe

45

Formalisation (1)Formalisation (1)

• Dilatation (Somme de Minkowski [SM93])

Ensemble de points

O

Ensemble de vecteurs

XO © X

{P+x, P2 O et x 2 X}

46

Formalisation (2)Formalisation (2)

• Erosion

Ensemble de points

O

Ensemble de vecteurs

X

O ª X

{P tel que 8 x 2 X, P+x 2 O }

47

ThéorèmeThéorème

Si un rayon (VM) est bloqué

par O ª X avec X convexe,

alors:

Tout rayon (V’M’) est

bloqué par O avec :

V’ 2 {V} © X et

M’2 {M}© X

V

MV’

M’

O ª X

O

48

Érosion approximativeÉrosion approximative

• Érosion exacte difficile à calculer

• On peut calculer des approximations

49

DifficultéDifficulté

• Érosion exacte difficile à calculer

• On peut calculer des approximations

O ª X

Érosion par X

O ª X

Érosion interne

½ O ª X

Érosion externe

½

50

Mise en oeuvreMise en oeuvre

• Construire une carte d’occlusionavec les érosions internes

• Tester les érosions externes par rapport à la carte

Objets+érosions

51

Mise en oeuvreMise en oeuvre



52

Modification de l’algorithmeModification de l’algorithme

Carte d’occlusion



53


Carte d’occlusion



54


Carte d’occlusion



55


Carte d’occlusion



56


Carte d’occlusion

Visibles



57


Carte d’occlusion

Visibles



58


Carte d’occlusion

Visibles



59


Carte d’occlusion

Visibles



60


Carte d’occlusion

Visibles

Cachés



61

Avantages & inconvénientsAvantages & inconvénients

Deux passes de rendu (carte + tests)

Tests faisables par le processeur graphique

Complexité linéaire

Coût mémoire linéaire

ObjetsObjets

2 passes2 passesÉrosion approximatives

Érosion approximatives

Érosion exactesÉrosion exactes 1 passe1 passePré-calcul de visibilité

Pré-calcul de visibilité

62

Érosion approximativesÉrosion approximatives

• Voxelisation de l’objet– Information volumique [SDDS00]– Représentation adaptée [DM01]

• Érosion sur les voxels– Simple– Robuste et rapide

63

VoxelisationVoxelisation

64


65


66

Érosion de voxels par un cubeÉrosion de voxels par un cube

= ©

= ©©

67


O ª (X ©Y) = (O ª X) ª Y

=ª

ª ª ª

68

Érosion 1DÉrosion 1D

• De la moitiéd’un voxel

Direction d’érosionChangement de topologie

69

Érosion 1DÉrosion 1D

• De la moitiéd’un voxel

Direction d’érosion

• De moins de la moitié

Changement de topologie

Topologie conservée

70


=ª

ª ª ª

Axes alignés

71

Érosion de voxels par X quelconqueÉrosion de voxels par X quelconque

Cellule X

voxels

Si X ½ Y alors O ª Y ½ O ª X

ªÉrosion externe

)

ªÉrosion interne

)

72

DémoDémo

• Érosion de voxels

• Pré-calcul de visibilité

73

BilanBilan• Formalisme et nouveau théorème

– Réduction bloqueurs et bloqués

• Voxelisation par objet– Orientation adaptée– Discrétise pas le vide

• Travail dans l’espace image– Fusion implicite des ombres et pénombres– Accélération

• Matérielle : processeurs graphiques• Logicielle : combinés avec d’autres algorithmes de visibilité

74

Prochaine étape…Prochaine étape…

On sait ce qui est visible

Comment l’afficher?

75





• Conclusion

76

Niveaux de détailsNiveaux de détails

• Simplification de maillage

•Clusterisation [RB93,LT97]

•Hierarchical Dynamic Simplification [LE97]

•Decimation of Triangle Meshes [SZL92]

•Re-tiling [Tur92]

•Progressive Meshes [Hop96,PH97]

•Quadric Error Metrics [GH97]

•Out of Core Simplification [Lin00]

•Re-tiling [Tur92]

•Voxel based reconstruction [HHK+95]

•Multiresolution analysis [EDD+95]

•Superfaces [KT96], face cluster [WGH00]

77

LimitationsLimitations

• Contraintes sur le modèle• Contrôle de l’erreur

– Simplification enveloppes [CVM96]– Permission Grids [ZG02]– Image driven [LT00]

• Gestion des attributs (textures et couleurs)– Intégration métrique [GH98][Hop99]– Re-génération [CMRS98,COM98]

• Simplification extrême– Sillouhette Clipping [SGG+00]

78

Rendu alternatifsRendu alternatifs

• Rendu à base d’images– Lightfield,Lumigraph [LH96,GGRC96]

– Imposteurs [DSSD99]

– Relief Textures [OB00]

• Rendu à base de point– Surfels [PZBG00]

– Pointshop 3D [ZPKG02]

79





• Conclusion

80

Nuage de BillboardsNuage de Billboards

• Nouvelle représentation

• Utilisée pour la simplification extrême

81

BillboardBillboard

• Solution classique [RH94]

• Généraliser à beaucoup de plans• Construction automatique

82

Vue d’ensembleVue d’ensemble

• Approximer la forme par un ensemble de plans

• Projeter le modèle sur ces plans ) textures

• L’enchevêtrement des textures restitue l’objet

83

PrincipePrincipemodèle polygonal 3D

84

PrincipePrincipe

Simplification par des plans

85

PrincipePrincipe• Déplacer les sommets

Déplacementautorisé pour P

P

86

PrincipePrincipe• Projeter les polygones sur des plans

Polygone

Plan valide

87

PrincipePrincipe• Combien de plans? Quels plans?

88

AperçuAperçu• C’est un problème d’optimisation

• Mesurer l’intérêt des plans

• Représenter l’ensemble des plans

• Choisir un ensemble de plans

89


– algorithme glouton

• Mesurer l’intérêt des plans



90

OptimisationOptimisation•Sur l’ensemble des nuages de Billboards, on définit :

– Une fonction d’erreur– Une fonction de coût

•Deux stratégies possibles– Orientée budget

coût fixé minimiser l’erreur

– Orientée erreurerreur maxi fixée minimiser le coût

91

•Sur l’ensemble des nuages de Billboards, on définit :

– Une fonction d’erreur– Une fonction de coût

•Deux stratégies possibles– Orientée budget

coût fixé minimiser l’erreur

– Orientée erreurerreur maxi fixée minimiser le coût

Optimisation Optimisation

92

OptimisationOptimisation

• Fonction de coût– Le nombre de plans

• Fonction d’erreur– Déplacement du sommet

• Dans l’espace objet

• Dans l’espace image

93



• Mesurer l’intérêt des plans– définition de la densité



94

remplace beaucoup de faces

Fonction de densitéFonction de densité• Plan important = faible coût

fonction de densité sur l’espace des plans

• densité = mesure du nombre de faces qu’un plan peut remplacer

95

ValiditéValidité• Faces pour lesquelles le plan est valide

– Respecte la borne d’erreur

• Densité = nombre de faces valides

Déplacement autorisé

Densité de 3

96

ValiditéValidité• Faces pour lesquelles le plan est valide

– Respecte la borne d’erreur

• Densité = nombre de faces valides

Déplacement autorisé

Densité de 3

97

ContributionContribution• Pondération par l’aire projetée

– Favorise les grandes faces– Favorise les plans parallèles aux faces

98




• Représenter l’ensemble des plans– discrétisation


99

DiscrétisationDiscrétisation• Discrétisation de l’espace des plans

• Paramétrisation de Hough [DH72]

ρ

φ

θ(θ,φ)

O

ρ

primal dual

H

100

Espace dualEspace dual• plans passant par un point ) une nappe

φθ

ρ

101

Espace dualEspace dual• Plans passant par une

sphère ) tranche

φθ

ρ

102

Espace dualEspace dual• Plans passant par une

sphère ) tranche

• Plans passant par 3 sphères ) intersection de 3 tranches

φθ

ρ• Discrétisation uniforme

103

Densité cumuléeDensité cumulée

104




• Considérer l’ensemble des plans– discrétisation

• Choisir un ensemble de plan– Raffinement

105

Itération gloutonneItération gloutonne

Faces

Espacedes plans

Plans validesPlans validespour la facepour la face

DiscrétisationDiscrétisation

106


Faces

Espacedes plans



DensitéDensité

+

-

107


Faces

Espacedes plans



DensitéDensité

+

-

108


Faces

Espacedes plans



DensitéDensité

+

-

109


Faces

Espacedes plans



DensitéDensité

+

-

110


Faces

Espacedes plans



DensitéDensité

+

-

111


Faces

Espacedes plans



DensitéDensité

+

-

112


Faces

Espacedes plans



DensitéDensité

+

-

113


Faces

Espacedes plans



DensitéDensité

+

-

114


Faces

Espacedes plans



DensitéDensité

+

-

115


Cellule de plusForte densité

Faces pourlesquellesla cellule est valide

116


Forte densité

Il existe probablement un plan valide pour toutes les faces

Comment le trouver?

117


On teste le plan central

On subdivise

Raffinementdes densités

118

Génération des texturesGénération des textures

• À chaque plan est associé une liste de faces

• Projection orthogonale sur le plan

• Rectangle englobant minimal (CGAL)

• Rendu orthogonal ) texture

119

RésultatsRésultats

• Films

Exemples Ombres

120

Extension View-dependentExtension View-dependent

• Changement de la fonction d’erreur– Erreur de reprojection

P-

M P+

cellule

V

T

θ

121

Extension View-dependentExtension View-dependent

• Textures rendues du centre de la cellule

• Choix automatique de la résolution

• Sauvegarde la matrice de projection

122


Près

zoom

vue de la cellule

nuage de billboards modèle polygonal

123


Moyen

zoom

vue de la cellule


124


Loin

zoom

vue de la cellule


125

BilanBilan

• Nouvelle représentation

• Construction automatique

• Modèles quelconques

• Critère d’erreur simple / pas de paramètres

• Simplification extrême

126

ExtensionsExtensions

• Optimiser l’utilisation des textures– Prise en compte dans le coût– Compression de textures

• Ré-éclairage– Cartes de normales– Pixel shading

• Transition• Objets en mouvement

127


• Problématique

• Travaux précedents

• Contributions– Pré-calcul de visibilité– Billboard cloud

• Conclusion

128

ConclusionConclusion

• Nouveaux outils pour le problème posé• Calcul de visibilité

– Résultat théorique

– Algorithme pratique et simple à mettre en oeuvre

• Niveaux de détails– Nouvelle représentation / Algorithme de construction

– Simplification extrême / Gestion des attributs

• Intégration

129

QuestionsQuestions

Documents

1 Pré-traitement de Grosses bases de données pour la Visualisation interactive Xavier Décoret iMAGIS-GRAVIR / IMAG i MAGIS est un projet commun CNRS -