O que é um bom algoritmo para detectar colisões entre esferas móveis?

27

Se (para fins de detecção de colisão) objetos 3D são representados em um jogo por esferas, qual é um bom algoritmo para detectar uma colisão entre esferas?

Se cada objeto tiver uma posição a partir do último quadro e uma nova posição (desejada), o que é um bom algoritmo que identificará colisões nas quais as esferas não se cruzam no quadro anterior e podem não se cruzar no segundo quadro, mas eles se cruzam em algum lugar no meio?

collision-detection kevin42
fonte

Respostas:

18

Basicamente, você está procurando um rastreamento.

Esta página provavelmente o ajudará: http://www.realtimerendering.com/intersections.html

Esfera em movimento / Esfera: (localização) Adicione o raio da esfera em movimento à esfera estática e trate a esfera em movimento como um raio. Use esse raio para executar a interseção raio / esfera. Veja Gomez; Schroeder para código (o artigo tem um erro na derivação, o código está bom); e RTR2, p. 622

Tetrad
fonte
11
Isso não funciona se as duas esferas se moverem (nem mesmo se você fizer duas vezes). Parece-me que você teria que primeiro fazer uma verificação de distância entre as linhas que abrangem o movimento ae o movimento de abrangem b, e se isso for menor que o raio a + raio b, você poderá ter uma colisão. Depois disso, eu faria uma verificação para ver onde esse ponto está no tempo da esfera ae onde a esfera b para ver se os tempos estão próximos. Nesse caso, eu verificaria a velocidade em relação à distância no tempo para esse ponto, se ainda é uma colisão possível, faria um refinamento gradual.
Kaj
15
Na verdade, você só precisa tornar o movimento relativo. Portanto, se as duas esferas estão se movendo, basta subtrair a velocidade de uma das esferas para que você tenha uma esfera "móvel" e uma esfera "estacionária". Então você pode usar o acima.
Tetrad 23/11
8

Use um teste de varredura, conforme demonstrado neste artigo do Gamasutra.

Firas Assaad
fonte
4

Em cima da minha cabeça:

  1. Crie dois segmentos de linha a partir do meio de cada círculo, de onde começou para onde se mudou naquele passo do tempo.
  2. Encontre a distância mínima entre esses dois segmentos de linha; como é explicado aqui .
  3. Se essa distância for menor ou igual ao raio do primeiro círculo mais o segundo, eles colidiram; caso contrário, não o fizeram.

E isso é tudo o que há, espero que seja bem rápido.

Robert Massaioli
fonte
1

Aqui está outro bom artigo da Gamasatura .

Mateen Ulhaq
fonte
11
Sei que isso ocorre 7 anos depois, mas essa resposta é apenas um link. Felizmente, o link ainda está ativo, mas se não estivesse, sua resposta ... não seria uma resposta.
Draco18s
0

Falando como alguém que fez isso: não vale a pena . A menos que o design do seu jogo absolutamente precise dele, e quase certamente não, você gastará muito mais esforço trabalhando varrendo do que realmente espera. E será mais lento do que você queria.

ZorbaTHut
fonte
Ele poderia estar fazendo um jogo de sinuca para todos que você conhece.
21410 Kaj
Se ele estava fazendo um jogo de sinuca, seu "design de jogo absolutamente precisa dele" .
Deft_code
Você está certo, não reinvente a roda . Mas apenas por exercício, pode valer a pena.
precisa saber é o seguinte
4
Discordo do desânimo direto como resposta .
precisa saber é o seguinte
Eu concordo com o @bobobobo, a questão não é se vale a pena o aborrecimento ou não, um usuário futuro que vê esse tópico pode absolutamente precisar da resposta, independentemente do custo. Isso seria melhor como um comentário.
TomTsagk
0

Há um artigo sobre como obter a detecção de colisão com matemática no Flipcode . Tem círculo. Há como detectar com precisão o ponto de colisão e verificar se há alguma colisão.

user712092
fonte
Sei que isso ocorre 7 anos depois, mas essa resposta é apenas um link. Felizmente, o link ainda está ativo, mas se não estivesse, sua resposta ... não seria uma resposta.
Draco18s
0

A detecção de colisão para um objeto em movimento é normalmente chamada de "Cálculo do volume varrido". Aqui estão alguns códigos / artigos sobre esse assunto.

http://www.gpu-voxels.org/demos/ (demonstração)

Bibliotecas de código fonte:

https://github.com/fzi-forschungszentrum-informatik/gpu-voxels

https://libigl.github.io/tutorial/#swept-volume

https://github.com/gradientspace/geometry3Sharp

Artigos:

http://gamma.cs.unc.edu/SV/sm03.pdf

https://www.cs.columbia.edu/~allen/PAPERS/abrams.swept.pdf (Nenhum código fonte, infelizmente)

http://www.realtimerendering.com/intersections.html (coleção bastante pesada de links)

TarmoPikaro
fonte
11
As respostas que contêm apenas um link (ou, nesse caso, várias) não contêm uma resposta real. Você deve incluir as informações relevantes em sua postagem para que, se esses links ficarem inoperantes, sua postagem ainda seja compreensível.
Draco18s
As informações por trás dos links explicam um pouco melhor do que eu no momento. Há também vídeos de demonstração por trás dos links, o que dá alguma percepção sobre o que está acontecendo em tempo real.
TarmoPikaro
11
Meta.stackexchange.com/a/8259/313685
Draco18s