separating axis collision detection
Posted: Sun Apr 29, 2007 12:26 am
Sorry it's in french , i'm sure you will find a lot of site about separating axis collision detection in english 
like this one
use key [F1] to change display (use mouse for red polygone and keyboard for yellow polygone)
use [space bar] to change polygones.
Include file "polygones.pb"
example :
like this one
use key [F1] to change display (use mouse for red polygone and keyboard for yellow polygone)
use [space bar] to change polygones.
Include file "polygones.pb"
Code: Select all
;J'ai largement utilisé le tutoriel d'Olivier renault pour construire ce code.
;Je ne retrouve plus l'adresse dans mes favoris, mais c'était sur gamedev je crois ?
;D'autres sites utiles
;http://www.limsi.fr/Individu/jacquemi/IG-TR-4-5-6/coll-inters-th-sep-axes1.html
;http://www.harveycartel.org/metanet/tutorials/tutorialA.html
;http://www.flashxpress.net/wikimedia/index.php/D%C3%A9tection_De_Collision
;faut que j'étudie ça de près !!
;http://gregory.corgie.free.fr/dotclear/index.php?2007/03/26/30--physic-engine-gestion-d-une-box-partie-2-2
;Principe de la méthode générale (pour n'importe quel polygone convexe)
; 1 - Calcule de chaque segment du polygone
; 2 - Calcule de la normale de ce segment
; 3 - Projection des polygones A et B sur cette normale (projection des sommets)
; 4 - Test du chevauchement des projections A et B
; 5 - Si pas de chevauchement , c'est qu'on a trouvé un plan de séparation, pas de collision.
; 6 - Calcule du déplacement mini à effectuer pour séparer les deux polygones en cours de test.
; Il s'agit ici d'une version simplifiée, Il manque la gestion de la vitesse et des matrices des polygones.
; il faut tenir compte de la vitesse pour éviter de traverser un polygone.
; C'est à dire qu'il faut projeter la vitesse et en déduire à quel moment aura lieu l'impact.
; Il manque aussi la gestion du point d'impact, je suis en train de bosser le sujet.
; En guise d'exercice il serait intéressant de faire une version qui ne gère que des box.
; Voir aussi pour structurer le code comme la gestion des collision3D que j'avais fait.
; C'est à dire calculer tous les polygones pour retenir la collision la plus proche et
; gérer la réponse d'une façon récursive.
Declare CalculeIntersection(*A.s_Polygone, *B.s_Polygone, *Axe.s_Vecteur2D, *Distance.s_Vecteur2D, *Chevauchement.Float)
Declare ChercheDeplacementMini(Array Axe.s_Vecteur2D(1), Array Chevauchement.f(1), NbAxes.l, *Collision.s_Collision)
Macro PRODUIT_SCALAIRE(V1, V2)
(V1\x * V2\x + V1\y * V2\y)
EndMacro
Procedure ConstructionPolygone(*Polygone.s_Polygone, Rayon.f)
;Permet de calculer un polygone convexe
Define.l i
Define.f Angle, Rayon
For i = 0 To *Polygone\NbSommet-1
*Polygone\Sommet[i]\x = Cos(Angle) * Rayon
*Polygone\Sommet[i]\y = Sin(Angle) * Rayon
Angle + 2.0 * #PI / *Polygone\NbSommet
Next i
EndProcedure
Procedure ConstructionMur(*Polygone.s_Polygone)
Define.l i
Define.f Angle, Rayon
Rayon = 22.63
Angle = #PI/4
For i = 0 To *Polygone\NbSommet-1
*Polygone\Sommet[i]\x = Cos(Angle) * Rayon
*Polygone\Sommet[i]\y = Sin(Angle) * Rayon
Angle + 2.0 * #PI / *Polygone\NbSommet
Next i
EndProcedure
Procedure ConstructionVoiture(*Polygone.s_Polygone)
Define.f Rayon
Rayon = 45
*Polygone\Sommet[0]\x = Cos(#PI/2) * Rayon
*Polygone\Sommet[0]\y = Sin(#PI/2) * Rayon
*Polygone\Sommet[1]\x = Cos(#PI-#PI/9) * Rayon
*Polygone\Sommet[1]\y = Sin(#PI-#PI/9) * Rayon
*Polygone\Sommet[2]\x = Cos(#PI+#PI/9) * Rayon
*Polygone\Sommet[2]\y = Sin(#PI+#PI/9) * Rayon
*Polygone\Sommet[3]\x = Cos(-#PI/2) * Rayon
*Polygone\Sommet[3]\y = Sin(-#PI/2) * Rayon
EndProcedure
Procedure AffichePolygone(*Voiture.s_Polygone, List Mur.s_Polygone())
StartDrawing(ScreenOutput())
;Affiche les murs
Couleur = #Red
With Mur()
ForEach Mur()
For i = 0 To \NbSommet-2
LineXY(\Position\x + \Sommet[i]\x, \Position\y + \Sommet[i]\y, \Position\x + \Sommet[i+1]\x, \Position\y + \Sommet[i+1]\y, Couleur)
Next i
LineXY(\Position\x + \Sommet[\NbSommet-1]\x, \Position\y + \Sommet[\NbSommet-1]\y, \Position\x + \Sommet[0]\x, \Position\y + \Sommet[0]\y, Couleur)
Next
EndWith
;Affiche la voiture
Couleur = #White
With *Voiture
For i = 0 To \NbSommet-2
LineXY(\Position\x + \Sommet[i]\x, \Position\y + \Sommet[i]\y, \Position\x + \Sommet[i+1]\x, \Position\y + \Sommet[i+1]\y, Couleur)
Next i
LineXY(\Position\x + \Sommet[\NbSommet-1]\x, \Position\y + \Sommet[\NbSommet-1]\y, \Position\x + \Sommet[0]\x, \Position\y + \Sommet[0]\y, Couleur)
If Fun=0
Circle(\Position\x + \Sommet[1]\x,\Position\y + \Sommet[1]\y,4,#Green)
Circle(\Position\x + \Sommet[2]\x,\Position\y + \Sommet[2]\y,4,#Green)
EndIf
EndWith
StopDrawing()
EndProcedure
Procedure CollisionPolygone(*A.s_Polygone, *B.s_Polygone, *Distance.s_Vecteur2D, *Collision.s_Collision)
Define.l j, i
Define.s_Vecteur2D Segment
If *A=0 Or *B=0 : ProcedureReturn #False : EndIf
; Tous les axes de séparation
Dim Axe.s_Vecteur2D(#NbPlan)
Dim Chevauchement.f(#NbPlan)
Define.l NoAxe
;Utilisation de la méthode générale,
;pour un rectangle on pourrait se contenter de tester 2 segments(largeur et longueur)
;Une autre méthode projette le centre et le rayon du rectangle(à tester).
; test séparation des axes du polygone A
j = *A\NbSommet-1
For i = O To *A\NbSommet-1
;Calcule chaque segment du polygone
Segment\x = *A\Sommet[i]\x - *A\Sommet[j]\x
Segment\y = *A\Sommet[i]\y - *A\Sommet[j]\y
;Calcul la normale pour chaque segment du polygone
Axe(NoAxe)\x = -Segment\y
Axe(NoAxe)\y = Segment\x
If CalculeIntersection(*A, *B, Axe(NoAxe), *Distance, @Chevauchement(NoAxe)) = #False
ProcedureReturn #False ; dès qu'on trouve un axe de séparation on peut sortir
EndIf
NoAxe + 1
j = i
Next i
; test séparation des axes du polygone B
j = *B\NbSommet-1
For i = O To *B\NbSommet-1
;Calcule chaque segment du polygone
Segment\x = *B\Sommet[i]\x - *B\Sommet[j]\x ; Le polygone pourrait être stocké avec cette valeur
Segment\y = *B\Sommet[i]\y - *B\Sommet[j]\y ; ça éviterait de la calculer à chaque fois
;Calcul la normale pour chaque segment du polygone
Axe(NoAxe)\x = -Segment\y
Axe(NoAxe)\y = Segment\x
If CalculeIntersection(*A, *B, Axe(NoAxe), *Distance, @Chevauchement(NoAxe)) = #False
ProcedureReturn #False ; dès qu'on trouve un axe de séparation on peut sortir
EndIf
NoAxe + 1
j = i
Next i
;Il faudra chercher le point d'impact !
If ChercheDeplacementMini(Axe(), Chevauchement(), NoAxe, *Collision) = #False
ProcedureReturn #False
EndIf
; Inverse la normale si nécessaire pour être sûr que les polygones seront bien séparés.
If PRODUIT_SCALAIRE(*Collision\Normale, *Distance) < 0.0
*Collision\Normale\x = -*Collision\Normale\x
*Collision\Normale\y = -*Collision\Normale\y
Debug "correction"
Debug *Collision\Normale\x
Debug *Collision\Normale\y
Debug "fin correction"
EndIf
ProcedureReturn #True
EndProcedure
; calcule la projection du polygone sur l'axe en cours de test
Procedure CalculeProjection(*Polygone.s_Polygone, *Axe.s_Vecteur2D, *Projection.s_Intervalle)
Define.l i
Define.f Projection
;Calcul la projection du Sommet[0] sur la normale du plan en cours de test
*Projection\mini = *Polygone\Sommet[0]\x * *Axe\x + *Polygone\Sommet[0]\y * *Axe\y
*Projection\maxi = *Projection\mini
;Recherche les projections mini et maxi en testant tous les sommets du polygone
For i = 1 To *Polygone\NbSommet-1
Projection = *Polygone\Sommet[i]\x * *Axe\x + *Polygone\Sommet[i]\y * *Axe\y
If (Projection < *Projection\mini)
*Projection\mini = Projection
ElseIf (Projection > *Projection\maxi)
*Projection\maxi = Projection
EndIf
Next i
EndProcedure
Procedure CalculeIntersection(*A.s_Polygone, *B.s_Polygone, *Axe.s_Vecteur2D, *Distance.s_Vecteur2D, *Chevauchement.Float)
Define.f h, dist0, dist1
Define.s_Intervalle A, B
;Calcul la projection des sommets du polygone A sur la normale du plan en cours de test
CalculeProjection(*A, *Axe, @A)
;Calcul la projection des sommets du polygone B sur la normale du plan en cours de test
CalculeProjection(*B, *Axe, @B)
;Calcul la projection de l'offset entre les polygones
h = *Distance\x * *Axe\x + *Distance\y * *Axe\y
;Ajoute la projection de l'offset à la projection du polygone A
A\mini + h
A\maxi + h
;Calcul le chevauchement entre les projections de A et B
dist0 = A\mini - B\maxi
dist1 = B\mini - A\maxi
;Test le chevauchement
If dist0 > 0.0 Or dist1 > 0.0
ProcedureReturn #False
Else
If dist0 > dist1
*Chevauchement\f = dist0
Else
*Chevauchement\f = dist1
EndIf
ProcedureReturn #True
EndIf
EndProcedure
Procedure.f Normalise(*V.s_Vecteur2D)
Define.f Longueur
Longueur = Sqr(*V\x * *V\x + *V\y * *V\y)
If Longueur <> 0.0
*V\x / Longueur
*V\y / Longueur
EndIf
ProcedureReturn Longueur
EndProcedure
Procedure ChercheDeplacementMini(Array Axe.s_Vecteur2D(1), Array Chevauchement.f(1), NbAxes.l, *Collision.s_Collision)
Define.l mini, i
Define.f n
;Initialise les données collision
mini = -1
*Collision\distance = 0
*Collision\Normale\x = 0
*Collision\Normale\y = 0
;On cherche parmi tous les axes de séparation le chevauchement le plus petit
For i = 0 To NbAxes-1
n = Normalise(@Axe(i)) ; Normalise l'axe et récupère sa longueur
Chevauchement(i) / n
;On retient le plus petit chevauchement pour se dégager de l'autre polygone
;les valeurs de chevauchement sont négatives d'où le test > ci dessous
;Par la suite il faudra aussi tenir compte du point d'impact !!
If (Chevauchement(i) > *Collision\distance) Or (mini = -1)
mini = i
*Collision\distance = Chevauchement(i)
*Collision\Normale\x = Axe(i)\x
*Collision\Normale\y = Axe(i)\y
EndIf
Next i
ProcedureReturn (mini <> -1)
EndProcedureCode: Select all
;Comtois le 02/09/09 - Avec l'aide du tutoriel d'Olivier Renault (gamedev)
; PureBasic 4.40 b2
If InitSprite()=0 Or InitMouse()=0 Or InitKeyboard()=0
MessageRequester("Erreur","Initialisation impossible",0)
End
EndIf
If OpenScreen(800, 600, 32,"Collision par la méthode de séparation des axes")=0
MessageRequester("Erreur","Ouverture d'un écran 800x600x32 impossible",0)
End
EndIf
#Epsilon = 0.00001
#NbSommet = 32 ;Nombre de Sommet maxi pour un polygone
#NbPlan = (#NbSommet*2)-1 ;Un plan par Sommet pour deux polygones
#DeltaAngle = 0.09/#PI
#NbPolygones = 25*18
Enumeration
#A
#B
EndEnumeration
Structure s_Vecteur2D
x.f
y.f
EndStructure
Structure s_Polygone
Position.s_Vecteur2D
Vitesse.f
Angle.f
NbSommet.l
Sommet.s_Vecteur2D[#NbSommet]
EndStructure
Structure s_Collision
Detectee.l
Normale.s_Vecteur2D
Distance.f
EndStructure
Structure s_Intervalle
Mini.f
Maxi.f
EndStructure
Define.s_Polygone Voiture
NewList Mur.s_Polygone()
Global Fun = 1 ; Changez cette valeur à #True pour tester avec des polygones quelconques(convexes)
XIncludeFile "polygones.pb"
Procedure InitialiseJeu(*Voiture.s_Polygone, List Mur.s_Polygone())
;Création du jeu
Define.l i, x, y
Restore Niveau
ClearList(Mur())
For i = 0 To #NbPolygones-1
Read Poly
x = 16 + (i % 25) * 32
y = 16 + (i / 25) * 32
If Fun
If poly = 2
*Voiture\Position\x = x
*Voiture\Position\y = y
*Voiture\NbSommet = Random(5)+3
*Voiture\Vitesse = 5
*Voiture\Angle = 0
ConstructionPolygone(*Voiture, Random(32)+16)
ElseIf Poly = 3
AddElement(Mur())
Mur()\Position\x = x
Mur()\Position\y = y
Mur()\NbSommet = Random(10)+3
ConstructionPolygone(Mur(),Random(32)+16)
EndIf
Else
If poly = 2
*Voiture\Position\x = x
*Voiture\Position\y = y
*Voiture\NbSommet = 4
*Voiture\Vitesse = 5
*Voiture\Angle = 0
ConstructionVoiture(*Voiture)
ElseIf Poly = 1
AddElement(Mur())
Mur()\Position\x = x
Mur()\Position\y = y
Mur()\NbSommet = 4
ConstructionMur(Mur())
EndIf
EndIf
Next i
EndProcedure
Procedure CollisionReponse(*Voiture.s_Polygone, List Mur.s_Polygone())
;A reprendre
; Il faudrait d'abord chercher le point d'impact le plus proche en testant tous les polygones
; Puis calculer la réponse d'une façon récursive, en prenant un vecteur vitesse en compte.
Define.s_Vecteur2D Distance
Define.s_Collision Collision
ForEach Mur()
Distance\x = *Voiture\Position\x - Mur()\Position\x
Distance\y = *Voiture\Position\y - Mur()\Position\y
Collision\Detectee = CollisionPolygone(*Voiture, Mur(), @Distance, @Collision)
;Séparation des polygones
If Collision\Detectee
*Voiture\Position\x - (Collision\Normale\x * (Collision\Distance * 1.0)) ; ou un peu moins que 1.5
*Voiture\Position\y - (Collision\Normale\y * (Collision\Distance * 1.0)) ; ou un peu moins que 1.5
If fun
MouseLocate(*Voiture\Position\x, *Voiture\Position\y)
EndIf
EndIf
Next
EndProcedure
Macro ROTATION(Angle)
CosAngle.f = Cos(Angle)
SinAngle.f = Sin(Angle)
x0.f = 0 ; Mettre 0 pour placer l'axe de rotation au centre
y0.f = 0
For i = 0 To *Voiture\NbSommet-1
x1.f = *Voiture\Sommet[i]\x - x0
y1.f = *Voiture\Sommet[i]\y - y0
*Voiture\Sommet[i]\x = x0 + x1 * CosAngle + y1 * SinAngle
*Voiture\Sommet[i]\y = y0 - x1 * SinAngle + y1 * CosAngle
Next i
EndMacro
Procedure GestionClavier(*Voiture.s_Polygone, List Mur.s_Polygone())
If ExamineKeyboard()
If KeyboardReleased(#PB_Key_F1)
Fun = 1 - Fun
InitialiseJeu(*Voiture, Mur())
ElseIf KeyboardReleased(#PB_Key_Space)
InitialiseJeu(*Voiture, Mur())
EndIf
If Fun = 0
If KeyboardPushed(#PB_Key_Left)
*Voiture\Angle + #DeltaAngle
ROTATION(#DeltaAngle)
ElseIf KeyboardPushed(#PB_Key_Right)
*Voiture\Angle - #DeltaAngle
ROTATION(-#DeltaAngle)
EndIf
If KeyboardPushed(#PB_Key_Down)
*Voiture\Position\x + Cos(*Voiture\Angle) * *Voiture\Vitesse
*Voiture\Position\y - Sin(*Voiture\Angle) * *Voiture\Vitesse
ElseIf KeyboardPushed(#PB_Key_Up)
*Voiture\Position\x - Cos(*Voiture\Angle) * *Voiture\Vitesse
*Voiture\Position\y + Sin(*Voiture\Angle) * *Voiture\Vitesse
EndIf
ElseIf ExamineMouse()
*Voiture\Position\x = MouseX()
*Voiture\Position\y = MouseY()
EndIf
EndIf
EndProcedure
InitialiseJeu(@Voiture, Mur())
Repeat
ClearScreen(#Black)
GestionClavier(@Voiture, Mur())
CollisionReponse(@Voiture, Mur())
AffichePolygone(@Voiture, Mur())
FlipBuffers()
Until KeyboardPushed(#PB_Key_Escape)
DataSection
Niveau:
Data.l 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,3,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,3,0,0,0,0,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,1,1,1,1
Data.l 1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,1,0,0,0,3,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1
Data.l 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
EndDataSection