Si je me souviens bien la dernière fois on avait vu comment remplir
un polygone, donc je suis sûr que vous avez essayé d'afficher vos
cubes en 3D avec des zolies faces pleines de couleurs... =)
Bon si cet article est le premier que vous lisez dans la looongue série
de putains d'articles que je me suis fait chier à taper (je rigole), ne
vous sentez pas largué d'entrée de jeu, l'article d'aujourd'hui n'a rien
à voir avec les précédents (ou presque).
Enfin disons que vous arriverez à le comprendre quand même. Voilou. Toc.
Bon maintenant je m'adresse à tous les lecteurs qui ont bien voulu lire mes articles jusque là, parce qu'il est vrai que je parle beaucoup et je suppose que c'est TRES chiant ;)
Well, aujourd'hui on va étudier une super façon de trier des données, ce
qui peut rendre grand service à tous les 3D-philes qui arrivent pas à
trier leurs faces :)
Je vous previens que c'est vachement simple, donc vous pouvez siroter
un whisky bien frais en lisant ceci... Euh pour les enfants disons un
verre de grenadine avec des glaçons. (Niark niark ;))
Sa rapidité est dûe au fait qu'il ne ralentissâtes point la vitesse d'avancement de la puce électronique (appelée micro-processeur) par des comparaisons fâcheusement inutiles, étant donné qu'il utilise les propriétés mathématiques concernant l'addition, et d'où découle son indiscutable rapidité. (c'que j'cause bien alors.. ;)
En clair ça veut dire qu'au lieu d'utiliser des CMP (beurk) pour trier les données, il utilise les propriétés de l'addition. Je vous vois déjà venir avec vos gros sabots : (BOUM BOUM BOUM) (ça c'est le bruit des gros sabots :)) (désolé) Vous allez me dire qu'un CMP n'est pas plus lent qu'un ADD.... Mais cete méthode avec l'addition permet de faire en beaucoup moins d'instruction qu'avec la méthode bourin du CMP... D'où optimisation donc gain de temps donc WondY très content (ça rime :)
Tout d'abord il nous faut un tableau de valeurs à trier. Bah oui ça parait con comme ça, mais faut être logique quoi...
Donc on va dire que TABL1, notre tableau à trier, est défini comme ça :
{ Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6
TABL1 { -------|---|---|---|---|---|---|---
{ Valeur | 1 | 3 | 2 | 5 | 7 | 3 | 0
Maintenant il nous faut un deuxième tableau pour contenir le nombre
de fois que chaque valeur apparaît.
Comme nous trions des OCTETS, la valeur maximale est 255.
Donc notre TABL2 aura 255 éléments.
Il faut d'abord l'initialiser à 0
for(i=0;i<256;i++)
TABL2[i]=0;
Maintenant on peut compter chaque valeur : pour chaque valeur de TABL1, on va incrémenter la case correspondante de TABL2.
for(i=0;i<7;i++) //7 valeurs à traiter
{
val=TABL1[i]; //on prend la valeur dans TABL1
TABL2[val]=TABL2[VAL]+1;
//et on incrémente l'élément de TABL2 correspondant
}
A la fin de cette étape, TABL2 contient le nombre d'occurence de chaque valeur.
{ Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6
TABL1 { -------|---|---|---|---|---|---|---
{ Valeur | 1 | 3 | 2 | 5 | 7 | 3 | 0
{ Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ... | 255
TABL2 { -------|---|---|---|---|---|---|---|---|---| ... |-----
{ Valeur | 1 | 1 | 1 | 2 | 0 | 1 | 0 | 1 | 0 | ... | 0
Maintenant il suffit d'ajouter à chaque case la valeur de la case précédente :
for(i=1;i<255;i++)
TABL2[i]=TABL2[i]+TABL2[i-1];
Mais pourquoi cette opération ? Regardez notre TABL2 après cette étape:
{ Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ...
TABL2 { -------|---|---|---|---|---|---|---|---|---| ...
{ Valeur | 1 | 2 | 3 | 5 | 5 | 6 | 6 | 7 | 7 | ...
Vous vous rendez compte que pour chaque valeur en indice, on a sa position
dans le tableau trié final !!!
En effet, la valeur 2 sera en 3eme position, la valeur 5 en 6ème etc...
C'est MAGIQUE! FANTASTIQUE ! (envoyez moi vos dons , cf fin du fichier)
Il ne nous reste donc plus qu'à relire les données de TABL1, regarder sa position dans le tableau final, et la placer ! Pour cela il nous faut un 3ème tableau identique à TABL1, qui sera le tableau de données triées. Nous l'appellerons TABL3. Il nous reste cependant un dernier détail à régler (très petit): Dans notre exemple, la valeur 3 revient 2 fois dans TABL1. Il faut donc qu'elle apparaisse deux fois également dans le tableau final. Pour cela, il suffit de décrémenter la case correspondante. En effet, dans notre exemple, la première valeur 3 se retrouvera en 5ème position dans le tableau final et la deuxième en 4ème position. OK!
for(i=0;i<7;i++) //7 valeurs
{
val=TABL1[i];
pos=TABL2[val];
TABL2[val]=TABL2[val]-1 // ne pas oublier de décrémenter !
TABL3[pos]=val;
}
Et voilou !
{ Indice | 0 | 1 | 2 | 3 | 4 | 5 | 6
TABL3 { -------|---|---|---|---|---|---|---
{ Valeur | 0 | 1 | 2 | 3 | 3 | 5 | 7
Vous voyez que c'est vraiment simple :)
Bon voilà c'est fini pour aujourd'hui les enfants... *<;-)
Pour me contacter :
Par S-Mail :
WondY / ZeN
DERRIER Pierre
267, Rue St Pierre
73300 St Jean de Maurienne
FRANCE-TERRE-UNIVERS
Par E-Mail : pderrier@icor.fr
Par Tel : +33-(0)4-795-984-30
Vous pouvez aussi venir voir la Zen'S HomE SwEet Page :
http://www.citeweb.net/zenpage
c'est tout
a++++ les biquettes
.....WondY.....ZeN...