56
IMN638 - Interactions visuelles num´ eriques Chapitre 2.6 - Gestion de la g´ eom´ etrie Universit´ e de sherbrooke 11 novembre 2014 1 of 56

IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

  • Upload
    buitram

  • View
    226

  • Download
    1

Embed Size (px)

Citation preview

Page 1: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

IMN638 - Interactions visuelles numeriquesChapitre 2.6 - Gestion de la geometrie

Universite de sherbrooke

11 novembre 2014

1 of 56

Page 2: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Sommaire

� Consolidation de la geometrie

� Optimisation par la geometrie� Simplification de maillage� Imposteurs� Niveaux de detail

2 of 56

Page 3: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Introduction

La 3D en temps reel est presentement a un stade d’evolution ou la plupart deson innovation est effectuee au niveau des effets d’image ou de texture. Cecietant dit,un certain nombre de techniques propres a la gestion de la geometriecontinuent neanmoins de voir le jour.

L’optimisation et la construction geometrique demeure un aspect importantde l’infographie en temps reel. Il est donc interessant de s’attarder a diversesnotions de consolidation de la geometrie et, surtout, diverses methodes d’op-timisation des performances par la reduction de complexite geometrique.

3 of 56

Page 4: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Consolidation de la geometrie

4 of 56

Page 5: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Consolidation de la geometrie

La premiere partie de ce chapitre porte sur la consolidation de la geometrie.

En effet, une fois la geometrie d’une scene ou d’un modele 3D construite, ilest important de proceder a sa ”consolidation”. La consolidation consiste aprendre la geometrie produite par un artiste ou un processus de generationprodecural et l’optimiser, l’organiser et l’uniformiser pour maximiser ses per-formances au rendu, sans toutefois la degrader ou modifier son informationutile.

Notons que la consolidation se fait habituellement hors ligne, avant le rendu.Dans le cadre de cette section, nous aborderons des techniques d’optimisa-tion par les primitives de rendu et d’uniformisation des faces avant/arrierepour une geometrie.

5 of 56

Page 6: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Consolidation de la geometrie

Le premier probleme de consolidation de geometrie que nous etudierons estl’optimisation d’une geometrie a l’aide de primitives de rendu.

Dans un contexte academique, la geometrie est habituellement composee deforme geometriques regulieres, facilement representables a l’aide de primitivesde rendu telles que les Triangle strip ou les Triangle fan.

Forme geometrie simple (tore), facilement representable a l’aide de primitives geometriques complexes (triangle strip).

6 of 56

Page 7: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

Dans un contexte reel, la geometrie sera rarement de forme reguliere. Souvent,cette derniere est envoyee comme une simple liste de triangles, sans prendreen consideration la connectivite entre les triangles ou leur structure.

Dans de tels cas, une quantite importante d’information est dupliquee puisquechaque vertex de chaque triangle doit etre specifie independemment, meme siplusieurs triangles partagent parfois un ou plusieurs memes vertices.

Pour reduire la quantite d’informationdupliquee et reduire la quantited’information requise pour envoyer lemodele 3D au processeur graphique, il estimportant de simplifier la geometrie engenerant des primitives de renduconstituees de plusieurs triangles.

7 of 56

Page 8: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

La problematique, en resume, revient a prendre une liste de triangles separes(communement appellee une soupe de triangles) et generer les primitives lesplus grandes possibles a partir de ces triangles.

Pour atteindre cet objectif nous devons, dans l’ordre, effectuer les etapessuivantes :

1. Eliminer les vertices dupliques.

2. Generer un graphe de connectivite entre les triangles.

3. Generer les primitives complexes (strips) de triangles.

Pour effectuer ces operations, nous avons les informations de position desvertices, et leur association a un triangle en particulier. (3 vertices par triangle)

Sachant quels vertices sont associes a un triangle, on sait du meme coup quelssont les segments de ce meme triangle.

8 of 56

Page 9: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

La premiere etape, soit l’elimination des vertices dupliques, peut etre effectueerelativement simplement.

La solution employee est de generer un identifiant unique (hash) a partir dela position du vertex dans l’espace.

Pour chaque vertex analyse, on genere l’identifiant correspondant a sa posi-tion. On verifie ensuite la table de hachage. Si aucun vertex n’a ete insere al’identifiant genere, on insere la position du vertex analyse a l’emplacementde l’identifiant dans la table de hachage. On remplace ensuite la position 3Ddu vertex dans la structure du triangle par l’identifiant correspondant.

A la fin du processus, nos triangles sont constitues de 3 identifiants pointantvers notre table de hachage. Si deux vertices sont identiques, les deux iden-tifiants pointeront au meme endroit. Nous avons donc de cette facon autantd’identifiants qu’il y a de vertices uniques, les duplicatats etant elimines dansle processus.

9 of 56

Page 10: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

Representation du processus de generation des identifiants et d’elimination des duplicatats.

10 of 56

Page 11: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

Les vertices dupliques elimines, on procede ensuite a la generation de l’in-formations de connectivite. L’objectif ici est de generer un graphe ou chaquenoeud du graphe est un triangle. Chaque segment du graphe indique que deuxtriangles ont une arete commune.

11 of 56

Page 12: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

1. Pour generer le graphe de connectivite, on commence par creer un noeudpour chaque triangle de notre geometrie.

2. Les noeuds crees, on selectionne une arete sur un triangle (une paire depoints) puis on parcoure les aretes non explorees des autres triangles denotre geometrie pour trouver un triangle different partageant cette arete(ayant la meme paire de points).

3. Si une telle arete est trouvee, on relie les noeuds de nos deux trianglesdans le graphe puis on marque les deux aretes comme etant ”explorees”.Dans le cas ou aucune arete connexe n’est trouvee, on marque l’areteinitiale comme ”exploree” sans modifier le graphe.

4. On repete les etapes tant que toutes les aretes n’ont pas ete explorees.Une fois toutes les aretes explorees, notre graphe de connectivite estcomplet.

12 of 56

Page 13: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

Le graphe de connectivite genere, la derniere etape de notre consolidation degeometrie consiste a generer nos primitives, soit nos triangle strips.

Globalement, la generation des primitives consiste a prendre notre graphe deconnectivite et former des listes de triangles connextes simples (chaque tri-angle de la liste possede 2 triangles voisins, excepte les triangles aux extremitesqui n’ont qu’un voisin).

Pour la generation des primitives, l’objectif n’est pas de generer les trianglestrips les plus longues, mais bien de generer le moins de triangle strips pos-sible. (La duplication de la geometrie augmente si le nombre de triangle stripsaugmente.)

13 of 56

Page 14: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

Pour separer nos triangles afin de former des strips, differents algorithmessont disponibles. Dans notre cas, nous utiliserons l’algorithme SGI StrippingAlgorithm pour sa simplicite. Les etapes sont :

1. Choisir un triangle de depart au hasard. (Favoriser les triangles ayantmoins de voisins afin de reduire le nombre de triangles seuls isoles.)

2. Initialiser autant de triangle strips que le triangle possede de voisins.

3. Etendre les triangle strips de triangle en triangle (noeud en noeud dans legraphe), de maniere a former la serie de triangles la plus longue possible.(Un triangle peut seulement etre parcouru une fois pour les 3 stripsgenerees.)

4. Des triangle strips crees, conserver uniquement la plus longue enlever lesnoeuds des triangles correspondants a celle-ci dans le graphe.

5. S’il reste des noeuds (triangles) dans le graphe, retourner a l’etape 1.14 of 56

Page 15: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Creation automatique de primitives

L’algorithme effectue, nous avons maintenant une serie de triangle stripsrepresentant la meme geometrie que la geometrie initialement soumise, maissous une forme plus compacte, avec une duplication des vertices grandementreduite.

Gauche : Geometrie initiale sans optimisation particuliere, chaque triangle est emis independemment. Droite : Geometrie apres la generation desprimitives complexes (triangle strips), les strips sont identifiees a l’aide de couleurs pour la visualisation.

15 of 56

Page 16: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Ajustement automatique de l’ordre des vertices

Comme nous l’avons vu au chapitre 2.4, l’ordre dans lequel les vertices sontdefinis influence sur la notion de face avant/face arriere. Par exemple, lors del’utilisation du front-face culling, les vertices definis dans le sens anti-horairepar rapport a la camera formeront les faces avant, qui seront affichees, alorsque les vertices definis dans le sens horaire formeront les faces arrieres et neseront pas affiches.

Dans un contexte de geometriequelconque, il arrive parfois que lestriangles ne soient pas tous generes avecle meme ordre de points. Certaines facessont alors percues vers l’avant alors qued’autres sont percues vers l’arriere, ce quicree des ”trous” dans le modele lorsque leface culling est active.

Geometrie quelconque contenant certains triangles dontles vertices ne sont pas definis dans le bon ordre.

16 of 56

Page 17: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Ajustement automatique de l’ordre des vertices

Pour regler un tel probleme, on effectue les etapes suivantes :

1. On commence par selectionner un triangle de notre geometrie dont lanormale est orientee du bon cote (donc dont les vertices sont definis dansle bon ordre). On marque le triangle comme ”explore”.

2. Pour chaque voisin non-explore du triangle courant.

2.1 On compare les points de l’arete commune entre le voisin et le trianglecourant. Si les points de l’arete commune sont definis dans le meme ordreque pour le triangle courant, on inverse l’ordre des points du triangle voisin.Si les points sont dans l’ordre inverse, les points du voisin sont declares dansle bon ordre.

2.2 On marque le voisin comme ”explore” et on effectue l’etape 1 recursivementavec ce voisin comme triangle courant.

17 of 56

Page 18: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Ajustement automatique de l’ordre des vertices

Prenons note que lorsqu’on parle”d’ordre” des vertices, on considereles vertices comme etant dans unesuite en boucle du type{..., 0, 1, 2, 0, 1, 2, ...}. Donc, parexemple, si le premier vertice est levertice 2, le vertice suivant en ordrecroissant est 0.

Representation schematique de l’ajustement de l’ordre des vertices selonl’algorithme de l’acetate precedente.

18 of 56

Page 19: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Optimisation par la geometrie

19 of 56

Page 20: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Optimisation par la geometrie

L’optimisation du rendu par la geometrie est un champ de recherche actif etencore tres ouvert en infographie.

Globalement, l’optimisation par la geometrie consiste a diminuer la com-plexite de la geometrie d’une scene de maniere non-apparente dans lebut d’accelerer le rendu en diminuant la charge de calcul associee aurendu de la geometrie.

L’optimisation par la geometrie se traduitdonc par la reduction du nombre detriangles/segments/vertices d’une scene sansqu’elle ne soit trop apparente pourl’utilisateur. La problematique revient donc atrouver quelle geometrie enlever et de quellefacon l’enlever pour eviter de diminuer outremesure la qualite visuelle de la scene.

Exemple de reduction non-apparente de lageometrie. Reduction de la geometrie d’environ75%. Gauche : Modele a 244 376 triangles.Droite : Meme modele a 60 000 triangles.(Garland, 1999)

20 of 56

Page 21: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

La simplification de maillage (mesh simplification) est une technique d’opti-misation consistant a reduire le nombre de vertices contenus dans un maillage,tout en conservant l’integrite de la geometrie de ce dernier. (On ne cree pasde trou ou de discontinuite dans le maillage.)

L’operation principale de la simplification de maillage est l’elimination desegments (edge collapse operation).

Une elimination de segment s’effectue en prenant les deux vertices d’un seg-ment, et en les deplacant au meme endroit. Lorsque les vertices sont au memeendroit, on peut remplacer ces derniers par un seul et meme vertex et le seg-ment disparait.

Operation d’elimination de segment. Le segment uv est elimine sur v . (Equivalent a remplacer le vertex u par le vertex v dans la geometrie.)Ceci elimine les triangles A et B qui se retrouvent avec une aire de 0. (RTR3 p.563)

21 of 56

Page 22: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Pour un modele 3D ferme, lorsqu’on effectue une elimination de segment, onplace a toute fin pratique deux vertices de la geometrie a la meme position.Les triangles connexes au segment elimines doivent alors etre enleves de lageometrie puisque leur aire devient 0. En resulte une diminution de geometriese chiffrant a :

� 2 triangles

� 3 segments

� 1 vertex

L’elimination de segment est aussi un processus reversible. Si pour une geometriesimplifiee quelconque on conserve la liste (dans l’ordre inverse) des eliminationsde segment effectuees, il est possible de partir du modele simplifie et delui ajouter en sequence chaque segment elimine jusqu’a obtenir la geometriedetaillee.

22 of 56

Page 23: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Tel que vu precedemment, l’operation d’elimination d’un segment peut etreeffectuee en prenant un vertex de la geometrie et en le remplacant par l’autrevertex du segment. Dans un tel cas, on utilise une strategie d’elimination ditepar ”placement de sous-ensemble” (subset placement). Autrement dit, onprend un sous-ensemble du modele 3D (un vertex) qu’on place a la positionexacte d’un autre sous ensemble (un autre vertex).

� Avantage : Tres compacte a exprimer (Onspecifie 1 segment et 1 identifiant pourdire quel vertex du segment est conserve.)

� Desavantage : Seulement deux optionsde position finale pour le point resultantde l’elimination d’un segment (un des deuxvertices). Engendre une plus grande perted’information du maillage.

Representation de la strategie de placement desous ensemble.

23 of 56

Page 24: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Alternativement, il est possible d’utiliser une strategie d’elimination dite de”placement optimal” (optimal placement). Une telle strategie d’eliminationdemande de calculer une nouvel position pour le vertex resultant de l’eliminationd’un segment, position n’etant pas necessairement celle d’un des deux verticesoriginaux.

Pour un tel calcul, diverses approches ont ete suggerees :

� Approche de Hoppe : Prendre le point milieu du segment elimine.[Hoppe 1996]

Representation de la strategie de Hoppe pour la determination du point resultant de l’elimination de segment.

24 of 56

Page 25: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

� Approche de Garland et Heckbert : Resoudre un polynome quantifiantla somme ponderee des modifications encourues par les differentstriangles lors de la simplification. Le minimum de ce polynome sera lenouveau point resultant de la simplification. [Garland et Heckbert, 1999]

Representation de la strategie de Graland et Heckbert pour la determination du point resultant de l’elimination de segment. On remarque que lepoint resultant n’est pas necessairement situe sur l’ancien segment.

Pour les deux methodes precedentes, l’avantage principal est la meilleure qua-lite du resultat apres compression. Le desavantage principal reside dans laquantite de calcul plus elevee requise pour obtenir le nouveau point apreselimination du segment.

25 of 56

Page 26: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Determiner comment reduire la geometrie et trouver ou sera situe le vertexfinal resultant de l’elimination d’un segment n’est qu’une partie du problemede la simplification de maillage.

Un probleme tout aussi important est de trouver quelle simplification peutetre effectuee sans trop affecter l’apparence du maillage.

Pour le segment donne par la paire de vertices e et c, les simplifications e → c et c → e peuvent etre effectuees. La simplification e → c,eliminant e est naturellement la plus efficace, mais comment peut-on determiner mathematiquement qu’elle l’est ? (RTR3, p.565)

26 of 56

Page 27: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Pour determiner quelle est la meilleure simplification a effectuer en regard a lapreservation de la geometrie, on definit une fonction de cout C (s) mesurantl’impact d’une simplification sur le modele. (Plus le resultat est eleve, plus lamodification altere le modele.)

Une fois la fonction de cout calculee pour toutes les simplifications possibles,on selectionne la simplification ayant le plus bas cout, qu’on applique sur lageometrie.

Fonction de cout associee a la simplification e → c et c → e. Le cout de la simplification e → c etant evalue a 0 par la fonction de cout, onselectionne cette simplification car c’est elle qui modifie le moins le modele selon notre fonction de cout. (RTR3, p.565)

27 of 56

Page 28: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Dans un contexte pratique, une fonction de cout tres efficace est la fonctionde cout de Garland et Heckbert.

Pour une simplification sur un segment s quelconque, la fonction de coutse construit tout d’abord en generant m plans a partir des m triangles quitouchent aux vertices qui composent le segment.

Il faut donc tout d’abord etre en mesure de generer un plan pour chaquetriangle connectes aux vertices de s.

28 of 56

Page 29: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Nous savons que le plan ax + by + cz + d = 0 (ou np + d = 0 si n = (a, b, c)et p = (x , y , z)) correspondant a un triangle defini par les vertices v0,v1,v2,doit passer par ses vertices et avoir la meme normale n que le triangle.

La normale peut etre calculee en effecuant n = (v1 − v0)× (v2 − v0) puis ennormalisant n.

Le plan en soit est defini comme etant l’ensemble des points p = (x , y , z)pour lesquels le vecteur les reliant a un point du triangle (v0 par exemple) estorthogonal a n. On exploite cette propriete pour calculer d :

0 = n · (p − v0) (1)

= n · p − n · v0 (2)

= (nx x + ny y + nz z) − (nx v0x + ny v0y + nz v0z ) (3)

a = nx , b = ny , c = nz , d = −(nx v0x + ny v0y + nz v0z ) (4)

29 of 56

Page 30: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

La fonction de cout calcule la somme des distances au carre entre les plansformes des m triangles avant la transformation, et le vertex v resultant del’elimination du segment. Pour un segment ayant m triangles connectes a lui,on forme m plans (n, d). On calcule ensuite le vecteur v qui resulterait del’elimination du segment, puis on evalue le cout tel que :

C (v) =m∑

i=1

(ni · v + di )2 (5)

A partir de cette fonction, nous sommes en mesure de determiner le cout d’uneelimination de segment pour n’importe quelle simplification sur le modele,employant n’importe quelle strategie de definition du nouveau vertex commun.

Notons que la fonction (5) est le polynome dont il etait precedemment ques-tion a l’acetate 25.

30 of 56

Page 31: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

A ce stade, nous savons maintenant comment enlever de la geometrie (eliminationde segment) et ou enlever de la geometrie (avec la fonction de cout).

Un algorithme de simplification simple ressemblerait donc a :

Algorithme de simplification simple

Tant que le maillage n’est pas suffisamment simplifie|| Pour chaque simplification possible| | Evaluer le cout| || Trouver cout minimal| Effectuer la simplification correspondant au cout minimal|

31 of 56

Page 32: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Avant de clore la section, notons que certaines simplifications peuvent donnerlieu a un phenomene d’inversement des triangles affectes par la simplification.Un tel phenomene cause des artefacts de rendu car il inverse les faces, ce quipose probleme lorsque le rendu des faces avant ou arriere est desactive.

Exemple de cas ou un triangle pourrait etre inverse. (RTR3 p.564)

Pour eliminer le phenomene, on verifie, lors de l’evaluation du cout, si lestriangles ont une normale pointant dans la meme direction avant et apresla simplification. (Si le produit scalaire des deux normales est inferieur a 0,c’est qu’un triangle a ete inverse.) Dans un tel cas, on fixe le cout de lasimplification a ∞ (infini) afin de s’assurer que la simplification ne sera paseffectuee.

32 of 56

Page 33: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Pour terminer cette section, il est important de garder en tete qu’un maillagesimplifie fini par perdre sa qualite et ses details au fur et a mesure que progressela simplification (au fur et a mesure qu’on enleve des segments).

Dans un contexte de 3D en temps reel, on effectue habituellement la sim-plification d’un maillage en fonction de sa distance par rapport a la cameraou l’aire qu’il prend dans l’image rendue. Plus l’objet sera loin ou petit dansl’image, plus la simplification de ce dernier sera accentuee.

L’objectif n’est donc pas necessairement de reduire la geometrie a toutcoup, mais de la reduire lorsqu’elle devient trop petite pour que soitobservable la perte de detail. On sauve ainsi du temps de calcul, sans altererde maniere sensible l’image.

33 of 56

Page 34: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Simplification de maillage

Trois versions de la meme geometrie a des degres de simplification variables (geometrie pleine a gauche, 50% de simplification au centre et 98%de simplification a droite). Selon la taille occupee dans l’image, certaines versions de la geometrie peuvent etre utilisees sans qu’une differencene soit observable. Pour les differentes tailles dans l’image, la geometrie offrant le meilleur rapport qualite/geometrie est encadree en vert.(Hoppe et al, 1995)

34 of 56

Page 35: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

L’optimisation par imposteur consiste a rendre de la geometrie sur une texture,puis afficher la texture sur un seul polygone oriente vers la camera. La textureest reutilisee sur plusieurs images, ce qui reduit le temps total requis pourle rendu puisqu’il n’est alors pas necessaire de rendre la geometrie a chaqueimage.

Gauche : Scene rendue sans imposteur, a 16 images par seconde. Centre : Meme scene, cette fois rendue avec des imposteurs, a 31 images parseconde. Droite : Scene identique a l’image du centre mais ou chaque imposteur est affiche en blanc pour montrer quelle geometrie estremplacee par un imposteur. (Unigine, 2008)

35 of 56

Page 36: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

La premiere etape pour la creation d’un imposteur est de prendre l’objet 3D,et de le rendre dans une texture (plutot que de l’afficher a l’ecran). La texturedoit etre completement transparente (donc etre initialisee avec un coefficientα de 0) excepte a l’endroit ou se trouve la geometrie.

Lors du rendu de l’objet sur la texture, la camera doit regarder vers le centrede l’objet.

Generation d’un imposteur (RTR3, p.458)

36 of 56

Page 37: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Mini-annexe : Rendu dans une texture a partir d’OpenGL.

//On genere 1 objet Framebuffer et on obtient son identifiant.GLuint FrameBuffer;glGenFramebuffers(1,&FrameBuffer);glBindFramebuffer(GL_FRAMEBUFFER,FrameBuffer);

//On cree la texture ou sera effectue le rendu.GLuint TextureCible;glGenTextures(1, &TextureCible);glBindTexture(GL_TEXTURE_2D,TextureCible);glTexImage2D( GL_TEXTURE_2D, 0, GL_RGBA8, largeur, hauteur,

0, GL_RGBA, GL_UNSIGNED_BYTE,NULL);

//On associe la texture au framebuffer courant.glFramebufferTexture2D(GL_FRAMEBUFER,GL_COLOR_ATTACHMENT0,GL_TEXTURE2D, TextureCible,0);

//[...]

37 of 56

Page 38: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Mini-annexe : Rendu dans une texture a partir d’OpenGL (suite)

//[...]//Lorsqu’on veut rendre dans la texture :

//On active notre framebuffer cree plus tot.glBindFrameBuffer(GL_FRAMEBUFFER,FrameBuffer);//On configure l’endroit ou sera effectue le rendu//dans la textureglViewport(0,0,largeur,hauteur);

////On shoot de la geometrie ici comme on fait//d’habitude quand on rend. (glBegin, glvertex, etc.)//

//On a fini le rendu donc on remet le framebuffer//par defaut pour pas continuer de rendre dans//la texture.glBindFrameBuffer(GL_FRAMEBUFFER,0);

38 of 56

Page 39: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Pour determiner la resolution de texture a utiliser pour notre imposteur, onutilise l’equation suivante :

ResTexture = ResolutionEcranTailleObjet

2 · Distance · tan(ChampDeVision/2)(6)

(On adapte les termes selon si on calcule la resolution de la texture en hauteurou en largeur.)

39 of 56

Page 40: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Une fois notre imposteur rendu, on peut l’afficher dans la scene. Pour l’affi-chage, on place l’imposteur sur un billboard oriente vers la camera.

A titre de rappel, l’affichage d’un imposteur sur un billboard oriente vers lacamera revient a prendre la matrice modele-vue courante et fixer sa sous-matrice 3× 3 superieure gauche a l’identite.

Imposteurs rendus sur des billboards orientes vers la camera. (Mark Harris, UNC-Chapel Hill,2002)

40 of 56

Page 41: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

L’imposteur une fois rendu sur la texture,nous pouvons le reutiliser sur les imagessubsequentes du rendu.

Ceci etant dit, si le point de vu de la camerachange trop, l’observateur de la scene sera enmesure de remarquer que l’objet n’est pasreellement rendu et qu’il regarde en realite unplan. Pour eviter que l’observateur de la scenesoit conscient de cette realite, il fautperiodiquement mettre a jour l’imposteur eneffectuant un nouveau rendu de celui-ci sur latexture, a partir du nouveau point de vue.

La difficulte avec un systeme d’imposteur estde savoir quand mettre a jour un imposteur.

Scene rendue avec des imposteurs. Lorsque laposition de la camera change trop, l’imposteurn’affiche plus le bon ”cote” du modele, il fautdonc le mettre a jour.

41 of 56

Page 42: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Le rendu etant effectue sur une image discretisee(pixels), il existe un certain intervale pour lequell’imposteur ou la camera peut bouger dans lascene sans qu’une mise a jour ne soit requise. Eneffet, toutes les transformations ayant un effetobservable inferieur a la taille d’un pixel dansl’image resultante peuvent reutiliser la memeimage puisque le pixel ne changera pas de toutefacon.

De meme maniere, la camera peut tourner sur ellememe sans qu’une mise a jour de l’imposteur nesoit requise, puisque la projection de la scene versla camera ne change pas dans un tel cas. (Et doncla partie apercue de l’imposteur reste constante.)

Scene rendue avec un imposteur (pointrouge). Tant que le deplacement percu del’imposteur par rapport a son point dedepart est contenu dans l’intervale d’unpixel, il n’y a pas de difference perceptibleau niveau de l’image rendue.

L’angle de la camera peut changer sansaffecter l’imposteur, puisque la projectionde l’image de l’imposteur elle ne changepas. (L’imposteur reste oriente dans lememe sens.) La camera peut donc tournersur elle-meme sans que l’imposteur nedoive etre mise a jour, pour autant qu’ellene se deplace pas.

42 of 56

Page 43: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Pour determiner si un imposteur doit etre mis a jour, il faut s’assurer queles changements de position de l’imposteur par rapport a la camera (ou dela camera par rapport a l’imposteur) n’ont pas un effet depassant 1 pixel al’ecran.

On determine donc 3 cas ou l’imposteur doit etre mis a jour :

1. Si les texels de la texture de l’imposteur deviennent plus grand a l’ecranqu’un pixel de l’image rendue.

2. Si la camera ou l’imposteur bouge lateralement au point d’avoir uneerreur de parallaxe superieure a 1 pixel.

3. Si la camera ou l’imposteur bouge l’un vers l’autre au point d’avoir uneerreur de perspective due au grandissement superieure a 1 pixel .

43 of 56

Page 44: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

On commence en determinant un seuil maximal qui sera utilise dans les testssubsequents. Si ce seuil est depasse, l’imposteur doit etre mis a jour. Ce seuilmaximal est donne par l’angle forme par un pixel de l’ecran, angle que nousnoterons βscr .

On calcule une approximation de βscr tel que :

βscr = ChampDeVision/ResolutionEcran (7)

(On calcule cette valeur pour chaque axe de l’image, soit en x et en y .)44 of 56

Page 45: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Pour verifier si les texels de la texture de l’imposteur deviennent plus granda l’ecran qu’un pixel de l’image rendue, on verifie si l’angle βtex forme par untexel de la texture est superieur a l’angle βscr :

On calcule le point minimum et le point maximum du billboard projete surl’axe pour lequel on souhaite faire le test, soit nos points min et max .

On calcule ensuite l’angle forme par un pixel :

βtex =ChampDeVision · (max −min)

Resolution · ResTexture(8)

45 of 56

Page 46: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Pour verifier si l’erreur de parallaxe ou l’erreur de grandissement depasse leseuil βscr , on calcule l’angle de parallaxe resultant de la translation de notrecamera βtrans et l’angle de grandissement associe au deplacement cameraβsize a partir du volume englobant de la geometrie ayant ete transformee enimposteur. Notons que V1 est la position de la camera lors de la generationde l’imposteur de V2 sa position courante.

Pour le calcul de βtrans , notons que lespoints b1 et b2 sont respectivement lepoint le plus loin et le point le plus prochedu volume englobant de la geometrie apartir du point de vue V1.

Pour βsize , b1 est le coin du volume englobant le plus pres de la camera, etb0 est la projection du vecteur passant par b1 sur le plan de l’imposteur.

46 of 56

Page 47: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Imposteurs

Les angles calcules, on verifie si l’imposteur doit etre mis a jour en comparantchaque angle a βscr . Si βtrans , βsize ou βtex sont plus grand que βsrc , alorsl’imposteur doit etre mis a jour.

Il faut garder en tete que les calculs d’angle ci-haut sont des approximations.Le calcul des angles reels sans les volumes englobant devient lourd a calculertres rapidement.

Pour terminer, notons que nous avons vu la theorie derriere les imposteursmais qu’il existe beaucoup de variations permettant d’optimiser la methode.Par exemple :

� Generer les imposteurs a partir de geometrie pre-simplifiee lorsqu’ils sontloins.

� Combiner plusieurs imposteurs sur differentes parties d’une meme textureafin de reduire le nombre de textures et le nombre de permutations detextures.

47 of 56

Page 48: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

La notion de niveaux de detail (Level of Detail ou LoD) n’est pas un algorithmeen soit mais plutot une technique utilisee en infographie pour le rendu d’objetsgeometriques. Globalement, les niveaux de details consistent a envoyerune version plus ou moins simplifiee de la geometrie en fonction de lacontribution de cette derniere a la scene.

Dans un cas ou l’objet contribue peu a la scene (s’il est loin de la camera),une version peu detaillee de l’objet sera envoyee. Dans le cas contraire (s’ilest proche de la camera), une version tres detaillee sera envoyee.

L’utilisation de niveaux de details est differente de la simplification de modele3D dans la mesure ou elle n’est pas necessairement continue et les versionssimplifiees de la geometrie sont pre-calculees.

48 of 56

Page 49: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

Le concept de niveau de detail se divise en trois phases :

1. La generation : Fixer le nombre de niveaux de detail et generer lageometrie propre a chaque niveau de detail pour le modele cible.

2. La selection : Lors du rendu, determiner quel niveau de detail doit etreaffiche en fonction de la contribution de l’objet a la scene.

3. La permutation : Lors du rendu, afficher le bon niveau de detail, ou unniveau de detail intermediaire selon le niveau de detail selectionne a ladeuxieme phase.

49 of 56

Page 50: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

Generation : Lors de la generation, on produit la geometrie pour chaqueniveau de detail. Pour passer d’un niveau de detail a l’autre, on peut utiliserdes methodes de simplifications vues en debut de chapitre. (Par exemple,enlever X% triangles a notre modele a chaque niveau de detail.)

Notons qu’il est aussi possible d’utiliser des versions completement modifieesde notre geometrie initiale. Par exemple, utiliser des versions simplifiees pourles premiers niveaux, puis ensuite utiliser des imposteurs, puis des billboards,et finalement simplement ne pas afficher la geometrie (equivalent a faire uneoptimisation de vision selon la contribution).

Differents niveaux de details generes pour une meme geometrie. A un certain niveau, on remarque que la geometrie n’est plus qu’un imposteurou un billboard, et qu’elle finie par ne plus etre affichee dans le niveau de detail le plus loin. Niveau ou la contribution de la geometrie a la sceneserait jugee insuffisante pour que la geometrie soit rendue.

50 of 56

Page 51: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

Selection : La selection du niveau de detail a rendre s’effectue en fonctionde la contribution de la geometrie a la scene. Cette contribution est habituel-lement estimee d’une de ces deux facons. Soit en fonction de la distance parrapport a la camera, ou en fonction de l’aire occupee par l’objet dans l’imagerendue.

En fonction de la distance :

La selection du niveau de detail s’effectue en fonction de la distance a la camera. (RTR3, p.688)

En fonction de l’aire couverte dans l’image :

Voir acetates 45 et 46 du chapitre 2.5 pour une methode d’estimation de l’aire

occupee par notre geometrie dans l’image rendue.51 of 56

Page 52: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

Permutation : Au niveau de la permutation, on rend la geometrie en fonctiondu niveau de detail retourne. Il existe differentes methodes pour rendre lageometrie en fonction du niveau de detail.

� Permutation discrete : On alterne directement d’un niveau de detail al’autre, sans transition entre les niveaux de detail.

Representation de la permutation discrete. Lorsque le niveau change, la geometrie change sans transition.

52 of 56

Page 53: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Permutation (suite) :� Permutation par transparence : Autour d’une limite entre deux

niveaux de detail, on combine la geometrie des deux niveaux de detailavec de la transparence. (Ceci donne une meilleure transition maisaugmente la quantite de geometrie affichee lors des transitions. Il fautdonc s’assurer que la transition est uniquement effectuee aux alentoursdes limites d’un niveau de detail.)

Representation de la permutation par transparence. Aux frontieres entre deux niveaux, on affiche les geometries de chaque niveau de manieresemi-transparente avec un coefficient alpha variant dans la transition.

53 of 56

Page 54: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Permutation (suite) :

� Permutation par geomorphisme : Il est possible d’interpolerlineairement la geometrie d’un niveau de detail a l’autre. Dans un tel cas,les niveaux de details sont continus et la forme se metamorphosegraduellement en passant d’un niveau a l’autre. (Possible dans un cas parexemple de simplification graduelle d’un modele 3D ou on enlevegraduellement 1 segment a la fois.) L’operation est couteuse mais offre lemeilleur resultat visuel.

Representation de la permutation par geomorphisme. La permutation s’effectue de facon graduelle d’un niveau a l’autre.

54 of 56

Page 55: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

Niveaux de detail

Exemple concret d’utilisation des niveaux de detail :

Exemple concret d’utilisation de niveaux de detail dans une application, un jeu en l’occurence. (Prenons note que la meme scene est afficheedans les deux images mais sous un angle de vu different. (Bethesda Softworks, 2006)

55 of 56

Page 56: IMN638 - Interactions visuelles num eriquesinfo.usherbrooke.ca/.../imn638/chapitres/imn638-chap026.pdf · IMN638 - Interactions visuelles num eriques Chapitre 2.6 - Gestion de la

References suggerees :

Livre T. Akenine-Moller, E. Haines et N.Hoffman, ”Real-Time Rendering”, 3rdEdition, A. K.Peters, Ltd., Natick, MA, USA, 2008. (pp. 531 a 561, pp.680 a 693)

Article Hoppe et al., ”Multiresolution Analysis of Arbitrary Meshes”,Proceedings of the 22nd annual conference on Computer graphics andinteractive techniques, New York, NY, USA, 1995. (pp. 173 - 182)

56 of 56