Maneira melhor / eficiente de implementar uma colisão 3D

16

Eu já programei um sistema de colisão 2D para um jogo anterior. Foi o meu primeiro sistema de colisão e foi feio. Eu estava procurando por colisão entre objetos, verificando todos os objetos com todos os objetos. Eu já ouvi falar de um sistema de grade com células em que um objeto só olhará a colisão com outros objetos de suas células atuais. É realmente uma boa maneira de verificar a colisão?

Eu gostaria de ter uma boa técnica para fazer um loop em todos os meus itens em um mundo 3D.

Jean-Philippe Leclerc
fonte

Respostas:

11

Você precisará de um bom algoritmo de particionamento de espaço, comumente usado em 3D, como octrees .

Depois disso, você poderá cercar os modelos, etc., com esferas delimitadoras, nas quais elas se encaixam perfeitamente, pois é muito fácil calcular uma colisão entre esferas delimitadoras. Depois de saber que duas esferas delimitadoras colidem, você pode iterativamente diminuir as esferas delimitadoras e adicionar esferas delimitadoras para manter o objeto coberto por elas, ou usar outro algoritmo inteligente para calcular colisões entre dois objetos complexos.

Veja esta imagem: várias esferas delimitadoras

Roy T.
fonte
12

Por fim, acho que a resposta para sua pergunta dependerá das necessidades de seu aplicativo específico, pois não há uma solução única para todos. Embora haja vários recursos decentes na Web, você economizará muito tempo e frustração ao detectar a detecção de colisão em tempo real da Christer Ericson , que apresenta detalhadamente uma ampla variedade de técnicas e algoritmos, por exemplo Código C ++.

Isso me ajudou a dar pequenos passos antes de tentar construir um grande sistema. Escrevendo uma função para determinar se um ponto está em um plano, se um ponto está em um triângulo, se um raio está em um triângulo, etc. Em seguida, passamos para testes estáticos de vários sólidos convexos: AABB vs. Triangle, etc. as coisas que pareciam impenetráveis ​​(perdoe o trocadilho) a princípio se tornaram menos assustadoras. Aqui está uma lista de um bom número de testes, com código de exemplo:

http://www.realtimerendering.com/intersections.html

Enquanto isso, como eu sei que nem todos podem pagar entre 70 e 80 dólares por um livro à vontade, eis alguns termos que você pode querer procurar:

  • Árvores de Particionamento Espacial, Octrees, Quadtrees, BSP
  • Árvores BIH
  • Volumes delimitadores e hierarquias de volume delimitador
  • Detecção de colisão discreta vs. contínua
  • Teorema do Eixo Separador
  • Algoritmo GJK
user_123abc
fonte