Un OBB es un casco convexo. Un casco convexo es una forma 3D que no tiene "grietas" en su superficie. Cada "protuberancia" (vértice) en el casco convexo sobresale hacia afuera , nunca hacia adentro. Si corta un plano a través de un casco convexo obtendrá (solo uno) polígono convexo. Si está dentro de un casco convexo y dispara un láser que apunta hacia afuera, solo atravesará la superficie del casco una vez (nunca dos veces).
La prueba del Teorema del eje de separación se puede utilizar para detectar la colisión de cascos convexos. El examen SAT es simple. Funciona en 2D y 3D. Aunque las imágenes a continuación estarán en 2D, podrían aplicarse fácilmente a 3D.
Concepto
Este es el concepto clave que está utilizando con SAT:
- Dos formas solo se cruzan si se solapan cuando se "proyectan" en cada eje normal de ambas formas .
La "proyección" de una forma en un vector 1D se ve así (lo que yo llamo "aplastamiento")
Una forma con verts rojos y un eje.
"Proyectar la forma en el eje" significa dejar caer una perpendicular desde cada punto de la forma solo para aterrizar en el eje. Puedes pensar en esto como "aplastar" los puntos con una mano que recoge todo y lo aplasta perpendicularmente hacia el eje.
Lo que te queda: puntos en un eje
SAT dice:
Para que 2 cascos convexos se crucen, tienen que superponerse en cada eje (donde cada normal en cualquier forma cuenta como un eje que debemos verificar).
Toma estas 2 formas:
Verá que no se cruzan, así que intentemos con algunos ejes para mostrar si no se produce una superposición .
Probar la parte superior normal del pentágono:
Estas son las extensiones. Se superponen.
Intenta con el lado izquierdo del rectángulo. Ahora no se superponen en este eje, por lo tanto, NO HAY INTERSECCIÓN.
Algoritmo:
Para cada cara normal en ambas formas:
- Encuentre las extensiones mínima y máxima (valor mayor y menor) de la proyección de todos los puntos de esquina de vértice de ambas formas en ese eje
- Si no se superponen, no hay intersección .
Y eso es todo. El código para hacer que SAT funcione es muy corto y simple.
Aquí hay un código que muestra cómo hacer una proyección del eje 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;
}
}
Código de llamada:
// 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 ;
}
Definitivamente deberías buscar el teorema del eje de separación . Es para objetos convexos. Hay una regla: "Si dos objetos convexos no se cruzan, entonces hay un plano donde la proyección de estos dos objetos no se intersecará".
Puedes encontrar algunos ejemplos en la wiki . Pero es un poco más complicado que para su caso.
Algo más adecuado para su problema se puede encontrar aquí (dos autos colisionando).
fuente
Más artículos del SAT .
El último artículo en este sitio viene con un código completo, creo que está en FLASH, no tengo idea, pero tuve exactamente 0 problemas al convertirlo a C ++ cuando tuve que usar SAT por primera vez, no debería ser difícil haz lo mismo para otros idiomas. Lo único que tendrá que agregar es almacenar el vector de desplazamiento en cada cálculo (si es el más pequeño, por supuesto, lo entenderá cuando aprenda sobre SAT), el código en este tutorial no lo hace, así que terminas con el último vector calculado.
http://rocketmandevelopment.com/tag/separation-axis-theorem/
Buenos, viejos tutoriales de N-Game. La mejor teoría SAT en la web.
http://www.metanetsoftware.com/technique/tutorialA.html
fuente