[Prog et Dev] Algo synthèse - duplication de vertex

-----------------------------------Modérateur-------------------------------------
Visiblement, je n'ais pas accès aux sections par filière... Donc si un hypothétique modérateur traine par là, merci de filer l'accès et de déplacer le post...
Sinon, je demanderais demain... et puis de toute manière si j'ai pas accès je suppose que les autres non plus, donc pour l'instant ça me parait être un bon endroit....

--------------------------------Prog_et_dev---------------------------------------
Ceci est réservé aux prog et Dev, pour le projet de synthèse.
-------------------------------------------------------------------------------------

Bon, comme je viens de trouver un algo pour la duplication des vertex, je vous le file, comme ça une fois que je l'aurais implémenté, on pourra comparer si par hasard quelqu'un décide d'utiliser le même algo.
Ca peut aussi servir à ce que quelqu'un me dise que l'algo comporte une erreur...
Je ne parle évidemment pas des opérations de nettoyage de la mémoire, ça dépend de l'implémentation.

Mon principe est de se placer au moment de la lecture du fichier Obj :
Au lieu de créer des faces structurées en dur avec des numéros, je décide qu'une face c'est un vecteur (ou tableau) de pointeur vers des objets qu'on appelera Sommet_unique (libre à vous d'utiliser un nom plus approprié).
Puisque cette explication n'est pas parlante...

Représentation:

Code:

  entrée                                            sortie
ns/nt/nn  ns1/nt1/nn1  ns2/nt2/nn2      -->          *s  *s1  *s2
Les Sommet_unique sont s, s1 et s2.

Entrée/sortie de ma table:
La table ne se manipule donc pas directement, elle s'interroge... on lui donne successivement les faces lues (sous la forme des entrées citées plus haut) et en retour elle nous renvoie sa sortie que l'on stoque dans notre tableau ou vecteur de face.

Fonctionnement:
La table contient 2 conteneurs: un vecteur de sommet_unique qu'on appellera "Final_Vector" et un autre vecteur de Sommet_unique qu'on appelera "To_Reindex_Vector".

Elle effectue la même opération sur chacun des triplets composant la face, donc pour simplifier, je pense que le mieux c'est d'envoyer les triplets de la face un par un et de mettre les pointeurs qu'elle nous renvoie dans la structure de la face en dehors de la table.
Quand elle reçoit un triplet elle procède ainsi:

Elle compare le ns de l'entrée aux ns de chaque sommet_unique de Final_Vector

Code:

    S'il n'y en a aucun d'égal, elle rajoute le triplet dans le vecteur et renvoie le pointeur associé à cette position de vecteur.

    Sinon si elle trouve ce numéro de sommet dans Final_Vector, elle regarde,

            Si nt et nn sont les mêmes et dans ce cas, elle renvoie juste le pointeur associé.

            Sinon elle regarde dans To_Reindex_Vector,

                Si il existe un sommet unique identique et dans ce cas elle renvoie là encore le pointeur vers cet élément

                Sinon elle rajoute le sommet_unique dans To_Reindex_Vector et renvoie le pointeur

    Sinon elle l'ajoute dans Final_Vector, et renvoie le pointeur

A la fin du traitement des faces, on appelera une fonction de la table "Reindex_moi_tout_ça", dont le role sera seulement de prendre chaque membre de To_Reindex_Vector de dupliquer pour chacun le sommet associé à ns et de l'ajouter en fin du vecteur de ns (à l'index z) et de changer ns en z dans To_Reindex_Vector.

Ainsi, en mémoire on aura bien une seule fois chaque vertex, chaque texture, chaque normale, une seule fois les triplets uniques ns/nt/nn (l'union de To_Reindex_Vector et Final_Vector) et une seule fois chaque face bien sur...
Il restera soit à réécrire dans un fichier les nouvelles données obtenues soit à les afficher...

Pour les afficher directement, il faut néanmoins bien sur recontruire les tableaux des faces et textures correctement... de toute manière si j'ai le temps, je pense que le faire en pré-traitement est mieux.

Il y a peut-être plus simple, bien que ça ne me paraisse pas, dans l'absolu, très compliqué...
Qu'en pensez vous ?

David

Ps: J'espère ne pas avoir fait de typos, au pire, je vous spammerais en mettant en couleur les changements... Je post sur forum et par mail, car certains ne lisent pas leur mail, d'autre pas le forum

Ps2: l'indentation des boites est nulle, mais c'est la galère de la refaire...

Waou !!! 7h30 du mat' !!
Je voulais aussi rajouter qu' il y'en avait qui avait de la salive à revendre (spéciale dédi à Rémy )
Bon sur ce que tu nous racontes (ou alors ce que j'ai compris... qui ressemble à ce que je pensais faire) :
En parcourant les faces dans le fichier obj, on crée un tableau de vertex déjà rencontrés, et lorsqu'on re-rencontre un de ces vertex dans l'indexage de face, on le ré-index.
Je pense que c'est plus simple de le ré-indexer directement au lieu de garder tous les vertex a ré-indexer après, ils suffit juste d'ajouter le vertex à ton tableau de vertex et de changer dans ton tableau de face en prenant pour index la nouvelle taille de ton tableau -1 !!! (Après j'ai ptetre faux..., d'ailleurs dites le moi !!)
Après j'ai un peu de mal à comprendre tous tes sinon... Tu compte gérer les cas où il y a exactement la même ligne dans le fichier obj ?? Ou alors j'ai pas vu tous les cas particuliers et je veux bien que tu éclaires ma lanterne.

"Sinon elle regarde dans To_Reindex_Vector,

Si il existe un sommet unique identique et dans ce cas elle renvoie là encore le pointeur vers cet élément"

Je pense qu'il peut y avoir plusieurs fois le même sommet à ré-indexer non?

Je compte faire ça cet aprem, je vous tiendrais au courant de mon avancé ou de mon pétage de cable

Bon, j'ai eut une journée assez occupée d'autres choses...

Je vais répondre à l'envers, car la dernière question trouve une réponse simple :

Citation :

Je pense qu'il peut y avoir plusieurs fois le même sommet à ré-indexer non?

Oui, c'est possible, mais peu importe puisque soit le couple ns/nt/nn sera le même (et dans ce cas on n'utilise qu'un seul jeu de données) ou non (et dans ce cas, on aura dupliqué notre sommet en fin d'algo).

Sinon, pour le:

Citation :

En parcourant les faces dans le fichier obj, on crée un tableau de vertex déjà rencontrés, et lorsqu'on re-rencontre un de ces vertex dans l'indexage de face, on le ré-index.
Je pense que c'est plus simple de le ré-indexer directement au lieu de garder tous les vertex a ré-indexer après, ils suffit juste d'ajouter le vertex à ton tableau de vertex et de changer dans ton tableau de face en prenant pour index la nouvelle taille de ton tableau -1 !!!

En fait, je n'ai pas fait ça, car j'ai identifié un autre problème dont la détection serait en n² ou en factoriel n...

Dans le parcours des faces(on a initialement n vertex):
En effet, disons que j'ai trouvé le sommet d'index 1
Je le rerencontre a l'identique... ok je laissse l'index 1 (*)
Je le rerencontre mais avec un nt et/ou nn différent... je lui mets l'index n et je crée le vertex associé (qui est un doublon du vertex d'index 1).(**)

Seulement voilà je rerencontre l'index 1 qui n'est pas identique au cas (*) mais qui est identique au cas (**) et là problème, car avec ta méthode tu vas créer un index n+1 et le vertex associé, car tu as pu faire pleins de choses entre et tu ne peux pas détecter que tu as la même combinaison ns/nt/nn que dans le cas (**)... en effet tu as déjà mis à jour ns.

C'est la raison pour laquelle j'utilise le temporisateur: To_Reindex_Vector.

Sinon, après avoir posté j'ai pensé que j'avais oublié de préciser que je parle de vector et de tableau, mais une part de mon algo serait bien mieux implémenté avec un map ou une hashtbl... enfin, j'ai pas trop regardé à quoi ils correspondent en c++, j'ai vu un truc qui s'appelle set aussi... bref, une structure de donnée de type table d'association donnerait surement une implémentation plus efficace.

Bon déjà, je n'avais pas compris qu'il fallait gérer le cas des doublons. Pour moi, s'il y a deux lignes identiques v/vn/vt alors le fichier obj est incorrect...

Bon ensuite je viens de finir mon algo... Déjà il fonctionne pas tres bien niveau affichage (mais la duplication et changement d'index est correct). De plus il me fait passer pour le loader de 2 sec à 2 heures (bon ok j'exagère un peu...), donc voila niveau optimisation c'est pas le top... Je vais attendre les conseils de notre cher prof comme il l'a indiquer dans son mail...

Sur ce, je finis ma journée de merde avec le sentiment qui habite souvent un programmeur : la frustration

A priori, quand l'objet est optimisé, il est restocké optimisé, pour pas avoir a recalculer l'optimisation ^^ Donc que ca prenne 2h, c'est que la 1e fois, c'est pas bien grave.

Non, mon truc gère effectivement le cas où il y a 2 fois la même ligne, mais j'avoues avoir zappé ta question... je ne vois pas ce qui te fait dire qu'une partie est dédiée à ça...

Je pense qu'il y a une partie de l'algo sur laquelle on ne s'est pas compris.
Je lis le vecteur de face (en fait je fais ça pendant la lecture du fichier obj, mais simplifions) et dans ce dernier il peut y avoir (et il y aura surement toujours) plusieurs références au même sommet.

Cependant, quand plusieurs références pointent vers la même texture ET la même normale, il faut que leurs index restent égaux (après réindexation) et je les regroupe donc en quelque sorte (en les faisant tous pointer sur le même vertex)... sachant qu'il peut y avoir nn groupes différents pour un index donné.

Bref on en reparle demain.

Et sinon, oui... peu importe le temps de réécriture du loader...
Le problème n'est pas tant performance.

Pour le moment, pour ma part je me suis planté quelque part, je crois que je vais réorganiser davantage ma structure de données.

David

Je me suis penché plus amplement sur ton algo, pour l'instant uniquement sur les couples (vertex, texture), et a priori on est arrivé sur la même démarche, ce qui est plutôt rassurant. Pour ce qui est du rouage interne du parcours des faces pour dédoubler les sommets, j'utilise un tableau pour "noter l'état des couples (vertex,texture)" et ainsi savoir exactement l'index de chaque couple (vertex,texture), ainsi que s'il y a besoin de dédoubler le vertex ou non.

Mon algorithme plus précisément :

Représentation :

En entrée : un objet, comportant une ou plusieurs faces, elle-même comportant chacune un tableau d'index (int) sur un vertex et une textures (entre autre).
En sortie : l'objet dont chaque face a vu sa table de vertex réajustée par dédoublement de certains vertex.

L'Algorithme :

Instanciation d'un tableau temp de taille n * m, où n est le nombre de vertex de l'objet et m le nombre de textures.
Toutes les cases sont initialisées à 0.


Tant que toutes les faces f n'ont pas été parcourues
|
| Tant que tous les couples (vertex v, texture vt) de la face f n'ont pas été parcourus
| |
| | On regarde dans la valeur de temp[v][vt]. Suivant le cas :
| |
| | => temp[v][vt] = 0 :
| | C'est la première fois que l'on rencontre le vertex d'index v, toute texture confondue.
| | Opérations effectuées : On initialise toute la colonne temp[v] à -1 (i.e. on signifie pour les textures différentes
| | de la 1e que l'on a deja parcourru le vertex)
| | , sauf temp[v][vt] qui prend la valeur v (i.e. le 1er couple garde l'index d'origine).
| |
| | => temp[v][vt] = -1 :
| | Nous avons déjà rencontré ce vertex, mais sur une texture différente !
| | Opérations effectuées : On instancie un nouveau point qu'on ajoute en fin de liste de vertex (son index sera un certain i).
| | Modification de la face en cours pour qu'elle prenne en compte le nouveau point. Enfin, temp[v][vt] = i
| |
| | => Sinon (temp[v][vt] = x > 0) :
| | Le vertex v de texture vt a deja été instanciée (ou dupliqué). Son indice est contenu dans temp[v][vt].
| | Opérations effectuées : Si l'indice est le même, on ne change pas. Sinon on le met à jour.
| |
| =
|
=

Appel à la fonction d'indexation (Pour réindexer les nouveaux sommets).

Avantages de l'algorithme :

Ne duplique que les objets qui ont besoin d'une duplication, on obtient donc le maillage minimal.

Désavantages :

Necessite l'instanciation d'un tableau à 2 dimensions gourmand en place.

___________

J'ai implémenté l'algorithme, et le texturage fonctionne.

A noter que mon algo ne duplique aussi que les vertex qui doivent l'être (je sais pas si c'était très clair).
La seule différence est véritablement le tableau en effet, sinon, l'algo est dans le fond précisément le même.


J'ai juste une question, tu as réindexé lors de la lecture pour que les index commencent à 0 ou les as tu laissé à 1 ?

Si tu l'as fait, tu auras je pense un soucis sur la valeur 0 qui ne vérifie alors pas que x > 0 pour cet index 0, mais bon, je suppose que non, vu que tu m'as dit que ça fonctionnait... cela dit ça pourrait aussi ne pas se voir si les arrêtes erronées résultantes de cette erreur sont dans l'objet... sauf bien sur au niveau de la texture.

David

Ps: Sinon, j'ai implémenté mon algo pour ceux qui veulent, je peux le découper de mon code afin de le mettre sur le réseau.
J'ai juste encore un pb sur la version indexée.... la version non indexée fonctionne pile/poil (d'ailleurs c'est assez marrant pour passer de l'une à l'autre version c'est assez rapide en fait).

Ah et puisque tu as donné les avantages et inconvénients du tien, voici ceux du mien:

Avantage: Pas de mémoire inutilement utilisée
Inconvénient: l'algo à une complexité en O(n²) sur les tests lors de la création de la structure donc forcément plus long. (n étant le nombre de face)
Tes tests sont à priori en O(n) auxquels il faut additionner la mise à jour des cases n*m (au pire), m étant le nombre de vt. En tout O(2n + m) et donc à priori beaucoup plus rapide.

Pas de soucis avec l'indexation, pour ce qui est de mon API, les tableaux de vertex, textures, etc commencent l'index 1 et non 0. Je résous le problème du tableau commençant à 0 juste au moment de passer les données à DirectX, donc pas de problème.

Cette optimisation a été incorporée directement dans le processus de chargement des objets : Chargement Brut => Optimisation => Indexation => Affichage. Quand j'aurai dégrossi ce qui est demandé par les autres UE, je m'attaquerai à l'implémentation de l'algorithme de triangulation que nous a présenté le prof. Si ça intéresse du monde, j'ouvrirai un topic dans le coin .

Celui des trapèzes ?
Perso j'ai triangulé à la volée avec la première méthode vendredi dernier...

Ps: j'ai édité mon précédent message pendant que tu répondais pour la complexité de ton algo .

Bon, ok, je viens de lire en survol les différentes manières de trianguler avec le second support qu'il nous a filé, ça fait mal .

J'ai une sainte horreur des cas non pris en compte, donc si je me lance dans une triangulation, elle prendra en compte les faces concaves à 3262936 sommets (Le perfectionnisme, c'est chiant).

J'ai chopé l'article en tout cas, si tu veux qu'on en parle demain

Ah, je m'excuse de te le dire mais ya un cas que tu ne pourras jamais afficher... celui où ya plus de place dans la mémoire .

----------------------------------------------------------------------------------------
Le perfectionnisme oui, mais tout dépend du prix.

A mon avis on arrivera plus vite au cas ou il n'y a plus de place sur l'ecran.

NOOOOON AAHHHHH Je burn ! Ma vie s'effondre !

En fait non, juste si un graphiste me fait ça un jour je lui fait manger son maillage !