1 Pré-traitement de Grosses bases de données pour la Visualisation interactive Xavier Décoret...

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

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

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)

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é

Actionsutilisateur

ProblématiqueProblématique

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

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

• Projections des sommets

• Remplissage des faces

Pyramide de vue

ImagePixel

Pixel =couleurprofondeur

profondeur

• Remplissage des faces• Z-buffer [Cat74]

Profondeur > profondeur

ConséquencesConséquences

• Modèle 3D complexe ) calculs nombreux

• Redondances de calculs

• Calculs inadaptés

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

• Conclusion

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

Fusion des ombresFusion des ombres

Point de vue

Cône d’ombre

Bâtiments (vue de dessus)

Point de vue

Cône d’ombre

Point de vue

Cône d’ombre

Point de vue

Fusion des pénombresFusion des pénombres

Cellule

Fusion des pénombresFusion des pénombres

Cellule

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]

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

• Conclusion

DifficultéDifficulté

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

• Objets visibles d’une région difficile

Se ramener à un problème ponctuel

Réduction de bloqueursRéduction de bloqueurs

• Proposé par [WWS00]

Cellule

Bloqueurs

Bloqueurs réduits

Centre de lacellule

O { P tel que Br(P) O }

r-réduction

• Généralisation à des cellules convexes

• Réduction des objets testés

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

Cellule

Bloqueurs

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

Formalisation (1)Formalisation (1)

• Dilatation (Somme de Minkowski [SM93])

Ensemble de points

Ensemble de vecteurs

XO © X

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

Formalisation (2)Formalisation (2)

• Erosion

Ensemble de points

Ensemble de vecteurs

O ª X

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

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

O ª X

Érosion approximativeÉrosion approximative

• Érosion exacte difficile à calculer

• On peut calculer des approximations

DifficultéDifficulté

• Érosion exacte difficile à calculer

• On peut calculer des approximations

O ª X

Érosion par X

O ª X

Érosion interne

½ O ª X

Érosion externe

Mise en oeuvreMise en oeuvre

• Construire une carte d’occlusionavec les érosions internes

• Tester les érosions externes par rapport à la carte

Objets+érosions

Mise en oeuvreMise en oeuvre

Modification de l’algorithmeModification de l’algorithme

Carte d’occlusion

Visibles

Carte d’occlusion

Visibles

Carte d’occlusion

Visibles

Carte d’occlusion

Visibles

Carte d’occlusion

Visibles

Cachés

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é

Érosion approximativesÉrosion approximatives

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

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

VoxelisationVoxelisation

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

= ©©

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

ª ª ª

Érosion 1DÉrosion 1D

• De la moitiéd’un voxel

Direction d’érosionChangement de topologie

Érosion 1DÉrosion 1D

• De la moitiéd’un voxel

Direction d’érosion

• De moins de la moitié

Changement de topologie

Topologie conservée

ª ª ª

Axes alignés

É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

DémoDémo

• Érosion de voxels

• Pré-calcul de visibilité

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é

Prochaine étape…Prochaine étape…

On sait ce qui est visible

Comment l’afficher?

• Conclusion

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]

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]

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]

• Conclusion

Nuage de BillboardsNuage de Billboards

• Nouvelle représentation

• Utilisée pour la simplification extrême

BillboardBillboard

• Solution classique [RH94]

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

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

PrincipePrincipemodèle polygonal 3D

PrincipePrincipe

Simplification par des plans

PrincipePrincipe• Déplacer les sommets

Déplacementautorisé pour P

PrincipePrincipe• Projeter les polygones sur des plans

Polygone

Plan valide

PrincipePrincipe• Combien de plans? Quels plans?

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

– algorithme glouton

• Mesurer l’intérêt des plans

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

•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

OptimisationOptimisation

• Fonction de coût– Le nombre de plans

• Fonction d’erreur– Déplacement du sommet

• Dans l’espace objet

• Dans l’espace image

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

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

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

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

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

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

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

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

• Paramétrisation de Hough [DH72]

θ(θ,φ)

primal dual

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

Espace dualEspace dual• Plans passant par une

sphère ) tranche

Espace dualEspace dual• Plans passant par une

sphère ) tranche

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

ρ• Discrétisation uniforme

Densité cumuléeDensité cumulée

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

• Choisir un ensemble de plan– Raffinement

Itération gloutonneItération gloutonne

Espacedes plans

Plans validesPlans validespour la facepour la face

DiscrétisationDiscrétisation

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Espacedes plans

DensitéDensité

Cellule de plusForte densité

Faces pourlesquellesla cellule est valide

Forte densité

Il existe probablement un plan valide pour toutes les faces

Comment le trouver?

On teste le plan central

On subdivise

Raffinementdes densités

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

RésultatsRésultats

• Films

Exemples Ombres

Extension View-dependentExtension View-dependent

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

cellule

Extension View-dependentExtension View-dependent

• Textures rendues du centre de la cellule

• Choix automatique de la résolution

• Sauvegarde la matrice de projection

vue de la cellule

nuage de billboards modèle polygonal

vue de la cellule

BilanBilan

• Nouvelle représentation

• Construction automatique

• Modèles quelconques

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

• Simplification extrême

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

• Problématique

• Travaux précedents

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

• Conclusion

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

QuestionsQuestions

1 Pré-traitement de Grosses bases de données pour la Visualisation interactive Xavier Décoret...

Documents

Simplification et abstraction de dessins au trait Pascal Barla – Joëlle Thollot – François Sillion GRAVIR-IMAG-INRIA

Voilà maintenant quatre jours qu - Maison Magis

Réaction aux collisions dans les animations physiques François Faure, Olivier Galizzi GRAVIR Projet commun CNRS,INRIA,INPG,UJF 1 1

Lettre spiridonienne 41 Octobre 2018 - ACFA · 2018. 10. 11. · 12 Un fol entraînement pour l’équipe, lorsqu’une ubuesque déraison nous prenait, consistait à gravir « à

Coquilles terrestres et fluviatiles, · Helix variegata Friw. — Coqu. Scbi. 1. 43. Var. pustulosa Parr. -- Solidior, magis lævigata, substriata , lineis et fasciis indistinctis,

I MAGIS is a joint project of CNRS - INPG - INRIA - UJF iMAGIS-GRAVIR / IMAG Modélisation de léclairage Nicolas Holzschuch

Magis Cours m2

Publication trimestrielle n° 6 Avril 2013 - peabastogne.com¨te... · N’allez-vous pas vous aussi vous lever très tôt pour visiter cette foire aux ... A - Maes Noël - Magis

1 Commercialisation et rémunération. 2 Gravir les échelons du succès

I MAGIS is a joint project of CNRS - INPG - INRIA - UJF iMAGIS-GRAVIR / IMAG Modèles de couleur Nicolas Holzschuch iMAGIS-GRAVIR/IMAG

Magis 10.indb

Qui veut gravir une montagne commence par le bas. ( Proverbe Chinois ) Cliquez

Actualités du Groupe GEOMAP-IMAGIS - N°4- Mars 2016€¦ · Le widget est une petite application ... Qu’est-ce qu ’arcOpole PRO ... La communauté arcOpole va bientôt publier

Anahi - STEREOPTIK L’Exposition · 2019-02-20 · ANAHI PRODUCTION 01 43 57 36 29 Emmanuel Magis, directeur emmanuel.magis@anahiproduction.fr Clémence Pierre, assistante clemence.pierre@anahiproduction.fr

magis magistra EN TD FR OKOK - Agrotehnix · qualité comme le chauffage au gaz des friteuses ... FULL COVERAGE BURNER PLATE/ PLAQUE DE CUISSON/ BRATPLATTENGERÄTE ... METHANE mc/h

1 Modélisation de linteraction avec objets déformables en temps-réel pour des simulateurs médicaux Diego dAulignac GRAVIR/INRIA Rhone-Alpes France

DOSSIER DE PRESSE - maison-objet.com · ibride • Jars • Kai & Sunny chez Colette • Koziel • Le Grand Cerf • Magis chez la Boutique du Centre Pompidou • Maison Deux chez

IMAGIS-GRAVIR / IMAG Environnement de Réalité Augmentée Collaboratif : Manipulation dObjets Réels et Virtuels Raphaël Grasset Jean-Dominique Gascuel iMAGIS-GRAVIR/IMAG

Créer, Simuler, Explorer des Univers Naturels sur Ordinateur Fabrice NEYRET Evasion - GRAVIR / IMAG - INRIA ( CNRS, INPG, INRIA, UJF )

Programme MAGIS Remise à niveau