Determinando se dois objetos em movimento rápido devem ser enviados para uma verificação de colisão

8

Eu tenho um mecanismo de física 2D básico em execução. É praticamente um mecanismo de partículas, apenas usa formas básicas como AABBs e círculos, para que nenhuma rotação seja possível. Tenho um CCD implementado que pode fornecer um TOI preciso para dois objetos em movimento rápido e tudo está funcionando sem problemas.

Meu problema agora é que não consigo descobrir como determinar se dois objetos em movimento rápido devem ser verificados um contra o outro em primeiro lugar. Estou usando uma árvore quádrupla para particionamento espacial e, para cada objeto em movimento rápido, verifico os objetos em cada célula que ele passa. Isso funciona bem para determinar a colisão com geometria estática, mas significa que qualquer outro objeto em movimento rápido que possa colidir com ele, mas que não esteja em nenhuma das células verificadas, nunca será considerado.

A única solução para isso que consigo pensar é ter as células grandes o suficiente e cruzar os dedos o suficiente, ou implementar algum tipo de algoritmo de força bruta. Existe uma maneira adequada de lidar com isso, talvez alguém tenha resolvido esse problema de maneira eficiente. Ou talvez haja uma maneira melhor de particionar o espaço que explica isso?

Aqui está um diagrama:

insira a descrição da imagem aqui

As "áreas de efeito" do objeto A e B se cruzam, elas devem ser verificadas uma contra a outra. Mas, do jeito que estou verificando colisões atualmente, não explica isso. Novamente, eu posso pensar em algumas soluções para isso, como verificar se os caminhos dos objetos se cruzam quando a velocidade é maior que x, ou algo assim, mas isso parece um hack e é uma bagunça tentar e implementar.

collision-detection physics dreta
fonte
Você poderia dar um exemplo de cenário em que seu método falha?
Anko
11
Eu acho que seria assim: os objetos A e B estão nesta configuração: [A] [] [B]. A está indo para a direita e B para a esquerda. Eles vão rápido. A verificação de colisão é a seguinte: a próxima célula está vazia para A? Sim, bcs não há nada na célula do meio. A próxima célula está vazia para B? Sim. Portanto, nenhuma colisão. Mas a física reais iria mostrar que A e B são susceptíveis de colidirem (especialmente neste uma dimensão jogo que eu decribe;)
Cystack
@Cystack Tenho o CCD implementado. A situação que você descreveu não é um problema. Os dois objetos estão indo diretamente um para o outro, a implementação que descrevi vai pegar e resolver isso.
dreta
A física da situação é clara. Digamos que você possa identificar um objeto como 'movimento rápido' antes do tempo. Então, quando você faz uma verificação de colisão, precisa verificar não apenas a célula em que o objeto está atualmente, mas todas as células pelas quais ele passou na última etapa. Portanto, cada objeto em movimento rápido tem vários locais, como toda a faixa verde que você desenhou na imagem acima.
theJollySin
@theJollySin eu já descrevi a solução que você está dando, é um hack, um caso especial, estou procurando uma solução geral, se houver uma.
Dreta 20/12/12

Respostas:

5

O problema de que você está falando é geralmente chamado de 'detecção de colisão de fase ampla' e sua solução é um 'volume varrido', não realmente um hack, exatamente como é feito (basta pegar o AABB do objeto, incluindo o início e o final do movimento e use isso para colisão - embora as coisas fiquem um pouco complicadas com as rotações).

Em seguida, o algoritmo de detecção de colisão de fase larga que torna esse processo rápido é chamado de "Varredura e remoção".

Jeff Gates
fonte
Eu descartei o SAP antes que esse problema surgisse. Estou fazendo isso em JavaScript, o que torna a sobrecarga das listas perceptível, e também as matrizes podem não ser confiáveis ​​quando se trata de desempenho. Acho que vou ter que reconsiderar as coisas. Obrigado, o algoritmo realmente resolve o problema.
dreta