Petit test pour Papydall

Bon pour que notre Papydall s'ennuie, je propose un petit jeu qui lui ait particulièrement destiné mais bien sûr tout le monde peut jouer.

Le défit consiste à faire le programme permettant de détecter s'il y a collision entre 2 polygones en utilisant les 4 étapes ci dessous.

1. On récupère tous les axes séparateurs possibles pour les deux polygones. Pour les polygones, les axes sont les normales à chaque face des polygones. Il y a donc autant d'axes que de faces et il est super facile de calculer une normale a une face (géométrie euclidienne!)

2. On projette les points des deux polygones sur chaque axes (un produit scalaire suffit...) et on prend pour les deux polygones, les points extrêmes des projections sur l'axe.

3. Si le segment des points extrêmes du 1er polygone chevauche le segment du 2eme polygone, on dit que l'axe n'est pas séparateur (il est séparateur si les deux segments sont disjoints)

4. On dit que le polygone ne touche pas l'autre polygone s'il existe un axe pour lequel l'axe est séparateur. Si tous les axes ne sont pas séparateurs, les polygones se touchent!

C'est un défit de vacances qui ne se veut pas trop complexe mais suffisamment intéressant pour remplacer les mots fléchés de notre Papydall qu'il remplit certainement dans une chaise longue à l'ombre d'un grand arbre, un peu avan l'apéro ...

Bonjour Jicehel.
Bonjour tout le monde.

En ce moment je n’ai pas le cœur gai.
Ma femme est entrée à l’hôpital pour intervention chirurgicale et elle me manque terriblement.

Le problème que tu soulèves est certainement intéressant, mais suis-je assez compétant  pour le résoudre ?
Difficile de répondre sur le coup.
Je m’associe à toi pour inviter tous ceux qui veulent bien se pencher sur ce problème à proposer et échanger leurs idées et leurs trucs et astuces.

J’espère y participer …
A plus !

@Papydall:
Je suis passé par là, et je sais ce que c'est. Je suis de tout coeur avec toi et je t'envoie mes sincères souhaits de bon rétablissement pour ton épouse. Courage...

@ Jicehel,

Je suis en pleine digestion de ISAM et je vais essayer d' avaler la combinaison avec BDR.
Donc, ce n' est pas tout de suite pour moi.  

@ Papydall,

Je suis de tout coeur avec toi et, comme Klaus, je te souhaite un bon rétablissement pour ton épouse.

Mince désolé Papydall. Si j'avais su je ne t'aurais pas mis au défit. Mais comme tu te faisais un peu discret, j'ai voulu te titiller. Maintenant que je sais pourquoi, tu as certainement en effet mieux à faire. Tous mes vœux de bon rétablissement à ta femme et j'espère que tu retrouveras vite le morale avec son retour en pleine santé. S'il te plait dit lui le bonjour de la part de tous les Panoramiciens et fais toi le relais de nos vœux.

Je m'associe à tous pour souhaiter un prompt rétablissement à Mme Papydall.

A+

Bon rétablissement a ton épouse Papydall.

Ça va sans dire, mais ça va mieux en le disant: pareil papydall, et bon courage à toi.

Je m'associe aux autres Panoramiciens pour souhaiter un retour heureux de ta femme.

Je souhaite un bon rétablissement à ta compagne Papydall

Bonjour tout le monde.
Merci à vous tous.
Vos petits mots me font beaucoup de plaisir.
Ma femme a quitté l’hôpital. Elle va plutôt mieux.
Elle aura encore pour quelques jours et j’espère être plus actif sur le forum dans peu de temps.
C'est toujours un plaisir pour moi à vous lire.
A +

Quel soulagement ! Prends bien soin de ta femme !

Merci Klaus, je n'y manquerai pas.
Tu es très gentil.

@ Papydall,
Content que les nouvelles soient bonnes,
Prends bien soin de madame Papydall...
Avec tous mes vœux de rétablissement.

Merci Ygeronimi.
D’habitude, c’est elle   qui prend soin de moi

De temps en temps il faut inverser les rôles. Si tu en prends bien soin en plus avec un peu de chance elle te le rendra largement

@jicehel
je n'ai pas tout compris à ton défi; pourquoi ces 4 étapes? C'est pour de la 2D? C'est une méthode que tu as imaginé?

C'est la méthode qui est utilisé dans un algorithme de détection de collisions de polygones quelconques.
Il existe peut être d'autres solutions. Tu ferais autrement toi ?
Comme Papydall est costaud en maths, ça me semblait être un bon défit pour lui mais sinon j'adapterais le programme à moins que tu ais envie de t'y intéresser ?

Le code à convertir est celui ci:
Using the code
The PolygonCollision() function does all of the above, and returns a PolygonCollisionResult structure containing all the necessary information to handle the collision:
Hide Copy Code
// Structure that stores the results of the PolygonCollision function
public struct PolygonCollisionResult {
// Are the polygons going to intersect forward in time?
public bool WillIntersect;
// Are the polygons currently intersecting?
public bool Intersect;
// The translation to apply to the first polygon to push the polygons apart.
public Vector MinimumTranslationVector;
}
Two helper functions are used by the PolygonCollision function. The first one is used to project a polygon onto an axis:
Hide Copy Code
// Calculate the projection of a polygon on an axis
// and returns it as a [min, max] interval
public void ProjectPolygon(Vector axis, Polygon polygon,
ref float min, ref float max) {
// To project a point on an axis use the dot product
float dotProduct = axis.DotProduct(polygon.Points[0]);
min = dotProduct;
max = dotProduct;
for (int i = 0; i < polygon.Points.Count; i++) {
dotProduct = polygon.Points[i].DotProduct(axis);
if (d < min) {
min = dotProduct;
} else {
if (dotProduct> max) {
max = dotProduct;
}
}
}
}
The second one returns the signed distance between two given projections:
Hide Copy Code
// Calculate the distance between [minA, maxA] and [minB, maxB]
// The distance will be negative if the intervals overlap
public float IntervalDistance(float minA, float maxA, float minB, float maxB) {
if (minA < minB) {
return minB - maxA;
} else {
return minA - maxB;
}
}
Finally, here is the main function:
Hide Shrink Copy Code
// Check if polygon A is going to collide with polygon B.
// The last parameter is the *relative* velocity
// of the polygons (i.e. velocityA - velocityB)
public PolygonCollisionResult PolygonCollision(Polygon polygonA,
Polygon polygonB, Vector velocity) {
PolygonCollisionResult result = new PolygonCollisionResult();
result.Intersect = true;
result.WillIntersect = true;

int edgeCountA = polygonA.Edges.Count;
int edgeCountB = polygonB.Edges.Count;
float minIntervalDistance = float.PositiveInfinity;
Vector translationAxis = new Vector();
Vector edge;

// Loop through all the edges of both polygons
for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
if (edgeIndex < edgeCountA) {
edge = polygonA.Edges[edgeIndex];
} else {
edge = polygonB.Edges[edgeIndex - edgeCountA];
}

// ===== 1. Find if the polygons are currently intersecting =====

// Find the axis perpendicular to the current edge
Vector axis = new Vector(-edge.Y, edge.X);
axis.Normalize();

// Find the projection of the polygon on the current axis
float minA = 0; float minB = 0; float maxA = 0; float maxB = 0;
ProjectPolygon(axis, polygonA, ref minA, ref maxA);
ProjectPolygon(axis, polygonB, ref minB, ref maxB);

// Check if the polygon projections are currentlty intersecting
if (IntervalDistance(minA, maxA, minB, maxB) > 0)\
result.Intersect = false;

// ===== 2. Now find if the polygons *will* intersect =====

// Project the velocity on the current axis
float velocityProjection = axis.DotProduct(velocity);

// Get the projection of polygon A during the movement
if (velocityProjection < 0) {
minA += velocityProjection;
} else {
maxA += velocityProjection;
}

// Do the same test as above for the new projection
float intervalDistance = IntervalDistance(minA, maxA, minB, maxB);
if (intervalDistance > 0) result.WillIntersect = false;

// If the polygons are not intersecting and won't intersect, exit the loop
if (!result.Intersect && !result.WillIntersect) break;

// Check if the current interval distance is the minimum one. If so store
// the interval distance and the current distance.
// This will be used to calculate the minimum translation vector
intervalDistance = Math.Abs(intervalDistance);
if (intervalDistance < minIntervalDistance) {
minIntervalDistance = intervalDistance;
translationAxis = axis;

Vector d = polygonA.Center - polygonB.Center;
if (d.DotProduct(translationAxis) < 0)
translationAxis = -translationAxis;
}
}

// The minimum translation vector
// can be used to push the polygons appart.
if (result.WillIntersect)
result.MinimumTranslationVector =
translationAxis * minIntervalDistance;

return result;
}
The function can be used this way:
Hide Copy Code
Vector polygonATranslation = new Vector();

PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);

if (r.WillIntersect) {
// Move the polygon by its velocity, then move
// the polygons appart using the Minimum Translation Vector
polygonATranslation = velocity + r.MinimumTranslationVector;
} else {
// Just move the polygon by its velocity
polygonATranslation = velocity;
}

polygonA.Offset(polygonATranslation);

En quoi ça peux servir de savoir faire ça en panoramic, pour quel genre de programme? En 2D, panoramic sait détecter les collisions entre sprites, donc je vois pas...

Panoramic ne sait pas détecter la collision entre sprite. C'est à toi de le coder.
On peut facilement le faire pour des formes rectangulaire, ou sphérique (voir articles précédents)
Pour 2 polygones quelconques c'est le cas le plus difficile.

Imaginons que tu veuilles par exemple tester la collision entre 2 polygones complexes pour voir si 2 gros astéroides rentrent en collision.

Ca pourrait même servir pour savoir si des pièces de Tetris se touchent même si dans ce cas là, l'utilisation d'une matrice est plus simple.

En fait c'est le dernier cas des détections de collision de formes pour l'article

A propos de Papydall, Quelqu'un a des nouvelles ?

Il n'est pas passé sur le forum depuis vendredi matin...