Un OBB est une coque convexe. Une coque convexe est une forme 3D qui n'a pas de "recoins" à sa surface. Chaque "bosse" (sommet) sur la coque convexe dépasse vers l'extérieur , jamais vers l'intérieur. Si vous coupez un avion à travers une coque convexe, vous obtiendrez (un seul) polygone convexe. Si vous êtes à l'intérieur d'une coque convexe et que vous tirez un laser pointant vers l'extérieur, vous ne traverserez la surface de la coque qu'une seule fois (jamais deux fois).
Le test du théorème d'axe de séparation peut être utilisé pour détecter la collision de coques convexes. Le test SAT est simple. Il fonctionne en 2D et 3D. Bien que les images ci-dessous soient en 2D, elles pourraient tout aussi bien être appliquées à la 3D.
Concept
Voici le concept clé que vous utilisez avec SAT:
- Deux formes ne se croisent que si elles se chevauchent lorsqu'elles sont "projetées" sur chaque axe normal des deux formes .
La "projection" d'une forme sur un vecteur 1D ressemble à ceci (ce que j'appelle "l'écrasement")
Une forme avec des verts rouges et un axe
«Projection de la forme sur l'axe» signifie laisser tomber une perpendiculaire à partir de chaque point de la forme juste pour atterrir sur l'axe. Vous pouvez penser à cela comme "écraser" les points par une main qui rassemble tout et l'écrase perpendiculairement à l'axe.
Ce qui vous reste: Points sur un axe
SAT dit:
Pour que 2 coques convexes se croisent, elles doivent se chevaucher sur chaque axe (où chaque normale sur l'une ou l'autre forme compte comme un axe, nous devons vérifier).
Prenez ces 2 formes:
Vous voyez qu'ils ne se croisent pas, alors essayons quelques axes pour montrer si un chevauchement ne se produit pas .
Essayer la normale supérieure du pentagone:
Ce sont les étendues. Ils se chevauchent.
Essayez le côté gauche du rectangle. Maintenant, ils ne se chevauchent pas dans cet axe, donc PAS D'INTERSECTION.
Algorithme:
Pour chaque face normale sur les deux formes:
- Trouver les étendues minimale et maximale (la plus grande et la plus petite valeur) de la projection de tous les sommets des sommets des deux formes sur cet axe
- S'ils ne se chevauchent pas, pas d'intersection .
Et c'est vraiment ça. Le code pour faire fonctionner SAT est très court et simple.
Voici un code qui montre comment faire une projection d'axe 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;
}
}
Code d'appel:
// 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 ;
}
Vous devriez certainement rechercher le théorème de l'axe de séparation . C'est pour les objets convexes. Il y a une règle: "Si deux objets convexes ne se croisent pas, alors il y a un plan où la projection de ces deux objets ne se croisera pas".
Vous pouvez trouver quelques exemples sur le wiki . Mais c'est un peu plus compliqué que pour votre cas.
Vous trouverez ici quelque chose de plus adapté à votre problème (deux voitures entrant en collision).
la source
Plus d' articles SAT .
Le dernier article sur ce site est livré avec du code complet, je pense qu'il est en FLASH, je n'en ai aucune idée, mais j'ai eu exactement 0 problème pour le convertir en C ++ lorsque j'ai dû utiliser SAT pour la première fois, cela ne devrait pas être difficile à faites de même pour les autres langues. La seule chose que vous devrez ajouter est le stockage du vecteur de déplacement sur chaque calcul (si c'est le plus petit, bien sûr, vous comprendrez cela lorsque vous en apprendrez sur SAT), le code de ce tutoriel ne le fait pas, donc vous vous retrouvez avec le dernier vecteur calculé.
http://rocketmandevelopment.com/tag/separation-axis-theorem/
Bon, vieux tutoriels N-Game. Meilleure théorie SAT sur le web.
http://www.metanetsoftware.com/technique/tutorialA.html
la source