Detecção de colisão OBB vs OBB

20

Digamos que você tenha dois Objetos de caixa delimitadora, cada um deles armazenando os vértices atuais da caixa em um vetor, com todos os vértices do objeto girados e traduzidos em relação a um eixo comum.

Aqui está uma imagem para ilustrar meu problema:

Como posso descobrir se os dois OBBs estão sobrepondo algum link para ajudar a explicar a solução do problema seria bem-vindo. Nada muito complicado por favor ...

Joshua Barnett
fonte

Respostas:

16

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

insira a descrição da imagem aqui

"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.

insira a descrição da imagem aqui

O que resta: pontos em um eixo

insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui

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:

insira a descrição da imagem aqui

Essas são as extensões. Eles se sobrepõem.

insira a descrição da imagem aqui

Tente o lado esquerdo do retângulo. Agora eles não se sobrepõem neste eixo, portanto, SEM INTERSECÇÃO.

insira a descrição da imagem aqui

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 ;
}
bobobobo
fonte
Hullinator implementa o teste SAT para cascos convexos
bobobobo
explicação incrível! obrigado. Eu acho que você pode ter um erro de digitação na linha: "então vamos tentar alguns eixos para mostrar eram uma sobreposição não acontece.", Porque então você prosseguir para dar exemplos onde eles fazem sobreposição. obrigado novamente!
Você não precisa fazer os testes também para todos os produtos cruzados das normais? Este artigo geometrictools.com/Documentation/DynamicCollisionDetection.pdf diz isso.
IFinitei 17/10
Vale ressaltar que esse método específico de SAT funciona apenas em 2D. Em 3D, você precisa obter mais do que apenas as normais de cada rosto. Porém, depois de ter as normais certas, o restante do processo (projeto, comparação) é exatamente o mesmo.
Fund Monica's Lawsuit
É realmente difícil dizer pelas suas imagens em 2D em que direção as setas estão indo.
WDUK 18/08/19
7

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).

zacharmarz
fonte
1

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

dreta
fonte
É tão irritante que ninguém publica a fonte de trabalho completa com todas as classes necessárias. Eu carreguei o código dele em uma demonstração minha, mas simplesmente não funciona. :( Este é o meu projeto até agora, se alguém poderia me ajudar a depurar-se que seria ótimo. Ligação
Joshua Barnett
como assim não funciona? preste atenção em como você está armazenando seus vértices, na imagem em um sistema de coordenadas cartesianas, no tutorial ele armazena os vértices como vetores em relação ao centróide (tudo o que você precisa fazer é subtrair o centróide de seus próprios vértices ou remova as linhas onde ele modifica seus próprios vértices), funciona como um produto de ponto que você pode criar, você não precisa de um guia para isso, o resto deve ser direto, não é um material para copiar e colar, aprenda SAT antes de tentar implementá-lo
Dreta 13/03/12
Foi assim que eu o implementei: SAT.as , Shape2D.as , o que você quer dizer com centróide? O centro do polígono, como (x, y)?
Joshua Barnett
No momento, tenho uma função getOBB () que retorna vértices conforme detalhado na minha imagem original. Isso é calculado a partir de um vetor <b2Vec2> que contém os vértices da forma, uma variável de ângulo e uma variável de posição.
13132 Joshua Barnett
sim, o centro, a maneira como esse cara cria seus polígonos é dando desvios do centro, idk AS3, mas pelo que eu vejo você projetar seus vértices como eles são, ao calcular o produto escalar, tente subtrair o centróide dos vértices (subtração do vetor ), ao lado deste que você não está verificando que a separação vector é o menor ainda, você só armazenar o último calculado
dreta