4. Problem mit dem SAT Algorithmus

Problem mit dem SAT Algorithmus

  • I

    Hallo zusammen, ich habe massive Probleme mit dem SAT Algortithmus. Dieser zeigt immer wieder Kollisionen an, obwohl gar keine existiert!! Was habe ich falsch gemacht?

    // -------------------------------- __handleCollisionDetection --------------------------------
void KB_TriggerManager::__handleCollisionDetection(void){
 // get the trigger - array in c - style to avoid performance penalities
 KB_Trigger **ppArrTri = reinterpret_cast<KB_Trigger**>(this->lstTri.getAllObjects());
 UINT       numTri     = this->lstTri.getNumberOfObjects();
 KB_Vector3 arrFce[15];

 for(UINT i=0;i<numTri;++i){
  for(UINT k=i+1;k<numTri;k++){
   // extract the two triggers
   KB_Trigger *pTri1 = ppArrTri[i];
   KB_Trigger *pTri2 = ppArrTri[k];
   bool       bSep   = false;

   // jump to the next loop if both trigger are inactive
   if(!(ppArrTri[i]->isActive() || ppArrTri[k]->isActive())) continue;

   // get the bounding boxes of the actual triggers
   KB_BoundingBox *pArrBox[2] = {pTri1->getBoundingBox(),pTri2->getBoundingBox()};

   // get the faces
   arrFce[0] = *pArrBox[0]->getFront();
   arrFce[1] = *pArrBox[0]->getRight();
   arrFce[2] = *pArrBox[0]->getUp();
   arrFce[3] = *pArrBox[1]->getFront();
   arrFce[4] = *pArrBox[1]->getRight();
   arrFce[5] = *pArrBox[1]->getUp();

   // calculate the cross - products of the face - normals
   D3DXVec3Cross(&arrFce[6],pArrBox[0]->getFront(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrFce[7],pArrBox[0]->getFront(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrFce[8],pArrBox[0]->getFront(),pArrBox[1]->getUp());
   D3DXVec3Cross(&arrFce[9],pArrBox[0]->getRight(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrFce[10],pArrBox[0]->getRight(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrFce[11],pArrBox[0]->getRight(),pArrBox[1]->getUp());
   D3DXVec3Cross(&arrFce[12],pArrBox[0]->getUp(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrFce[13],pArrBox[0]->getUp(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrFce[14],pArrBox[0]->getUp(),pArrBox[1]->getUp());

   // start a loop for walking each potential separation - axis
   for(int l=0;l<15;++l){
    // declare and init scope variables
    float arrMin[2] = {0.0f},arrMax[2] = {0.0f};

    // start a loop for walking each involved bounding - box
    for(int m=0;m<2;++m){
     // calculate the radius of the projected interval
     float rad  = fabs(D3DXVec3Dot(pArrBox[m]->getRight(),&arrFce[l]))*pArrBox[m]->getSize()->x;
           rad += fabs(D3DXVec3Dot(pArrBox[m]->getUp(),&arrFce[l]))*pArrBox[m]->getSize()->y;
           rad += fabs(D3DXVec3Dot(pArrBox[m]->getFront(),&arrFce[l]))*pArrBox[m]->getSize()->z;

     // calculate the minimum and maximum - point
     float cnt = D3DXVec3Dot(pArrBox[m]->getPosition(),&arrFce[l]);
     arrMin[m] = cnt - rad;
     arrMax[m] = cnt + rad;
    }

    // check if the projected intervals overlap
    if(arrMin[0] > arrMax[1] || arrMin[1] > arrMax[0]){
     // define that a separation - axis were found and break the loop
     bSep = true;
     break;
    }
   }

   // check if no separation - axis could be found
   if(!bSep){
    // call the onTrigger - event for the active window
    this->pWnd->onTrigger(pTri1,pTri2);

    // call the onTrigger - event for the assigned components 
    if(pTri1->isComponentAssigned()) pTri1->getComponent()->onTrigger(pTri1,pTri2);
    if(pTri2->isComponentAssigned()) pTri2->getComponent()->onTrigger(pTri1,pTri2);
   }
  }
 }
}
// --------------------------------------------------------------------------------------------
    0
  • V

    was ist der SAT Algorithmus - hast du da ein Tutorial dazu? oder Buch?
    du weißt doch selber wie das ist wenn dir einer ne Seite Quellcode hinklatscht und du weißt gar nicht wo das Problem liegt - ich werde dir nicht weiterhelfen können, da mich damit nicht auskenne, aber wenn das Problem etwas abstrakter Dargestellt wird kann dir eher geholfen werden

    0
  • S

    Hi,

    also für meine müden Augen sieht das erstmal korrekt aus. Nur eine Frage:

    Box::getSize()

    Gibt das die tatsächliche Größe auf der jeweiligen Achse oder die halbe Größe? Für die Projektion verwendet man nur die halbe Abmesung der Box.

    Ciao,
    Stefan

    0
  • I

    @Stefan Zerbst
    Vielen Dank, das war das Problem, ich habe den Algorithmus noch ein wenig abgeändendert und so erweitert, dass ebenfalls der MTD berechnet wird. Hier ist nocheinmal der vollständige Code mit MTD!
    Kannst du mal überprüfen, ob alles stimmt, besonders die Sache mit dem MTD habe ich komplett improvisiert, da ich keinen Beispielcode gefunden hatte, den ich hätte ableiten können...

    P.S.
    Als nächstes muss ich die Implementation noch dahingehend erweitern, dass jeder Trigger sogenannte Subtriggers haben kann. Sowas wie ein OOB - Tree, aber dass dürfte nun kein Problem mehr sein! 😋 👍

    Grüsse aus der Schweiz

    // -------------------------------- __handleCollisionDetection --------------------------------
void KB_TriggerManager::__handleCollisionDetection(void){
 // get the trigger - array in c - style to avoid performance penalities
 KB_Trigger **ppArrTri = reinterpret_cast<KB_Trigger**>(this->lstTri.getAllObjects());
 UINT       numTri     = this->lstTri.getNumberOfObjects();
 KB_Vector3 arrVecAxi[15];

 // update all triggers
 for(UINT i=0;i<numTri;++i) ppArrTri[i]->update();

 // start loops for walking each trigger by each trigger
 for(UINT i=0;i<numTri;++i){
  for(UINT k=i+1;k<numTri;k++){
   // extract the two triggers
   KB_Trigger     *pTri1      = ppArrTri[i];
   KB_Trigger     *pTri2      = ppArrTri[k];
   KB_BoundingBox *pArrBox[2] = {pTri1->getBoundingBox(),pTri2->getBoundingBox()};
   bool           bSep        = false;
   KB_Vector3     vecRay,vecMtd,vecMtdTmp;

   // jump to the next loop if both trigger are inactive
   if(!(pTri1->isActive() || pTri2->isActive())) continue;

   // get the faces
   arrVecAxi[0] = *pArrBox[0]->getFront();
   arrVecAxi[1] = *pArrBox[0]->getRight();
   arrVecAxi[2] = *pArrBox[0]->getUp();
   arrVecAxi[3] = *pArrBox[1]->getFront();
   arrVecAxi[4] = *pArrBox[1]->getRight();
   arrVecAxi[5] = *pArrBox[1]->getUp();

   // calculate the cross - products of the face - normals
   D3DXVec3Cross(&arrVecAxi[6],pArrBox[0]->getFront(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrVecAxi[7],pArrBox[0]->getFront(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrVecAxi[8],pArrBox[0]->getFront(),pArrBox[1]->getUp());
   D3DXVec3Cross(&arrVecAxi[9],pArrBox[0]->getRight(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrVecAxi[10],pArrBox[0]->getRight(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrVecAxi[11],pArrBox[0]->getRight(),pArrBox[1]->getUp());
   D3DXVec3Cross(&arrVecAxi[12],pArrBox[0]->getUp(),pArrBox[1]->getFront());
   D3DXVec3Cross(&arrVecAxi[13],pArrBox[0]->getUp(),pArrBox[1]->getRight());
   D3DXVec3Cross(&arrVecAxi[14],pArrBox[0]->getUp(),pArrBox[1]->getUp());

   // start a loop for walking each potential separation - axis
   for(int l=0;l<15;++l){
    // declare and init scope variables
    float rad = 0.0f;

    // jump to the next loop if the separation axis is zero
    if(arrVecAxi[l].x == 0.0f && arrVecAxi[l].y == 0.0f && arrVecAxi[l].z == 0.0f) continue;

    // start a loop for walking each involved bounding - box
    for(int m=0;m<2;++m){
     // calculate the radius of the projected interval
     KB_Vector3 *pVecSze = pArrBox[m]->getSize();
     rad += fabs(D3DXVec3Dot(pArrBox[m]->getRight(),&arrVecAxi[l]))*pVecSze->x/2.0f;
     rad += fabs(D3DXVec3Dot(pArrBox[m]->getUp(),&arrVecAxi[l]))*pVecSze->y/2.0f;
     rad += fabs(D3DXVec3Dot(pArrBox[m]->getFront(),&arrVecAxi[l]))*pVecSze->z/2.0f;
    }

    // compute the ray from one box - center to the other
    D3DXVec3Subtract(&vecRay,pArrBox[1]->getPosition(),pArrBox[0]->getPosition());

    // check if the projected intervals overlap
    if(fabs(D3DXVec3Dot(&vecRay,&arrVecAxi[l])) > rad){
     // define that a separation - axis were found and break the loop
     bSep = true;
     break;
    }
    // otherwise
    else{
     // calculate the mtd of the current separation - axis
     D3DXVec3Scale(&vecMtdTmp,&arrVecAxi[l],rad-fabs(D3DXVec3Dot(&vecRay,&arrVecAxi[l]))+0.1f);    

     // check if the current vector is shorter than the actual
     if(!l || (D3DXVec3Length(&vecMtdTmp) < D3DXVec3Length(&vecMtd))){
      // set the temporary MTD to the actual MTD
      vecMtd = vecMtdTmp;

      // normalize the ray
      D3DXVec3Normalize(&vecRay,&vecRay);

      // check if the opposite face is the shorted distance
      if(acosf(D3DXVec3Dot(&vecRay,&arrVecAxi[l])) > D3DX_PI/2.0f)
       // inverse the mtd - vector by multiplying it by -1
       D3DXVec3Scale(&vecMtd,&vecMtd,-1.0f);
     }
    }
   }

   // check if no separation - axis could be found
   if(!bSep){
    // call the onTrigger - event for the active window
    this->pWnd->onTrigger(pTri1,pTri2,&vecMtd);

    // call the onTrigger - event for the assigned components 
    if(pTri1->isComponentAssigned()) pTri1->getComponent()->onTrigger(pTri1,pTri2,&vecMtd);
    if(pTri2->isComponentAssigned()) pTri2->getComponent()->onTrigger(pTri1,pTri2,&vecMtd);
   }
  }
 }
}
// --------------------------------------------------------------------------------------------

    @Vertexwahn
    SAT steht für Separation Axis Theorem und wird verwendet, um eine mögliche Kollision zweier Oriented Bounding Boxes zu berechnen. Der MTD ist die Minimal Translation Distance, welcher ich in Form eines Vektors implementiert habe, den man einfach zum vorhandenen Positionsvektor der zweiten Bounding Box addieren muss, um diese aus der ersten zu entfernen.

    P.S.
    Ich muss mich echt wundern, dass plötzlich alle so still werden, wenn plötzlich eine Frage gestellt wird, welche nichts mit irgendwelchen Rendertricks zu tun haben. Ich meine, wie implementiert ihr den die Kollisionserkennung? Doch hoffentlich nicht mit BoundingSpheres? 😮

    Ich sollte mich vielleicht nicht so weit aus dem Fenster lehnen, denn ich habe selber noch kein einziges eigenes Spiel geschrieben, bin aber kurz davor, mein erstes fertigzustellen... Nach 2 Jahren Entwicklungszeit...
    Aber Ich werde einfach das Gefühl nicht los, dass 99 Prozent der hier Anwesenden noch nie über das Anzeigen und Texturieren von ein paar Meshes + vielleicht noch eine ResourceManager hinausgekommen ist. Anders kann ich mir die Tatsache nicht erklären, dass so gut wie gar niemand diesen Algorithmus kennt...

    0
  • S

    Hi,

    also im Moment habe ich leider zu wenig Zeit mir die MDT Berechnung anzuschauen, aber eine Quelle kann ich Dir geben:

    http://uk.geocities.com/olivier_rebellion/Cube3D.zip

    Da findet sich ein Tutorial was SAT ausgesprochen gut erklärt. Auch die Berechnung der MDT wird dort behandelt. Letztes Mal als ich es ausprobierte war dort allerdings ein Bug weil die Berechnung des Radius bzw. des Überlappungskriteriums nicht ganz korrekt war. Es geht dort auch um bewegte Polyhedra, nicht nur statische.

    Es ist aber nicht richtig, dass SAT nur für Obb vs Obb ist. Es ist generell für alle Volumen anwendbar, allerdings gibt es für einfache Volumen oftmals schnellere Verfahren. Für Obb ist es allerdings wohl die noch schnellste Methode. Aber man kann das Verfahren auch auf generelle Polyhedra anwenden, also auch auf beliebige Tri-Meshes. Da dürfte es allerdings so langsam sein, dass das keinen Sinn macht 🙂

    Ciao,
    Stefan

    0
  • S

    Ishildur schrieb:

    Ich muss mich echt wundern, dass plötzlich alle so still werden, wenn plötzlich eine Frage gestellt wird, welche nichts mit irgendwelchen Rendertricks zu tun haben. Ich meine, wie implementiert ihr den die Kollisionserkennung?

    Welche Kollisionserkennung?!?!? 🤡 👍

    0
  • I

    ???

    0
  • P

    Ishildur schrieb:

    ???

    Das sollte ein Witz sein o_O

    0
Anmelden zum Antworten