Algorithme de suppression de doublons et d'indexation

Version imprimable

30/10/2011, 01h23
hugolapointe

Algorithme de suppression de doublons et d'indexation

Bonjour à tous,

Voici mon problème à résoudre. En OpenGL, j'ai un tableau de vertices (points ou sommet) gardé en mémoire et j'envoie un tableau d'index à ma carte graphique pour dessiner.

Alors, afin de bien expliquer mes désirs je vais vous donner un simple exemple. Pour ceux et celles qui aimerait comprendre l'intérêt, je vous explique rapidement.

Prenons pour exemple un cube. Pour dessiner une face de ce cube je dois envoyer 4 vertices à la carte graphique. Alors, afin de dessiner un cube (6 faces) je dois envoyer 24 vertices. Nous savons très bien qu'il y aura que 8 vertices différents (car il y a que 8 sommets) et qu'ils seront présents dans le tableau chacun 3 fois.

En ce moment, je garde en mémoire un tableau de 24 vertices et j'envoie un tableau de 24 index (rapport : 1 pour 1). Le but : gardé en mémoire un tableau de 8 vertices et envoyer un tableau de 24 index (rapport: 1 pour 3).

Alors, pour se faire, mon algorithme devra supprimer les doublons et garder un index de ceux-ci.

Des idées?

Merci à vous tous.
30/10/2011, 14h28
FR119492

Salut!

Citation:

tableau de vertices

En français, ça s'appelle des sommets.
Jean-Marc Blanc
30/10/2011, 18h26
pseudocode
Citation:

Envoyé par hugolapointe

Alors, pour se faire, mon algorithme devra supprimer les doublons et garder un index de ceux-ci.

Des idées?

Je suppose qu'il y a des contraintes que tu n'as pas énoncées. Parce que sinon, l'algorithme est assez trivial : tu tries les sommets (et les index associés) selon une relation d'ordre quelconque. Du coups, les doublons se suivent, ce qui permet facilement de compresser le tableau de sommets et de reindexer tes points.

Sommets et Index originaux
```
A C B D A D E B A C
0 1 2 3 4 5 6 7 8 9
```
Tri suivant les Sommets
```
A A A B B C C D D E
0 4 8 2 7 1 9 3 5 6
```
Compression et reindexation -> 5 sommets necessaires
```
A A A | B B | C C | D D | E |
0 4 8 | 2 7 | 1 9 | 3 5 | 6 |
      |     |     |     |   |
  0      1     2     3    4
```
30/10/2011, 19h20
hugolapointe
Premièrement merci.

Déjà ta réponse s'approche de ce que je souhaite. Alors, j'explique à nouveau et cette fois-ci avec plus de précision.

Voici un exemple :

Tableaux initiaux :
Code:

1 2 3 A B C D A E F D C B - - - - - - - - - - 0 1 2 3 4 5 6 7 8 9
Tableaux résultants :
Code:

1 2 3 A B C D E F - - - - - - - - - - 0 1 2 3 0 4 5 3 2 1
Alors, si vous me suivez... Je retourne un tableau de 5 sommets et un tableau de 9 index.

J'espère que cette fois-ci, je suis plus précis.
31/10/2011, 19h17
pseudocode
Citation:

Envoyé par hugolapointe

J'espère que cette fois-ci, je suis plus précis.

C'était déjà précis.

Initial
```
A B C D A E F D C B
- - - - - - - - - -
0 1 2 3 4 5 6 7 8 9
```
Trié
```
A A B B C C D D E F
- - - - - - - - - -
0 4 1 9 2 8 3 7 5 6
```
regroupé et réindexé
```
A A | B B | C C | D D | E | F
- - | - - | - - | - - | - | -
0 4 | 1 9 | 2 8 | 3 7 | 5 | 6
    |     |     |     |   | 
 0     1     2     3    4   5
```
A partir de là, la première ligne nous donne le nouveau tableau de sommets (il suffit d'avancer dans le tableau trié sans prendre les doublons)
```
A B C D E F
```
Les 2 autres lignes nous donnent la table de conversion ancien index / nouvel index : 0->0, 4->0, 1->1, ..., 5->4, 6->5. Il suffit alors de parcourir la table des anciens index, et de mettre les nouveaux a la place.
```
0 1 2 3 0 4 5 3 2 1
```
31/10/2011, 19h45
hugolapointe

Merci pseudocode. Maintenant je comprends. Est-ce que c'est abusé de te demander comment implémenterais-tu cet algorithme en langage C++ de façon à demeurer le plus optimal.

La partie que je me pose le plus de question à savoir comment je vais procéder est celle où je dois ré-indexer.