Share
Le théorème de séparation des axes est souvent utilisé pour vérifier les collisions entre deux polygones simples ou entre un polygone et un cercle. Comme avec tous les algorithmes, il a ses forces et ses faiblesses. Dans ce tutoriel, nous allons passer en revue le calcul derrière le théorème et montrer comment il peut être utilisé dans le développement de jeux avec des exemples de code et des démos..
Remarque: Bien que les démos et le code source de ce didacticiel utilisent Flash et AS3, vous devriez pouvoir utiliser les mêmes techniques et concepts dans presque tous les environnements de développement de jeux..
Le théorème de séparation des axes (SAT en abrégé) indique essentiellement que si vous pouvez tracer une ligne pour séparer deux polygones, ils ne se heurtent pas. C'est si simple.
Dans le diagramme ci-dessus, vous pouvez facilement voir les collisions se produisant dans la deuxième ligne. Quoi que vous essayiez de faire avec une ligne entre les formes, vous échouerez. La première rangée est exactement le contraire. Vous pouvez facilement tracer une ligne pour séparer les formes - et pas seulement une ligne, mais plusieurs d'entre elles:
Ok, n'exagérons pas cela; Je pense que vous comprenez l'idée. L'argument clé ici est que si vous pouvez tracer une telle ligne, il doit y avoir un espace séparant les formes. Alors, comment vérifions-nous cela??
Supposons pour l'instant que les polygones auxquels nous nous référons sont des carrés: box1 à gauche et box2 sur la droite. Il est facile de voir que ces carrés sont séparés horizontalement. Une méthode simple pour le déterminer dans le code consiste à calculer la distance horizontale entre les deux carrés, puis à soustraire les demi-largeurs de box1 et box2:
Accentsconagua
// Pseudo-code pour évaluer la séparation de box1 et box2 var length: Number = box2.x - box1.x; var half_width_box1: Number = box1.width * 0.5; var half_width_box2: Number = box2.width * 0.5; var gap_between_boxes: Number = length - half_width_box1 - half_width_box2; if (gap_between_boxes> 0) trace ("il y a un grand espace entre les cases") sinon if (gap_between_boxes == 0) trace ("les cases se touchent") sinon if (gap_between_boxes < 0) trace("Boxes are penetrating each other") Et si les boîtes ne sont pas bien orientées?
Bien que l’évaluation de l’écart reste la même, il faudra penser à une autre approche pour calculer la longueur entre les centres et les demi-largeurs - cette fois le long du P axe. C'est là que les mathématiques vectorielles sont utiles. Nous projeterons les vecteurs A et B le long de P pour obtenir les demi-largeurs.
Faisons une révision des mathématiques.
Nous allons commencer par récapituler la définition du produit scalaire entre deux vecteurs UNE et B:
Nous pouvons définir le produit scalaire en utilisant uniquement les composants des deux vecteurs:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
(A_x) (B_x) + (A_y) (B_y)
\]
Alternativement, nous pouvons comprendre le produit scalaire en utilisant les grandeurs des vecteurs et l'angle entre eux:
\ [
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix B_x \\ B_y \ end bmatrix =
A_ magnitude * B_ magnitude * cos (thêta)
\]
Maintenant, essayons de comprendre le projection de vecteur UNE sur P.
En vous référant au diagramme ci-dessus, nous savons que la valeur de projection est \ (A_ magnitude * cos (thêta) \) (où thêta est l'angle entre A et P). Bien que nous puissions aller de l'avant et calculer cet angle pour obtenir la projection, c'est délicat. Nous avons besoin d'une approche plus directe:
\ [
A. P = A_ magnitude * P_ magnitude * cos (thêta) \\
A. \ frac P P_ magnitude = A_ magnitude * cos (thêta) \\
\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitude * cos (thêta)
\]
Notez que \ (\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix \) est en fait le vecteur unitaire de P.
Maintenant, au lieu d'utiliser le côté droit de l'équation, comme nous étions, nous pouvons opter pour le côté gauche et toujours arriver au même résultat.
Avant de poursuivre, j'aimerais clarifier la convention de dénomination utilisée pour désigner les quatre coins des deux cases. Cela sera reflété dans le code plus tard:
Notre scénario est comme ci-dessous:
Disons que les deux cases sont orientées à 45 ° de l'axe horizontal. Nous devons calculer les longueurs suivantes afin de déterminer l’écart entre les cases.
Prenez note des instructions des flèches. Alors que la projection de A et C sur P donnera une valeur positive, la projection de B sur P produira en réalité une négatif valeur car les vecteurs pointent dans des directions opposées. Ceci est couvert dans la ligne 98 de l'implémentation AS3 ci-dessous:
var dot10: Point = box1.getDot (0); var dot11: Point = box1.getDot (1); var dot20: Point = box2.getDot (0); var dot24: Point = box2.getDot (4); // Calculs réels de l'axe var: Vector2d = new Vector2d (1, -1) .unitVector; var C: Vector2d = nouveau Vector2d (dot20.x - dot10.x, dot20.y - dot10.y) var A: vector2d = nouveau Vector2d (dot11.x - dot10.x, dot11.y - dot10.y) var B : Vector2d = new Vector2d (dot24.x - dot20.x, dot24.y - dot20.y) var projC: nombre = C.dotProduct (axe) var projA: nombre = A.dotProduct (axe); var projB: Number = B.dotProduct (axe); var gap: Nombre = projC - projA + projB; // projB devrait être une valeur négative si (écart> 0) t.text = "Il y a un espace entre les deux cases" sinon si (écart> 0) t.text = "Les cases se touchent" sinon t.text = "La pénétration avait eu lieu."
Voici une démonstration utilisant le code ci-dessus. Cliquez et faites glisser le point central rouge des deux cases pour afficher les commentaires interactifs..
Pour la source complète, consultez DemoSAT1.as dans le téléchargement source.
Eh bien, nous pouvons aller avec la mise en œuvre ci-dessus. Mais il y a quelques problèmes - laissez-moi les signaler:
Premièrement, les vecteurs A et B sont fixes. Alors, quand vous permutez les positions de box1 et box2, la détection de collision échoue.
Deuxièmement, nous n'évaluons l'écart que le long d'un axe. Les situations comme celle ci-dessous ne seront donc pas évaluées correctement:
Bien que la précédente démo soit imparfaite, nous avons appris le concept de projection. Ensuite, améliorons-le.
Donc tout d’abord, nous aurons besoin d’obtenir les projections minimum et maximum des coins (en particulier les vecteurs de l’origine aux coins des cases) sur P.
Le diagramme ci-dessus montre la projection des angles minimal et maximal sur P lorsque les cases sont bien orientées le long de P.
Mais si box1 et box2 ne sont pas orientés en conséquence?
Le diagramme ci-dessus montre des cases qui ne sont pas parfaitement orientées le long de P et leurs projections min-max correspondantes. Dans cette situation, nous devrons parcourir en boucle chaque coin de chaque case et sélectionner ceux qui conviennent le mieux..
Maintenant que nous avons les projections min-max, nous allons évaluer si les boîtes entrent en collision les unes avec les autres. Comment?
En observant le diagramme ci-dessus, nous pouvons clairement voir la représentation géométrique pour la projection de box1.max et box2.min sur l'axe P.
Comme vous pouvez le constater, quand il y a un écart entre les deux cases, box2.min-box1.max sera plus que zéro - ou en d'autres termes, box2.min> box1.max. Lorsque la position des cases est intervertie, alors box1.min> box2.max implique qu'il y a un écart entre eux.
En traduisant cette conclusion en code, nous obtenons:
// SAT: Pseudocode pour évaluer la séparation de box1 et box2 si (box2.min> box1.max || box1.min> box2.max) trace ("collision le long de l'axe P s'est produite") else trace ("no collision le long de l'axe P ") Regardons un code plus détaillé pour comprendre cela. Notez que le code AS3 n'est pas optimisé ici. Bien qu’il soit long et descriptif, l’avantage est que vous pouvez voir comment fonctionne le calcul..
Tout d’abord, nous devons préparer les vecteurs:
// préparant les vecteurs de l'origine aux points // puisque l'origine est (0,0), nous pouvons aisément prendre les coordonnées // pour former des vecteurs var axis: Vector2d = new Vector2d (1, -1) .unitVector; var vecs_box1: vecteur.= nouveau vecteur. ; var vecs_box2: vecteur. = nouveau vecteur. ; pour (var i: int = 0; i < 5; i++) var corner_box1:Point = box1.getDot(i) var corner_box2:Point = box2.getDot(i) vecs_box1.push(new Vector2d(corner_box1.x, corner_box1.y)); vecs_box2.push(new Vector2d(corner_box2.x, corner_box2.y));
Ensuite, nous obtenons la projection min-max sur box1. Vous pouvez voir une approche similaire utilisée sur box2:
// définition de min max pour box1 var min_proj_box1: Number = vecs_box1 [1] .dotProduct (axis); var min_dot_box1: int = 1; var max_proj_box1: Number = vecs_box1 [1] .dotProduct (axis); var max_dot_box1: int = 1; pour (var j: int = 2; j < vecs_box1.length; j++) var curr_proj1:Number = vecs_box1[j].dotProduct(axis) //select the maximum projection on axis to corresponding box corners if (min_proj_box1 > curr_proj1) min_proj_box1 = curr_proj1 min_dot_box1 = j // sélectionne la projection minimale sur l’axe aux angles de boîte correspondants si (curr_proj1> max_proj_box1) max_proj_box1 = curr_proj1 max_dot_box1 = j
Enfin, nous évaluons s'il y a une collision sur cet axe spécifique, P:
var isSeparated: Boolean = max_proj_box2 < min_proj_box1 || max_proj_box1 < min_proj_box2 if (isSeparated) t.text = "There's a gap between both boxes" else t.text = "No gap calculated."
Voici une démo de l'implémentation ci-dessus:
Vous pouvez faire glisser l'une des boîtes par son point central et la faire pivoter avec les touches R et T. Le point rouge indique le coin maximum d'une case, le jaune le minimum. Si une case est alignée sur P, vous remarquerez peut-être que ces points clignotent lorsque vous faites glisser, car ces deux coins partagent les mêmes caractéristiques..
Découvrez la source complète dans DemoSAT2.as dans le téléchargement source.
Si vous souhaitez accélérer le processus, vous n'avez pas besoin de calculer le vecteur unitaire de P. Vous pouvez donc sauter un nombre assez élevé de calculs de théorèmes coûteux de Pythagore qui impliquent Math.sqrt ():
\ [\ begin bmatrix A_x \\ A_y \ end bmatrix.
\ begin bmatrix P_x / P_ magnitude \\ P_y / P_ magnitude \ end bmatrix =
A_ magnitude * cos (thêta)
\]
Le raisonnement est le suivant (voir le diagramme ci-dessus pour des indications visuelles sur les variables):
/ * Soit: P_unit le vecteur unitaire de P, P_mag la magnitude de P, v1_mag la v1, v2_mag la v2, theta_1 l'angle entre v1 et P, theta_2 l'angle entre v2 et P, theta_1 étant l'angle entre v1 et P, alors: box1.max < box2.min => v1.dotProduct (P_unit) < v2.dotProduct(P_unit) => v1_mag * cos (theta_1) < v2_mag*cos(theta_2) */
Maintenant, mathématiquement, le signe de l'inégalité reste le même si les deux côtés de l'inégalité sont multipliés par le même nombre, A:
/ * Donc: A * v1_mag * cos (theta_1) < A*v2_mag*cos(theta_2) If A is P_mag, then: P_mag*v1_mag*cos(theta_1) < P_mag*v2_mag*cos(theta_2)… which is equivalent to saying: v1.dotProduct(P) < v2.dotProduct(P) */
Donc, qu’il s’agisse d’un vecteur unitaire ou non, le résultat est le même..
N'oubliez pas que cette approche est utile si vous recherchez uniquement les chevauchements. Pour trouver la longueur de pénétration exacte de box1 et box2 (dont vous aurez probablement besoin pour la plupart des jeux), vous devez toujours calculer le vecteur unitaire de P.
Nous avons donc résolu le problème pour un axe, mais ce n’est pas la fin. Nous devons encore nous attaquer à d'autres axes - mais qui?
L’analyse des cases est assez simple: nous comparons deux axes P et Q. Afin de confirmer une collision, tout les axes doivent être vrais - s'il y a des axes sans chevauchement, on peut en conclure qu'il n'y a pas de collision.
Et si les boîtes sont orientées différemment?
Cliquez sur le bouton vert pour passer à une autre page. Donc, parmi les axes P, Q, R et S, il n'y a qu'un seul axe qui ne montre aucun chevauchement entre les cases, et notre conclusion est qu'il n'y a pas de collision entre les cases..
Mais la question est de savoir comment décider des axes pour vérifier le chevauchement. Eh bien, nous prenons le normales des polygones.
Sous une forme généralisée, avec deux cases, nous devrons vérifier selon huit axes: n0, n1, n2 et n3 pour chacun des box1 et box2. Cependant, nous pouvons voir que les éléments suivants se trouvent sur les mêmes axes:
n0 et n2 de box1 n1 et n3 de box1 n0 et n2 de box2 n1 et n3 de box2 Nous n’avons donc pas besoin de passer par les huit; Seulement quatre feront l'affaire. Et si box1 et box2 partageons la même orientation, nous pouvons encore réduire à évaluer seulement deux axes.
Qu'en est-il des autres polygones?
Malheureusement, pour le triangle et le pentagone au-dessus, il n’existe aucun raccourci de ce type; nous devrons donc effectuer des vérifications le long de toutes les normales..
Chaque surface a deux normales:
Le diagramme ci-dessus montre les normales gauche et droite de P. Notez les composantes commutées du vecteur et le signe pour chaque.
Pour ma mise en œuvre, j'utilise une convention dans le sens des aiguilles d'une montre, donc j'utilise le la gauche normales. Ci-dessous un extrait de SimpleSquare.as démontrant cela.
fonction publique getNorm (): Vector.normales de var: vecteur. = nouveau vecteur. pour (var i: int = 1; i < dots.length-1; i++) var currentNormal:Vector2d = new Vector2d( dots[i + 1].x - dots[i].x, dots[i + 1].y - dots[i].y ).normL //left normals normals.push(currentNormal); normals.push( new Vector2d( dots[1].x - dots[dots.length-1].x, dots[1].y - dots[dots.length-1].y ).normL ) return normals;
Je suis sûr que vous pouvez trouver un moyen d'optimiser le code suivant. Mais pour que nous ayons tous une idée claire de ce qui se passe, j'ai tout écrit en entier:
// résultats de P, Q var result_P1: Object = getMinMax (vecs_box1, normals_box1 [1]); var result_P2: Object = getMinMax (vecs_box2, normals_box1 [1]); var result_Q1: Object = getMinMax (vecs_box1, normals_box1 [0]); var result_Q2: Object = getMinMax (vecs_box2, normals_box1 [0]); // résultats de R, S var result_R1: Object = getMinMax (vecs_box1, normals_box2 [1]); var result_R2: Object = getMinMax (vecs_box2, normals_box2 [1]); var result_S1: Object = getMinMax (vecs_box1, normals_box2 [0]); var result_S2: Object = getMinMax (vecs_box2, normals_box2 [0]); var separ_P: Boolean = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj var separate_Q:Boolean = result_Q1.max_proj < result_Q2.min_proj || result_Q2.max_proj < result_Q1.min_proj var separate_R:Boolean = result_R1.max_proj < result_R2.min_proj || result_R2.max_proj < result_R1.min_proj var separate_S:Boolean = result_S1.max_proj < result_S2.min_proj || result_S2.max_proj < result_S1.min_proj //var isSeparated:Boolean = separate_p || separate_Q || separate_R || separate_S if (isSeparated) t.text = "Separated boxes" else t.text = "Collided boxes."
Vous verrez que certaines des variables ne sont pas nécessairement calculées pour atteindre le résultat. Si l'un des Séparer_P, Séparer_Q, Séparer_R et separé_S est vrai, alors ils sont séparés et il n'y a même pas besoin de procéder.
Cela signifie que nous pouvons économiser beaucoup d’évaluations, en vérifiant chacun de ces Booléens après qu’ils ont été calculés. Il faudrait réécrire le code, mais je pense que vous pouvez le parcourir (ou consulter le bloc commenté dans DemoSAT3.as).
Voici une démonstration de la mise en œuvre ci-dessus. Cliquez et faites glisser les cases via leurs points centraux, puis utilisez les touches R et T pour faire pivoter les cases:
Lorsque cet algorithme est exécuté, il vérifie les chevauchements dans les axes normaux. J'ai deux observations à souligner:
Voici un autre extrait de code permettant de détecter une collision entre un hexagone et un triangle:
fonction privée refresh (): void // prépare les normales, var normals_hex: Vector.= hex.getNorm (); var normals_tri: vecteur. = tri.getNorm (); var vecs_hex: vecteur. = prepareVector (hex); var vecs_tri: vecteur. = prepareVector (tri); var isSeparated: Boolean = false; // utilise les normales d'hexagone pour évaluer (var i: int = 0; i < normals_hex.length; i++) var result_box1:Object = getMinMax(vecs_hex, normals_hex[i]); var result_box2:Object = getMinMax(vecs_tri, normals_hex[i]); isSeparated = result_box1.max_proj < result_box2.min_proj || result_box2.max_proj < result_box1.min_proj if (isSeparated) break; //use triangle's normals to evaluate if (!isSeparated) for (var j:int = 1; j < normals_tri.length; j++) var result_P1:Object = getMinMax(vecs_hex, normals_tri[j]); var result_P2:Object = getMinMax(vecs_tri, normals_tri[j]); isSeparated = result_P1.max_proj < result_P2.min_proj || result_P2.max_proj < result_P1.min_proj if (isSeparated) break; if (isSeparated) t.text = "Separated boxes" else t.text = "Collided boxes."
Pour le code complet, consultez DemoSAT4.as dans le téléchargement source.
La démo est ci-dessous. L’interaction est la même que dans les démos précédentes: faites glisser le curseur vers le milieu et utilisez R et T pour faire pivoter.
La collision avec un cercle peut être l’un des plus simples. Parce que sa projection est la même dans toutes les directions (il s’agit simplement du rayon du cercle), nous pouvons simplement procéder comme suit:
fonction privée refresh (): void // prépare les vecteurs var v: Vector2d; var current_box_corner: Point; var center_box: Point = box1.getDot (0); var max: Number = Number.NEGATIVE_INFINITY; var box2circle: Vector2d = new Vector2d (c.x - center_box.x, c.y - center_box.y) var box2circle_normalised: Vector2d = box2circle.unitVector // obtenir le maximum pour (var i: int = 1; i < 5; i++) current_box_corner = box1.getDot(i) v = new Vector2d( current_box_corner.x - center_box.x , current_box_corner.y - center_box.y); var current_proj:Number = v.dotProduct(box2circle_normalised) if (max < current_proj) max = current_proj; if (box2circle.magnitude - max - c.radius > 0 && box2circle.magnitude> 0) t.text = "Pas de collision" sinon t.text = "Collision"
Découvrez la source complète dans DemoSAT5.as. Faites glisser le cercle ou la boîte pour les voir entrer en collision.
Eh bien, c'est tout pour l'instant. Merci de votre lecture et laissez vos commentaires avec un commentaire ou une question. A bientôt le tutoriel!
