Discussion :

[mok_tun]

Bonjour à tous,
Svp j'ai un exercice à résoudre concernant la détection des objets dans un triangle en 2D.
La figure ci-dessous explique mon problème. Il s'agit de détecter des objets, dans cet exemple des carrées.
En fait, il y a différents cas pour résoudre le problème:
-Un carré noir : je le détect pas.
-Un carré rouge : je le détecte en entier.
-Un carré vert : je le détecte partiellement (aussi je dois récupérer la parite détéctée).
Comme données, j'ai l'angle et la hauteur (distance) de ce triangle.
Des suggestions svp ?
Merci

[Kannagi]

Pour ma part il faut faire plusieurs test:
4 test avec les points (s'ils sont dans le triangle ou non).
4 autre test segment /triangle (ou 3x segment/segment) (si 2 segment se croise alors collision).

Bien sur si un seul est vrai , inutile de tester les autres .
Le test avec les points étant le plus rapide (et sûrement le cas le plus courant) c'est celui que tu devrait tester en premier

[guitz]

Par soucis de performance, un premier test permet d'écarter des candidats à un coût algorithmique très faible :

si le carré n'est pas dans le rectangle englobant du triangle, alors il est impossible qu'il soit dans le triangle.

Si ça renvoie true alors tu lances l'algo suggéré par Kannagi

[Obsidian]

Hello,

Bonjour à tous,
Svp j'ai un exercice à résoudre concernant la détection des objets dans un triangle en 2D.
La figure ci-dessous explique mon problème. Il s'agit de détecter des objets, dans cet exemple des carrées.

Tant que ce ne sont que des carrés et qu'ils ont tous la même taille, ça ne pose pas trop de problème. Si tu dois en revanche, à terme, être capable de « voir » n'importe quel polygone en 2D (fussent-ils éventuellement extrudés verticalement, ce qui est le principe de DOOM et DOOM II, dans les années 1990), alors tu auras déjà des difficultés s'ils sont concaves par endroits. Le plus simple consistant alors à les découper en plusieurs polygones strictement connexes : BSP.

Ensuite, beaucoup des techniques exposées ci-dessus te feront gagner beaucoup de temps mais aucune d'elle n'est parfaite en l'état. Il se peut très bien que le centre de gravité de ta figure soit en dehors du triangle mais que les parties extérieures du polygone « mordent » dessus quand même. Il se peut également que tous les sommets soient en dehors du triangle mais que les côtés traversent quand même un coin de celui-ci. Une bonne approche, assez rapide, consiste alors à détecter une intersection entre un segment de ton polygone et chacun des trois segments de ton triangle.

Avec cela, tu seras capable de détecter les polygones qui « franchissent la frontière » mais pas ceux qui sont déjà entièrement dedans. Pour cela, le plus simple est de vérifier si au moins un des sommets est à l'intérieur du triangle, chose qui peut s'optimiser grandement au vu de la forme de la disposition du triangle. Il suffit de vérifier si le sommet est au dessus du point le plus bas du triangle mais dans la limite d'une hauteur h (donc en faisant une simple soustraction et en vérifiant si le résultat est compris entre 0 et h), puis de vérifier si son abscisse est sur l'axe, avec une tolérance proportionnelle à la hauteur (avec une simple règle de trois).

Ces deux approches combinées te permettront de détecter tes polygones mais, surtout si tu dois ensuite estimer la surface intrusive, tout le problème se rapporte en fait à vérifier si l'intersection de tes deux surfaces (dans le sens ensembliste du terme : ∩) est non-vide. Dans ce cas, tu serais peut-être intéressé par faire directement de la CSG.

[guitz]

Bonjour à tous,
En fait, il y a différents cas pour résoudre le problème:
-Un carré noir : je le détect pas.
-Un carré rouge : je le détecte en entier.
-Un carré vert : je le détecte partiellement (aussi je dois récupérer la parite détéctée).

Bonjour,

Pour te répondre en prenant plus le temps :

Soient C ton carré et T ton triangle. Soit la fonction EvaluerCarreDansTriangle qu'on nomme ECDT, qui renvoie un booléen, et Un tableau P de points (ceus qui sont dans T).

Algo :

1/ Si aucun points de C sont dans le rectangle englobant de T, ECDT renvoie false. Cout très faible pour éliminer facilement des candidats
2/ Sinon, boucler sur tous les points pi de C et calculer s'ils sont présents dans T, si oui: ajouter pi dans dans P, et en fin de boucle renvoyer true et P

Pour calculer si un point est présent dans un polygône :

https://jeux.developpez.com/tutoriel...omplexes/#LIII

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
bool Collision(Point tab[],int nbp,Point P)
{
  int i;
  for(i=0;i<nbp;i++)
  {
     Point A = tab[i];
     Point B;
     if (i==nbp-1)  // si c'est le dernier point, on relie au premier
         B = tab[0];
     else           // sinon on relie au suivant.
         B = tab[i+1];
     Vecteur D,T;
     D.x = B.x - A.x;
     D.y = B.y - A.y;
     T.x = P.x - A.x;
     T.y = P.y - A.y;
     float d = D.x*T.y - D.y*T.x;
     if (d<0)
        return false;  // un point à droite et on arrête tout.
  }
  return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
}

[Kannagi]

@guitz
Le test avec seulement des points n'est pas exhaustive.
Il se peut qu'il y est des collisions avec un triangle sans que aucun point ne se trouve dans a l'intérieur du triangle.
(D'ou qu'il faut rajouter des collision segment/segment en plus ).

[guitz]

Exact

[Astraya]

Bonjour,

Je vais couper court au débat sur comment faire le test ^^

Le seul test valable et performant est le test Cone2D ( Triangle ) avec 4 segments ( Carré ).
Les coordonnées de ton Triangle sont polaire il faut donc que tu en déduise les 3 points de ton triangle pour le test de collision.
De plus tu dois non seulement trouver si collision il y a mais aussi ou les collisions ont lieux ( Il s'agit donc de trouver les points d'intersections entre les 4 segments de tes carrés avec le triangle )

Il existe des librairies qui font très bien cela et je te conseille fortement de t’en inspirée et surtout de comprendre les mathématique derrière cela.
GeomtricTools est une excellente source de savoir de ce coté la ==> https://www.geometrictools.com/Source/Mathematics.html


Pour la suite de l'explication je te conseille de prendre papier et crayon:

De son coté, il part du principe simple:
- Ton carré n'est que 4 segments.
- Si un segment intersecte le triangle il y a collision.
- Si la droite ( ton segment infini ) ne collisionne pas ton triangle tu n'as pas de collision de segment a tester.

Donc il faut que tu fasse dans l'ordre:
1- La collision d'une droite avec un triangle ( récupéré le 2 points max de collision )
2- Tu utilises cet algorithme pour faire le second test ( très rapide ) du segment qui se base sur ta droite.
- Si les points de collision de ta droite sont sur ton segment, le segment collision et le point d'intersection est celui de la droite également.
- Si les points de collision de ta droite ne sont pas sur ton segment ( 0 collision )

Une optimisation importante est de ne pas représenter ton segment comme 2 points. mais comme un point au centre de ton segment, une direction ( Vecteur unitaire ) et une distance ( Extent ).
Une autre est de représenter ta droite comme un point et une direction ( Tu devineras que le point de la droite est le centre de ton segment, que la direction de ta droite est la direction de ton segment ). L'Extent de ton segment n'est quand a lui plus que la distance absolue du point de ta droite/segment.

Le test de la droite ne te donneras pas les points d'intersection directement mais la distance entre le point de ta droite et le point d'intersection.
Le test du segment utilisera la distance donné par le test de la droite en comparant à son Extent. Donc si (Distance Absolue Intersection Droite <= Extent) == Intersection!
Et le point n'est autre que (Point Segment)*Direction*(Distance Intersection Droite). Et ce pour les 2 distances du test de la droite.

Ce test est extrêmement simple mais à un défaut. il te donnera aucune intersection si le triangle est entièrement dans le carré.
Pour palier à ce problème, tu peux prendre un autre test qui est le test d'une OBB2D avec 3 segments (triangle) et le test se trouve ici ( https://www.geometrictools.com/GTEng...OrientedBox2.h )

Pour info les TIQuery sont les Test Intersection Query et les FIQuery sont les Find Intersection Query ( le premier test juste, le 2nd trouve les points d'intersections )

[guitz]

Bonjour,

Pour mon projet j'ai implémenté en c++ l'algorithme issu du Separating Axis Theorem (SAT).

Cet algo permet de tester la collision entre 2 polygones quelconques convexes.

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
61
62
float AInfrastructureGraphManager::ScalarProjection(FVector v1, FVector v2) { //DotProduct()
 
	float Ang = AngleBetweenVectors(v1, v2);
 
	return v1.Size() * FMath::Cos(Ang);
 
}
 
bool AInfrastructureGraphManager::PolygonesAreColliding(TArray<FVector> Polygone1, TArray<FVector> Polygone2) { //Teste collision entre 2 polygones convexes quelconques
 
	TArray<FVector> l_EveryAxis;
	TArray<float> l_Poly1Projs, l_Poly2Projs; //Stocke les projections respectives des 2 polygones sur chaque axe
	float l_minPoly1Proj, l_maxPoly1Proj, l_minPoly2Proj, l_maxPoly2Proj; 
	FVector l_Axis;
 
	for (int32 i = 0; i < Polygone1.Num(); i++){
 
		l_Axis = Polygone1[(i + 1) % Polygone1.Num()] - Polygone1[i];
		l_Axis = FVector(-l_Axis.Y, l_Axis.X, 0.f);
		l_Axis.Normalize();
 
		l_EveryAxis.Add(l_Axis);
	}
 
	for (int32 i = 0; i < Polygone2.Num(); i++) {
 
		l_Axis = Polygone2[(i + 1) % Polygone2.Num()] - Polygone2[i];
		l_Axis = FVector(-l_Axis.Y, l_Axis.X, 0.f);
		l_Axis.Normalize();
 
		l_EveryAxis.Add(l_Axis);
 
	}
 
	for (int32 i = 0; i < l_EveryAxis.Num(); i++) {
 
		for (int32 j = 0; j < Polygone1.Num(); j++) {
			l_Poly1Projs.Add(ScalarProjection(Polygone1[j], l_EveryAxis[i]));
		}
 
		for (int32 j = 0; j < Polygone2.Num(); j++) {
			l_Poly2Projs.Add(ScalarProjection(Polygone2[j], l_EveryAxis[i]));
		}
 
		l_minPoly1Proj = FMath::Min<float>(l_Poly1Projs);
		l_maxPoly1Proj = FMath::Max<float>(l_Poly1Projs);
		l_minPoly2Proj = FMath::Min<float>(l_Poly2Projs);
		l_maxPoly2Proj = FMath::Max<float>(l_Poly2Projs);
 
		//UE_LOG(LogTemp, Warning, TEXT("MAX projetés de poly1 : %f"), l_maxPoly1Proj);
 
		if (l_maxPoly1Proj < l_minPoly2Proj || l_maxPoly2Proj < l_minPoly1Proj) {
			return false;
		}
 
		l_Poly1Projs.Empty();
		l_Poly2Projs.Empty();
 
	}
 
	return true;
 }

En esperant que ce ça puisse servir à la communauté..