i MAGIS is a joint project of CNRS - INPG - INRIA - UJF °Graphics Labs, MIT, Boston iMAGIS-GRAVIR / IMAG Billboard Clouds Xavier Décoret Frédo Durand

*iMAGIS is a joint project of CNRS - INPG - INRIA - UJF °Graphics Labs, MIT, Boston

iMAGIS-GRAVIR / IMAG

Billboard Clouds

Xavier Décoret*

Frédo Durand°

François Sillion*


Introduction•Complexité croissante

•Dépassement des capacités d’affichage

• Il faut simplifier– Réduire la complexité– Utiliser des représentations alternatives

•Mais pas que difficulté d’affichage.– Problème d’aliassage


Simplification de maillage•De nombreuses méthodes performantes

•Marche bien sur des maillages

•Difficulté de gérer les textures– Appearance-Preserving [Cohen98]– Silhouette Clipping [Sander00]

•Erreur géométrique vs. fidélité visuelle– Image-Driven Simplification [Lindstrom2000]


Représentation alternatives•Le polygone s’est imposé

– Surtout comme primitive de modélisation– Et aussi comme primitive de rendu

• Image Based Rendering– Textures [Oliveira00]– Imposteurs [Decoret99]– Lightfield [Levoy96]

•Point Based Rendering– Surfels [Pfister01]


Représentation•Une information de forme

– Élimination des parties cachées– Parallaxe

•Une information d’apparence– Couleur– Modèle d’éclairage


Utilisation•Générer des images

•Ombres

•Calcul d’éclairage

•Calcul de collision


Problèmes

•Simplification extrême: pas de solution

•Beaucoup d’intervention manuelle

•Pas de méthodes pour certains modèles


Billboard Cloud•Nouvelle représentation

•Des plans pour représenter la forme

•Des textures pour l’apparence


Principe

modèle polygonal 3D


Principe

Simplification par des plans


Principe•Déplacer les sommets

Domaine de validité

P


Principe•Projeter les polygones sur des plans

Polygone

Plan valide


Principe•Combien de plans? Quels plans?


Aperçu

•C’est un problème d’optimisation– algorithme glouton

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

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

•Choisir un ensemble de plan– Raffinement


Aperçu

•C’est un problème d’optimisation– algorithme glouton





Formalisation•Pour un Billboard Cloud, 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


Formalisation•Pour un Billboard Cloud, 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


Formalisation•Fonction de coût

– Le nombre de plans– La taille des textures

•Fonction d’erreur– Déplacement du sommet

• Dans l’espace objet (view independent)• Dans l’espace image (view dependent)


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

– algorithme glouton





Fonction de densité

•L’importance d’un plan est évaluée en utilisant une densité dans l’espace des plans

•Combien de polygones peut remplacer un plan?


Validité

•Plan valide pour un polygone

• Importance d’un plan = nb de polygones valides


Contribution

•Pondération par l’aire projetée– Favorise les grandes faces– Favorise les plans parallèles aux faces


Contribution

• Pondération par l’aire projetée– Favorise les grandes faces– Favorise les plans parallèles aux faces


Contribution

• Pondération par l’aire projetée– Favorise les grandes faces– Favorise les plans parallèles aux faces


Pénalité

•Favoriser les plans tangents


Pénalité



Pénalité


n


Pénalité


n


Pénalité


Densité

• si valide alors

• somme pondéré de contribution et validité


Aperçu

•C’est un problème d’optimisation



•Choisir un ensemble de plan– algorithme glouton


Discrétisation

•Discrétisation de l’espace des plans

•Paramétrisation de Hough

ρ

φ

θ(θ,φ)

O

ρ

primal dual

H


Espace dual•plans passant par un point une nappe

φθ

ρ


Espace dual

• Pour un point:plans valides = tranche

φθ

ρ


Espace dual


φθ

ρ


Espace dual


• pour un triangle: intersection de 3 tranches

φθ

ρ


Espace dual



• Discrétisation uniforme

φθ

ρ


Espace dual



• Discrétisation uniforme

φθ

ρ


Densité cumulée


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

– algorithme glouton





Algorithme glouton

• C case de densité max

• E ensemble des faces valides

• Tant que le plan central de C non valide pour E

– subdiviser C et ses voisines

– Calculer localement une densité pour ces sous cases

– C sous-case de densité max

– E ensemble des faces (de E) valides

• Mettre à jour les densités

• Créer un Billboard avec le plan central et E


Raffinement


Raffinement

valid(f1)

valid(f2)

B


Raffinement

valid(f1)

valid(f2)


Raffinement

valid(f1)

valid(f2)


Raffinement

valid(f1)

valid(f2)


Raffinement

valid(f1)


Raffinement

valid(f1)


Raffinement & voisins


Raffinement & voisins


Génération des textures

•A chaque plan est associé un ensemble de faces

•Projection orthogonale sur le plan

•Rectangle englobant minimal (CGAL)

•Rendu orthogonal texture


Résultats

•Films

•Démo


Extension View-dependent

• Erreur de reprojection

P-

M P+

Viewcell

V

T

θ


Extension View-dependent

•Textures rendues à partir du centre de la cellule

•Choix automatique de la résolution

•Sauvegarde la matrice de projection


Résultats

Près

zoom

vue de la cellule

billboard cloud modèle polygonal


Résultats

Moyen

zoom

vue de la cellule



Résultats

Loin

zoom

vue de la cellule



Conclusion

•Nouvelle représentation

•Algorithme de construction

•Soupe de polygones

•Applications multiples


Travaux Futurs

•Optimiser l’utilisation des textures

•Transition

•Objets en mouvement

•Utilisation pour – Des ombres– Du calcul de collision

Documents

*i MAGIS is a joint project of CNRS - INPG - INRIA - UJF °Graphics Labs, MIT, Boston iMAGIS-GRAVIR / IMAG Billboard Clouds Xavier Décoret * Frédo Durand

i MAGIS is a joint project of CNRS - INPG - INRIA - UJF °Graphics Labs, MIT, Boston iMAGIS-GRAVIR / IMAG Billboard Clouds Xavier Décoret Frédo Durand