Discussion :

[patbier]

Bonjour à tous, j'ai besoin d'un coup de main pour optimiser mon code.
Je vous explique. J'ai besoin de générer un masque de collisions de différentes formes. Pour cela j'ai créé un tableau de la taille du plateau, dans lequel j'utilise des unsigned char (32 bits) pour que je puisse stocker 32 informations binaire 0/1 : soit un pixel est occupé, soit il est libre.
Donc j'initialise mon tableau avec un memset pour tout mettre à 0.
J'ai aussi créé des tableaux pour représenter les pixels de mes objets, par exemple un cercle.

Voici la fonction que j'utilise pour copier les bits d'un cercle dans le plateau :

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
44
45
46
47
 
void plateau_cercle(int i,int j){
	unsigned char mbitMin,mnum,mbit;
	unsigned char cbitMin,cnum,cbit;
	int xc,yc,ym;
	unsigned int *z;
	unsigned int *c;
        /* ici je calcule la position théorique dans laquelle je vais copier le cercle dans le plateau car l'image du cercle fait 128x128 */
	int xmin=i,xmax=i+128,ymin=j,ymax=j+128;
        /* ici je calcule la position du cercle qui va m'interesser */
	int cxmin=0;int cymin=0;int cxmax=128;int cymax=128;
        /* ici je teste si je ne suis pas en dehors des limites */
        /* TPCX et TPCY sont les tailles maxi du plateau */
	if (xmin<0) {cxmin=xmin * -1;xmin=0;} if (xmax>TPCX) {cxmax=128 - xmax +TPCX;xmax=TPCX;}
	if (ymin<0) {cymin=ymin * -1;ymin=0;} if (ymax>TPCY) {cymax=128 - ymax +TPCY;ymax=TPCY;}
        /* ici je cherche sur quel octet je vais commencer et sur quel bit */ 
	mnum = xmin/32 ; mbit = mbitMin = xmin - (mnum  * 32);
	cnum = cxmin/32; cbit = cbitMin= cxmin - (cnum * 32);
 
	ym=ymin;
	yc=cymin;
        /* je reutilise xmax pour boucler sur les y */
	xmax=cymax - cymin;
	xmin=cxmax - cxmin;
        /* je boucle pour tous les y qui m'interessent */
	while(xmax--){
                /* je me positionne sur le bon octet du plateau */
		z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + mnum]);
		mbit=mbitMin;
		cbit=cbitMin;
                /* je me positionne sur le bon octet du cercle */
		c=(unsigned int *)(&cercle_32[yc * 4 + cnum]);
 
		xc=xmin;
                /* pour chacun des bits */
		while (xc--){
			if ((*c >> cbit) & 1) {*z &= ~ (1 << mbit);}
			mbit++;if (mbit>31){z++;mbit=0;}
			cbit++;if (cbit>31){c++;cbit=0;}
		}
 
		ym++;
		yc++;
	}
 
 
}

Vous remarquerez que j'ai essayé d'optimiser un peu déjà. Avant j'utilisais naïvement un int pour chaque valeur 0/1 des pixels, et ça a déjà bien amélioré les choses de passer aux nombres binaires stockés dans une variable 32 bits. J'en viens à ma question : est il possible d'optimiser les choses et existe t il une fonction pour ne pas avoir à passer les valeurs bit à bit ? Car il peut y avoir du décalage : un pixel de cercle peut être affecté au 9ème pixel d'un octet du plateau.

Merci pour votre aide !

[Obsidian]

Oula, oui, tu peux aller encore beaucoup plus loin.

Si tu es obligé de faire des décalages de bits et des « & 1 » pour extraire celui qui t'intéresse, c'est justement parce que ton micro-processeur, même seul, est une machine en parallèle qui traite n bits à la fois. C'est dommage de les décomposer pour les confronter un à un.

En faisant directement un & entre ton masque et ton plateau, tu testes d'un coup 4 octets sur une machine 32 bits, soit autant de pixels. Comme le résultat d'un & entre deux bits est 1 si et seulement si les bits des deux opérandes sont à 1 eux aussi, ton résultat doit forcément être nul, sinon c'est que deux pixels se chevauchent, et qu'il y a donc collision.

Si, en plus, tu connais déjà la forme de ce que tu affiches, alors tu n'es même plus obligé de recourir à des masques : pour un disque, par exemple, il te suffit d'appliquer le simple théorème de Pythagore pour connaître la distance d'un point au centre de ce disque. Si celle-ci est inférieure au rayon de celui-ci, il y a automatiquement collision.

Tu peux aussi puiser quelque idées dans ce fil : http://www.developpez.net/forums/d83...oches-voisins/

[patbier]

Bonjour et merci pour la réponse.
En fait, je me suis mal exprimé, j'ai besoin de ce "masque" non pas pour connaitre les collisions, mais pour un calcul de lumière. N'ayant pas possibilité d'utiliser un stencil buffer, je gère moi-même l'affichage ou non de pixel selon le fait qu'un cercle (et donc une source de lumière) existe ou non sur ce pixel.

Il me faudrait un coup de main pour tester plusieurs bits d'un coup.
J'ai essayé toute la journée d'hier à peaufiner mes algos mais malheureusement je ne m'en sors pas.

Je vous explique : l'idée est donc de comparer plusieurs bits à la fois.
Dans un cas parfait où je compare un nombre de 32 bits avec un autre nombre de 32 bits, cela est tres simple : *z &= *c
Pas de problème.
Par contre, dans mon cas, imaginez que je place un cercle à la position 37,0.
Etant donné que mon plateau est constitué de nombre 32 bits, il faut donc que j'affecte les valeurs binaires du cercle à partir du 2eme nombre et au 27ème bit
car :

Code :

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

1
2
3
4
5
6
 
1er nombre         -        2eme nombre
 
31 30 29 ... 2 1 0 - 31 30 29 28 27 ... 2 1 0
                                  |
                                  37eme position

En gros, j'ai besoin d'un algo me permettant de comparer un buffer binaire avec un autre buffer binaire avec un décalage.
J'ai essayé plein de possibilités en utilisant << et >> mais je ne m'en sors pas.

Je sais calculer à quel nombre et quel bit commencer sur le plateau : mnum et mbitMin
Je sais calculer à quel nombre et quel bit commencer sur le cercle : cnum et cbitMin
je calcule donc le décalage : decal = mbitMin - cbitMin

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
	if (decal==0){
		while(xmax--){ // environ 128
			unsigned int test;
			z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + mnum]);
			c=(unsigned int *)(&cercle_32[yc * 4 + cnum]);
			//on teste d'abord les 1ers décalés
			xc=xmin;		
			test=(*c << mbitMin) >> mbitMin;
			*z &= test;
			xc-=mbitMinInv;
			z++;c++;
			// puis les octets suivants
			while(xc>=32){*z &= *c;xc-=32;z++;c++;}
			// s'il reste un bout
			if (xc > 0){test=0;	test=(*c >> (32 - xc)) << (32 - xc);*z &= test;}
			ym++;yc++;
		}
	}
	else{
		if(decal>0){
			while(xmax--){ // environ 128
				unsigned int test;
				z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + mnum]);
				c=(unsigned int *)(&cercle_32[yc * 4 + cnum]);
				//on teste d'abord les 1ers décalés
				// c pointe sur trop
				xc=xmin;
				test=(*c >> cbitMin) << mbitMin;
 
				*z &= test;
				xc-=mbitMinInv;
				z++;c++;
				// puis les octets suivants
				while(xc>=32){*z &=( (*(c - 1)) >> (cbitMin + mbitMinInv) )| (*c << (cbitMin + mbitMinInv)) ;xc-=32;z++;c++;}
				// s'il reste un bout
				if (xc > 0){test=((( (*(c - 1)) >> (cbitMin + mbitMinInv) )| (*c << (cbitMin + mbitMinInv))) << (32 - xc)) >> (32 - xc);*z &= test;}
				ym++;yc++;
			}
		}
		else{ // ici negatif
			while(xmax--){ // environ 128
				unsigned int test;
				z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + mnum]);
				c=(unsigned int *)(&cercle_32[yc * 4 + cnum]);
				//on teste d'abord les 1ers décalés
				// c pointe sur pas assez
				xc=xmin;		
				test=(*c >> (decal * -1));
				*z &= test;
				xc-=mbitMinInv;
				z++;c++;
				// puis les octets suivants
				while(xc>=32){*z &=((*c << cbitMin)|((*(c +1)) >> (32 - cbitMin))) ;xc-=32;z++;c++;}
				// s'il reste un bout
				if (xc > 0){test=(((*c << cbitMin)|((*(c +1)) >> (32 - cbitMin))) >> (32 - xc)) << (32 - xc);*z &= test;}
				ym++;yc++;
			}
		}
	}

Je ne sais pas si je m'exprime clairement mais j'ai vraiment besoin d'aide ! Est ce qu'un tel algo existe ? Merci pour votre aide.

[patbier]

J'ai simplifié mon algo, mais vraiment je ne m'en sors pas avec ces nbs binaires...

J'ai besoin de faire une fonction qui va mettre des 0 dans mon masque :

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
 
void MazMasqueCercle(int mx1,int mx2,int ym){
	int o,o1,o2,b1,b2;
	unsigned int *z;
	unsigned int test;
	o1= mx1/32;b1= 32 - (mx1 - (o1  * 32));
	o2= mx2/32;b2= mx2 - (o2  * 32);
 
	// le 1er bit est soit complet, soit incomplet
	z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + o1]);
 
	if (o1==o2){
                test = -1;
		*z &= (test << b1);
		test = -1;
                *z &= (test >> b2);
	}
	else{
	       test = -1;	
               *z &= test << b1;
		z++;
 
		for(o=o1+1;o<o2;o++){ //forcement complets
			*z=0;
			z++;
		}
		test = -1;
		*z &= test >> b2;
	}
 
}

C'est beau sur le papier mais ça ne marche pas...

[patbier]

Bon enfin, je m'en suis sorti !!
En fait, je lisais les bits à l'envers. Pour information, voilà la fonction corrigée :

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
 
void MazMasqueCercle(int mx1,int mx2,int ym){
	int o,o1,o2,b1,b2;
	unsigned int *z;
	unsigned int test;
	o1= mx1/32;b1= 31 - (mx1 - (o1  * 32));
	o2= mx2/32;b2= mx2 - (o2  * 32);
 
	// le 1er bit est soit complet, soit incomplet
	z=(unsigned int *)(&plateau.masque_cercle[ym*TPCX32 + o1]);
 
	if (o1==o2){ test = -1;	*z &= (test >> b1) | (test << b2);}
	else{
		test = -1; *z &= (test >> b1);
		z++;
		for(o=o1+1;o<o2;o++){ //forcement complets
			*z=0; z++;
		}
		test = -1; *z &= (test << b2);
	}
}