Discussion :

[LittleWhite]

Bonjour à tous,

Voici le troisième tutoriel sur la théorie des collisions. Celui-ci explore les algorithmes de collision et les techniques permettant d'effectuer des collisions au pixel près..

N'hésitez pas à faire des commentaires.

Bonne lecture

[forthx]

C'est simple et clair

Par contre quant tu dit:

Nous avons dit qu'il fallait prendre une image 1, la parcourir et tester ses pixels par rapport à l'image 2. Afin que l'algorithme soit moins lourd, on prendra comme image 1 l'image la plus petite

Voici une petite piste d'optimisation qui ne change pas le coté pixel perfect de l'algo :

une fois que l'on a fait un test de collisions AABB et que la collision est avéré Il suffi d'extraire les sommets de la zone de collision, on peu alors réduire l'analyse aux pixels de cette zone (en vert sur l'image).


Cela demande un peu plus de code (notamment pour tester les condition aux limites comme le recouvrement total d'une image pas l'autre)
Dans le pire des cas on se retrouve dans la situation d'origine, avec un petit test en plus. Dans le cas de sprites se déplacent de quelques pixels entre chaque test AABB, par exemple 2 sprites de 64*64 qui se recouvrent sur 10*64 pixels, cela donnera 640 tests max au lieu de 4096 soit 6.4 fois moins de calculs. (edit: l'exemple n'est pas vrai si lors du calcul précédent il y a recouvrement partiel des 2 sprites mais pas collision, comme c'est le cas sur l'image précédente.)

Je conclurai en ajoutant que comme d'autre algo de collisions simple les objets qui se déplacent trop vite peuvent se traverser sans générer la moindre collision.

En espérant avoir été compréhensible et constructif.

[Franck.H]

C'est une idée qui me plaît bien

[ggnore]

L'article se termine par :

Voici donc quelques algorithmes de collision au pixel près.

Mais il n'y a rien derrière, ou bien je n'ai pas vu les liens.

[LittleWhite]

C'est plus une phrase de conclusion. "voila" serait peut être mieux choisi.

[borisxXx]

Bonjour, je me permet de poser une question parce qu'en fait j'ai un gros doute sur le calcul de la complexité, je m'explique :

Dans l'algorithme on parcours une image (de préférence la plus petite) et pour chaque pixel du masque (en blanc), il est écrit qu'on cherche le point correspondant dans la seconde image.

Hors je ne vois pas du tout ce que signifie "ce point correspondant". J'ai tendance à penser naïvement qu'il faut plutôt à partir de ce moment là, parcourir toute la seconde image pour s'assurer qu'aucuns de ses pixels blancs ne correspondent à ce dernier.

La complexité dans ce cas, serait beaucoup plus élevé. Soit n, le nombre de pixels dans l'image 1 et m le nombre de pixel dans l'image deux.
Dans le pire des cas (pas de collisions), la complexité serait en O(n*m) soit pour deux images de la même taille, O(n^2) !

De manière plus générale, l'algorithme fonctionne dans le cas où on peut savoir facilement (en O(1)) si un point de coordonnés monde (x,y) est bien le pixel blanc d'une image (difficile à savoir si cette image à subit des transformation locale (translation, rotation, scaling)).

Bien entendu, je ne fais part que de mes doutes, j'aimerais faire la lumière sur la raison de mon erreur de compréhension.

[forthx]

J'ai tendance à penser naïvement qu'il faut plutôt à partir de ce moment là, parcourir toute la seconde image pour s'assurer qu'aucuns de ses pixels blancs ne correspondent à ce dernier.

Je pense que l'on peu faire hypotypose que les coordonnées des "boîtes englobantes" sont connue (au mois un coin qui va servir d'origine: Xo1,Yo1,Xo2,Yo2). A partir de la on sais a priori quel pixel du masque 1 (x1,y1) et du masque 2 (x2,y2)se superposent (ca doit ressembler a : x1=Xo2+x2-Xo1 et y1=Yo2+y2-Yo1). Du coup on a pas a effectuer plus d'une comparaison par pixel au niveau des masques: on fait varier x2,y2 entre 0,0 et w,h (je l'image ad hoc) et le tour est jouer.

De manière plus générale, l'algorithme fonctionne dans le cas où on peut savoir facilement (en O(1)) si un point de coordonnés monde (x,y) est bien le pixel blanc d'une image (difficile à savoir si cette image à subit des transformation locale (translation, rotation, scaling)).

En fait si on se place au bon endroit dans la pipeline de rendu (juste avant l'affichage des sprites mais après les transformations) et qu'on a bien des sprites rectangulaires (droit) l'algo fonctionne. Dans les jeux 2d on peu facilement se retrouver dans ce cas a mois de laisser un framework faire le travail (de transformation et d'affichage des sprites)a notre place.

vous m'arrêtez si je me trompe !

[borisxXx]

Effectivement dans ce cas, il y a seulement une translation des sprites (translation de vecteur (Xo1,Yo1) pour le premier sprite et de vecteur (Xo2,Yo2) pour le second). On peut donc retrouver relativement trivialement le "point correspondant en question".

Ce qui me chagrine, c'est que les deux autres transformations (mise à l'échelle et rotation) ne seraient pas prises en compte.

Il est évident que le cas de la mise à l'échelle pourrait être réglé de la même façon en modifiant un peu la formule pour prendre en compte le ratio de scaling, ça devrait donner un truc comme ça:
x1=(Xo2+x2*Sx2-Xo1)*Sx1 et y1=(Yo2+y2*Sy2-Yo1)*Sy1

Hors, tout ça va fonctionner seulement si on considère un sprite droit (grosse limitation).
Dans le cas généralisé, il faudrait attribuer à nos sprites, une matrice de transformation qui permet à partir d'un point 2D en coordonnées sprites d'obtenir ses coordonnées monde. Si on inverse la matrice, on réalise l'effet inverse et trouver le point correspondant devient trivial:

p1 = WorldToLocal*LocalToWorld2*p2

Le cas échéant, on obtient bien du O(n). Mais si c'est ce que voulait dire l'auteur de l'article, il manque la partie la plus importante de l'explication: comment trouver le point correspondant.