Teste 2D de interseção de caixas delimitadoras alinhadas a objetos

9

Eu tenho duas caixas delimitadoras alinhadas a objetos (ou seja, não alinhadas ao eixo, elas giram com o objeto). Gostaria de saber se duas caixas alinhadas a objetos se sobrepõem. ( Edit: note - Estou usando um teste de caixa delimitadora alinhada por eixo para descartar rapidamente objetos distantes, por isso não importa se a rotina quad é um pouco mais lenta. )

Minhas caixas são armazenadas como quatro pontos x, y. Eu procurei por respostas, mas não consigo entender os nomes e algoritmos das variáveis ​​nos exemplos para aplicá-los ao meu caso particular.

Alguém pode me ajudar a mostrar como isso seria feito, de maneira clara e simples? Obrigado. (O idioma específico não é importante, o pseudocódigo no estilo C está bom.)

AshleysBrain
fonte

Respostas:

5

Se você sabe onde procurar, é fácil. Você está procurando oobb. Acesse aqui: http://www.realtimerendering.com/intersections.html .
Lá você encontra o link para este site http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html
e encontra o código correto. (ctrl + f "Interseção de caixas (2D)")

Ele usa SAT e contém códigos-fonte e artigos.

Notabene
fonte
O algoritmo descrito pelas ferramentas geométricas é o que eu apontaria.
Jari Komppa
Eu entendo que isso foi há 4 anos, mas sempre explique um voto negativo e tudo isso. Isso é bonito "Sua resposta está em outro castelo", e agora a resposta nem parece estar lá no segundo caso.
Yann
2

A maneira mais fácil é provavelmente testar cada vértice da caixa B em cada lado da caixa A (calcular a distância sinalizada). Dessa forma, você pode classificar cada vértice como "na frente" ou "atrás" do segmento.

Se todos os vértices de B são classificados como "na frente" de um dos segmentos de A, B e A não se sobrepõem; caso contrário, eles fazem.

Isso está um pouco envolvido, então você pode obter algum ganho de desempenho fazendo uma verificação de círculo em círculo primeiro, usando os círculos delimitadores dos quadrados (trivial para calcular)

ggambett
fonte
Primeiro, estou fazendo um teste de caixa delimitadora alinhada ao eixo para descartar rapidamente objetos distantes ... Você ainda tem mais detalhes sobre o teste quad-quad?
AshleysBrain
gire temporariamente ambos os quadriláteros com a mesma transformação, de modo que um deles acabe alinhado ao eixo ... em seguida, use o teste SAT como não mencionado. quando o resultado for encontrado, inverta a rotação para recuperá-los.
31711 Steve