begin process at 2013 06 19 10:39:16
  Trouver un code source :
 
dans
 
Accueil > 

Code

 > 

Maths & Algorithmes

 > COLLISION DE RECTANGLES 2D

COLLISION DE RECTANGLES 2D


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :collision, rectangle, physique, algorithme, contact Niveau :Débutant Date de création :15/11/2006 Date de mise à jour :17/11/2006 17:39:36 Vu / téléchargé :16 360 / 862

Auteur : Galmiza

Ecrire un message privé
Site perso
Commentaire sur cette source (10)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
Algorithmes de calcul d'intersection de rectangles.
Les rectangles sont définis par leur centre, leur hauteur, leur largeur et leur angle de rotation dans le sens trigonométrique.

Permet de déterminer si deux rectangles sont en contact et de récupérer suffisamment d'informations sur la collision (point de contact + profondeur de pénétration du point + normale au contact) pour faire un moteur physique.

L'interface graphique GLUT n'est pas beaucoup commentée (bien que bien présentée :D) car n'est pas le sujet de cette source (inclut dans le zip).
Elle permet de manipuler les rectangles intuitivement avec la souris.

Les algorithmes de calcul de collision sont dans la classe Rectangle.
Le fichier main.cpp contient exclusivement l'interface graphique.

Aller amusez-vous !

Source

  • // Un simple rectangle
  • class CRectangle
  • {
  • public:
  • CPoint2D Centre;
  • float Hauteur; // Hauteur
  • float Largeur; // Largeur
  • float Angle; // Angle en radian sens trigonométrique
  • CPoint2D A,B,C,D; // Les points (à jour moyennant un appel à UpdatePointPositions)
  • // 2 FONCTIONS IMPORTANTES
  • // Dit si le point P est dans le rectangle. Si oui et nX et nY != NULL, écrit dans nX,nY les composantes de la normale à la face la plus proche du point.
  • BOOL IsPointIn(CPoint2D *P, float *nX, float *nY, float *depht);
  • // Dit si le rectangle est en contact avec un autre. Si oui, écrit dans les paramètres le point de contact I et la normal au contact (nX,nY)
  • BOOL GetCollision(CRectangle *rect, CPoint2D *I, float *nX, float *nY, float *depht);
  • // 2 FONCTIONS MINEURES
  • // Ecrit dans les paramètres les points extrêmes P1=(bas gauche) P2=(haut droite) de la boite englobante dont les cotés sont alignés aux axes du repère
  • void GetAABB(CPoint2D *P1, CPoint2D *P2);
  • // Met à jour les points A B C et D du rectangle en fonctions de ses paramètres
  • void UpdatePointPositions(void);
  • };
// Un simple rectangle
class CRectangle  
{

public:

	CPoint2D Centre;
	float Hauteur;	// Hauteur
	float Largeur;	// Largeur
	float Angle;		// Angle en radian sens trigonométrique

	CPoint2D A,B,C,D;	// Les points (à jour moyennant un appel à UpdatePointPositions)

	// 2 FONCTIONS IMPORTANTES
	// Dit si le point P est dans le rectangle. Si oui et nX et nY != NULL, écrit dans nX,nY les composantes de la normale à la face la plus proche du point.
	BOOL IsPointIn(CPoint2D *P, float *nX, float *nY, float *depht);

	// Dit si le rectangle est en contact avec un autre. Si oui, écrit dans les paramètres le point de contact I et la normal au contact (nX,nY)
	BOOL GetCollision(CRectangle *rect, CPoint2D *I, float *nX, float *nY, float *depht);
	
	// 2 FONCTIONS MINEURES
	// Ecrit dans les paramètres les points extrêmes P1=(bas gauche) P2=(haut droite) de la boite englobante dont les cotés sont alignés aux axes du repère
	void GetAABB(CPoint2D *P1, CPoint2D *P2);

	// Met à jour les points A B C et D du rectangle en fonctions de ses paramètres
	void UpdatePointPositions(void);	
};

 Conclusion

Commandes:
Tout se fait avec la souris.
Cliquez gauche sur un rectangle et faites glisser pour le déplacer.
Cliquez droit sur un rectangle et faites glisser pour le faire tourner.

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

15 novembre 2006 19:02:53 :
Changement du l'extension de l'image de .JPG à .jpg car elle n'apparaissait pas avec la source.
15 novembre 2006 21:05:29 :
Ajout d'une interface graphique de base. Soyez indulgent c'est ma première utilisation de GLUT.
15 novembre 2006 21:19:42 :
Affichage de la normale au contact (+ au passage correction d'un bug sur le calcul de la normale)
15 novembre 2006 23:48:04 :
Interface graphique améliorée. Affichage de la sphère englobante et de la boite englobante parallèle aux axes. Manipulation des rectangles intuitive avec la souris.
16 novembre 2006 19:08:37 :
Création de la classe CRectangle.
17 novembre 2006 17:39:37 :
Creation de la classe CPoint2D pour faciliter la lecture du code. La détection de collision des rectangles quand aucun des points d'un rectangle ne soit dans l'autre rectangle est désormais valide. La profondeur de pénétration du point est accessible (pratique pour les moteurs physiques orientés efforts). Amélioration générale de la présentation et des commentaires.

 Sources du même auteur

Source avec Zip Source avec une capture EXEMPLES D'UTILISATION DES PIXELS SHADERS 2.0 AVEC DIRECTX 9...
Source avec Zip Source avec une capture 2D HARDWARE AVEC DIRECTX 9
Source avec Zip Source avec une capture MOTEUR 3D EN C++ AVEC DIRECTX 8.1 (GESTION SOURIS, CLAVIER, ...

 Sources de la même categorie

Source avec Zip LE PROBLÈME DU VOYAGEUR DE COMMERCE EN LANGAGE C (ANT SYSTEM... par casseur
Source avec Zip VECTEUR CREUX par stroke599
Source avec Zip Source avec une capture FONCTIONS EN ACTION par ringo73
CALCUL DE PI AVEC LA BIBLIOTHÈQUE GMP par lann
Source avec Zip Source avec une capture MAGEO3D, POUR GÉRER LES POINTS ET LES VECTEURS DE L'ESPACE R... par pgl10

 Sources en rapport avec celle ci

Source avec Zip ASCII_PHYSIX par BuuG63
Source avec Zip Source avec une capture ALGORITHME ACO TOILE D'ARAIGNÉE par RyBeN
Source avec Zip Source avec une capture TRAITEMENT D'IMAGE EN C++, QT par Akham75
Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip ÉDITEUR DE RECTANGLES EN CONSOLE par seoseo

Commentaires et avis

Commentaire de Galmiza le 15/11/2006 20:08:58

Bon, je rajoute une interface graphique tout à l'heure.

Commentaire de Ombitious_Developper le 15/11/2006 21:47:41

Salut:

J'ai attendu que les deux rectangles sont en mouvement et que le processus de détection de collision sera mis en évidence au fur à mesure.

Je pense que ça sera une bonne amélioration à faire.

Bonne continuation ...

Commentaire de Galmiza le 15/11/2006 22:04:25

Merci pour le commentaire !

Comment ça au fur et à mesure ?
Tu parles de plusieurs couches de test genre (sphère + aabb = axis aligned bounding boxes) avant de tester précisement ?
Sinon tu peux actuellement tourner les rectangles avec les touches 'a' et 'z' ainsi que 'q' et 's'.
Je vais rajouter les sphères englobantes et les aabb en visuel et un controle intuitif avec la souris des rectangles sans trop alourdir la source.

Commentaire de Arnaud16022 le 16/11/2006 11:47:33

trop dingue, t'as une façon de coder et de commente ta source, je me suis réellement demandé si c'était de moi :S

Quoi qu'il en soit :

stuct, c'est mal.
Utilise class.
Pour vérifier collision, fais un proto comme ça :
bool Crectangle::collide ( Crectangle & _rect );

D'ailleurs
Plutôt que de retourner un bool, tu devrais retourner une struct qui donne des infos sur la collision. Problème: on ne peut pas retourner 2 trucs en même temps, et le bool, c'est quand même bien pratique.

Perso je ferais ça :
bool Crectangle::collide ( Crectangle & _rect , CCollisionResults & _results = NULL);

comme ça, ça retourne un bool bien sympathique à l'usage.
Si l'utlisateur a besoin de plus de précision, il fera :
Rect1.Collision(Rect2, Resultats);
et aura des précisions dans Resultats.membres
Attention, faut pas écrire dans Resultats si c'est NULL,hein ^^

pis sinon manque quand même le cas ou l'un est dans l'autre.

Galmiza : ya des touches pour les faire bouger ;)

Commentaire de Arnaud16022 le 16/11/2006 11:48:42

heuuu la dernire remarque était pour ombitious , on s'est compris ^^

Commentaire de Galmiza le 16/11/2006 11:53:58

Pour gérer les mouvements ces rectangles c'est une autre paire de manche.

On peut faire de la simulation cinématique:
dès qu'on a contact, on inverse la vitesse de rotation du rectangle et on fait "rebondir" le vecteur vitesse du rectangle sur l'orthogonal à la normale au contact.
Il n'y a pas de notions d'efforts.

On peut faire de la simulation dynamique:
dès qu'on a contact, on applique l'effort résultant au rectangle.
On déduit l'accélération linéaire et angulaire que doit subit le rectangle (avec à son inertie et à sa masse) puis en intégrant deux fois on obtient sa position et son angle.
Pour intégrer il existe de nombreuses méthodes. Celles que je connais bien sont obsolètes (euler, euler modifié, runge kutta, ...). Pour ceux qui sont intéressés, la méthode actuellement employée par les moteurs physiques est celle des multiplicateurs de Lagrange, extrêmement puissante et accessible sans prise de tête pour des bac+2.

Commentaire de Galmiza le 16/11/2006 11:58:03

Oups post croisés ;)

Ok je passerais tout en C++ et ajouterais des classes pour le rapport de collision (regrouper contacts + normales aux contacts), ça sera plus facile de faire évoluer la source.
Il n'y a pas que les touches: maintenant on peut tout manipuler avec la souris: clique gauche ou clique droit sur rectangle + glisser.

Commentaire de Arnaud16022 le 16/11/2006 12:58:57

yop
sympa
par contre, tu vois, ca merdouille un peu dès que les rectangles sont un peu trop imbriqués les uns dans les autres.
Runge-Kutta est obsolète ?????!!!!!!?????
Vais aller me renseigner un peu sur ton Lagrange. BAC+2 j'y suis, mais j'ai quand même un doute sur la prise de tête hihi

Pour ta cinématique :
tu vas galérer.
Commence déjà par faire une classe pour que le client puisse avoir le plus d'infos possibles sur la collision.
et gère le cas ou l'un est dans l'autre, ici tu as subtilement évité le cas en mettant des dimension incompatibles ^^

Je ne mets pas de note avant que ça ne soit plus avancé, elle peut monter assez haut cette source ( et être utile à pas mal de monde ). Finalise la :)

Commentaire de Galmiza le 16/11/2006 16:59:35

En fait, la source était au départ une réponse à une question posée sur le forum :D.
Il se peut qu'aucun des points des rectangles ne soient à l'intérieur d'un autre rectangle alors qu'il y a collision, met les en croix par exemple ;).
Je vais modifier l'algo pour éviter ce problème.

Une petite question: GLUT monopolise 100% du proc, comment paramétrer GLUT pour éviter ce problème sans mettre de pause dans le code ?

En fait, je me suis planté à propos Lagrange :$, la technique des multiplicateurs de Lagrange permet d'obtenir équations matricielles à coups d'étude énergétique des systèmes d'objets, je ne me souviens plus trop mais elle permet d'éviter d'avoir à intégrer angles et positions.... à vérifier.
Bref, ce n'est pas une technique d'intégration comme je l'ai peut-etre laissé entendre.

Pas de soucis sur les performances et la suprématie :D de Runge-Kutta. Je ne sais pas s'il y a mieux actuellement (mieux = plus rapide ET moins gourmand ET plus précis).

Commentaire de Arnaud16022 le 16/11/2006 20:30:30

pour GLUT : pas de paramétrisation possible, ça se code. Mais tu t'en fous c'est pas le but ici.

Pour Runge-Kutta : ouff ^^

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Opengl : Collision Box [ par BARACOUDAS ] Bonjour à tous,Bravo pour ce site, sa fait plaisir de savoir qu'il existe des personnes pretes à aider les débutants comme moi...Voila mon soucis,j'ai Collision entre 2 rectangles [ par unrealgun ] Hi,Je débute le C++ et je programme sous windows avec la library Opengl, sans Glut.Voila mon probleme :je souhaite detecter une collision entre deux r Collision pixel perfect [ par UltimAKnighT ] Bonjour, Savez-vous où je pourrais trouver de la documentation là-dessus(en français de préférence) car j'ai eu beau chercher, les tutos sur lesquels Bibliothèque Collision [ par Ombitious_Developper ] Salut:Je suis en train de chercher une bibliothèque pour gérer les collisions (en 2D) de préference qu'elle soit multi-plateforme. Cherche ecole programmation (pur) [ par Booster ] Bonjour à tous, Alors voila tout est dans le titre je cherche une école de programmation (Pas école d'ingénieur car je pense que je vais m'ennuyer, je supprimer un rectangle déssiné [ par lafolle24320 ] Bonjour à tous , voici mon pb : en fait je dessine un rectangle avecRectangle( hdc, rectMove.left, rectMove.top, rectMove.right, rectMove.bottom );si algorithme génitique [ par rahma_bou22 ] je veut avoir si c'est possible l'algorithme de probléme de sac à dos probleme de collision casse brique en c [ par loizokitue ] bonjour a tous je fais un casse brique en C pour un projet que je dois rendre ... le probleme est que l'on a pas le droit aux librairy graphiques... j Formatage fscanf [ par xsybus ] bonjour, j'ai un probleme avec fscanf, il en prend pas en compte le formatage que je lui impose.j'ai un fichier repertoire.txt dans lequel j'ai: Moteur physique : détecter les collisions [ par noncommunique ] Bonjour !!Je suis en train de tenter de réaliser un moteur physique et j'ai le problème suivant : je ne sais pas comment faire pour détecter une évent


Nos sponsors


Sondage...

Comparez les prix

CalendriCode

Juin 2013
LMMJVSD
     12
3456789
10111213141516
17181920212223
24252627282930

Consulter la suite du CalendriCode

Photothèque

A découvrir



 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,466 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales