Teorema do eixo separador com múltiplos polígonos?

9

Estou tentando implementar o teorema do eixo separador em C #. Eu tenho uma função que pode calcular o vetor de conversão mínimo entre dois polígonos. No entanto, não consigo criar uma função que calcule o vetor mínimo de conversão entre um polígono e vários outros polígonos. Sinceramente, estou trabalhando nisso há meses e não estou mais perto de uma solução e não consegui encontrar uma solução online. Sempre há alguns casos extremos que não retornam o resultado correto, levando a erros de alta prioridade no meu jogo.

Aqui estão casos comuns de borda que não funcionam corretamente:

casos de borda

Existe uma solução conhecida para esse problema? Tudo o que posso encontrar são pessoas dizendo "apenas execute o SAT em cada polígono", mas isso raramente produz o vetor mínimo de tradução.

Qualquer ajuda seria muito apreciada.

collision-detection separating-axis-theorem user40698
fonte
Uma idéia, que eu nunca cheguei a testar, é que alguns eixos de separação - aqueles que moveriam você de lado em um polígono adjacente - poderiam ser sinalizados para nunca serem considerados o mínimo. Em seguida, algum tipo de teste repetido forneceria bons resultados (possivelmente com algum tipo de FIFO e / ou limite de iteração para evitar que ele fique preso em um loop).
Andrew Russell
Uma versão ainda mais difícil de resolver é quando uma aresta de uma forma é apenas parcialmente coberta por outra. Por exemplo, na imagem superior direita, se o quadrado do meio se estender para a direita, para ser um retângulo maior. Isto é semelhante à saída de alguma utilidade código I que leva dezenas de milhares de células ocupadas / não-ocupados e reduz que para menos de uma centena de formas de colisão maiores
Richard Tingle

Respostas:

2

Idealmente, você não cria seu ambiente com polígonos. Você o constrói a partir de arestas (que talvez você calcule a partir de um conjunto de polígonos). No seu primeiro exemplo, por exemplo, há uma única borda diagonal; no último exemplo, a caixa está apoiada em uma única aresta horizontal.

O fato de seu editor ou ferramentas usarem formas individuais menores para criar um nível não deve afetar o tempo de execução.

Uma abordagem um pouco mais simples simplesmente removeria as bordas "internas" das formas básicas. Para o seu último exemplo, existem duas arestas entre as caixas "floor"; ignore-os durante a detecção de colisão.

Você pode encontrar algumas fotos melhores e algumas idéias de implementação lendo a seção 4.5 (arestas e cadeias de arestas) na documentação do Box2D .

Sean Middleditch
fonte
2
O uso de arestas (principalmente arestas, é um pouco melhor com cadeias de arestas) tem a principal desvantagem de que fica muito fácil para objetos de física apresentarem falhas dentro da geometria do nível.
Andrew Russell
11
@AndrewRussell: esses problemas são evitados com as correções comuns de encapsulamento. Certifique-se de que seus objetos em movimento tenham um volume / área razoavelmente decente, mantenha a velocidade máxima por quadro baixa o suficiente para que eles não possam se mover mais que ~ metade da sua dimensão mais curta (ou pise várias vezes se precisar que se mova mais rápido), evite fendas muito acentuadas e semelhantes em sua geometria de nível, itere a resolução várias vezes até convergir para um local final "seguro" etc.
Sean Middleditch