Je suis en train de coder un programme de conversion de mesh 3D et il faut donc que j'ai une liste des sommets du mesh. Mais voilà, le format d'origine contient des sommets redondants (sommets partagés par plusieurs faces), ce que j'aimerais éviter.
Donc avant d'ajouter un sommet à mon std::vector, je teste si ce sommet y est déjà en parcourant tout le vector. Pour qu'un sommet soit égal à un autre, il faut qu'ils aient memes coordonnées, memes normales et memes coordonnées de mapping ce qui se traduit par 16 inégalités, donc le test est assez lourd.
Le problème, c'est que mes meshs contiennent plus de 10000 sommets et donc, à la fin, lorsque je veux ajouter un sommet, je doit le tester contre les 10000 qui sont déjà dans la liste
Vous auriez pas un idée pour améliorer les performances, parce que du coup, mon programme met plusieurs minutes à s'exécuter? Je ne suis pas obliger de rester avec std::vector, je peux changer de container.

void list::unique() est ton ami.

D'après la doc de la STL:

Donc, si j'ai bien compris, unique() supprime juste les éléments égaux qui se suivent. Ca n'a pas l'air de résoudre mon problème

void list::sort() juste en dessous !!!!

Penses à créer un opérateur < dans ton type d'élément...

Donc je fais un sort puis un unique!
 
Merci pour ton aide

2 lignes, pas mieux ! :-) Par contre, ca reste lourd en  traitement.... je n'ai pas d'idée plus optimale.

ça va, vous avez pas mieux en performance ?
blaireaux
 
tu peux utiliser des trucs genre tas (quoi que), table hachée, arbre ou collection où l'ordre est à ta charge. Dans STL tu as :
- std::set pour les arbre
- pour les tas tu as std::vector + make_heap, push_heap, pop_heap, sort_heap
- std::queue + binary_search pour le reste
Dans certaines extension de STL, notemment celle de GNU et de SGI, tu trouveras:
- std::hash_set pour les tables hachées.
 
étudie attentivement les propriétés de ces structures, regarde bien ce qu'elles te fournissent comme service, et fais un choix.
 
 

ce qui s'avère stupide. Surtout avec une liste.
Tu vas pas t'amuser à trier à chaque fois.
Il faut que tu considère la performance des algorithmes et l'utilisation que tu fais (en fonction du nombre d'insertion, suppression, accès)

y a personne qui a été à l'école ?

Il fait un sorte à la fin qd il a tout ajouté (pas a chaque insertion).

 
lol, l'école c'est loin.... le C++ etait pas normalisé.

ça change rien au problème : il se passe quoi si sur 10000 insertion, seul 1000 valeurs sont uniques ?
 
une solution : d'abord comprends ce que tu veux faire

ça change rien, c'est l'algorithmie de base ça. Que t'es pas de notion de d'arbre ok, mais de là à lui conseillé le parcours et le tri d'une liste de 10000 éléments, c'est grave

C'est bien ce que j'ai dis, la solution n'est pas optimale !!! Tu sais lire qd même.

en fait, c'est la pire

 
C'est grave.... non.

Taz >> je ne comprends pas en quoi l'utilisation de struct hachees ou coll. serait ici meilleure que sort +crunch ?
 
Tu peux donner une piste stp ?

les arbres sont des structures qui maintiennent un ordre interne. ça t'évite de passer ton temps à tout le temps tout retrier et tout parcourir.
 
les hashset, ne maintiennent pas d'ordre, mais l'accès un un élément est en temps amorti constant à l'aide d'une clef. Dans un hashset, la clef est la donnée. Le test d'appartenance est très rapide.

^^ OK, je vois l'idee. Thx

_Momone_ >> tu fais comme dit Taz, mais surtout pour ton histoire de mesh/modèle 3D, tu fais ça en hors-ligne:
 
tu créer ton propre format de mesh/modèle 3D dont la structure est optimisée pour le rendu, et tu te fait un prog optimiseur qui avale le mesh non optimisé et produit un fichier optimisé.
 
et dans ton app de rendu 3D, tu charges ton modèle 3d optimisé par rapport à l'api/hardware 3d.
 

Ouaip c'est ce que je comptais faire. C'est pour ça que je sais pas si ça vaut le coup de se prendre la tête avec table de hashage ou arbre pour un programme exécuté "hors-ligne".
 
Enfin, je vais quand même essayer, même si j'ai un peu de mal à voir comment stocker mes sommets sous forme d'arbre?!
En gros, si mon sommet est "inférieur" au premier sommet de l'arbre, je monte un étage et je reteste, sinon, je pose mon sommet comme feuille de l'arbre. C'est ça?
 
Merci pour vos réponses.

mais je t'ai pas dit de coder toi même un ordre, j'ai bien compris que t'en étais pas capable. Je t'ai dit d'__utiliser__

 
moi j'aurai dit tu descends d'un étage mais bon
 
bon sinon pour en revenir à nos moutons, ton format source c'est quoi ?
 
ça:
vertex 1 : 100,50,60 ....
vertex 2 : 80,60,10
.....
 
triangle 1 : vertexs 1,2,3
triangle 2 : vertexs 1000,10,1
 
ou ça:
 
triangle 1:
          vertex 100,50,60
          vertex 80,60,10
          vertex 50,40,20
triangle 2:
          vertex 50,40,20
          vertex 100,50,60
          vertex 200,80,30        
....
 
la première approche étant la meilleure.

avec un format binaire, ça serait pas bien méchant non plus

 
oui, mais ce que je veux dire, mais par rapport au hardware 3d, un système indicé est le format naturel de traitement de la géométrie des cartes 3d.

Mon format source, c'est du style:

et je veux le transformer en format avec sommets indexés et non redondants. Donc j'ai une fonction AddVertex qui rajoute le sommet à la liste (et qui vérifie si le sommet n'y est pas déjà) et qui me renvoie l'indice du sommet dans la liste.
Donc, en fait, la méthode sort puis unique n'est pas valable puisque les éléments vont changer de place et donc d'indice. Je vais donc utiliser un arbre binaire.

oui donc c'est un format de merde

Ouaip en fait, c'est encore pire que ça... je prends en entrée le format .map de GtkRadiant (ou WorldCraft) et les blocs ne sont pas définis par des sommets mais par des plans. Il faut donc trouver l'intersection des plans pour avoir les sommets et ensuite, il faut les réordonner dans le sens trigonométrique.
 
Enfin, bon, merci pour votre aide

ha oki, ça se défends (vu qu'après tu dois avoir la moulinette pour le bsp et les lightmaps)

Pour ce genre de cas, ma preference ira a une structure légère en mémoire, ici il ne sert a rien de construire un arbre, 3 tableaux de list suffisent (je ne sais plus trop le nom de ce genre d'algo)
 
Le 1er tableau contient un mapping des X, le 2eme des Y et le dernier ... des Z    
 
Tu parcours une premiere fois ton tableau de vertices pr determiner l'intervalle min/max de chacune des composantes. C'est ce qui bornera tes tableaux.
 
Pour chaque vertex dont tu souhaites tester l'uniciter tu calcules avec les 3 composantes les index des 3 tableaux.
Tu testes ton vertex sur les vertices contenu dans les cases. Si il y en a au moins 1 dont la distance est < à ton treshold c'est qu'il y a doublon, sinon tu le rajoutes.
 
J'espere avoir été clair

Désolé de ne pas avoir répondu plus tôt mais je n'ai accés à Internet que le WE.
 
Nithril> Je ne suis pas sûr d'avoir compris ce que tu m'as dit, mais bon c'est pas grave, je pense m'orienter vers une structure en arbre binaire.
 
Par contre, j'ai vu sur ton site que tu calculais toi-même les lightmaps pour ton moteur. Je vais bientôt m'attaquer moi aussi au calcul des lightmaps (le format map ne contient ni l'arbre BSP, ni les lightmaps) et je te contacterais surement bientôt pour te poser quelques questions.