User Tools

Site Tools


pestova_guerin:valentina_pestova_guillaume_guerin_de_tourville

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Valentina Pestova & Guillaume Guerin de Tourville's corner

Improved Efficiency of Spring Embedders: Taking Advantage of GPU Programming


Court résumé de l’article: il décrit un procédé pour optimiser les temps de calculs en les déportant sur le GPU lorsque l’on applique des forces (plus particulièrement des Spring Embedders) sur le dessin de graphe.


Tulip

Pour ce projet, nous avions pensé dans un premier temps à l’implémenter sous la forme d’un plugin pour tulip. Pour cela nous avions téléchargé les sources de tulip et installé toutes ses dépendances, en suivant les tutoriels disponibles.

http://tulip.labri.fr/Documentation/4_4/tulip-dev/html/installation.html#installation-on-a-unix-like-os

http://tulip.labri.fr/Documentation/4_4/tulip-dev/html/IDE.html

Lors de la génération du Makefile avec cmake, nous n’avons rencontré aucune erreur, toutes les dépendances étaient trouvées. nous avons obtenu le résultat suivant :

Et la compilation réussissait également en affichant seulement quelques warnings:

Le début de plugin que nous avions créé était trouvé par le programme également:

Cependant lorsque nous lancions le programme, la perspective de tulip ne se lançait pas et il nous était impossible de travailler sur un graphe.


De même lorsque nous forçions celle ci en cliquant sur Open Project où via la ligne de commande: ./tulip_perspective -p Tulip

Après plusieurs échanges par mail avec M. B. Pinaud et M. P. Mary nous n’y sommes pas parvenus. Et avons choisit, en demandant l’accord, de réaliser le projet autrement, c’est à dire uniquement avec C++ et openGL.


OpenGL

Nous sommes parti d’un programme de base, qui est un ancien TP réalisé en cours de Programmation Graphique Haute Performance.

Le module responsable de l'affichage dans notre projet s'apelle RenderWidget.cpp

Modélisation d'un Graphe

Création d'un graphe

Nous avons créés deux structures Vertex et Node et une classe Graph afin de manipuler les graphes (fichier graph.h).

// données dans la structure Vertex :
struct Vertex {
    Vector3f coordinates;
    std::vector<int> neighbors;
    Vector2f texcoord;
};
// données dans la structure node :
struct node {
    int edges_listCoordX;
    int edges_listCoordY;
    int numNeighbors;
};
// données dans la classe Graph :
class Graph {
public:
    std::vector<Vertex> vertices;
    std::vector<Vector3i> edges;
 
    unsigned int mVertexBufferId; 
    unsigned int mIndexBufferId;
    unsigned int mVertexArrayId;
};

Nous créons notre Graphe dans le fichier RenderWidget.cpp dans la fonction createScene().

Représentation du graphe dans les tableaux de texture

L’article explique comment formater les données d’un graphe pour les passer au GPU. Il s’agit de 4 tableaux de textures utilisant des flottants, et qui sont organisés de la manière suivante:

  • T_cur contient les coordonnées des noeuds courant
  • T_next les coordonnées des noeuds du graphe à traiter
  • T_nodes contient la position d’une première arête avec une autre noeud dans le tableau
  • T_edges_lists, ainsi que son nombre de sommets voisins, ce qui nous permet de retrouver dans le même tableau les autres arêtes qu’il a en commun avec les autres noeuds.
  • T_edges_list contient les positions dans les 3 tableaux précédent du noeud voisin.

Dans graph.cpp, la fonction fillArrays s’occupe de faire la conversion d’un graphe vers ces 4 tableaux de texture. Cette fonction est appelée dans RenderWidget.cpp :

graph->fillArrays(mTextureT_cur, mTextureT_next, mTextureT_nodes, mTextureT_edges_list);

Le schéma de l'article considère ces tableaux comme des matrices pour simplifier, mais ensuite ils sont implémentés sous la forme d'un tableau 1D.

Création du Framebuffer Object (FBO)

L’étape d’après est d’inclure ces 4 textures dans le Framebuffer Object et de passer ce dernier au GPU. Cette étape est effectuée dans le fichier RenderWidget.cpp dans creatScene() via les fonctions d’openGL.

Cette étape nous a demandé beaucoup de temps car elle exigeait de l'attention aux paramètres de fonctions d'OpenGL et à l'ordre de leurs appels. Afin de comprendre leur fonctionnement et les utiliser correctement nous nous adressions aux exemples et à l'explication (dans la documentation d'OpenGL ainsi que dans des tutoriels externes).
Afin de passer dans le shader les données nécessaires pour l'algorithme (représentées sous forme de textures), nous avons élargi la classe RenderWidget par plusieurs membres:

  • les identifiants pour chaque texture
  • les textures pour garder l'information sur le graphe
  • les identifiants pour les samplers correspondants
  • l'identifiant pour le FBO

Les samplers sont les objets nécessaires pour passer une texture dans le shader et travailler avec ses éléments: texels. Et les identifiants: pour indiquer à OpenGL avec quelle objet travailler (quelle texture, FBO, sampler).

L'initialisation des données nécessaires pour les calculs dans le shader ainsi que le remplissage d' un petit graphe de test se font par l'appel de la fonction de la classe RenderWidget: createScene().

La simulation de calcul sur GPU s'exécute par la fonction paintGL() qui est appelée automatiquement dans un certain intervalle de temps. Elle peut être arrêtée dès qu'on dépasse un certain nombre d'itérations (sans interrompre la visualisation).
Afin de se servir du FBO pour le rendu dans une texture il faut faire l'affichage deux fois: la première fois: en utilisant le FBO et la deuxième: après avoir renouvelé les coordonnées de sommets récupérés depuis la texture changée.
Le premier passage renvoie le coordonnées actuelles de sommets dans le fragment shader computeForces.frag qui fait les calculs nécessaires. Cette opération remplit la texture T_next par les coordonnées changées en fonction de forces appliquées et qui ensuite envoyée sur CPU.

La séquence suivante décrit la chaîne de traitement et de recalcul des coordonnées:

  1. Remplir les textures contenant les coordonnées et la topologie du graphe
  2. Transférer les textures dans le GPU et recalculer les coordonnées dans le shader
  3. Rendre la texture avec les coordonnées recalculées dans le FBO
  4. Lire la texture modifiée depuis le FBO dans un tableau de type GLfloat par la fonction glReadPixel()
  5. Renouveler les coordonnées des sommets du graphe
  6. Afficher le résultat
  7. Passer à l'étape 1) avec des nouvelles coordonnées de sommets

Shaders et Calcul des forces

Forces

Une fois que Le Framebuffer Object a été construit et envoyé au GPU, le shader doit s’exécuter. Il doit pour chaque noeud calculer l'équation differentielle :

F étant la somme des forces internes et la somme des forces externes.

le résultat est ensuite stocké dans le tableau de texture T_cur vu précédemment.
Dans les formules suivantes :

avec a(t) et b(t), coordonnées des noeuds a,b à l'instant t.

Nous devons utiliser la méthode d'Euler implicite pour déterminer la variable t.


  • Forces internes

Pour le calcul des forces internes d'un noeud a, il est dit dans l'article d'appliquer la loi de Hooke entre a et chacun de ses voisins. La formule de la loi de Hooke est la suivante : est un facteur pour déterminer la force d'un ressort

représente la distance entre les coordonées des noeuds a et b à l'instant t, et à l'instant 0.

nous donne un vecteur unitaire correspondant à la direction de la force


  • Forces externes

Pour le calcul des forces externes d'un noeud a, il faut appliquer une force répulsive définie de la manière suivante sur chacun de ses voisins :

où q représente un facteur d'échelle et α une valeur comprise entre 1 et 2


Shader

La première étape dans le shader que nous programmé en GLSL, est de récupérer les coordonnées d'un noeud à partir des tableaux de textures définis dans la partie Modélisation d'un graphe.
Voici un exemple de code pour récupérer les coordonnées d'un noeud :

float x, y, z;
 
//Récupération des coordonnées du noeud a
vec3 a = vec3(texture2D(T_cur, vec2(i,j)).r,
              texture2D(T_cur, vec2(i,j)).g,
              texture2D(T_cur, vec2(i,j)).b);
 
//Récupération des coordonnées d'un noeud b, étant le k ième voisin de a
float u = texture2D(T_nodes, vec2(i,j)).r;
float v = texture2D(T_nodes, vec2(i,j)).r;
float k2 = k/width;
//pour le cas où le voisin est sur la ligne d'après
if(u+k2 > width){
   v += 1;
   u = (u+k2 - width);
}
else
   u+=k2;
vec2 coordB = vec2(texture2D(T_edgesList, vec2(u, v)).r,
                   texture2D(T_edgesList, vec2(u, v)).g);          
 
vec3 b = vec3(texture2D(T_cur, coordB).r,
              texture2D(T_cur, coordB).g,
              texture2D(T_cur, coordB).b);

Les calculs des forces internes et externes vues dans la partie précedente se font respectivement par l'intermédiaire des fonctions :

vec3 totalInternForce(int width, sampler2D T_cur, sampler2D T_next, sampler2D T_nodes, sampler2D T_edgesList){ ... }
vec3 totalRepulsiveForce(int width, sampler2D T_cur, sampler2D T_next, sampler2D T_nodes, sampler2D T_edgesList){ ... }

Résultats

Nous avons étudié l'article qui propose une méthode de visualisation de graphe optimisée par les calculs sur GPU. Notre objectif était de l'implémenter et d'analyser ses résultats.
Nous avons implémenté l'encodage du graphe dans les textures, la visualisation, le calcul des forces et l'intéraction avec le FBO.
Lors d'implémentation nous avons renconté un problème qui exige plus de temps à résoudre: définition et transmission correctes de coordonnées de textures dans le shader. Malheuresement à cause d'un manque de temps nous ne l'avons pas corrigé afin de voir le résultats d'implémentation, mais nous avons implémenté et vérifié les étapes intermediaires citées ci-dessus.


Code du projet

Vous trouverez notre code source dans le dépôt suivant : http://code.google.com/p/spring-embedders/source/checkout

pour le compiler et lancer le projet il vous suffit de créer un dossier build dans le répertoire, puis de se placer dedans et d'effectuer les commandes suivantes :

cmake ..
make
./springEmbedders
/net/html/perso/melancon/Visual_Analytics_Course/data/pages/pestova_guerin/valentina_pestova_guillaume_guerin_de_tourville.txt · Last modified: 2014/01/18 22:43 by gguerind