Intro
Dans notre viewer, la molécule principale est composée d'un peu plus de 350 000 triangles, soit de plus d'un million de sommets. Réfléchissons à ce que cela nous donne dans les faits.
Mode normal
On appel par mode normal le mode consistant à constuire la molécule triangle par triangle via des glBegin() / glEnd() Pour chaque vertex, on passe la position ( 3 floats ), la couleur ( "3 floats" ) et la normale ( "3 floats" ) à la carte graphique :
- Donc un vertex équivaut à 9 floats.
- Donc si l'on veut tracer notre molécule en la construisant triangle par triangle, on aura
Nombre de float = Nombre de triangles * Nombre de sommet par triangle * Nombre de float utiles par sommet
Nombre de float = 350 000 * 3 * 9
Nombre de float = 9 450 000 floats utiles
Ce mode de rendu est sous-optimal pour plusieurs raisons :
- Tout d'abord parce que dans le million de sommets, beaucoup vont être commun à plusieurs triangles et on va donc se retrouver à passer plusieurs fois les mêmes informations. Pas bien !
- Ensuite parce que le transfert des informations d'un vertex est en réalité un passage d'informations de l'application (CPU) vers la carte graphique (GPU). Il faut savoir que ces transferts sont significativement plus lent que les transferts d'information à partir de la mémoire de la carte graphique. On retiendra que la communication GPU-GPU est plus efficace que la communication CPU-GPU
Mode indexé
Le mode indexé permet principalement de pallier au premier problème, c'est à dire de limiter le nombre de passage d'information par vertex à la dénomination la plus simple possible, c'est-à-dire un identifiant de sommet. Chaque sommet sera identifié par un entier
Prenons l'exemple d'un simple quad ABCD qui se décompose donc en 2 triangles.
Dès lors, on se rend compte qu'au lieu de passer toutes les informations de chaque sommet ( à savoir position, normale et couleur dans notre exemple ), nous n'allons passer qu'un identifiant de sommet. Les identifiants 0 - 1 - 2 pour le premier triangle et 1 - 2 - 3 pour le second. Alors oui tout cela est bien joli allez-vous me dire, mais ces informations comment sont-elles passées ?
Via les fonction glVertexPointer, glNormalPointer, glColorPointer et glDrawElements.
Ces 3 fonctions permettent de lire les informations directement à partir d'une adresse mémoire. Pour faire simple dans mon exemple, j'ai fabriqué 3 buffers distincts :
- Un buffer contenant de vecteurs 3D représentant les positions des différents vertex
- Un buffer contenant des vecteurs 3D représentant les normales de différents vertex
- Un buffer contenant les identifiants de sommets permettant de reconstruire la molécule
ps: Je n'ai pas fait de buffer de couleur, car j'utilise une couleur constante pour tous les sommets
L'utilisation des fonctions donne donc quelque chose comme ça
glNormalPointer( GL_FLOAT, sizeof( CVector3 ), _geometrie._p_normbuf );
glVertexPointer( 3, GL_FLOAT, sizeof( CVector3 ), _geometrie._p_vertbuf );
glDrawElements( GL_TRIANGLES, index_to_render, GL_UNSIGNED_INT, _geometrie._p_indbuf );
L'idée de base
Très bien maintenant que l'on connait les appels OpenGL à faire, il va falloir construire nos tableaux de données à passer à ces magnifiques fonctions. Partons sur un exemple simple pour illustrer ce que l'on cherche à faire.
Prenons une forme composée de 4 triangles qui ont tous un sommet commun. Le but est donc à partir des 9 sommets fournis en entrée A - B - C - D - E - F - G - H - I - J - K - L, de constituer une géométrie composée d'identifiants de sommets, soit,
Maintenant que l'on sait ce que l'on souhaite obtenir, voyons à quoi va ressembler l'algorithme.
Initialisation du premier index libre à 0
Pour chaque sommet
- Si le sommet n'est pas dans la liste des sommets répertoriés
> On l'ajoute à liste des sommets
> On ajoute au tableau d'index la valeur du premier index de sommet libre (qui sera donc associé au sommet courant)
> On incrémente la valeur du premier index libre
- Sinon
> On récupère l'index du sommet correspondant à ce sommet dans la liste des sommets déjà répertoriés
> On ajoute au tableau d'index cette valeur
Méthode d'indexation naïve
Comment implémenter "Si le sommet n'est pas dans la liste des sommets répertoriés" ? L'idée qui vient naïvement est de faire un tableau de coordonnées de sommets, et pour chaque sommet vérifier si ses coordonnées sont égales à celles d'un sommet stocké dans le tableau.
Voilà un algorithme tout bête qui marche parfaitement MAIS avec un faible nombre de sommets. En effet, pour chaque sommet traité, on doit parcourir (dans le pire de cas) toute la liste des sommets. Dans le cas de l'insertion du 10ième sommet, on aura au pire des cas 10 tests à faire. Pour le 100ième, 100 tests etc... La complexité de cet algorithme est une complexité quadratique O(n^2) ( n sommets à traiter * n sommets à comparer ).
Dans l'exemple de la molécules la géométrie est composée de 9 millions de sommets !!! Pour être honnête, mon application n'a jamais dépassée le stade de l'indexation de la géométrie complète et après 35 minutes de calculs, un magnifique message Windows est venu m'indiquer qu'il n'y avait plus assez de mémoire disponible sur mon système...
Methode d'indexation très rapide
L'algorithme précédent est inutilisable à grande échelle à cause du nombre de comparaisons à exécuter par sommet. On va donc accélérer ça en utilisant une map de la STL.
Qu'est qu'une map ?
TODO
Comment l'appliquer à notre cas ?
TODO