Share
Dans mon précédent tutoriel sur la détection de collision entre un cercle et une ligne, je couvrais la projection sur une ligne à l'aide du produit scalaire d'un vecteur. Dans ce tutoriel, nous examinerons le produit scalaire perpendiculaire et nous en servirons pour prédire le point d'intersection de deux lignes..
Jetons un coup d'œil au résultat final sur lequel nous allons travailler. Utilisez les touches fléchées gauche et droite pour diriger le navire (triangle), puis appuyez vers le haut pour augmenter la vitesse temporairement. Si le point de collision futur projeté est sur le mur (la ligne), un point rouge sera peint dessus. Pour une collision qui "est déjà" survenue (c’est-à-dire qui aurait eu lieu dans le passé, selon la direction actuelle), un point rouge sera toujours peint mais légèrement transparent..
Vous pouvez également cliquer sur la souris et faire glisser les points noirs pour déplacer le mur. Notez que nous ne prédisons pas seulement l'emplacement de la collision, mais aussi le temps.
Avant d’entrer dans le sujet, faisons quelques révisions. Voici l'équation du produit scalaire (précédemment couvert ici):
Et voici la définition du produit par points perpendiculaires extraite de Wolfram:
Maintenant, pour nous aider à former une image mentale, j'ai préparé l'image ci-dessous. Je suis persuadé que vous êtes maintenant en mesure de dériver les composantes verticales et horizontales d'un vecteur. Les composantes impliquant le sinus et le cosinus ne devraient donc pas poser de problème..
Remplaçons les deux composants par leur équivalent. J'ai utilisé A avec un chapeau pour représenter le vecteur unitaire de A (c’est-à-dire un vecteur qui pointe dans la même direction que A, mais a une magnitude d’exactement 1). Un autre détail est que la perpendiculaire de B est en fait la normale de B - plus sur les normales, étape suivante.
Le diagramme ci-dessus montre que la projection de B sur A produira | B | * cos (thêta). Mais pourquoi la projection de la production normale de B | B | * sin (thêta)?
Pour mieux comprendre cela, j'ai inclus une démo Flash ci-dessous. Cliquez et faites glisser la pointe de flèche noire. En le déplaçant doucement, vous remarquerez que son axe perpendiculaire suit également. À leur tour, les lignes rouges audacieuses seront également animées. Notez que ces deux longueurs sont identiques - d’où l’équation du produit ponctuel perpendiculaire.
Les normales, par définition, reposent sur une ligne perpendiculaire coupant votre ligne d’intérêt. Essayons d'imaginer ces lignes sur un plan géométrique.
Le système de coordonnées cartésien est utilisé dans le diagramme ci-dessus. B est la normale à gauche et C est la normale à droite. On voit que la composante x de B est négative (car elle pointe vers la gauche) et la composante y de C est négative (car elle pointe vers le bas).
Mais vérifiez les similitudes entre B et C. Leurs composants x et y sont les mêmes que ceux de A, à l'exception de swizzled. La différence n'est que la position du signe. Nous arrivons donc à une conclusion par l'image ci-dessous.
Notez que nous nous référons spécifiquement à la cartésien système de coordonnées dans cet exemple. L'axe des y de l'espace de coordonnées de Flash est le reflet de celui en cartésien, ce qui entraîne un échange entre la normale gauche et la normale.
Pour déterminer le point de collision du vecteur k sur le plan A, nous allons relier les queue de k avec un point arbitraire sur le plan A premier. Pour le cas ci-dessous, le vecteur j est le vecteur de liaison; alors nous obtenons la projection perpendiculaire de k et j sur le plan A.
Le point rouge sur l'image ci-dessous est le point de collision. Et j'espère que vous pouvez voir le triangle similaire dans le diagramme ci-dessous.
Donc, étant donné les trois composantes ci-dessus, nous pouvons utiliser le concept de ratio pour déduire la longueur entre les points rouge et bleu. Enfin, nous définissons la magnitude du vecteur k à ladite longueur et nous avons notre point de collision!
Alors, voici l'implémentation ActionScript. J'ai inclus une démo ci-dessous. Essayez de déplacer les pointes de flèche afin que les deux lignes se croisent. Un petit point noir marquera le point d'intersection des lignes. Notez que ces segments ne se croisent pas nécessairement, mais les lignes infinies qu’ils représentent sont.
Voici le script qui fait les calculs. Check-out Basic.as dans le téléchargement source pour le script complet.
recalcul de fonctions privées (): void reorient (); / * Expliquer: * v1 et v2 sont des vecteurs représentant les deux segments de ligne * v1 joint set1b (queue) à set1a (tête) - analogue au vecteur k du diagramme * v2 joint set2b (queue) à set2a (tête) * àV2b est un vecteur analogue à celui du vecteur j du diagramme * / var perp1: Number = v1.perpProduct (v2.normalise ()); var toV2b: Vector2D = new Vector2D (set2b.x - set1b.x, set2b.y - set1b.y); var perp2: Number = toV2b.perpProduct (v2.normalise ()); / * Expliquer: * la longueur est calculée à partir du même ratio de triangles * elle est utilisée plus tard comme magnitude pour un vecteur * qui pointe dans la direction de v1 * / var longueur: Number = perp2 / perp1 * v1.getMagnitude (); var longueur_v1: Vector2D = v1.clone (); longueur_v1.setMagnitude (longueur); / * Explain * étend pour localiser l'emplacement exact du point de collision * / intersec.x = set1b.x + length_v1.x; intersec.y = set1b.y + length_v1.y;
J'espère donc que la première approche que j'ai présentée a été facilement comprise. Je comprends que la performance pour obtenir le point d'intersection est importante, alors je vais maintenant proposer des approches alternatives, bien que cela nécessite quelques révisions mathématiques. Supporter avec moi!
Parlons d’abord des équations linéaires. Il existe plusieurs formes d’équation de ligne, mais nous en toucherons simplement deux dans ce tutoriel:
J'ai inclus l'image ci-dessous pour vous aider à vous rappeler. Les personnes intéressées peuvent se référer à cette entrée sur Wikipedia.
Avant de procéder à des manipulations sur des équations à deux lignes, nous devons d’abord en déduire ces équations. Considérons le scénario où l'on nous donne les coordonnées de deux points p1 (a, b). et p2 (c, d). Nous pouvons former une équation de ligne reliant ces deux points à partir des gradients:
Ensuite, en utilisant cette équation, nous pouvons dériver les constantes A, B et C pour la forme standard:
Ensuite, nous pouvons procéder à la résolution d'équations de ligne simultanées.
Maintenant que nous pouvons former des équations de ligne, prenons deux équations de ligne et les résolvons simultanément. Étant donné ces deux équations de ligne:
Je vais déposer ces coefficients selon la forme générale Ax + By = C.
| UNE | B | C |
| E | F | g |
| P | Q | R |
Pour obtenir la valeur de y, nous procédons comme suit:
| UNE | B | C | Multiplier par |
| E | F | g | P |
| P | Q | R | E |
Et nous arrivons à la table suivante.
| UNE | B | C |
| EP | FP | GP |
| PE | QE | RÉ |
Après avoir soustrait deux équations, on arrive à:
Passons à l'obtention de x:
| UNE | B | C | Multiplier par |
| E | F | g | Q |
| P | Q | R | F |
Nous arrivons à la table suivante
| UNE | B | C |
| EQ | FQ | GQ |
| PF | QF | Rf |
Après avoir soustrait les deux équations, on arrive à:
Réorganisons encore y.
Nous arrivons donc au point d'intersection de x et y. Nous remarquons qu'ils partagent le même dénominateur.
Maintenant que nous avons mis au point les opérations mathématiques et obtenu le résultat, il suffit d'inscrire des valeurs et nous avons le point d'intersection..
Voici l'implémentation Actionscript. Ainsi, toutes les opérations vectorielles sont réduites à une simple arithmétique, mais cela nécessitera quelques travaux d'algèbre au début.
recalcul de fonctions privées (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Nombre = set2b.y - set2a.y; var Q: nombre = set2a.x - set2b.x; var R: Nombre = set2a.x * set2b.y - set2a.y * set2b.x; Dénominateur var: Nombre = (E * Q - P * F); intersec.x = (G * Q - R * F) / dénominateur; intersec.y = (R * E - G * P) / dénominateur;
Bien sûr, c’est le même résultat que la démo précédente, mais avec moins de maths et sans utilisation de la Vector2D classe.
Une autre solution pour résoudre ce problème consiste à utiliser les mathématiques matricielles. Encore une fois, j'invite les lecteurs intéressés à se plonger dans la conférence du professeur Wildberger sur les équations des lignes. Ici, nous allons simplement parcourir le concept rapidement.
Selon le Prof. Wildberger, nous pouvons adopter deux cadres:
Passons d'abord au cartésien. Regardez l'image ci-dessous.
Notez que les matrices T et S contiennent des valeurs constantes. Ce qui reste inconnu est A. Alors, réorganiser l'équation de la matrice en fonction de A nous donnera le résultat. Cependant, nous devons obtenir la matrice inverse de T.
Voici l'implémentation de ce qui précède avec ActionScript:
recalcul de fonctions privées (): void reorient (); var E: Number = set1b.y - set1a.y; var F: Number = set1a.x - set1b.x; var G: Number = set1a.x * set1b.y - set1a.y * set1b.x; var P: Nombre = set2b.y - set2a.y; var Q: nombre = set2a.x - set2b.x; var R: Nombre = set2a.x * set2b.y - set2a.y * set2b.x; var T: matrice = nouvelle matrice (E, P, F, Q); T.invert (); var S: Matrix = new Matrix (); S.a = G; S.b = R; S.concat (T); // multipliant la matrice intersec.x = S.a; intersec.y = S.b;
Enfin, il y a la forme paramétrique de l'équation de la droite, et nous allons essayer de la résoudre à nouveau à l'aide de la matrice mathématique.
Nous aimerions avoir le point d'intersection. Compte tenu de toutes les informations sauf pour vous et v que nous essayons de trouver, nous allons réécrire les équations sous forme matricielle et les résoudre.
Encore une fois, nous effectuons des manipulations matricielles pour arriver à notre résultat.
Alors, voici l'implémentation du formulaire matriciel:
recalcul de la fonction rivate (): void reorient (); / * Expliquez: * r, s font en réalité référence aux composants de v2 normalisés * p, q font en réalité référence aux composants de v1 normalisés * / var norm_v2: Vector2D = v2.normalise (); var norm_v1: Vector2D = v1.normalise (); var a_c: Number = set1b.x - set2b.x; var b_d: Number = set1b.y - set2b.y; var R: Matrix = new Matrix; R.a = norm_v2.x; R.c = norm_v1.x; R.b = norm_v2.y; R.d = norm_v1.y; R.invert (); var L: Matrix = new Matrix; L.a = a_c; L.b = b_d; L.concat (R); intersec.x = set2b.x + L.a * norm_v2.x; intersec.y = set2b.y + L.a * norm_v2.y;
Nous avons couvert quatre approches pour résoudre ce petit problème. Alors qu'en est-il de la performance? Eh bien, je pense que je laisserai ce problème aux lecteurs de juger, même si j'estime que la différence est négligeable. N'hésitez pas à utiliser ce harnais de test de performance de Grant Skinner.
Alors maintenant que nous avons cette compréhension, quelle est la prochaine étape? L'appliquer!
Supposons qu'une particule se déplace sur un chemin obligé d'entrer en collision avec un mur. Nous pouvons calculer le délai d’impact par la simple équation de:
Vitesse = Déplacement / Temps
Imaginez que vous êtes à l'intérieur de cette particule ronde orange et que, pour chaque image qui passe, une annonce est faite au moment de la collision avec le mur. Vous entendrez:
"Délai avant impact: 1,5 images" - image 1
"Délai avant impact: 0,5 image" - image 2
"Délai avant impact: -0,5 images" - image 3
Lorsque nous atteignons l’image 3, la collision avec la ligne s’est déjà produite (comme indiqué par le signe négatif). Vous devez rembobiner le temps pour atteindre le point de collision. Évidemment, une collision devrait se produire quelque temps entre les images 2 et 3, mais Flash se déplace par incréments d'une image. Donc, si la collision a eu lieu à mi-chemin entre les images, un basculement du signe en négatif indique que la collision a déjà eu lieu.
Pour obtenir un temps négatif, nous allons utiliser le produit vectoriel à points. Nous savons que lorsque nous avons deux vecteurs et que la direction de l'un n'est pas à moins de 90 degrés de l'autre côté, ils produiront un produit de points négatif. En outre, le produit scalaire est une mesure de la façon dont deux vecteurs sont parallèles. Ainsi, lorsque la collision est déjà survenue, la vitesse et la direction d'un vecteur vers un point du mur seront négatives - et inversement.
Alors, voici le script (inclus dans CollisionTime.as). J'ai également ajouté la détection de collision dans le segment de ligne. Pour ceux qui ne le connaissent pas, référez-vous à mon tutoriel sur la détection de collision entre un cercle et un segment de ligne, étape 6. Et pour obtenir de l'aide sur le pilotage des navires, voici une autre référence.
Accentsconagua
// décider si dans le segment de mur var w2_collision: Vector2D = new Vector2D (collision.x - w2.x, collision.y - w2.y); collision.alpha = 0; // lorsque le navire se dirige vers la gauche du mur if (w2_collision.dotProduct (v1) < 0) t.text = "Ship is heading to left of wall"; else //when ship is heading to right of wall if (w2_collision.getMagnitude() > v1.getMagnitude ()) t.text = "Le navire se dirige vers la droite du mur" // lorsque le navire se dirige vers le segment du mur else var navire_collision: Vector2D = nouveau Vector2D (collision.x - ship.x, collision. y - ship.y); var déplacement: Nombre = ship_collision.getMagnitude (); if (ship_collision.dotProduct (velo) < 0) displacement *= -1; //showing text var time:Number = displacement / velo.getMagnitude(); t.text = "Frames to impact: " + time.toPrecision(3) + " frames.\n"; time /= stage.frameRate; t.appendText("Time to impact: " + time.toPrecision(3) + " seconds.\n"); //drop down alpha if collision had happened if (displacement > 0) collision.alpha = 1; else collision.alpha = 0,5; t.appendText ("La collision était déjà arrivée.") Alors, voici une démo de ce que vous allez arriver. Utilisez les touches fléchées gauche et droite pour diriger le navire (triangle), puis appuyez sur Haut pour augmenter la vitesse temporairement. Si le futur point de collision prévu se trouve sur le mur (la ligne), un point rouge sera peint dessus. Pour les collisions "déjà" passées, un point rouge sera toujours peint mais légèrement transparent. Vous pouvez également faire glisser les points noirs de chaque côté du mur pour le déplacer..
J'espère donc que ce tutoriel a été instructif. Partagez si vous avez réellement appliqué cette idée ailleurs que celle que j'ai mentionnée. Je prépare un bref compte-rendu sur son utilisation pour peindre des cibles au laser - qu'en pensez-vous? Merci de votre lecture et laissez-moi savoir s'il y a des erreurs.
