[Geo]Detecter le chevauchement de 2 formes géometriques

Version imprimable

12/10/2004, 14h02
Pill_S

[Geo]Detecter le chevauchement de 2 formes géometriques
Bonjour à tous,

je suis en train de développer un petit jeu (casse-briques), et je bute sur un problème pourtant simple:

Je souhaiterais savoir si un disque (de centre 'O' et de rayon 'R') se superpose (partiellement ou complètement) à un rectangle (autrement dit, si la balle touche une brique !)

Pour l'instant, je regarde les coordonnees de 5 points "sensibles" de la balle afin de détecter les collisions
Code:

1 2 3 4 5 _x_ / \ x x x \_x_/
C'est pas vraiment top, y'aurait-il un moyen "mathématique" ?

:merci: beaucoup !
12/10/2004, 14h25
Guigui_

je sais pas si c'est très bien ce que je propose mais bon:
tu peux déjà faire un test qui te permets de savoir si ta balle focément à l'extérieur de ton rectangle (donc le cas général):
- en calculant la distance entre le centre de ta balle et celui de la brique. Si ca dépasse le rayon+la moitié de la longueur de la diagonale du rectangle, a coup sur y'a pas collision

Puis si la distance est plus petite:
pour qu'il y ait collision, il faut que l'écart pour les coordonnées en X du centre de la balle au centre de la brique (en supposant que la brique soit horizontale (ou verticale)) ne dépasse pas R (rayon du cercle) + demi-largeur du rectangle et il faut que l'écart pour les coordonnées en Y du centre de la balle au centre de la brique (en supposant que la brique soit horizontale (ou verticale)) ne dépasse pas R + demi-longueur du rectangle

En gros ca te fait gérer la boule comme un carré, ce qui est pas forcément juste du fait que ce soit une boule ) mais je pense qu'on élimine quand même les erreurs (avec la première condition) qui pourrait arriver si le boule est en bas à droite (en gros vers un coin) du rectangle et que le contact ne se fasse pas avec les points haut,bas,gauche,droite de la boule. Mais au moins ca a l'avantage d'être très rapide
12/10/2004, 14h37
2Eurocents

Vérifier si l'un des points des briques est à une distance R (rayon) du centre de la balle ...

Pour trouver les points les plus favorables des briques (les plus susceptibles d'être "dans" la balle), prendre chaque arête et considérer le point de l'arête tel que la droite de ce point au centre de la balle soit perpendiculaire à l'arête (une bête histoire d'annulation de produit scalaire).

Mais tester toutes les briques de cette façon n'est vraiment pas optimal ...

Pour limiter les briques à tester, on peut limiter à celles situées à une distance critique de la balle ...

C'est quand même très mathématique et pas forcément optimal ... pour un casse-brique !
12/10/2004, 15h30
clemaire

Tu traces une droite imaginaire entre le centre de ta balle et le centre de ton rectangle. Tu considères les coordonnées des deux points à l'intersection de la droite et du périmètre de la balle.

Ceci fait, vérifie si l'un des deux points du cercle est dans le rectangle -> collision. Sinon, vérifie si le centre du rectangle est compris entre les deux points du cercle -> collision.

A procéder ainsi, on se blinde contre des pas de déplacement trop grands, et des rectangles trop petits par rapport à la balle. Le pas doit quand même rester inférieur à la longueur du plus petit côté, auquel on a sommé le diamètre de la balle, sinon tu risques de passer au travers de la brique sans t'en apercevoir!

Sur le plan mathématique, un peu de produit scalaire, puis le tour est joué!
12/10/2004, 15h44
Higgins

Je ne sais pas sur quel OS tu bosses mais si c'est sous windows, tu peux utiliser directX il ya des détections automatiques de collisions entre objets
12/10/2004, 16h00
Pill_S

Oki, merci à tous pour vos réponses,

je pense pouvoir arriver a quelques chose en compilant les solutions entre elles

bon je met pas encore le tag résolu parce que c'est pas encore implémenté, et j'aurai peut-être encore d'autres questions

mais déjà, :merci: bcp ! :wink:
12/10/2004, 16h01
Pill_S

Citation:

Envoyé par Higgins

Je ne sais pas sur quel OS tu bosses mais si c'est sous windows, tu peux utiliser directX il ya des détections automatiques de collisions entre objets

désolé, c'est à base de java, donc si direrctx -> bye bye portabilité :lol:

:wink:
12/10/2004, 17h17
ShootDX

Un casse-brique n'a pas besoin d'une très grande précision. Le mieux est de se représenter le cercle comme inscrit dans un carré. On test les bords de ce carré. Ca suffit largement.

Ensuite, pour les briques à tester.
Le mieux est de mettre les briques dans une matrice (chaque case est soit un 1 soit un 0; on peut inventer un code plus élaborer si par exemple tu accepte des murs indémolissables ou des briques qui disparaissent au bout de 3 ricochets).
Ensuite, par une histoire de modulos et de division savante (cherche, c'est pas très compliqué), tu dois pouvoir trouver la case de la matrice ou se trouve la balle. Notez que les chevauchement entre deux cases n'a pas a être traité: si on se retrouve entre deux cases, c'est qu'on était sur l'une des deux avant et qu'on a donc déjà fait le nettoyage.

Si tu as d'autres questions, n'hésite pas: j'ai fait une thèse sur le casse-brique (3 pages :lol: ).

Citation:

Envoyé par ShootDX

Un casse-brique n'a pas besoin d'une très grande précision. Le mieux est de se représenter le cercle comme inscrit dans un carré. On test les bords de ce carré. Ca suffit largement.

Je pense que ne pas faire d'approximations n'est pas plus compliqué :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
// écartement signé entre le cercle (Xc, Yc) et le centre de la brique (Xb, Yb)
dX = Xb - Xc;
dY = Yb - Yc;
 
// les deux points sur le périmètre (R = rayon du cercle)
Xp1 = Xc + dX*R/sqrt(dX*dX + dY*dY);
Yp1 = Yc + dY*R/sqrt(dX*dX + dY*dY);
Xp2 = Xc - dX*R/sqrt(dX*dX + dY*dY);
Yp2 = Yc - dY*R/sqrt(dX*dX + dY*dY);
 
// l'un des deux points du périmètre dans la brique?
// dXb = largeur d'une brique, dYb = hauteur d'une brique
boolean bCollision = pointDansRectangle(Xp1, Yp1, Xb - dXb/2, Yb - dYb/2, Xb + dXb/2, Yb + dYb/2);
bCollision = !bCollision && pointDansRectangle(Xp2, Yp2, Xb - dXb/2, Yb - dYb/2, Xb + dXb/2, Yb + dYb/2);
 
// le centre de la brique entre les deux points du cercle (que l'on verra
// comme formant un rectangle, même si celui-ci est réduit à un segment) ?
bCollision = !bCollision && pointDansRectangle(Xb, Yb, Xp1, Yp1, Xp2, Yp 2);

avec la fonction pointDansRectangle() valant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// marche aussi lorsque les deux points du rectangle sont sur la même abcisse ou la même ordonnée.
boolean pointDansRectangle(Xp, Yp, X0_p, Y0_p, X1_p, Y1_p) {
  // on normalise les points diagonaux du rectangle dans (X0, Y0) et (X1, Y1)
  if (X0_p < X1_p) {
    X0 = X0_p;
    X1 = X1_p;
  } else {
    X0 = X1_p;
    X1 = X0_p;
  }
  if (y0_p < y1_p) {
    Y0 = Y0_p;
    Y1 = Y1_p;
  } else {
    Y0 = Y1_p;
    Y1 = Y0_p;
  }
  // on fait le test d'appartenance du point au rectangle
  return (Xp >= X0 && Xp <= X1) && (Yp >= Y0 && Yp <= Y1);
}

Pas besoin d'en faire tout un fromage, non :wink: ?

12/10/2004, 19h17
ShootDX
Code:

1 2 3 4 Xp1 = Xc + dX*R/sqrt(dX*dX + dY*dY); Yp1 = Yc + dY*R/sqrt(dX*dX + dY*dY); Xp2 = Xc - dX*R/sqrt(dX*dX + dY*dY); Yp2 = Yc - dY*R/sqrt(dX*dX + dY*dY);
Tu es sûr que ça changerai quelque chose à ma méthode avec application sur des malheureux pixels à coordonées entières?
12/10/2004, 19h41
clemaire

Ma méthode s'applique à un vrai cercle. Ton procédé n'est pas le même. Pour moi, la balle et les briques sont composées d'un nombre assez conséquent de pixels. Les effets seront plus précis à considérer un cercle.

Et puis, pourquoi faire de grosses approximations quand cela ne coûte rien de simuler une vraie balle ? C'était plus ça que je voulais dire :) !

Citation:

Envoyé par clemaire

avec la fonction pointDansRectangle() valant :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
// marche aussi lorsque les deux points du rectangle sont sur la même abcisse ou la même ordonnée.
boolean pointDansRectangle(Xp, Yp, X0_p, Y0_p, X1_p, Y1_p) {
  // on normalise les points diagonaux du rectangle dans (X0, Y0) et (X1, Y1)
  if (X0_p < X1_p) {
    X0 = X0_p;
    X1 = X1_p;
  } else {
    X0 = X1_p;
    X1 = X0_p;
  }
  if (y0_p < y1_p) {
    Y0 = Y0_p;
    Y1 = Y1_p;
  } else {
    Y0 = Y1_p;
    Y1 = Y0_p;
  }
  // on fait le test d'appartenance du point au rectangle
  return (Xp >= X0 && Xp <= X1) && (Yp >= Y0 && Yp <= Y1);
}

ça c'est un méthode qui existe déjà dans java mais merci quand même :wink:

mais lorsque tu fais

Code:

1
2
3
4
5
 
Xp1 = Xc + dX*R/sqrt(dX*dX + dY*dY); 
Yp1 = Yc + dY*R/sqrt(dX*dX + dY*dY); 
Xp2 = Xc - dX*R/sqrt(dX*dX + dY*dY); 
Yp2 = Yc - dY*R/sqrt(dX*dX + dY*dY);

c'est pour trouver quoi au fait ? les "deux points sur le périmètre" représentent quoi ?

:wink:

12/10/2004, 20h12
Pill_S

je viens de penser à une nouvelle solution, beaucoup plus simple et plus rapide !

- j'utilise un autre rectangle, dont les dimensions sont d'un rayon de balle plus grandes que la brique (et les angles sont arrondis).
- si ce rectangle contient le centre de la balle -> collision
- je regarde les coordonnée pour savoir si c'est un mur horizontal ou vertical et je change la direction de la balle en conséquence

c'est mieux non ? en plus comme ça je peux me servir de java (et la méthode contains()) pour faire le gros du travail... après, reste plus qu'a limiter les tests aux briques les plus proche de la balle et c gagné !
14/10/2004, 13h54
Pill_S

Voilà, c'est implémenté et ça marche pas trop mal :wink:
25/10/2004, 17h25
SuperCed

Il existe aussi une solution, que l'on peut également interpoler à la 3D.
J'avais fait ça pour un système de collision surfacique pour un glissement.

En fait, tu fais comme si ta balle avait un rayon (ce qui est vraie), et tu lances des rayons normés par ta vitesse dans 7 directions. cad dans 7 direction, sauf la direction opposée à ta vitesse.
Tu teste ensuite les intersections de tes vecteurs (rayons normé) avec tes objets. S'il y a bien une intersection, alors tu réduit la norme de ton vecteur en fonction de la distance de ta balle à au point d'intersection considéré.
Une fois que tu as fait ça pour tes 7 vecteurs, tu les ajoutes vectoriellement.

Ceci te donne le vecteur de glissement de ta balle.

Dans le cas d'un rebond, lorsqu'il y a intersection, il te suffit de redéfinir la norme de ton vecteur ET de changer le signe de celui-ci. (a,b) deviendra (-a,-b). Et voilà, tu as un rebond.

Pour tester le point d'intersection, ça revient tout simplement à résoudre un système de 2 équations à 2 inconnues. Pour vérifier que ton point d'intersection est bien inclus dans ton vecteur, c'est facile aussi.

Par contre, il faut que tu fasses un tri préalable, une sorte de distance maxi pour ne pas appliquer l'algo à tous tes objets. Dernière chose : Il faut bien prendre le point d'intersection le entre le vecteur et les droites définissant le polygone de façon à faire un rebond sur l'objet le plus proche, et pas un qui serait caché derrière.

L'intérêt de cette méthode est que ça s'applique à la 3D, à des polygones concaves, tordus dans tous les sens, et pas forcément rectangulaire et parallèle à l'horizontal. ou à la verticale. L'inconvénient est que ça prend pas mal de temps processeur...