Astuces et codes utiles sur les Mathématiques

Partagez votre expérience de PureBasic avec les autres utilisateurs.
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Intersection de deux cercles

Message par fweil »

J'espère ne pas faire double emploi avec un code antérieur.

Je me suis attaché à réfléchir sur les collisions de sprites.

Pour commencer par exercice de niveau intermédiaire, c'est à dire qui permette d'être plus précis que le SpriteCollision() de base, j'ai choisi d'envisager le test de collision de deux enveloppes circulaires.

Voici une proposition de code à peu près optimisé.

Le programme principal est une simple mise en oeuvre pour montrer le résultat de la procédure.

Si les deux cercles testés sont en contact, ils sont affichés en rouge, sinon ils sont en blanc.

L'utilisation de ce type de calcul dans une gestion de sprites avec enveloppes circulaires (des balles en particulier), est simple. Attention toutefois, la procédure prend en argument les coordonnées des centres et les rayons. Lorsqu'on affiche un sprite, les paramètres d'affichage sont le coin haut gauche et la taille (correspondant au diamètre dans le cas d'une balle).

Je vais laisser ce chapitre ouvert sur mon PC, pour proposer des variantes de tests de collisions si il y a des amateurs.

Petite explication pour l'algorithme utilisé ici : on considère les équations respectives de chacun des cercles, et on travaille sur la différence des équations.

Par le jeu du raisonnement mathématique, on constate que la différence des équations des deux cercles revient à une forme de polynome du second degré. Lorsque l'on calcule les racines de cette équation finale, on en déduit les points d'intersection éventuels des cercles. Si il y a au moins un point d'intersection c'est que les cercles se touchent ou se superposent en tout ou partie.

Code : Tout sélectionner

Procedure Circles_Collision(x1.f, y1.f, r1.f, x2.f, y2.f, r2.f)
  dx.f = (x1 - x2)
  dy.f = (y1 - y2)
  If Abs(dx) <= r1 And Abs(dy) <= r1
      ProcedureReturn #True
  EndIf
  If dx = 0 And dy = 0
      ProcedureReturn #True
    Else
      dxdy.f = dx / dy
      N.f = (r2 * r2 - r1 * r1 - x2 * x2 + x1 * x1 - y2 * y2 + y1 * y1) / (2 * (y1 - y2))
      A.f = dxdy * dxdy + 1
      B.f = 2 * y1 * dxdy - 2 * N * dxdy - 2 * x1
      C.f = (x1 * x1 + y1 * y1 + N * N - r1 * r1 - 2 * y1 * N)
      Delta.f = B * B - 4 * A * C
      If Delta < 0
          ProcedureReturn #False
        Else  
          ProcedureReturn #True
      EndIf
  EndIf
EndProcedure

  ScreenWidth = GetSystemMetrics_(#SM_CXSCREEN)
  ScreenHeight = GetSystemMetrics_(#SM_CYSCREEN)
  ScreenDepth = 32
  If InitSprite() And InitMouse() And InitKeyboard()
      If OpenScreen(ScreenWidth, ScreenHeight, ScreenDepth, "")
          Quit = #False
          Repeat
            FlipBuffers()
            ClearScreen(0, 0, 0)
            ExamineKeyboard()
            ExamineMouse()
            MouseX = MouseX()
            MouseY = MouseY()
            If KeyboardPushed(#PB_Key_Escape) : Quit = #True : EndIf
            StartDrawing(ScreenOutput())
              DrawingMode(4)
              If Circles_Collision(ScreenWidth / 2, ScreenHeight / 2, 200, MouseX, MouseY, 200)
                  Color = #Red
                Else
                  Color = #White
              EndIf
              Circle(ScreenWidth / 2, ScreenHeight / 2, 200, Color)
              Circle(MouseX, MouseY, 200, Color)
            StopDrawing()
          Until Quit
      EndIf
  EndIf
End
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Bon j'ai trouvé une méthode différente, mais sans doute moins compliquée et plus rapide !!! Bien fait pour moi.

C'est tout simplement basé sur la distance des centres des cercles, comparée à la somme des rayons des deux cercles. Bête comme choux.

Code : Tout sélectionner

Procedure Circles_Fast_Collision(cx1.f, cy1.f, radius1.f, cx2.f, cy2.f, radius2.f)
  d.f = Sqr((cx2 - cx1) * (cx2 - cx1) + (cy2 - cy1) * (cy2 - cy1))
  If d <= radius1 + radius2
      ProcedureReturn #True
    Else
      ProcedureReturn #False
  EndIf
EndProcedure
Si vous êtes intéressés et que vous me faites des tests et du retour ...
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

cool !! :D

c'est quand meme un plus d'etre un matheux ! :D

Bravo et Merci çela pourra me servir ! :D

y aurai t'il une possibilité de transposer ton dernier exemple
pour la collision de Pavé ? (ou de rectangle) ?
en pouvant savoir si la collision viens du haut de droite ou du bas ou de gauche ?
car ce qui manque au Pure c'est ça justement , savoir la provenance de la collision !!
pour le cercle ce serai pareil , connaitre l'angle par rapport a zero (midi)
de la collision , que ça retourne le nombre de degres, (ou l'heure :D)
ça doit etre un challenge interrressant pour quelqu'un qui maitrise les Math ..
:D
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Je suis en train d'étudier la question, mais pour l'instant la collision entre un rectangle et un cercle me pose plus de problèmes pour obtenir un résultat limpide, et performant.

Je pense pouvoir proposer qq chose aujourd'hui ou demain.

L'idée que j'ai est de faire une série de procédures simples pour assurer le test de collision sur des formes basiques, et dans une étape suivante d'essayer de résoudre des collisions d'enveloppes hybrides. Mais ce n'est qu'un sujet d'étude pour l'instant.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

crois tu que Fred serai interressé d'integrer ton travail dans le pure si c'etait concluant ?
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Je suppose que cela pourrait tout simplement s'intégrer au travers d'une librairie.

Je le mettrai sous cette forme si cela avance suffisament, mais ce sont en fait de simples fonctions faciles à utiliser sous toutes les formes (copier / coller, include, etc).

Si Fred souhaite ajouter celà comme fonctions natives de PureBasic, je suis tout à fait d'accord, dans ce cas, je lui donnerait une version complètement optimisée.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Dr. Dri
Messages : 2527
Inscription : ven. 23/janv./2004 18:10

Message par Dr. Dri »

@fweil
elle a servi à quoi mon astuce sur la fonction Sqr() ?

Code : Tout sélectionner

Procedure Circles_Faster_Collision(cx1.f, cy1.f, radius1.f, cx2.f, cy2.f, radius2.f)
  dCenter.f = (cx2 - cx1) * (cx2 - cx1) + (cy2 - cy1) * (cy2 - cy1)
  dRadius.f = (radius1 + radius2) * (radius1 + radius2)
  If dCenter <= dRadius
      ProcedureReturn #True
    Else
      ProcedureReturn #False
  EndIf
EndProcedure
:0: tusors:

@dobro
l'angle 0 n'est pas à midi parce que les coordonnées de l'écran ne le permettent pas ;)

Dri
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Voici le test de collision entre une boite et un cercle !

Je pense avoir choisi la méthode la moins coûteuse. J'optimiserai peut-être encore un peu la chose.

Les arguments sont logiquement les coordonnées du centre du cercle et son rayon, ainsi que les coordonnées de la boite. Attention, ici la boite est définie en coordonnées des coins opposés, et non pas par les coordonnées d'un coin et la taille (contrairement à la commande Box())

Edité : je remets le code complet avec le prog principal de test, ce qui facilitera la compréhension des choses.

Edité : avec qq mises à jour et plus de possibilités

Code : Tout sélectionner

Procedure Triangle(tx1.f, ty1.f, tx2.f, ty2.f, tx3.f, ty3.f, Color.l, Mode.l) ; Dessin d'un triangle avec attribut de couleur et mode de tracé (4 = vide, 0 = plein)
  LineXY(tx1, ty1, tx2, ty2, Color)
  LineXY(tx2, ty2, tx3, ty3, Color)
  LineXY(tx3, ty3, tx1, ty1, Color)
  If Mode <> 4
      FillArea((tx1 + tx2 + tx3) / 3, (ty1 + ty2 + ty3) / 3, Color, Color)
  EndIf
EndProcedure

Procedure Box_And_Box_Collision(b1x1.f, b1y1.f, b1x2.f, b1y2.f, b2x1.f, b2y1.f, b2x2.f, b2y2.f)
  If b1x1 > b1x2 ; on redresse les enveloppes
      xz.f = b1x1
      b1x1 = b1x2
      b1x2 = xz
  EndIf
  If b2x1 > b2x2
      xz.f = b2x1
      b2x1 = b2x2
      b2x2 = xz
  EndIf

  If b1y1 > b1y2
      yz.f = b1y1
      b1y1 = b1y2
      b1y2 = yz
  EndIf
  If b2y1 > b2y2
      yz.f = b2y1
      b2y1 = b2y2
      b2y2 = yz
  EndIf

  dx1.f = b1x2 - b1x1 ; on prend les dimensions de chaque boite
  dy1.f = b1y2 - b1y1
  dx2.f = b2x2 - b2x1
  dy2.f = b2y2 - b2y1

  bbx1.f = b1x1 ; on calcule l'enveloppe dans laquelle s'inscrivent les deux boites
  If bbx1 > b2x1
      bbx1 = b2x1
  EndIf
  bbx2.f = b1x2
  If bbx2 < b2x2
      bbx2 = b2x2
  EndIf
  bby1.f = b1y1
  If bby1 > b2y1
      bby1 = b2y1
  EndIf
  bby2.f = b1y2
  If bby2 < b2y2
      bby2 = b2y2
  EndIf
  
  dbx.f = bbx2 - bbx1 ; on prend les dimensions de l'enveloppe globale
  dby.f = bby2 - bby1
      
  If dbx <= dx1 + dx2 And dby <= dy1 + dy2 ; Si la boite globale est plus petite que la plus petite enveloppe des deux boites disjointes, c'est qu'elles sont en contact
      ProcedureReturn #True
  EndIf

  ProcedureReturn #False
EndProcedure

Procedure Box_And_Triangle_Collision(bx1.f, by1.f, bx2.f, by2.f, tx1.f, ty1.f, tx2.f, ty2.f, tx3.f, ty3.f)
  envx1.f = tx1 ; Pour l'instant je calcule le rectangle dans lequel le triangle est inscrit
  If envx1 > tx2
      envx1 = tx2
  EndIf
  If envx1 > tx3
      envx1 = tx3
  EndIf
  envx2.f = tx1
  If envx2 < tx2
      envx2 = tx2
  EndIf
  If envx2 < tx3
      envx2 = tx3
  EndIf
  
  envy1.f = ty1
  If envy1 > ty2
      envy1 = ty2
  EndIf
  If envy1 > ty3
      envy1 = ty3
  EndIf
  envy2.f = ty1
  If envy2 < ty2
      envy2 = ty2
  EndIf
  If envy2 < ty3
      envy2 = ty3
  EndIf
  Box(envx1, envy1, envx2 - envx1, envy2 - envy1, #Green) ; je le dessine pour info
  ProcedureReturn Box_And_Box_Collision(bx1, by1, bx2, by2, envx1, envy1, envx2, envy2)
EndProcedure

Procedure Triangle_And_Triangle_Collision(t1x1.f, t1y1.f, t1x2.f, t1y2.f, t1x3.f, t1y3.f, t2x1.f, t2y1.f, t2x2.f, t2y2.f, t2x3.f, t2y3.f)
  env1x1.f = t1x1 ; Pour l'instant je calcule le rectangle dans lequel le triangle est inscrit
  If env1x1 > t1x2
      env1x1 = t1x2
  EndIf
  If env1x1 > t1x3
      env1x1 = t1x3
  EndIf
  env1x2.f = t1x1
  If env1x2 < t1x2
      env1x2 = t1x2
  EndIf
  If env1x2 < t1x3
      env1x2 = t1x3
  EndIf
  
  env1y1.f = t1y1
  If env1y1 > t1y2
      env1y1 = t1y2
  EndIf
  If env1y1 > t1y3
      env1y1 = t1y3
  EndIf
  env1y2.f = t1y1
  If env1y2 < t1y2
      env1y2 = t1y2
  EndIf
  If env1y2 < t1y3
      env1y2 = t1y3
  EndIf

  env2x1.f = t2x1
  If env2x1 > t2x2
      env2x1 = t2x2
  EndIf
  If env2x1 > t2x3
      env2x1 = t2x3
  EndIf
  env2x2.f = t2x1
  If env2x2 < t2x2
      env2x2 = t2x2
  EndIf
  If env2x2 < t2x3
      env2x2 = t2x3
  EndIf
  
  env2y1.f = t2y1
  If env2y1 > t2y2
      env2y1 = t2y2
  EndIf
  If env2y1 > t2y3
      env2y1 = t2y3
  EndIf
  env2y2.f = t2y1
  If env2y2 < t2y2
      env2y2 = t2y2
  EndIf
  If env2y2 < t2y3
      env2y2 = t2y3
  EndIf
  Box(env1x1, env1y1, env1x2 - env1x1, env1y2 - env1y1, #Green) ; je le dessine pour info
  Box(env2x1, env2y1, env2x2 - env2x1, env2y2 - env2y1, #Green)
  ProcedureReturn Box_And_Box_Collision(env1x1, env1y1, env1x2, env1y2, env2x1, env2y1, env2x2, env2y2)
EndProcedure

Procedure Circle_And_Circle_Collision(cx1.f, cy1.f, radius1.f, cx2.f, cy2.f, radius2.f)
  dx.f = cx2 - cx1 ; On calcule la distance entre le centre du cercle 1 et le centre du cercle 2
  dy.f = cy2 - cy1
  min_distance.f = radius1 + radius2
  min_distance2.f = min_distance * min_distance
  If dx * dx + dy * dy <= min_distance2 ; si cette distance est inférieure à la somme des rayons, il y a collision
      ProcedureReturn #True
    Else
      ProcedureReturn #False
  EndIf
EndProcedure

Procedure Circle_And_Box_Collision(cx.f, cy.f, radius.f, x1.f, y1.f, x2.f, y2.f)
  If x1 > x2 ; Redressement du rectangle de référence si nécessaire
      xz.f = x1
      x1 = x2
      x2 = xz
  EndIf
  If y1 > y2
      yz.f = y1
      y1 = y2
      y2 = yz
  EndIf
  If cx + radius => x1 And cy => y1 And cy <= y2 And cx + radius <= x2 ; Test pour savoir si le cercle touche le bord gauche de la boite
      ProcedureReturn #True
  EndIf
  If cx - radius <= x2 And cy => y1 And cy <= y2 And cx - radius => x1 ; Test pour savoir si le cercle touche le bord droit de la boite
      ProcedureReturn #True
  EndIf
  If cy + radius => y1 And cx => x1 And cx <= x2 And cy + radius <= y2 ; Test pour savoir si le cercle touche le bord bas de la boite
      ProcedureReturn #True
  EndIf
  If cy - radius <= y2 And cx => x1 And cx <= x2 And cy - radius => y1 ; Test pour savoir si le cercle touche le bord haut de la boite
      ProcedureReturn #True
  EndIf
  dx1.f = cx - x1 ; Si le cercle ne touche pas par un bord, on vérifie qu'il n'est pas en contact par un coin
  dy1.f = cy - y1
  dx2.f = cx - x2
  dy2.f = cy - y2
  radius2.f = radius * radius
  If dx1 * dx1 + dy1 * dy1 <= radius2 ; Test pour le coin x1, y1
      ProcedureReturn #True
  EndIf
  If dx1 * dx1 + dy2 * dy2 <= radius2 ; Test pour le coin x1, y2
      ProcedureReturn #True
  EndIf
  If dx2 * dx2 + dy1 * dy1 <= radius2 ; Test pour le coin x2, y1
      ProcedureReturn #True
  EndIf
  If dx2 * dx2 + dy2 * dy2 <= radius2 ; Test pour le coin x2, y2
      ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

Procedure Circle_And_Triangle_Collision(cx.f, cy.f, radius.f, tx1.f, ty1.f, tx2.f, ty2.f, tx3.f, ty3.f)
  envx1.f = tx1 ; Pour l'instant je calcule le rectangle dans lequel le triangle est inscrit
  If envx1 > tx2
      envx1 = tx2
  EndIf
  If envx1 > tx3
      envx1 = tx3
  EndIf
  envx2.f = tx1
  If envx2 < tx2
      envx2 = tx2
  EndIf
  If envx2 < tx3
      envx2 = tx3
  EndIf
  
  envy1.f = ty1
  If envy1 > ty2
      envy1 = ty2
  EndIf
  If envy1 > ty3
      envy1 = ty3
  EndIf
  envy2.f = ty1
  If envy2 < ty2
      envy2 = ty2
  EndIf
  If envy2 < ty3
      envy2 = ty3
  EndIf
  Box(envx1, envy1, envx2 - envx1, envy2 - envy1, #Green) ; je le dessine pour info
  ProcedureReturn Circle_And_Box_Collision(cx, cy, radius, envx1, envy1, envx2, envy2) ; et j'utilise le test cercle / boite. On verra plus tard pour faire mieux
EndProcedure

;
;
;
  ScreenWidth = GetSystemMetrics_(#SM_CXSCREEN)
  ScreenHeight = GetSystemMetrics_(#SM_CYSCREEN)
  ScreenDepth = 32
  cx1 = 3 * ScreenWidth / 4
  cy1 = ScreenHeight / 2
  radius1 = 150
  radius2 = 100
  bx1 = 200
  by1 = 300
  bx2 = 350
  by2 = 400
  tx1 = ScreenWidth / 4
  ty1 = 3 * ScreenHeight / 4- 30
  tx2 = ScreenWidth / 2
  ty2 = 3 * ScreenHeight / 4
  tx3 = 3 * ScreenWidth / 8
  ty3 = ScreenHeight / 2
  Statistics = #True
  #Circle = 0
  #Triangle = 1
  #Box = 2
  Mode = #Circle
  If InitSprite() And InitMouse() And InitKeyboard()
      If OpenScreen(ScreenWidth, ScreenHeight, ScreenDepth, "")
          Quit = #False
          Repeat
            FlipBuffers(0)
            ClearScreen(0, 0, 0)
            ExamineKeyboard()
            ExamineMouse()
            If KeyboardPushed(#PB_Key_Escape) : Quit = #True : EndIf
            If KeyboardPushed(#PB_Key_F1) : Repeat : ExamineKeyboard() : Until KeyboardReleased(#PB_Key_F1) : Statistics = 1 - Statistics : EndIf
            If KeyboardPushed(#PB_Key_F2) : Repeat : ExamineKeyboard() : Until KeyboardReleased(#PB_Key_F2) : Detect_Collisions = 1 - Detect_Collisions : EndIf
            If KeyboardPushed(#PB_Key_Left) : Repeat : ExamineKeyboard() : Until KeyboardReleased(#PB_Key_Left) : Mode - 1 : If Mode < #Circle : Mode = #Circle : EndIf : EndIf
            If KeyboardPushed(#PB_Key_Right) : Repeat : ExamineKeyboard() : Until KeyboardReleased(#PB_Key_Right) : Mode + 1 : If Mode > #Box : Mode = #Box : EndIf : EndIf
            StartDrawing(ScreenOutput())
              DrawingMode(4)
              Color = #White
              Select Mode
                Case #Circle
                  cx2 = MouseX()
                  cy2 = MouseY()
                  Circle(cx2, cy2, radius2, #White)
                  If Detect_Collisions
                      If Circle_And_Circle_Collision(cx2, cy2, radius2, cx1, cy1, radius1)
                          Circle(cx1, cy1, radius1, #Red)
                        Else
                          Circle(cx1, cy1, radius1, #White)
                      EndIf
                      If Circle_And_Box_Collision(cx2, cy2, radius2, bx1, by1, bx2, by2)
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #Red)
                        Else
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      EndIf
                      If Circle_And_Triangle_Collision(cx2, cy2, radius2, tx1, ty1, tx2, ty2, tx3, ty3)
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #Red, 4)
                        Else
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                      EndIf
                    Else
                      Circle(cx1, cy1, radius1, #White)
                      Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                  EndIf
                Case #Triangle
                  t2x1 = MouseX()
                  t2y1 = MouseY()
                  t2x2 = t2x1 - 110
                  t2y2 = t2y1 + 70
                  t2x3 = t2x1 - 90
                  t2y3 = t2y1 - 80
                  Triangle(t2x1, t2y1, t2x2, t2y2, t2x3, t2y3, #White, 4)
                  If Detect_Collisions
                      If Triangle_And_Triangle_Collision(tx1, ty1, tx2, ty2, tx3, ty3, t2x1, t2y1, t2x2, t2y2, t2x3, t2y3)
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #Red, 4)
                        Else
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                      EndIf
                      If Circle_And_Triangle_Collision(cx1, cy1, radius1, t2x1, t2y1, t2x2, t2y2, t2x3, t2y3)
                          Circle(cx1, cy1, radius1, #Red)
                        Else
                          Circle(cx1, cy1, radius1, #White)
                      EndIf
                      If Box_And_Triangle_Collision(bx1, by1, bx2, by2, t2x1, t2y1, t2x2, t2y2, t2x3, t2y3)
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #Red)
                        Else
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      EndIf
                    Else
                      Circle(cx1, cy1, radius1, #White)
                      Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                  EndIf
                Case #Box
                  b2x1 = MouseX()
                  b2y1 = MouseY()
                  b2x2 = b2x1 + 100
                  b2y2 = b2y1 + 150
                  Box(b2x1, b2y1, b2x2 - b2x1, b2y2 - b2y1, #White)
                  If Detect_Collisions
                      If Box_And_Box_Collision(bx1, by1, bx2, by2, b2x1, b2y1, b2x2, b2y2)
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #Red)
                        Else
                          Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      EndIf
                      If Circle_And_Box_Collision(cx1, cy1, radius1, b2x1, b2y1, b2x2, b2y2)
                          Circle(cx1, cy1, radius1, #Red)
                        Else
                          Circle(cx1, cy1, radius1, #White)
                      EndIf
                      If Box_And_Triangle_Collision(b2x1, b2y1, b2x2, b2y2, tx1, ty1, tx2, ty2, tx3, ty3)
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #Red, 4)
                        Else
                          Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                      EndIf
                    Else
                      Circle(cx1, cy1, radius1, #White)
                      Box(bx1, by1, bx2 - bx1, by2 - by1, #White)
                      Triangle(tx1, ty1, tx2, ty2, tx3, ty3, #White, 4)
                  EndIf
              EndSelect
              If Statistics
                  DrawingMode(1)
                  BackColor(0, 0, 0)
                  FrontColor(255, 255, 255)
                  Locate(10, 10)
                  DrawText("FPS : " + Str(FPS))
                  Locate(10, 30)
                  DrawText("Aide / Statistiques (F1)")
                  Locate(10, 50)
                  Select Detect_Collisions
                    Case #False
                      sDetect_Collisions.s = "False"
                    Case #True
                      sDetect_Collisions.s = "True"
                  EndSelect
                  DrawText("Detect collisions (F2) : " + sDetect_Collisions)
                  Locate(10, 70)
                  Select Mode
                    Case #Circle
                      sMode.s = "Circle"
                    Case #Triangle
                      sMode.s = "Triangle"
                    Case #Box
                      sMode.s = "Box"
                  EndSelect
                  DrawText("Mode (Left / Right) : " + sMode)
              EndIf
              NFrames + 1
              If ElapsedMilliseconds() - tz => 1000
                  FPS = NFrames
                  NFrames = 0
                  tz = ElapsedMilliseconds()
              EndIf
            StopDrawing()
          Until Quit
          CloseScreen()
      EndIf
  EndIf
  CallDebugger
End
Dernière modification par fweil le lun. 19/sept./2005 15:49, modifié 1 fois.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

ha ben oui ! une lib ce serai cool !

@Dri : ben on fait ce qu'on veut en fait ! rien n'interdit de faire un -90 degré
au depart pour "forcer" le zero degré a midi , c'est d'ailleurs ce que je fait dans mon PureGolo ! la tortue commence la tete vers le haut de l'ecran
et je considere cette position comme etant 0 degres ! :D
Dernière modification par Backup le lun. 19/sept./2005 18:26, modifié 1 fois.
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Edité : avec qq mises à jour et plus de possibilités

J'ai travaillé un peu l'interface utilisateur pour avoir une présentation des résultats de tests qui ne me sème pas la confusion.

Les tests de formes triangle ne sont pas finalisés, pour l'instant je prends le rectangle dans lequel un triangle s'inscrit comme aire de test.

A noter la procedure de test d'intersection de deux boites (rectangles quelconques). Le cheminement que j'ai choisi est un peu indirect, mais il permet de faire à mon avis une séquence très simple et rapide. Quelqu'un a t-il un commentaire ou des idées sur la question ?

Maintenant, aux finitions près, on dispose donc de tests d'intersection de formes boite, rond et triangle. Je suppose qu'il n'est pas utile de compliquer les choses en travaillant d'autres primitives. Je vais terminer les procedures triangle, et ensuite je tenterai de généraliser à un test entre polylines.

Mais je prendrai sans doute un peu de recul pour ça.

Un point : j'ai assumé l'ensemble des paramètres en flottants. Disons par goût ! Je ne sais pas si il est utile de travailler sur deux jeux de fonctions pour supporter aussi bien les entiers que les flottants.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

j'ai assumé l'ensemble des paramètres en flottants
il suffit de le savoir au depart ! , pour ma part ça change pas grand chose
sauf si en flottants les resultats soient plus precis ! :D
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Pour les flottants ça ne donne rien en précision à proprement parler, mais j'ai une autre idée derrière la tête.

En fait, j'anticipe sur l'avenir !

Et l'avenir est à la flotte, parce que cet été on l'a dans le dos !
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
fweil
Messages : 505
Inscription : dim. 16/mai/2004 17:50
Localisation : Bayonne (64)
Contact :

Message par fweil »

Une étape supplémentaire pour avancer sur les questions de géométrie.

Avant de pouvoir terminer les outils de calcul de collision, il me fallait résoudre de manière générale le calcul d'intersection de segments de droites.

En effet, pour les calculs de collisions de boites et de cercles, il y a des méthodes rapides pour déduire les éventuels points de contact, mais lorsque l'on traite des triangles quelconques, on est dépendant d'un calcul plus complexe.

J'ai donc fait un petit atelier de test, qui permet de voir ce qui se passe entre une série de segments de droites et un triangle quelconque.

La procédure Intersect() qui est présentée ici permet de résoudre à priori la question.

En fait, il me semble qu'il reste un bug et un peu d'optimisation.

Néanmoins le prog est bien joli à regarder.

Quand ce sera parfaitement fiable et que j'aurai trouvé les voies d'optimisation, j'intègrerai ces nouveaux éléments dans la suite des procédures de gestion de collision.

Code : Tout sélectionner

Structure fPoint ; Conteneur pour un point en coordonnées flottantes
  x.f
  y.f
EndStructure

Structure Line ; Conteneur pour un vecteur
  x1.f
  y1.f
  x2.f
  y2.f
EndStructure

Procedure Triangle(tx1.f, ty1.f, tx2.f, ty2.f, tx3.f, ty3.f, Color.l, Mode.l) ; Dessin d'un triangle avec attribut de couleur et mode de tracé (4 = vide, 0 = plein)
  LineXY(tx1, ty1, tx2, ty2, Color)
  LineXY(tx2, ty2, tx3, ty3, Color)
  LineXY(tx3, ty3, tx1, ty1, Color)
  If Mode <> 4
      FillArea((tx1 + tx2 + tx3) / 3, (ty1 + ty2 + ty3) / 3, Color, Color)
  EndIf
EndProcedure

Procedure Intersect(x1S1.f, y1S1.f, x2S1.f, y2S1.f, x1S2.f, y1S2.f, x2S2.f, y2S2.f, Address.l) ; Recherche du point d'intersection éventuel de deux segments finis
;
; La procédure prend deux segments de droites (x1S1, y1S1)-(x2S1, y2S1) et (x1S2, y1S2)-(x2S2, y2S2) et recherche si ces deux segments
; ont un point commun d'intersection. Si ce point existe il est retourné à l'argument Address
;
*fPoint.fPoint = Address ; On définit une structure fPoint (deux flottants pour retourner les coordonnées du point d'intersection)
  If x1S1 > x2S1 ; On redresse les vecteurs pour faciliter les tests
      xz.f = x1S1
      x1S1 = x2S1
      x2S1 = xz
      yz.f = y1S1
      y1S1 = y2S1
      y2S1 = yz
  EndIf
  If x1S2 > x2S2
      xz.f = x1S2
      x1S2 = x2S2
      x2S2 = xz
      yz.f = y1S2
      y1S2 = y2S2
      y2S2 = yz
  EndIf
  d1x.f = x2S1 - x1S1 ; On calcule l'équation des droites porteuses des deux segments
  d1y.f = y2S1 - y1S1
  d2x.f = x2S2 - x1S2
  d2y.f = y2S2 - y1S2
  a1.f = d1y / d1x
  b1.f = y1S1 - a1 * x1S1
  a2.f = d2y / d2x
  b2.f = y1S2 - a2 * x1S2
  ;
  ; On retourne 0 si il n'y a pas de point d'intersection
  ; si le point d'intersection est bien sur l'un ou l'autre des segments on retourne  la valeur 2, si il n'est pas sur l'un des segments, on retourne 1
  ;
  ; Ici il faut traiter au cas par cas pour savoir si les droites porteuses sont parallèles, superposées ou incidentes.
  ; Une fois filtré les cas de figure et calculer les points d'intersection des droites porteuses, on vérifie si ce point est partie d'un des deux segments.
  ;
  If a1 <> a2 ; droites incidentes n'ayant qu'un seul point d'intersection
      *fPoint\x = (b2 - b1) / (a1 - a2)
      *fPoint\y = a1 * *fPoint\x + b1
      If *fPoint\x => x1S1 And *fPoint\x <= x2S1 And *fPoint\x => x1S2 And *fPoint\x <= x2S2
          ProcedureReturn 2
        Else
          ProcedureReturn 1
      EndIf
    ElseIf a1 = a2 And b1 <> b2 ; droites parallèles, pas d'intersection
      ProcedureReturn #False
    ElseIf a1 = a2 And b1 = b2 ; droites coïncidentes
      If (x1S1 =>x1S2 And x1S1 <= x2S2) Or (x2S1 => x1S2 And x2S1 <= x2S2)
          ProcedureReturn 2
        Else
          ProcedureReturn 1
      EndIf
  EndIf
EndProcedure

;
; Le code de test consiste à générer un triangle aléatoire, qui sera déplacé à la souris sur l'écran
; ainsi qu'une série de segments de droites aléatoires également
;
; Lorsque le triangle passe sur les segments, cela doit montrer les points d'intersection
; Les points d'intersection sont affichés en plein.
;
; Les points d'intersection des droites de fuite, ne faisant pas partie des segments, sont affichés en creux.
;
; La touche espace permet de changer les objets utilisés pour le test
;
  ScreenWidth = GetSystemMetrics_(#SM_CXSCREEN)
  ScreenHeight = GetSystemMetrics_(#SM_CYSCREEN)
  ScreenDepth = 0
  NLines = 10
  NewList Lines.Line()
  If InitSprite() And InitMouse() And InitKeyboard()
      If ExamineScreenModes()
          While NextScreenMode()
            If ScreenModeWidth() = ScreenWidth And ScreenModeHeight() = ScreenHeight
                If ScreenModeDepth() > ScreenDepth
                    ScreenDepth = ScreenModeDepth()
                EndIf
            EndIf
          Wend
      EndIf
      If OpenScreen(ScreenWidth, ScreenHeight, ScreenDepth, "")
          ClearList(Lines())
          For i = 1 To NLines
            AddElement(Lines())
            Lines()\x1 = Random(ScreenWidth)
            Lines()\y1 = Random(ScreenHeight)
            Lines()\x2 = Random(ScreenWidth)
            Lines()\y2 = Random(ScreenHeight)
          Next
          tx1 = Random(200)
          ty1 = Random(200)
          tx2 = Random(200)
          ty2 = Random(200)
          tx3 = Random(200)
          ty3 = Random(200)
          Quit = #False
          Repeat
            FlipBuffers(0)
            ClearScreen(0, 0, 0)
            ExamineMouse()
            MouseX = MouseX()
            MouseY = MouseY()
            ExamineKeyboard()
            If KeyboardPushed(#PB_Key_Escape) : Quit = #True : EndIf
            If KeyboardPushed(#PB_Key_F1) : Repeat : ExamineKeyboard() : Until KeyboardReleased(#PB_Key_F1) : Statistics = 1 - Statistics : EndIf
            If KeyboardPushed(#PB_Key_Space)
                ClearList(Lines())
                For i = 1 To NLines
                  AddElement(Lines())
                  Lines()\x1 = Random(ScreenWidth)
                  Lines()\y1 = Random(ScreenHeight)
                  Lines()\x2 = Random(ScreenWidth)
                  Lines()\y2 = Random(ScreenHeight)
                Next
                tx1 = Random(200)
                ty1 = Random(200)
                tx2 = Random(200)
                ty2 = Random(200)
                tx3 = Random(200)
                ty3 = Random(200)
            EndIf
            StartDrawing(ScreenOutput())
              Collision1 = #False
              ForEach Lines()
                Collision = #False
                Select Intersect(Lines()\x1, Lines()\y1, Lines()\x2, Lines()\y2, tx1 + MouseX, ty1 + MouseY, tx2 + MouseX, ty2+ MouseY, @fPoint.fPoint)
                  Case 0
                  Case 1
                    DrawingMode(4)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue)
                  Case 2
                    DrawingMode(0)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue + #Green)
                    Collision = #True
                  Default
                EndSelect
                Select Intersect(Lines()\x1, Lines()\y1, Lines()\x2, Lines()\y2, tx1 + MouseX, ty1 + MouseY, tx3 + MouseX, ty3+ MouseY, @fPoint.fPoint)
                  Case 0
                  Case 1
                    DrawingMode(4)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue)
                  Case 2
                    DrawingMode(0)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue + #Green)
                    Collision = #True
                  Default
                EndSelect
                Select Intersect(Lines()\x1, Lines()\y1, Lines()\x2, Lines()\y2, tx2 + MouseX, ty2 + MouseY, tx3 + MouseX, ty3+ MouseY, @fPoint.fPoint)
                  Case 0
                  Case 1
                    DrawingMode(4)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue)
                  Case 2
                    DrawingMode(0)
                    Box(fPoint\x - 2, fPoint\y - 2, 5, 5, #Blue + #Green)
                    Collision = #True
                  Default
                EndSelect
                If Collision
                    LineXY(Lines()\x1, Lines()\y1, Lines()\x2, Lines()\y2, #Green)
                    Collision1 = #True
                  Else
                    LineXY(Lines()\x1, Lines()\y1, Lines()\x2, Lines()\y2, #Blue + #Green)
                EndIf
              Next
              If Collision1
                  Triangle(tx1 + MouseX, ty1 + MouseY, tx2 + MouseX, ty2+ MouseY, tx3 + MouseX, ty3 + MouseY, #Red, 4)
                Else
                  Triangle(tx1 + MouseX, ty1 + MouseY, tx2 + MouseX, ty2+ MouseY, tx3 + MouseX, ty3 + MouseY, #Blue, 4)
              EndIf
              If Statistics
                  BackColor(0, 0, 40)
                  FrontColor(255, 255, 255)
                  Locate(10, 10)
                  DrawText("FPS : " + Str(FPS))
              EndIf
            StopDrawing()
            NFrames + 1
            If ElapsedMilliseconds() - tz => 1000
                FPS = NFrames
                NFrames = 0
                tz = ElapsedMilliseconds()
            EndIf
            Delay(1)
          Until Quit
          CloseScreen()
      EndIf
  EndIf
  CallDebugger
End
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

waoou ! tres fort ! et rapide en plus !
les points de contacts sont bien calculé ! :D

tu vas nous faire une lib de collision trop cool ! :D
Backup
Messages : 14526
Inscription : lun. 26/avr./2004 0:40

Message par Backup »

......................
Dernière modification par Backup le sam. 19/mars/2011 19:23, modifié 3 fois.
Répondre