Um OBB é um casco convexo. Um casco convexo é uma forma 3D que não possui "recantos" em sua superfície. Cada "solavanco" (vértice) no casco convexo se projeta para fora , nunca para dentro. Se você cortar um avião através de um casco convexo, obterá (apenas um) polígono convexo. Se você estiver dentro de um casco convexo e disparar um laser apontando para fora, você só perfurará a superfície do casco uma vez (nunca duas vezes).
O teste do Teorema do Eixo Separador pode ser usado para detectar colisão de cascos convexos. O teste SAT é simples. Funciona em 2D e 3D. Embora as imagens abaixo sejam em 2D, elas podem ser aplicadas com a mesma facilidade ao 3D.
Conceito
Este é o conceito principal que você está usando com o SAT:
- Duas formas somente se cruzam se elas se sobrepõem quando "projetadas" em todos os eixos normais das duas formas .
A "projeção" de uma forma em um vetor 1D se parece com isso (o que eu chamo de "esmagamento")
Uma forma com verts vermelhos e um eixo
"Projetar a forma no eixo" significa soltar uma perpendicular de cada ponto da forma apenas para pousar no eixo. Você pode pensar nisso como "esmagar" os pontos com uma mão que reúne tudo e o esmaga perpendicularmente ao eixo.
O que resta: pontos em um eixo
O SAT diz:
Para que dois cascos convexos se cruzem, eles precisam se sobrepor em todos os eixos (onde todas as normais de qualquer forma contam como um eixo que devemos verificar).
Tome estas 2 formas:
Você vê que eles não se cruzam, então vamos tentar alguns eixos para mostrar onde uma sobreposição não ocorre.
Tentando o top normal do pentágono:
Essas são as extensões. Eles se sobrepõem.
Tente o lado esquerdo do retângulo. Agora eles não se sobrepõem neste eixo, portanto, SEM INTERSECÇÃO.
Algoritmo:
Para cada rosto normal nas duas formas:
- Encontre as extensões mínimas e máximas (maior e menor valor) da projeção de todos os pontos de canto dos vértices de ambas as formas nesse eixo
- Se eles não se sobrepõem, não há interseção .
E é isso mesmo. O código para fazer o SAT funcionar é muito curto e simples.
Aqui está um código que demonstra como fazer uma projeção de eixo 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 chamada:
// 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 ;
}
Você definitivamente deveria procurar o Teorema do Eixo Separador . É para objetos convexos. Existe uma regra: "Se dois objetos convexos não se cruzam, existe um plano em que a projeção desses dois objetos não se cruza".
Você pode encontrar alguns exemplos no wiki . Mas é um pouco mais complicado do que para o seu caso.
Algo mais adequado para o seu problema pode ser encontrado aqui (dois carros colidindo).
fonte
Mais artigos do SAT .
O último artigo deste site vem com código completo, acho que está em FLASH, não faço ideia, mas tive exatamente 0 problemas para convertê-lo em C ++ quando tive que usar o SAT pela primeira vez, não deve ser difícil faça o mesmo para outros idiomas. A única coisa que você precisará adicionar é armazenar o vetor de deslocamento em cada cálculo (se for o menor, é claro, você entenderá isso quando aprender sobre SAT), o código neste tutorial não o fará, portanto você acaba com o último vetor calculado.
http://rocketmandevelopment.com/tag/separation-axis-theorem/
Bons tutoriais antigos de N-Game. Melhor teoria do SAT na web.
http://www.metanetsoftware.com/technique/tutorialA.html
fonte