Discussion :

[mister3957]

Bonjour à tous,

Je suis en train de lire un format de fichier graphique pour en importer les objets dans une application, et voici le problème:

J'ai des sommets avec des caractéristique variables pour chaque objet (certain n'auront que la position de renseignée (+3 floats), d'autres où il y aura des coordonnées de texture(+2 floats), d'autres les normales (+3floats)).

Chaque groupe de valeurs (position, normales, coordonnées de textures, etc...) est indépendante des autres groupes de valeurs, stockée dans leur tableau.

Donc je prépare un vector qui va acceuillir les sommet. Lorsque je parcours mon tableau d'entier qui référencent un groupe de valeur par caractéristique du sommet, je commence par aller chercher à droite à gauche les valeurs à prendre, puis je parcours le vector de sommet pour voir si celui que je voudrais inséré n'existe pas déjà. Si il existe, je récupère juste son indice dans le vector pour le placer dans un tableau d'indice. Si il n'existe pas, je le rajoute, et j'ajoute également la nouvelle taille du vector - 1 comme indice au tableau des indices...

Bref, ce qui ralenti considérablement le traitement, c'est qu'à chaque sommet "lu" il faut reparcourir tout le vector à la recherche d'un identique. Sans ça, c'est rapide...

Alors j'ai essayé plusieurs trucs mais c'est toujours aussi long. J'ai essayé plutôt que de comparer les valeurs comparer les index qui pointent vers ces valeurs (souvent on passe de 8 floats à comparer à 3 unsigned int) mais ça reste trop long.

Là j'ai commencé un truc hier, c'est de créer un tableau de floats de taille(nbTriangle * nbFloatsPerSommet * 3), de le remplir comme si on s'en foutait des doublons. Jusque là c'est rapide.
Maintenant il faut que je le reparcours... En espérant que travailler avec des tableaux soient un peu plus rapide qu'avec des vector. Comme ça je cré un tableau comme s'il n'y avait pas de doublons (même taille que le précédent) et lorsque je positionnerais les valeurs à DirectX, j'lui dirais de pas tout prendre le tableau mais juste le nombre de floats correct.

Car j'avais chargé un objet de 15000 sommets... ça mettait plus d'une minute avant d'avoir parcouru les tableau/vector récursivement... :s

Je vous met le code que j'avais fait qui était trop long:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
std::vector<FLOAT*> vertexVector;
for(unsigned int numP = 0; numP < nbP; numP += nbPOffset)
{
    FLOAT* vertexValues = new FLOAT[nbFloatsPerVertex];
    int currentValueIndex = 0;
    for(unsigned int j = 0; j < nbPOffset; j++)
    {
          int reference = pTab[numP];
          source* src = implementation->GetSource(j);
          unsigned int nbFloats = src->GetNbValues();
          for(unsigned int k = 0; k < nbFloats; k++)
          {
              vertexValues[currentValueIndex] = src->GetValue()[reference + k];
              currentValueIndex++;
          }
 
          bool exist = false;
          unsigned int position = 0;
          for(std::vector<FLOAT*>::iterator it = vertexVector.begin(); it != vertexVector.end(); it++)
          {
                bool sameVertex = true;
                for(int numValue = 0; numValue < nbFloatsPerVertex; numValue++)
                {
                      if((*it)[numValue] != vertexValues[numValue])
                             sameVertex = false; break;
                }
                if(sameVertex)
                         exist = true; break;
                position++;
          }
 
          if(exist)
          {
                 indexVector.push_back(position);
          }
          else
          {
                vertexVector.push_back(vertexValues);
                indexVector.push_back(vertexVector.size() - 1);
          }
    }
}

Voilà et à partir de ce style de code, mes variantes (préparer en amont les valeurs plutôt qu'aller chercher les sources au fur et à mesure, comparer non pas chaque float d'un vertex mais les références vers les valeurs, comparer avant les index et si et seulement si c'est pas déjà dans le vector, aller les chercher, mais rien a faire, c'est long...)

Quelqu'un a une astuce pour optimiser ce genre de traitement?

Je vous remercie

A bientôt

Aurélien

[Luc Hermitte]

Avoir une table d'indexage triée qui assurera la recherche en O(ln n) ou carrément en O(1) avec des tables de hashage ?

[mister3957]

une table undexé ou une table de hashage? je fais comment ça?

Merci pour ta réponse,

A bientôt

Aurélien

[Luc Hermitte]

Il te faudra définir de quoi réaliser l'index
- std::set ou std::map dans le premier cas (O(ln n))
- pour les tables de hashage, il y a rien de standard pour l'instant. Cela dépendra donc de ton fournisseur de SL.

Puis éventuellement toujours avoir la structure, non triée, qui stocke les données.

boost.multi_index peut peut-être aider dans cette optique -- je n'en suis pas sûr, mais c'est une piste.

[mister3957]

Ok, merci beaucoup Luc

J'ai je suis arrivé à quelque chose de pas trop dégueulasse, donc je vais garder ça pour les tests et avancer, mais je note tes idées dans les points à optimiser

Merci,

A bientôt,

Aurélien