[PDF] Visualisation interactive de graphes: élaboration et optimisation d

View - Download Visualisation interactive de graphes: élaboration et optimisation d

Previous PDF

Next PDF

N od'ordre :4664 TH ESE presentee a

L'UNIVERSIT

E BORDEAUX I

ECOLE DOCTORALE DE MATHEMATIQUES ET INFORMATIQUE

parAntoine LAMBERT

POUR OBTENIR LE GRADE DE

DOCTEUR

SP ECIALITE . InformatiqueVisualisation interactive de graphes :

elaboration et optimisation d'algorithmesa co^uts computationnels eleves.Soutenue le : 12 decembre 2012

Apres avis de :

M.Alexandru Telea ......... Professeur ...........Rapporteur M.Alexander Wol .......... Professeur ...........Rapporteur

Devant la Commission d'Examen composee de :

M.Jean-Philippe Domenger . Professeur ...........President M.Christophe Hurter ....... Professeur ...........Examinateur invite M.Alexandru Telea ......... Professeur ...........Rapporteur M.Alexander Wol .......... Professeur ...........Rapporteur M.Guy Melancon ........... Professeur ...........Directeur de these M.David Auber ............. Ma^tre de conferencesCo-directeur de these - 2012 -

Remerciements

Mes remerciements vont dans un premier temps a l'Agence Nationale pour la Recherche qui aura nanc"ee ma bourse de these via le projet TANGUY men"e en partenariat avec Thales Communications, Xerox, FIDAL et l'"equipe projet Inria GRAVITE dans laquelle j'"etais int"egr"e. Je remercie "egalement l'Universit"e Bordeaux 1, l'Inria et le LaBRI qui m'ont permis de r"ealiser cette these dans de tres bonnes conditions de travail. Un grand merci "egalement a mes rapporteurs : M. Alexandru Tela et M. Alexander Wol d'avoir accept"e de relire ce manuscript et pour leurs suggestions d'am"elioration et de correction. Je tiens ensuite a remercier l'ensemble des membres de l'"equipe projet Inria GRAVITE pour leur convivialit"e et bonne humeur quotidienne durant ces trois ann"ees pass"ees a leur c^ot"e. Je tiens particulierement a remercier mon encadrant de these David Auber pour la conance qu'il m'a accord"e durant ces ann"ees et son soutien dans les moments diciles et de doute que tout doctorant rencontre au cours de sa these. Je lui signie toute ma gratitude et mon amiti"e pour les bons moments pass"es ensemble et son go^ut communicatif pour la recherche innovante. Je tiens "egalement a remercier Romain Bourqui, ma^tre de conf"erences de l'"equipe, pour son amiti"e et toute l'aide qu'il a pu m'apporter dans mon travail de recherche. Cette these serait bien moins riche en publications si tu n'avais pas eu les bonnes id"ees. Merci "egalement a tous les autres membres et ex-membres de GRAVITE que j'ai eu la chance de rencontrer : Guy Melancon, Maylis Delest, Bruno Pinaud, Patrick Mary, Alice Riviere, Jonathan Dubois, Morgan Mathiaut, Frederic Gilbert, Pierre-Yves Koenig, Paolo Simonetto, Daniel Archambault, Arnaud Sallaberry, Faraz Zaidi, Francois Queyroi, Maurin Nadal, Ludwig Fiolka et Charles Huet. Enn je voudrai remercier Laurent Garnier, dj et producteur de musique "electronique francais, pour toute la bonne musique ("electronique et acoustique) que j'ai pu d"ecouvrir gr^ace a lui durant toute mes ann"ees de these. Si le lecteur est un brin int"eress"e par la musique et sa diversit"e, je conseille fortement d'"ecouter l'"emission de radio de Laurent It is what it isainsi que sa radio webPedro's Broadcasting Basement (PBB), accessible depuis son site web :http://www.laurentgarnier.com/PBB.html. i ii Visualisation interactive de graphes : elaboration et optimisation

d'algorithmes a co^uts computationnels eleves.Résumé :Un graphe est un objet mathematique modelisant des relations sur un ensemble

d'elements. Il est utilise dans de nombreux domaines a des ns de modelisation. La taille et la complexite des graphes manipules de nos jours entra^nent des besoins de visualisa- tion an de mieux les analyser. Dans cette these, nous presentons dierents travaux en visualisation interactive de graphes qui s'attachent a exploiter les architectures de calcul parallele (CPU et GPU) disponibles sur les stations de travail contemporaines. Un premier ensemble de travaux s'interesse a des problematiques de dessin de graphes. Dessiner un graphe consiste a le plonger visuellement dans un plan ou un espace. La premiere contribution dans cette thematique est un algorithme de regroupement d'ar^etes en faisceaux appeleWinding Roads. Cet algorithme intuitif, facilement implementable et parallelisable permet de reduire considerablement les problemes d'occlusion dans un dessin de graphe dus aux nombreux croisements d'ar^etes. La seconde contribution est une methode permettant de dessiner un reseau metabolique complet. Ce type de reseau modelise l'ensemble des reactions biochimiques se produisant dans les cellules d'un organise vivant. L'avantage de la methode est de prendre en compte la decomposition du reseau en sous-ensembles fonctionnels ainsi que de respecter les conventions de dessin biologique. Un second ensemble de travaux porte sur des techniques d'infographie pour la vi- sualisation interactive de graphes. La premiere contribution dans cette thematique est une technique de rendu de courbes parametriques exploitant pleinement le processeur graphique. La seconde contribution est une methode de rendu nommeeEdge splatting permettant de visualiser la densite des faisceaux d'ar^etes dans un dessin de graphe avec regroupement d'ar^etes. La derniere contribution porte sur des techniques permettant de mettre en evidence des sous-graphes d'inter^et dans le contexte global d'une visualisation

de graphes.Mots-clés :Visualisation de graphes, regroupement d'ar^etes, bioinformatique, infographie

Discipline :Informatique.iii

Interactive graph visualisation : elaboration and optimisation

of algorithms with high computationnal cost.Abstract :A graph is a mathematical object used to model relations over a set of elements.

It is used in numerous elds for modeling purposes. The size and complexity of graphs manipulated today call a need for visualization to better analyze them. In that thesis, we introduce dierent works in interactive graph visualisation which aim at exploiting parallel computing architectures (CPU and GPU) available on contemporary workstations. A rst set of works focuses on graph drawing problems. Drawing a graph consists of embedding him in a plane or a space. The rst contribution in that theme is an edge bundling algorithm namedWinding Roads. That intuitive, easyly implementable and pa- rallelizable algorithm allows to considerably reduce clutter due to numerous edge crossings in a graph drawing. The second contribution is a method to draw a complete metabolic network. That kind of network models the whole set of biochemical reactions occurring within cells of a living organism. The advantage of the method is to take into account the decomposition of the network into functionnal subsets but also to respect biological drawing conventions. A second set of works focuses on computer graphics techniques for interactive graph visualisation. The rst contribution in that theme is a technique for rendering parametric curves that fully exploits the graphical processor unit. The second contribution is a ren- dering technique namedEdge splattingthat allows to visualize the bundles densities in an edge bundled layout. The last contribution introduces some techniques for emphasizing

sub-graphs of interest in the global context of a graph visualization.Keywords :Graph visualization, edge bundling, bioinformatic, computer graphics.

Field :Computer Science.iv

Table des matieres

Remerciementsi

Resum"eiii

Abstractiv

Table des matieresv

Table des guresix

Liste des tableauxxxv

1 Introduction1

1.1 Visualisation d'Information. . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1 Pipeline de visualisation. . . . . . . . . . . . . . . . . . . . . . . . 4

1.1.2 Exemples de visualisations. . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Visualisation interactive de graphes. . . . . . . . . . . . . . . . . . . . . . 11

1.2.1 Dessin de graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.2 Techniques d'interaction. . . . . . . . . . . . . . . . . . . . . . . . 20

1.3 Processeur graphique et pipeline de rendu. . . . . . . . . . . . . . . . . . 26

1.3.1 Denition d'un processeur graphique. . . . . . . . . . . . . . . . . 26

1.3.2 Fonctionnement du pipeline de rendu. . . . . . . . . . . . . . . . . 27

1.3.3 Exploitation du processeur graphique pour la visualisation. . . . . 31

1.4 Organisation du memoire. . . . . . . . . . . . . . . . . . . . . . . . . . . 32

v

Table des matieres

2 D"enitions et notations35

2.1 Graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.2 Autres denitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2.1 Graphes de visibilite. . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.2.2 Quadtree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.2.3 Octree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.2.4 Diagramme de Vorono

. . . . . . . . . . . . . . . . . . . . . . . . . 43

I Dessin de graphes47

3 R"eduction des problemes d'occlusion par regroupement d'ar^etes51

3.1 Etat de l'art. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2Winding Roads: un algorithme de regroupement d'ar^etes en faisceaux dans

le plan.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.2.1 Vue d'ensemble de la methode. . . . . . . . . . . . . . . . . . . . 58

3.2.2 Details de l'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . 58

3.2.3 Optimisation de l'implementation. . . . . . . . . . . . . . . . . . . 63

3.2.4 Niveaux de reduction d'occlusion. . . . . . . . . . . . . . . . . . . 69

3.2.5 Exemples d'application sur des reseaux geographiques. . . . . . . 70

3.3 Generalisation de l'algorithme pour les dessins de graphe dans l'espace. . 74

3.3.1 Methode de regroupement d'ar^etes pour un dessin de graphe en

trois dimensions. . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

3.3.2 Adaptation de la methode pour un dessin de graphe spherique. . 77

4 Repr"esentation de r"eseaux m"etaboliques81

4.1 Etat de l'art. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.2 Dessin de reseaux metaboliques : les des a relever. . . . . . . . . . . . . 88

4.3 Technique de dessin automatique d'un reseau complet preservant les voies

metaboliques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.3.1 Construction d'un graphe quotient multi-niveaux. . . . . . . . . . 89

4.3.2 Dessin des niveaux les plus bas de la hierarchie. . . . . . . . . . . 93

vi

4.3.3 Dessin du graphe quotient de plus haut niveau. . . . . . . . . . . 94

4.3.4 Reduction de l'occlusion : regroupement des ar^etes entre les groupes

94

4.3.5 Exemple de resultat : visualisation du reseau metabolique de la levure95

4.3.6 Relaxation de la contrainte de duplication. . . . . . . . . . . . . . 98

4.3.7 Complexite et temps de calcul. . . . . . . . . . . . . . . . . . . . 99

4.4 Mise en evidence de voies metaboliques dans la representation. . . . . . . 102

II Infographie pour la visualisation interactive de graphes105

5 Utilisation de courbes parametriques pour lisser la forme des ar^etes109

5.1 Introduction aux courbes parametriques. . . . . . . . . . . . . . . . . . . 110

5.1.1 Courbes de Bezier. . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.1.2 Courbes B-Spline. . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.1.3 Courbes de Catmull-Rom. . . . . . . . . . . . . . . . . . . . . . . 114

5.2 Optimisation du temps de rendu de courbes parametriques. . . . . . . . 116

5.2.1 Techniques classiques pour le rendu de courbes parametriques. . . 117

5.2.2 Techniques exploitant le processeur graphique pour le rendu de

courbes parametriques. . . . . . . . . . . . . . . . . . . . . . . . . 118

5.2.3 Performances. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

6Edge splatting: une technique pour visualiser la densite des faisceaux

d'ar^etes127

6.1 Principe de la technique. . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.2 Details d'implementation. . . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.3 Exemples d'application sur des visualisations de reseaux geographiques. . 131

7 Visualisation de sous-ensembles d'inter^et d'un reseau dans un contexte

global137 7.1 Etat de l'art. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

7.2 Utilisation d'enveloppes concaves. . . . . . . . . . . . . . . . . . . . . . . 139

7.2.1 Generation d'enveloppes a partir de l'espace image. . . . . . . . . 141

7.2.2 Generation d'enveloppes a partir de l'espace topologique. . . . . . 142

7.3 Utilisation d'une deformation 3D. . . . . . . . . . . . . . . . . . . . . . . 148

vii

Table des matieres

8 Conclusion155

8.1 Objectifs et realisations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

8.1.1 Dessin de graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

8.1.2 Infographie pour la visualisation interactive de graphes. . . . . . . 158

8.2 Futures directions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

8.2.1 Ameliorations pouvant ^etre apportees a notre methode de regrou-

pement d'ar^etes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

8.2.2 Suggestions pour ameliorer les representations de reseaux metabo-

liques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

8.2.3 Exploitation de notre technique optimisee de rendu de courbes pa-

rametriques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

8.2.4 Visualisation de sous-graphes d'inter^et dans le contexte global : pos-

sibles ameliorations et futurs travaux. . . . . . . . . . . . . . . . . 164

Bibliographie165

A Exemple d'exploitation du processeur graphique dans un contexte de visualisation d'information : impl"ementation d'unFisheye183 B D"etails d'impl"ementation pour le rendu de courbes param"etriques au

GPU189

B.1 Implementation avec stockage des points de contr^ole dans un tableau. . . 190 B.2 Implementation avec stockage des points de contr^ole dans une texture 2D190 B.3 Implementation avec stockage des points de contr^ole dans untexture buer object. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 B.4Geometry shaderpour extruder une courbe. . . . . . . . . . . . . . . . . 195 B.5 Implementation des fonctions interpolant le point d'une courbe. . . . . . 199 B.5.1 Courbe de Bezier. . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 B.5.2 Courbe B-Spline. . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 B.5.3 Courbe de Catmull-Rom. . . . . . . . . . . . . . . . . . . . . . . . 199 CMarching Squares: un algorithme d'extraction de contours203 viii

Table des gures

1.1 Le probleme des sept ponts de K

onigsberg "etudi"e par Euler [69] (source des images : Wikip"edia) (a) La ville de K onigsberg est construite autour de deux ^les situ"ees sur la riviere Pregel. Les deux ^les sont reli"ees entre elles par un pont. Six autres ponts relient les berges de la riviere a l'une des deux ^les. Le probleme "etait de d"eterminer si a partir d'un point de d"epart aux choix dans la ville il existait une promenade passant une et une seule fois par chaque pont pour revenir a son point de d"epart. (b) et (c) Euler a montr"e que ce probleme n'avait pas de solution en le mod"elisant sous forme de graphe. Les sommets de ce graphe repr"esentent les ^les et les deux berges de la riviere, les ar^etes les ponts. Il d"emontra qu'il n'existait pas de chemin dans ce graphe associ"e a la promenade recherch"ee.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Exemple de visualisation de graphe. Le graphe visualis"e est le r"eseau social

du club de karat"e de Zachary [199] (34sommets/78ar^etes). Chaque sommet repr"esente un membre du club et une ar^ete relie deux membres si une relation d'amiti"e existe entre eux.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Pipeline de visualisation, adapt"e de dos Santos et Brodlie [57]. Les "etapes

entour"ees en bleu sont celles dans lesquelles s'inscrivent les di"erentes contri- butions de cette these.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.4 Histogrammes de fr"equence de six dimensions du jeu de donn"ees [150]. Les

"el"ements graphiques repr"esentants chaque voiture (des carr"es) ont "et"e empil"es dans chaque barre mat"erialisant une classe de l'histogramme. Ce type de vi- sualisation permet de se faire une id"ee de la distribution des donn"ees sur ces dimensions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 ix

Table des gures

1.5 Matrice descatter plotcomparant six dimensions du jeu de donn"ees [150] deux

a deux. Dans ce type de repr"esentation, chaque "el"ement graphique repr"esentant une voiture est positionn"e dans le plan suivant deux axes mat"erialisant l'"echelle de valeur de chaque dimension. Les repr"esentations r"esultantes permettent de sugg"erer des corr"elations positives, n"egatives ou nulles entre paire de dimen- sions. Les couleurs de fond des cases de la matrice re etent le coecient de corr"elation entre les deux dimensions. Plus la couleur de fond est verte, plus les dimensions sont positivement corr"el"ees. Plus la couleur de fond est bleue, plus les dimensions sont n"egativement corr"el"ees. On peut ainsi observer que le nombre de chevaux et la cylindr"ee sont tres positivement corr"el"ees, on peut en conclure que sur les modeles de voiture dans ce jeu de donn"ees, plus la cylindr"ee est importante, plus le nombre de chevaux l'est "egalement.. . . . . 8

1.6 Visualisation de typepixel-orientedsur six dimensions du jeu de donn"ees [150].

Ce type de technique de visualisation de donn"ees a "et"e "elabor"e par Keim [115] pour repr"esenter une tres grande masse de donn"ees en associant a chaque donn"ee un pixel. Les donn"ees sont g"en"eralement ordonn"ees en fonction d'une dimension et positionn"ees dans une image via l'utilisation d'une courbe de remplissage. Une coloration pertinente des pixels permet alors une analyse de tendance entre les di"erentes dimensions. Dans notre cas, les pixels repr"esen- tant les voitures ont "et"e positionn"es en utilisant une courbe de type spirale. Ainsi pour chaque dimension les "el"ements ayant les valeurs les plus faibles se retrouvent au centre et ceux ayant les valeurs les plus "elev"ees sur l'ext"erieur. Les donn"ees sont toujours color"ees en fonction du nombre de cylindres dans le moteur des voitures. En comparant les repr"esentations associ"ees a chaque di- mension, on peut par exemple observer que plus le moteur des voitures contient de cylindres, plus le nombre demilespar galon d'essence diminue.. . . . . . 9

1.7 Visualisation de typecoordonnees parallelessur six dimensions du jeu de

donn"ees [150]. Dans ce type de visualisation, "elabor"e par Inselberg et Dim- sdale [104], chaque dimension est mat"erialis"ee par un axe repr"esentant son "echelle de valeurs. Les axes sont ensuite plac"es dans le plan de maniere paral- lele et sont r"egulierement espac"es. Une donn"ee est alors repr"esent"ee en tracant une ligne bris"ee/courbe entre les di"erents axes en fonction des valeurs de sesquotesdbs_dbs24.pdfusesText_30

[PDF] Ch12. La classification périodique des éléments. - Asthme

[PDF] Ch14. Exercices corrigés p:364

[PDF] Ch17 : agrandissements et réductions 1 Propriétés des

[PDF] Ch19. Exercice corrigé. p:513 n°19. Synthèse de l?acétate de

[PDF] CH2

[PDF] CH2 : Les mécanismes de transmission du mouvement

[PDF] Ch2 Le théorème de Pythagore Préparation du contrôle (sans

[PDF] Ch21 : Cosinus d`un angle aigu 1 Définition du cosinus d`un angle 2

[PDF] ch3 intégration, forces de pression sur un quart de sphère

[PDF] Ch3 – L`unité centrale : composants et fonctionnement - Travail

[PDF] Ch3. Exercice corrigé. p:78 n°19

[PDF] CH3578_METHODE ABCDE E2

[PDF] Ch390 en ce temps là: damals plus brûlant: glühender se ramasser

[PDF] Ch4. Cours. ANALYSE SPECTRALE.

[PDF] ch5 - Institut Montefiore