Załóżmy, że masz dwa obiekty ramki granicznej, z których każdy przechowuje bieżące wierzchołki ramki w wektorze, a wszystkie wierzchołki obiektu są obrócone i przesunięte względem wspólnej osi.

Oto obraz ilustrujący mój problem:

Jak mogę się dowiedzieć, czy dwa OBB nakładają się na linki, aby pomóc w wyjaśnieniu rozwiązania problemu, byłoby mile widziane. Proszę, nic skomplikowanego ...

OBB to wypukły kadłub. Wypukły kadłub jest kształtem 3D, który nie ma „zepsutych” powierzchni. Każdy „wybrzuszenie” (wierzchołek) wypukłego kadłuba wystaje na zewnątrz , nigdy do wewnątrz. Jeśli przekroisz płaszczyznę przez wypukły kadłub, otrzymasz (tylko jeden) wielokąt wypukły. Jeśli znajdziesz się w wypukłym kadłubie i wystrzelisz laser skierowany na zewnątrz, przebijesz powierzchnię kadłuba tylko raz (nigdy dwa razy).

Test twierdzenia o separującej osi może być wykorzystany do wykrycia kolizji wypukłych kadłubów. Test SAT jest prosty. Działa w 2D i 3D. Chociaż poniższe zdjęcia będą w 2D, równie dobrze można je zastosować do 3D.

Pojęcie

Oto kluczowa koncepcja, której używasz w SAT:

• Dwa kształty przecinają się tylko wtedy , gdy zachodzą na siebie po „rzutowaniu” na każdą normalną oś obu kształtów .

„Projekcja” kształtu na wektor 1D wygląda tak (to, co nazywam „miażdżeniem”)

Kształt z czerwonymi wierzchołkami i osią

„Rzutowanie kształtu na oś” oznacza upuszczenie prostopadłej z każdego punktu na kształt, aby wylądować na osi. Możesz myśleć o tym jako o „miażdżeniu” punktów ręką, która zbiera wszystko i prostopadle miażdży je do osi.

Co zostało: Punkty na osi

SAT mówi:

Aby przeciąć 2 wypukłe kadłuby, muszą one zachodzić na siebie na każdej osi (gdzie każda normalna postać w dowolnym kształcie liczy się jako oś, którą musimy sprawdzić).

Weź te 2 kształty:

Widzisz, że się nie przecinają, więc wypróbujmy kilka osi, aby pokazać, że nakładanie się nie występuje.

Próbowanie najwyższej normalnej pięciokąta:

To są zakresy. One się pokrywają.

Spróbuj lewej strony prostokąta. Teraz nie pokrywają się one w tej osi, dlatego NIE MA SKRZYŻOWANIA.

Algorytm:

Dla każdej twarzy normalnej dla obu kształtów:

• Znajdź minimalny i maksymalny zasięg (największa i najmniejsza wartość) rzutowania wszystkich punktów narożnych wierzchołków obu kształtów na tę oś
• Jeśli się nie pokrywają, nie ma skrzyżowania .

I to jest naprawdę to. Kod umożliwiający działanie SAT jest bardzo krótki i prosty.

Oto kod pokazujący, jak wykonać rzut osi SAT:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Kod telefoniczny:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}

Zdecydowanie powinieneś poszukać twierdzenia o oddzielaniu osi . To jest dla wypukłych obiektów. Istnieje reguła: „Jeśli dwa wypukłe obiekty nie przecinają się, wówczas istnieje płaszczyzna, w której rzut tych dwóch obiektów się nie przecina”.

Możesz znaleźć kilka przykładów na wiki . Ale jest to trochę bardziej skomplikowane niż w twojej sprawie.

Można tu znaleźć coś bardziej odpowiedniego dla twojego problemu (zderzenie dwóch samochodów).

Więcej artykułów SAT .

Ostatni artykuł na tej stronie zawiera kompletny kod, myślę, że jest we FLASH, nie mam pojęcia, ale miałem dokładnie 0 problemów z konwersją do C ++, kiedy musiałem używać SAT po raz pierwszy, nie powinno być trudne zrób to samo dla innych języków. Jedyną rzeczą, którą musisz dodać, jest przechowywanie wektora przemieszczenia przy każdym obliczeniu (jeśli jest to najmniejsze, oczywiście zrozumiesz to, gdy dowiesz się o SAT), kod w tym samouczku tego nie robi, więc otrzymujesz ostatni obliczony wektor.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Dobre, stare samouczki N-Game. Najlepsza teoria SAT w sieci.

http://www.metanetsoftware.com/technique/tutorialA.html