Eu já programei um sistema de colisão baseado em 2D para um jogo anterior. Foi meu primeiro sistema de colisão e ele estava feio. Eu estava procurando por colisão entre objetos verificando todos os objetos com todos os objetos. Já ouvi falar de um sistema de grade com células onde um objeto só olhará a colisão com outros objetos de sua (s) célula (s) atual (is). É realmente uma boa maneira de verificar a colisão?
Eu gostaria de ter uma boa técnica para percorrer todos os meus itens em um mundo 3D.
Resposta
Você vai precisar de um bom algoritmo de particionamento de espaço; comumente usados em 3D são octrees .
Depois disso, você pode cercar os modelos, etc., com esferas delimitadoras nas quais eles se encaixam perfeitamente, porque uma colisão entre esferas delimitadoras é muito fácil de calcular. Depois de saber que duas esferas delimitadoras colidem, você pode iterativamente tornar as esferas delimitadoras menores 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: 
Resposta
Em última análise, acho que a resposta a sua pergunta vai depender das necessidades de seu aplicativo específico, já que não existe uma solução única para todos. Embora haja uma série de recursos decentes na web, você economizará muito tempo e frustração pegando Christer Ericson “s Detecção de colisão em tempo real , que descreve detalhadamente uma ampla variedade de técnicas e algoritmos, com exemplo de código C ++.
Isso me ajudou a dar pequenos passos antes de começar a tentar construir um grande sistema. Escrever uma função para determinar se um ponto está em um plano, o n se um ponto está em um triângulo, se um raio está em um triângulo, etc. Em seguida, passar para os testes estáticos de vários sólidos convexos: AABB vs. Triângulo, etc. Com o tempo, coisas que pareciam impenetráveis (perdoe o trocadilho) inicialmente se tornaram menos assustador. Aqui está uma lista de um bom número de testes, com código de exemplo:
http://www.realtimerendering.com/intersections.html
Nesse ínterim, como sei que nem todo mundo pode desembolsar à vontade 70-80 $ por um livro, aqui estão alguns termos que você pode querer examinar:
- Particionamento espacial, octrees, quadtrees, árvores BSP
- Árvores BIH
- Volumes delimitadores e hierarquias de volumes delimitadores
- Detecção de colisão discreta vs. contínua
- Teorema do eixo de separação
- Algoritmo GJK